回溯法(探索与回溯法)是一种选优搜索法,按选优条件向前搜索,以达到目标。但当探索到某一步时,发现原先选择并不优或达不到目标,就退回一步重新选择,这种走不通就退回再走的技术为回溯法,而满足回溯条件的某个状态的点称为“回溯点”。
用回溯法解题的一般步骤:
(1)针对所给问题,定义问题的解空间;
(2)确定易于搜索的解空间结构;
(3)以深度优先方式搜索解空间,并在搜索过程中用剪枝函数避免无效搜索。
用回溯法解决八皇后问题的C语言程序
#include<stdio.h>
#include<stdlib.h>
int col[9] = {0}, a[9];
int b[17], c[17];
main()
{
int m, good;
int i, j, k;
char q;
for(i = 0; i < 17; i++)
{
if(i < 9) a[i] = 1;
b[i] = 1;
c[i] = 1;
}
good = 1;
col[1] = 1;
m = 1;
while(col[0] != 1)
{
if(good)
if(m == 8)
{
for(i = 1; i < 9; i++)
printf("col[%d] %d/n", i, col[i]);
printf("input 'q' to quit/n");
scanf("%c", &q);
getchar();
if(q == 'q' || q == 'Q') exit(0);
while(col[m] == 8)
{
m--;
a[col[m]] = b[m+col[m]] = c[8+m-col[m]] = 1;
}
a[col[m]] = b[m+col[m]] = c[8+m-col[m]] = 1;
col[m]++;
}
else
{
a[col[m]] = b[m+col[m]] = c[8+m-col[m]] = 0;
m++;
col[m] = 1;
}
else
{
while(col[m] == 8)
{
m--;
a[col[m]] = b[m+col[m]] = c[8+m-col[m]] = 1;
}
col[m]++;
}
good = a[col[m]] && b[m+col[m]] && c[8+m-col[m]];
}
}
分享到:
相关推荐
利用回溯算法解决0/1背包问题。类knapsack为背包类,bound是上界函数,函数bknapsack实现0/1背包回溯算法。内有详细注释。
最优装载问题的回溯算法,用回溯法解决装载问题的c++算法。
北大老师写的kmp无回溯算法,数据结构与算法,大家懂得
实验目的:0/1背包问题的回溯算法设计 实验原理:回溯算法设计。 实验要求:基本掌握回溯算法设计的原理方法。熟练掌握VC++中编程实现算法的常用技术和方法。 算法思想: 0-1背包问题:给定n种物品和一背包.物品i的...
回溯算法解0--1背包问题
VC++编写的野人传教士问题,可输入野人传教士人数,船可容纳人数,采用回溯算法,正确求解。
八皇后问题是一个古老而著名的问题,是回溯算法的典型例题。该问题是十九世纪著名的数学家高斯1850年提出:在8X8格的国际象棋上摆放八个皇后,使其不能互相攻击,即任意两个皇后都不能处于同一行、同一列或同一斜线...
回溯算法求数独的解,数独就是同一行不能有重复,同一列不能有重复,同一宫内不能有重复, 思考的时候也看了很多博客,写完发现并没有那么麻烦 其实知道了这些规则,就很好办了,总体采用回溯算法
回溯算法旅行商问题代码实现。算法backtrack在最坏情况下可能需要更新当前最优解O(n-1)!)次,每次更新bestx需计算时间O(n),从而整个算法的计算时间复杂性为O(n!)。
有26个元素a...z ...我写了一个回溯算法,结果有1.7G,Petium4算了5分钟,所以此算法只可学习,不可实践啊。。 详细请看:http://topic.csdn.net/u/20120827/11/82310200-cc30-46b8-93f7-cd7555ea2845.html
穷举算法 回溯算法 介绍 几篇文章,还是值得一看的
算法分析论文——回溯算法的应用 包括算法的即便额概念,思想,回溯法应用及其在某些方面的改进
基于回溯算法的高校排课系统 基于回溯算法的高校排课系统 基于回溯算法的高校排课系统 基于回溯算法的高校排课系统 基于回溯算法的高校排课系统 基于回溯算法的高校排课系统
用C#语言实现作业分配问题,算法采用的是回溯算法,具有输入数据 具有可视化界面
用回溯算法解决旅行商问题,返回最优旅游路径的耗费,最优路径
C++回溯算法实验报告,包括实验过程,实验代码,运行结果。
matlab 回溯算法 模拟退火算法-matlab
是一道不错的回溯算法学习例题。
其中包含了常见的回溯算法,如0-1背包问题的回溯算法、符号三角形和跳马问题。
回溯算法回溯算法回溯算法回溯算法回溯算法回溯算法