系统讲解回溯法6
发布网友
发布时间：2023-11-29 03:51
共4个回答
热心网友
时间：2024-02-26 23:08
有许多问题，当需要找出它的解集或者要求回答什么解是满足某些约束条件的最佳解时，往往要使用回溯法。
回溯法的基本做法是搜索，或是一种组织得井井有条的，能避免不必要搜索的穷举式搜索法。这种方法适用于解一些组合数相当大的问题。
回溯法在问题的解空间树中，按深度优先策略，从根结点出发搜索解空间树。算法搜索至解空间树的任意一点时，先判断该结点是否包含问题的解。如果肯定不包含，则跳过对该结点为根的子树的搜索，逐层向其祖先结点回溯；否则，进入该子树，继续按深度优先策略搜索。
在n×n格的棋盘上放置彼此不受攻击的n个皇后。按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。n后问题等价于在n×n格的棋盘上放置n个皇后，任何2个皇后不放在同一行或同一列或同一斜线上。
解向量：(x1, x2, … , xn)
显约束：xi=1,2, … ,n
隐约束：
1)不同列：xixj
2)不处于同一正、反对角线：|i-j||xi-xj|
bool Queen::Place(int k)
{
for (int j=1;j<k;j++)
if ((abs(k-j)==abs(x[j]-x[k]))||(x[j]==x[k])) return false;
return true;
}
void Queen::Backtrack(int t)
{
if (t>n) sum++;
else
for (int i=1;i<=n;i++) {
x[t]=i;
if (Place(t)) Backtrack(t+1);
}
}
热心网友
时间：2024-02-26 23:09
勉强看看吧
回溯的精髓在于不知道解决问题的确定方向，
就硬着头皮往前走，可以走的地方都走，
到最后没路可走到死路时，才往回退回上一个路口试探别的路
个人感觉有点像图的深度遍历
--------------------------------------------
//八皇后问题
//2008-04-23
//作者：leo
#include <iostream>
using namespace std;
#define N 8//皇后个数
int x[N+1]={0};//定义棋盘
bool place(int k)//判断k位置摆放皇后是否合理
{
int i=1;
while(i<k)
{
if(x[i]==x[k]||(abs(x[i]-x[k])==abs(i-k)))return false;
i++;
}
return true;
}
void print()//打印结果
{
for(int i=1;i<N+1;i++)
cout<<x[i]<<" ";
cout<<endl;
}
void nqueen(int k)//
{
int count=0;//解决方案数
while(k>=1)
{
x[k]++;
while(x[k]<=N&&!place(k))//从第一个位置开始试摆第k个皇后
{
x[k]++;
}
if(x[k]<=N)//第k个皇后安全时在棋盘内
{
if(k==N)//已经是第最后一个皇后则得到一个解决方案
{
count++;
cout<<count<<endl;
print();
}
else k++;//继续处理下一个皇后
}
else x[k--]=0;//第k个皇后安全时不在棋盘内，则回溯
}
}
void main()
{
nqueen(1);
}
热心网友
时间：2024-02-26 23:09
//
#include "stdafx.h"
#include <stdio.h>
#include <stdlib.h>
char Queen[8][8],chessboard[8][8][200];
int column[8], askew1[15], askew2[15];
int answer=0;//开始之前，八皇后的解个数为零
void BlankChessboard()//构造初始法的国际棋盘与检验冲突的数组
{
int i,j;
for(i=0;i<8;i++)
{
column[i]=0;
for(j=0;j<8;j++)
Queen[i][j]='\35';
}
for(i=0;i<15;i++)
{
askew1[i]=0;
askew2[i]=0;
}
}
void Putqueen(int c_row,int c_col)//放置皇后的函数
{
Queen[c_row][c_col]='Q';
column[c_col]=1;//该位置[c_row][c_col]的列不能再放皇后
askew1[c_row-c_col+7]=1;//该位置[c_row][c_col]的右斜线不能再放皇后
askew2[c_row+c_col]=1;//该位置[c_row][c_col]的左斜线不能再放皇后
}
void RecordChessboard()//利用一个三维数组记录合法棋盘的函数
{
answer++;
int i,j;
for(i=0;i<8;i++)
for (j=0;j<8;j++)
chessboard[i][j][answer]=Queen[i][j];
}
void solveQueen(int c_row)
{
int c_col;
for (c_col=0;c_col<8;c_col++)
{
if ((column[c_col]==0)&&(askew1[c_row-c_col+7]==0)&&(askew2[c_row+c_col]==0))//如果当前位置的行列斜都没有皇后，该位置可以放皇后
{
Putqueen(c_row,c_col);//将皇后放到当前位置Queen[c_row][c_col]
if (c_row<7)
solveQueen(c_row+1);//利用递归，放置下一个皇后
else RecordChessboard();//记录当前合法的棋盘
Queen[c_row][c_col]='\35';
column[c_col]=0;
askew1[c_row-c_col+7]=0;
askew2[c_row+c_col]=0;
}
}
}
void Fprintf(FILE *fpw)//打印答案的函数
{
int i,j,k;
for(k=1;k<=answer;k++)
{
fprintf(fpw,"八皇后的第%d种解:\n",k);
for (i=0;i<8;i++)
{
for (j=0;j<8;j++)
{
fprintf(fpw,"%c ",chessboard[i][j][k]);
}
fprintf(fpw,"\n");
}
fprintf(fpw,"\n");
}
}
int main()
{
printf("八皇后问题是一个古老而著名的问题，是递归算法的典型例题。该问题是十九世纪著名的数学家高斯1850年提出：在8X8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。高斯认为有76种方案。1854年在柏林的象棋杂志上不同的作者发表了40种不同的解，后来有人用图论的方法解出92种结果。现代教学中把八皇后问题当成一个经典递归算法例题。\n");
printf("程序运行后，答案放在当前目录的'八皇后的解.txt'\n");
FILE *fpw=fopen("八皇后的解.txt","w");
BlankChessboard();//初始化棋盘
solveQueen(0);//解决问题
Fprintf(fpw);//调用输出函数"Fprintf"
fclose(fpw);
system("pause");
return 0;
}
/*
printf("");
*/
热心网友
时间：2024-02-26 23:10
