人工智能学习(3)---广度优先搜索
广度优先搜索:
在深度优先搜索中，深度越大的结点越先得到扩展。如果把它改为深度越小的结点越先得到扩展，就是广度优先搜索法。
广度优先搜索算法的基本思想：
（1）建立一个空的状态队列SS；
（2）建立一个空的状态库SB；
（3）把初始状态S（0）存入队列SS中；
（4）若队列状态是目标状态，则搜索成功，算法运行中止。如该状态的形式为S（path)，则解就是（path);
（5）若某种搜索极限已经达到（如空间用完等），则搜索失败，算法运行结束，没有解；
（6）按某种原则取一个可以应用于SS第一个状态S(path)并产生合适的新状态的规则Rn，产生新状态T(path,n),并将其置于SS的最后，转（4）。若扩展失败，即没有新状态产生，则将SS中第一个状态从SS中除去，送入SB中，执行下步；
（7）若SS成为空队列，则搜索失败，算法运行结束，没有解。否则转（5）。
注：在实际解题中，算法可能有许多不同的变型，要视具体情况应变。下给出算法可供参考：
广度优先基本算法如下：
program BFS;
初始化；建立数据库data;初始状态存入数据库；
设队列首指针closed:=0;队列尾指针open:=1;
repeat
取下一个closed所指结点；
for r:=1 to rmax do {r为产生规则编号}
begin
if 子结点符合条件 then
begin
open增1，把新结点存入数据库队尾；
if 新结点与原有结点重复 then
删去该结点（open减1）
else
if 新结点即目标 then 输出并退出；
end
end
until closed>=open{队列空}；
广度优先搜索的显著特点是，在产生新的子结点时，深度越小的越得到优先扩展，即先产生它的子结点。当结点到根结点的费用和结点的深度成正比，特别是当每一结点到根结点的费用等于深度值时，用广度优先得到的解一定是最优解。但只要将上述算法进行改进也可以求得最优解，这就成了代价优先搜索。
下面是一个24点程序的代码:
#include <iostream>
#include <string>
#include <cmath>
using namespace std;
const double PRECISION = 1E-6;
const int COUNT_OF_NUMBER = 4;
const int NUMBER_TO_BE_CAL = 24;
double number[COUNT_OF_NUMBER];
string expression[COUNT_OF_NUMBER];
bool Search(int n)
{
if (n == 1) {
if ( fabs(number[0] - NUMBER_TO_BE_CAL) < PRECISION ) {
cout << expression[0] << endl;
return true;
} else {
return false;
}
}
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
double a, b;
string expa, expb;
a = number[i];
b = number[j];
number[j] = number[n - 1];
expa = expression[i];
expb = expression[j];
expression[j] = expression[n - 1];
expression[i] = '(' + expa + '+' + expb + ')';
number[i] = a + b;
if ( Search(n - 1) ) return true;
expression[i] = '(' + expa + '-' + expb + ')';
number[i] = a - b;
if ( Search(n - 1) ) return true;
expression[i] = '(' + expb + '-' + expa + ')';
number[i] = b - a;
if ( Search(n - 1) ) return true;
expression[i] = '(' + expa + '*' + expb + ')';
number[i] = a * b;
if ( Search(n - 1) ) return true;
if (b != 0) {
expression[i] = '(' + expa + '/' + expb + ')';
number[i] = a / b;
if ( Search(n - 1) ) return true;
}
if (a != 0) {
expression[i] = '(' + expb + '/' + expa + ')';
number[i] = b / a;
if ( Search(n - 1) ) return true;
}
number[i] = a;
number[j] = b;
expression[i] = expa;
expression[j] = expb;
}
}
return false;
}
void main()
{
for (int i = 0; i < COUNT_OF_NUMBER; i++) {
char buffer[20];
int x;
cin >> x;
number[i] = x;
itoa(x, buffer, 10);
expression[i] = buffer;
}
if ( Search(COUNT_OF_NUMBER) ) {
cout << "Success." << endl;
} else {
cout << "Fail." << endl;
}
}
