算法分析

一些简单的算法

八皇后问题

查找（哨兵）

八皇后问题

八皇后问题是一个以国际象棋为背景的问题：如何能够在 8×8 的国际象棋棋盘上放置八个皇后，使得任何一个皇后都无法直接吃掉其他的皇后？为了达到此目的，任两个皇后都不能处于同一条横行、纵行或斜线上。八皇后问题可以推广为更一般的 n 皇后摆放问题：这时棋盘的大小变为 n1×n1，而皇后个数也变成 n2。而且仅当 n2 = 1 或 n1 ≥ 4 时问题有解。

问题解析：8*8 棋盘上每行每列都有一个皇后，且任意两皇后不能处于同一行、同一列、同一斜线上

为了简化问题，下面讨论四皇后问题。回溯法从空棋盘开始，首先把皇后 1 摆放到它所在行的第一个位置，也就是第一行第一列，得到图 8.7 (a)。

对于皇后 2，在经过第一列和第二列的尝试后，摆放到第二行第三列，得到图 8.7 (b)。

对于皇后 3，摆放到第三行的哪一列都会引起冲突 (即违反约束条件)，进行回溯，回
到对皇后 2 的处理，把皇后 2 摆放到下一个位置，也就是第二行第四列，得到图 8.7 (d)。

对于皇后 3，在经过第一列的尝试后，摆放到第三行第二列，得到图 8.7 (e)。

对于皇后 4，摆放到第四行的哪一列上都会引起冲突，进行回溯，回到对皇后 3 的处
理；皇后 3 摆放到第三行的哪一列上都会引起冲突，再次进行回溯，但此时皇后 2 位于棋
盘的最后一列，继续回溯，回到对皇后 1 的处理，把皇后 1 摆放到第一行第一列，得到
图 8.7 (g)。

接下来，把皇后 2 摆放第二行第四列的位置，把皇后 3 摆放到第三行第一列的位置，把皇后 4 摆放到第四行第三列的位置，得到四皇后问题的一个解，如图 8.7 (j) 所示。

算法

【算法】设函数 Queen 实现 n 皇后问题，皇后 k 摆放在 k 行 x [k] 列的位置，算法用伪代码描述如下。

算法8.3:回溯法求解n皇后问题Queen
输人:皇后的个数n
输出:n皇后问题的解x[n]
1.初始化解向量x[n]={-1};
2.k=1;
3.while(k>=1)
	3.1 把皇后k摆放在下一列的位置,即x[k]++;
	3.2 从x[k]开始依次考察每一列,如果皇后k摆放在x[k]位置不发生冲突,则转步骤3.3;
		否则x[k]++试探下一列;
	3.3 若n个皇后已全部摆放,则输出一个解,算法结束;
	3.4 若尚有皇后没摆放,则k++,转步骤3摆放下一个皇后;
	3.5 若x[k]出界,则回溯,x[k]=-1,k--,转步骤3重新摆放皇后k;
4.退出循环,说明n皇后问题无解;

实现

/***************

八皇后问题

************/
#include <iostream>
#include<stdlib.h>
using namespace std;
void Queen(int k);
const int n=8;
int x[n];
int main(){
	Queen(n);
}
int Place(int k){                                   //考察皇后k放在 x[k]是否发生冲突
	for (int i=0;i<k;i++)
	{
		if (x[i]==x[k] || abs(i-k)==abs(x[i]-x[k])) //abs() 求绝对值 ||违反约束条件
		{
			return 1;                               //冲突，返回1
		}
	}
	return 0;                                       //不冲突，返回0
}
void Queen(int n){                                    //求解n皇后问题
	int k=0;                                          //皇后
	while (k>=0)
	{
		x[k]++;                                       //在下一列排放皇后
		while (x[k]<n && Place(k)==1)                 //发生冲突
		{
			x[k]++;                                   //皇后k试探下一列
		}
		if (x[k]<n && k==n-1)                         //得到下一个解，输出
		{
			for(int i=0;i<n;i++){
			    for(int j=0;j<x[i];j++){
			    cout<<"□ ";
			    }
			    if(x[i]<9){
			        cout<<x[i]+1<<" ";  //数组下标从0开始，打印的序号从1开始
			    }else{
			        cout<<x[i]+1;  //数组下标从0开始，打印的序号从1开始
			    }
				
				for(int j=n-1;j>x[i];j--)
			    {
			        cout<<"□ ";
			    }
			    cout<<endl;
			}                   
			cout<<endl;
			return ;                                  //只求出一个解
		}
		if(x[k]<n && k<n-1)                           //尚有皇后未摆放
			k = k +1;                                 //准备拜访下一个皇后
		else
			x[k--] = -1;                              //重置x[k],回溯，重新摆放皇后k
	}
	cout<<"无解"<<endl;
}

遍历查找（哨兵）

利用观察哨，则无需判断查找是否越界

较传统蛮力查找，设置观察哨他们的时间复杂度都是 O (n)，而系数相差一倍。实验表明，设置观察哨之后的算法在表长大于 1000 时，一次顺序查找的时间几乎一半

算法 c++ 核心代码

int SeqSearch2(int r[],int n,int k) //数组r[1]~r[n]存放查找集合
{
    int i=n;  //从数组最高端开始查找
    r[0] = k;  //设置哨兵
    while(r[i] != k)
        i--;
    return i;
}

以后想起来什么再写，先到这，继续写 python