汽车网站建设的基本功能,南昌网站建设公司渠道,网站建设需要多少钱小江,小程序怎么删除文章目录1. 回溯算法思想2. 算法应用2.1 八皇后问题1. 回溯算法思想
前面讲过贪心算法并不能保证得到最优解#xff0c;那怎么得到最优解呢#xff1f;
回溯思想#xff0c;有点类似枚举搜索。枚举所有的解#xff0c;找到满足期望的解。为了有规律地枚举所有可能的解那怎么得到最优解呢
回溯思想有点类似枚举搜索。枚举所有的解找到满足期望的解。为了有规律地枚举所有可能的解避免遗漏和重复把问题求解的过程分为多个阶段。每个阶段我们都会面对一个岔路口我们先随意选一条路走当发现这条路走不通的时候不符合期望的解就回退到上一个岔路口另选一种走法继续走。
2. 算法应用
2.1 八皇后问题
有一个8×8的棋盘希望往里放8个棋子皇后每个棋子所在的行、列、对角线都不能有另一个棋子。请找到所有满足这种要求的放棋子方式。 把这个问题划分成8个阶段依次将8个棋子放到第一行、第二行、第三行。。。第八行放置的过程中不停地检查当前的方法是否满足要求如果满足则跳到下一行继续放置棋子如果不满足那就再换一种方法继续尝试如果一整行都不能放下一颗那么这种方法无效退到上一行上一行列位置1再往下尝试 从0,0位置开始放置 下标5的行走到最后也没有放下这颗棋子都不满足那么退到下标4的行列位置1从4列开始新的尝试 下标5的行容不下一颗棋子再次回退下标4行退到最后了再往上退下标3行棋子往右挪 下标7行放不下退到6行 6行也容不下棋子接着看5行 5行也不可以容下棋子看第4行。。。第一种可行解怎么还没出来好累就到这里吧大家自行 ppt 画个图配合代码推一下就理解了 第一个解是这样的哈哈挪了好长时间终于出来了
/*** description: 回溯算法--八皇后问题* author: michael ming* date: 2019/7/7 0:10* modified by: */
#include iostream
using namespace std;
class EightQueen
{int result[8];//下标表示行值表示queen在哪一列void printQueens(int *result){int i,r,c,flag 1;cout ;for(i 0; i 8; i)cout ▁;cout endl;for(r 0; r 8; r){cout ┃;for(c 0; c 8; c){if(result[r] c)cout ★;else{if(flag 0)cout ;elsecout ■;}flag -1*flag;}cout ▏ endl;flag -1*flag;}cout ;for(i 0; i 8; i)cout ▔;cout endl;}bool isOk(int r, int c)//判断在r行c列放置是否可以满足要求{int leftup c - 1, rightup c 1;for(int i r - 1; i 0; --i)//逐行向上考察每一行{if(result[i] c)//第i行的c列有棋子吗return false;if(leftup 0)//考察左上对角线{if(result[i] leftup)//第i行leftup列有棋子吗return false;}if(rightup 8)//考察右上对角线{if(result[i] rightup)//第i行rightup列有棋子吗return false;}--leftup; rightup;}return true;}
public:int kinds; //可行布局种类EightQueen():kinds(0){}void cal8queens(int row) //调用方式cal8queens(0){if(row 8) //8个棋子都放置好了打印结果{kinds;cout 第 kinds 种放法 endl;printQueens(result);return;//都放置好了没法再递归了}for(int column 0; column 8; column)//每行有8种放法{if(isOk(row,column)) //该放法满足要求{result[row] column;//第row行的棋子放到了column列cal8queens(row1); //考察下一行}}}};
int main()
{EightQueen eq;eq.cal8queens(0);cout 共有 eq.kinds 种摆放方法。 endl;return 0;
}
