1、ID3—— 最大信息增益
2、C45——最大信息增益比
3、CART——最大基尼指数(Gini)
ID3—— 最大信息增益
对于样本集合D，类别数为K，数据集D的经验熵表示为
C45——最大信息增益比
有时候我们会发现，当特征为ID或者有某一个特征有很多值的时候，ID3就不起作用，举个栗子，当特征值为ID的时候，每个样本是一类，那么所求出来的最大信息增益，肯定是最大的。由此可见，其他特征有很多值的情况。因此引入最大信息增益比来减少某个特征类别过多带来的影响。
特征A对于数据集D的信息增益比定义为
CART——最大基尼指数(Gini)
Gini描述的是数据的纯度，与信息熵含义类似。
三者之间的差异。
1、ID3是采用信息增益作为评价标准， 会倾向于取值较多的特征。因为，信息增益反映的是给定条件以后不确定性减少 的程度，特征取值越多就意味着确定性更高，也就是条件熵越小，信息增益越大。
2、从样本类型的角度，ID3只能处理离散型变量，而C45和CART都可以 处理连续型变量。
3、应用角度，ID3和C45只能用于分类任务，而CART(Classification and Regression Tree，分类回归树)从名字就可以看出其不仅可以用于分类，也可以应用于回归任务(回归树使用最小平方误差准则)。
#pragma warning(disable:4786)
#include <algorithm>
#include <cstdio>
#include <set>
#include <utility>
#include <ctime>
#include <cassert>
#include <cstring>
#include <iostream>
using namespace std;
/item记录搜索空间中一个结点
state 记录用整数形式表示的8数码格局
blank 记录当前空格位置，主要用于程序优化，
扩展时可不必在寻找空格位置
g, h 对应g(n), h(n)
pre 记录当前结点由哪个结点扩展而来 /
struct item
{
int state;
int blank;
int g;
int h;
int pre;
};
const int MAXSTEPS = 100000;
const int MAXCHAR = 100;
char buf[MAXCHAR][MAXCHAR]; //open表
item open[MAXSTEPS];
//vector<item> open;
int steps = 0;
//closed表，已查询状态只要知道该状态以及它由哪个结点扩展而来即可，用于输出路径
//每次只需得到对应f值最小的待扩展结点，用堆实现提高效率
pair<int, int> closed[MAXSTEPS];
//读入，将8数码矩阵格局转换为整数表示
bool read(pair<int,int> &state)
{
if (!gets(buf[0]))
return false;
if (!gets(buf[1]))
return false;
if (!gets(buf[2]))
return false;
//cout << strlen(buf[0]) << ' ' << strlen(buf[1]) << ' ' << strlen(buf[2]) << endl;
assert(strlen(buf[0]) == 5 && strlen(buf[1]) == 5 && strlen(buf[2]) == 5);
// astarin中的每行数据长度必须为5
statefirst = 0;
for (int i = 0, p = 1; i < 3; ++i)
{
for (int j = 0; j < 6; j += 2)
{
if (buf[i][j] == '0')
statesecond = i 3 + j / 2; // statesecond为0（空格）在节点中的位置
else
statefirst += p (buf[i][j] - '0');
p = 10;
}
}
/ 若初试节点为:
1 2 3
8 0 4
7 6 5
则statefirst为567408321，statesecond为4
/
return true;
}
//计算当前结点距目标的距离
int calculate(int current, int target) // return h=the sum of distances each block have to move to the right position,这里的each block不包括空格
{
int c[9], t[9];
int i, cnt = 0;
for (i = 0; i < 9; ++i)
{
c[current % 10] = t[target % 10] = i;
current /= 10;
target /= 10;
}
for (i = 1; i < 9; ++i)
cnt += abs(c[i] / 3 - t[i] / 3) + abs(c[i] % 3 - t[i] % 3);
return cnt;
}
//open表中结点间选择时的规则 f(n) = g(n) + h(n)
class cmp
{
public: inline bool operator()(item a, item b)
{
return ag + ah > bg + bh;
}
};
//将整数形式表示转换为矩阵表示输出
void pr(int state)
{
memset(buf, ' ', sizeof(buf));
for (int i = 0; i < 3; ++i)
{
for (int j = 0; j < 6; j += 2)
{
if (state % 10)
buf[i][j] = state % 10 + '0';
state /= 10;
}
buf[i][5] = '\0';
puts(buf[i]);
}
}
//用于判断当前空格是否可以向对应方向移动
inline bool suit(int a, int b) //空格移动后的坐标为(a,b)
{
return (a >= 0 && a < 3 && b >= 0 && b < 3);
}
//递归输出搜索路径
void path(int index)
{
if (index == 0)
{
pr(closed[index]first);
puts("");
return;
}
path(closed[index]second);
pr(closed[index]first); //将整数形式表示转换为矩阵表示输出
puts("");
++steps;
}
int getNixuNum( int state ) //求节点的逆序对数
{
int sum = 0;
int result[9];
memset( result, 0, sizeof(result) );
//cout << result[8] << result[7] << endl;
char buf[10];
itoa( state, buf, 10 );
//cout << buf << endl;
int k = 0;
while( buf[k] != '\0' )
{
result[9-k-1] = buf[k] - '0';
k++;
}
for( int i = 0; i < 9; i++ )
{
for( int j = i + 1; j < 9; j++ )
{
if( result[i] && result[j] && result[i] > result[j] )
{
sum++;
}
}
}
return sum; //返回33方格数组的逆序对数
}
int main()
{
//cout << getNixuNum(87654321);
//openresize(MAXSTEPS);
unsigned int t1 = clock();
//cout << opensize() << endl;
if( freopen("astarin", "r", stdin) == NULL )
{
cout << "file not find\n";
exit(0);
};
freopen("astar2out", "w", stdout);
set<int>states;
char tmp[100];
int i, x, y, a, b, nx, ny, end, next, index, kase = 0;
pair<int,int> start, target;
item head; //4个方向移动时的偏移量
const int xtran[4] = {-1, 0, 1, 0};
const int ytran[4] = {0, 1, 0, -1};
const int p[] = {1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000, 1000000000};
while (read(start)) // 读取初试状态节点
{
unsigned int t2 = clock();
printf("Case %d:\n\n", ++kase);
gets(tmp);
read(target); // 读取目标状态节点
gets(tmp);
int targetNixuNum = getNixuNum(targetfirst);
//若两者的逆序对数不是同为奇数或同为偶数，则无解
if( !(getNixuNum(startfirst)&1 && targetNixuNum&1 || !(getNixuNum(startfirst)&1) && !(targetNixuNum&1)) )
{
cout << "无法从初始节点到终态节点\n";
exit(0);
}
//初始化open表，将初始状态加入
open[0]state = startfirst;
open[0]h = calculate(startfirst, targetfirst); // 计算当前节点到目标节点的估计距离
open[0]blank = startsecond;
open[0]pre = -1; // 初始节点无父节点
open[0]g = 0; // 初始节点的g为0
index = 0;
statesinsert(startfirst); // 扩展过节点保存在states中，即出现过的状态保存在states中，states为set<int>类型，其中的states中的元素唯一
//提取open表中f值最小元素放入closed表，并对该结点进行扩展
for (end = 1; end > 0; ++index) // end为open表中的元素个数，一直循环到open表为空
{
assert(index < MAXSTEPS);
//临时存储
head = open[0]; // 由于使用pop_heap函数和push_heap函数，所以open[0]为g+h最小的元素
//放入closed表记录当前格局和由哪个结点扩展而来（该结点肯定已在closed表中）
closed[index]first = open[0]state; //放入close表中，表示已经扩展完的节点，下面的for循环会扩展其节点
closed[index]second = open[0]pre; // index表示当前close表中当前扩展节点的下标
//从open表中删除该结点
pop_heap(open, open + end, cmp());//为algorithm文件中的函数，第一个参数指定开始位置，第二个指定结束，第三个指定比较函数
--end;
//得到结果，递归输出路径
if (headstate == targetfirst)
{
path(index);
break;
}
x = headblank / 3;
y = headblank % 3; //空格在33方格中的x,y坐标
/
|2 0 3|
A = |1 8 4|
|7 6 5| // 看成33的数组
则headblank=1
x=0,y=1,即空格的在33的数组中下标为(0,1)
/
for (i = 0; i < 4; ++i)
{
nx = x + xtran[i];
ny = y + ytran[i];
/
i=0时：(nx,ny）为当前空格向上移动一格后的坐标
i=1时：(nx,ny）为当前空格向右移动一格后的坐标
i=2时：(nx,ny）为当前空格向下移动一格后的坐标
i=3时：(nx,ny）为当前空格向左移动一格后的坐标
/
if (suit(nx, ny)) // 判断是否能够移动
{
a = headblank; // 空格当前位置,以上面矩阵A为例，a=1
b = nx 3 + ny; // 空格移动后的新位置,开始是能够向右边移动，故b=03+2=2
//调换十进制表示整数对应两个数字位
next = headstate + ((headstate % p[a + 1]) / p[a] - (headstate % p[b + 1]) / p[b]) p[b] + ((headstate % p[b + 1]) / p[b] - (headstate % p[a + 1]) / p[a]) p[a];
// 如headstate=567481302,空格向右移动一次后，next=567481032,即为移动后的节点
// 判断能否由当前节点到达目标节点
if( ( getNixuNum(next)&1 && targetNixuNum&1 ) || ( !(getNixuNum(next)&1) && !(targetNixuNum&1) ) )
{
//判断是否已经扩展过，即已经出现过
if (statesfind(next) == statesend()) //没出现就保存一下，也存入open表
{
statesinsert(next);
open[end]pre = index; //扩展后的子节点，其父节点为当前扩展节点
open[end]blank = b;
open[end]state = next;
open[end]h = calculate(next,targetfirst);
open[end]g = headg + 1;
++end; //open表中元素加1
push_heap(open, open + end, cmp()); //压入堆中
}
}
}
}
}
if (end <= 0)
puts("No solution");
else
{
printf("Num of steps: %d\n", steps);
printf("Num of expanded: %d\n", index);
printf("Num of generated: %d\n", index + end);
printf("Time consumed: %d\n\n", clock() - t2);
}
statesclear();
steps = 0;
}
printf("Total time consumed: %d\n", clock() - t1);
return 0;
}
人工智能原理 2004年
一、回答下列问题（30分）
1、什么叫宽度优先搜索？宽度优先搜索的优点在何处？缺点在何处？
2、试说明逻辑符号“ ”、“→”的含义和差别。
3、请举出输入归结演绎不完备的例子。
4、设S={P(x),Q(f(a))}是子句集，请举出I是S的普通解释，而不是其Herbrand解释的例子。
5、请举出公式与其Skolem范式不等价的例子。
6、什么叫A算法？什么叫A算法？什么叫A算法是可采纳的？两个A算法如何比较好坏？
二、求解下列问题（30分）
1、设八数码问题有估价函数：f(n)=d(n)+W(n)；其中d(n)是节点n在搜索树中的深度，W(n)是节点n中“不在位”数码的个数；试给出以下面为初始节点和目标节点的图搜索过程，指明各节点估价函数值和整体解路径，并计算该搜索过程的渗透度是多少？有效分枝系数是多少？
3 4 5
2 6
1 8 7
3 4 5
8 6
2 1 7
2、将公式G化为Skolem范式，并给出G的子句集S。
3、使用基于规则的正向演绎系统证明下面问题：
已知事实 ；规则两条 ， ；目标 。画出演绎过程与/或图。
三、证明第一种形式的Herbrand定理：设S是子句集，则S是不可满足的，当且仅当对应于S的每一个完全语义树都存在一个有限的封闭语义树。（15分）
四、总结α-β过程，并以下述博弈树为例，以优先产生左边子节点的次序进行α-β剪枝，指出在何处发生剪枝、何处为α修剪、何处为β修剪？标明发生剪枝的节点和初始节点返回值的变化。图中□表示极大点，○表示极小点。（15分）
五、什么叫支架集归结演绎，试证明基子句集支架集归结演绎的完备性。（10分）
人工智能原理 2003年
一、叙述图搜索算法GRAPHSEARCH过程；设八数码问题有两个估价函数：f1(n)=d(n)+W(n)；f2(n)=d(n)+P(n)+3S(n)。其中d(n)是节点n在搜索树中的深度，W(n)是节点n中“不在位”数码的个数，P(n)是每个数码离开目标位置的距离的和。S(n)是由如下方式得到的序列分：对于非中心的外圈上的数码沿顺时针方向走一圈，如果一个数码后面的数码不是它在目标状态下的后继者，则给这个数码记2分，否则记0分；对于中心位置，有数码的记1分，没有的话记0分。然后把所有上述得分加起来，就得到序列分S(n)。现有初始状态和目标状态描述如下：请画出各自的启发式搜索过程图，在图中标明各节点的估价函数值，并标明节点扩展的次序。计算出各自的渗透度和有效分枝系数。（40分）
3 4 5
2 6
1 8 7
3 4 5
8 6
2 1 7
二、总结博弈搜索的极小极大过程和α-β过程，并以下述博弈树为例，给出两个过程的各节点返回值和搜索到的路径（请画出两个过程图）。对于其中的α-β过程以优先产生左边子节点的次序进行α-β剪枝，指出在何处发生剪枝、何处为α修剪、何处为β修剪？标明发生剪枝的节点和初始节点返回值的变化。图中□表示极大点，○表示极小点。（20分）
三、（27分）
1、设子句集 ，求S的H域，S的原子集，子句 的基例集合。
2、使用合一算法判断表达式集合W={Q(f(a), g(x)), Q(y, y)}是否可合一，若可合一，则求出最一般合一。
3、试用表推演方法证明 共同蕴含 。
四、设S是命题逻辑子句集，P是S中出现的一个原子符号，于是可将S中子句分为三部分：含有文字P的部分 ，含有文字～P的部分 ，和不含文字P或~P的部分S3。令 ， ，请证明S是不可满足的当且仅当S1’ , S2’ 都是不可满足的。（8分）
五、请举出基于规则的正向演绎系统不完备的例子。（5分）
人工智能原理 2002年
一、简要回答下列问题（24分）
1、以八数码问题为例，说明产生式系统的基本组成。
2、什么叫A算法？A算法的主要性质是什么？
3、在基于规则的演绎系统中，什么是合一复合替换？为什么要考虑替换的相容性？
4、在基于规则的正向演绎系统中，规则和目标各要求怎样的形式？
5、基于规则的正向演绎系统是否完备？反向演绎是否完备？双向演绎是否完备？
6、在启发式搜索中，估价函数一般定义为f(n)＝g(n)＋h(n)，指明定义中各部分的含义，并说明为什么使用这种定义方式。
7、在合一算法中，设W是非空表达式集合，D是W的差异集合，则当D具有怎样的形式时，W是不可合一的？
8、常用的知识表示方法有哪几种，简要回答各自的特点。
二、判断对错（14分）
1、OPEN表上任一具有f(n)≤f(s)的点，最终都将被A算法选作扩展的节点。
2、若满足单调限制，则A算法所扩展的节点序列的f值是单调递增的。
3、设θ，λ是两个替换，则θ•λ=λ•θ。
4、表达式集合W={P(f(x), g(y, z), z), P(y, h(k(x)), f(z))}是可合一的。
5、渗透度和有效分枝系数都是关于图搜索方法启发能力的空间复杂性度量标准。
6、子句集S恒假，当且仅当对每一个解释I，使S中的每个子句C的基例C’被I弄假。
7、一阶逻辑中任一公式是否是恒假的，可用归结方法判定。
三、（12分）
1、若E=Q(y, f(y, g(x))), θ={a/x, b/y, y/z},λ={a/x, z/y, f(x)/z}, 求Eθ, Eλ, Eθ•λ
2、使用回溯搜索策略求解四皇后问题。其中规则排序使用对角线函数diag(i, j)，若diag(i, j)＜diag(m, n)，则在排序中把规则Rij放在规则Rmn的前面。diag (i, j)定义为用过单元(i, j)的最长对角线的长度。若diag函数值相同则规则随机排序。
四、使用归结方法证明下述子句集是不可满足的（写出整个归结过程和每一步归结使用的合一替换）。
（10分）
五、设产生式系统PS，其状态集合DB={a, b, c, d, e, f, g, h, i, m}，产生式规则为：
a→b，c→m，g→h，a→c，d→e，h→i，a→d，e→f，m→i，b→g，f→m
设a为初始状态，规则应用费用为1，各状态的启发函数值为：
状态 a b c d e f g h i m
h值 1 1 8 2 2 2 4 4 10 4
用A算法画出节点c扩展前与扩展后的搜索图与搜索树，要求标出图中节点的扩展次序、估价函数值，写出节点c扩展前CLOSED表与OPEN表中的元素。（15分）
六、已知子句集S={P(g(x), z), ~P(f(y), h(a))}，求S的原子集、S的语义树。若给定S的一个解释I如下：
D={1, 2} a g(1) g(2) f(1) f(2) h(1) h(2) P(1, 1) P(2, 2) P(2, 1) P(1, 2)
2 2 1 1 2 2 1 F F T T
请构造S对应与I的H解释I。（15分）
人工智能原理 2002年
七、对下面的博弈树以优先产生左边子节点的次序进行α-β剪枝，指出在何处发生剪枝、何处为α修剪、何处为β修剪？标明发生剪枝的节点和初始节点返回值的变化，以及搜索到的路径。图中□表示极大点，○表示极小点。说明一般的α-β剪枝过程中，什么情况下效率最高。（10分）
人工智能原理 2000年
一、简要回答下列问题（24分）
1、请叙述产生式系统的过程。
2、回答产生式系统的分类，并说明各自的优缺点。
3、叙述什么样的产生式系统是可交换的产生式系统。
4、说明无信息的图搜索过程与启发式图搜索过程的差异，并举出两种典型的无信息图搜索方法。
5、叙述一阶逻辑解释的定义。
6、在语义上证明子句集恒假时，仅考虑该子句集的Herbrand解释是否够用？为什么？
7、在基于规则的演绎系统中，什么是合一复合替换？为什么要考虑替换的相容性？
8、机器学习一般分为哪几种类型？
二、设八数码问题有估价函数：f(n)=d(n)+W(n)；其中d(n)是节点n在搜索树中的深度，W(n)是节点n中“不在位”数码的个数。现有初始状态描述和目标状态描述如下：
3 4 5
2 6
1 8 7
3 4 5
8 6 7
2 1
请画出启发式搜索过程图，在图中标明各节点的估价函数值，并标明节点扩展的次序。（20分）
三、试用表推演方法证明 共同蕴含 。（16分）
四、叙述合一算法，并用合一算法求出W={P(a, x, f(g(y))), P(z, f(z), f(u))}的最一般合一。（写出算法的执行步骤，20分）
五、欲对某一有解的图搜索问题试用A算法，试证明A算法终止前的任何时刻OPEN表中总存在节点n’，n’在最佳解路径上，满足f(n’)≤f(s)，其中s为初始节点。（15分）
六、在归结推理方法中，若不取因子而仅使用二元归结式是不完备的，请举出一个反例。（5分）
人工智能原理 xxxx年
一、回答下列问题（20分）
1、什么是可交换产生式系统？
2、影响A算法启发能力的因素有哪些？
3、叙述α-β过程的剪枝规则。
4、归结原理有哪几种重要的改进？
5、描述基于规则的正向演绎系统的初始状态、规则和目标的一般形式。
二、请用估价函数：f(n)=d(n)+W(n) 求解八数码问题，其中d(n)是节点n在搜索树中的深度，W(n)是节点n中“不在位”数码的个数。
3 2 1
4 8
5 6 7
3 8 2
4 6 1
5 7
画出启发式搜索过程图，在图中标明各节点的估价函数值，并标明节点扩展的次序。（20分）
三、叙述合一算法，并用该算法寻找表达式集W={R(x, x), R(f(a), g(y))}的最一般合一。（20分）
四、使用AO算法，启发函数应满足什么条件？下图是已给出的与/或图，其中n0是初始节点，{n7, n8}是目标节点集，h是启发函数，并假定k-连接符的费用是k。请用AO算法求解其最优解图。（20分）
n n0 n1 n2 n3 n4 n5 n6 n7 n8
h(n) 0 2 4 4 1 1 2 0 0
五、证明下述归结方法的完备性定理：如果基子句集S是不可满足的，则存在从S推出空子句的归结演绎。（20分）
人工智能原理 xxxx年A
一、简要回答下列问题
1、人工智能的主要研究领域有哪些？
2、产生式系统由哪几部分组成？各部分的作用是什么？
3、产生式系统的控制策略有哪几种方式？
4、什么是深度优先搜索？什么是宽度优先搜索？
5、什么叫启发信息？它是如何使用的？
6、影响A算法启发能力的要素有哪些？
7、搜索方法的启发能力有哪几种基本的度量方法？
8、什么是从子句集S推出子句C的归结演绎？
9、什么是可交换产生式系统？
10、在归结演绎中，什么叫最一般的合一替换？
二、试述可分解产生式系统的基本过程。
三、已知八数码难题的初始状态和目标状态为：
1 2 3
8 4
7 6 5
2 8 3
1 6 4
7 5
设估价函数：f(n)=d(n)+W(n) ，其中d(n)是节点n在搜索树中的深度，W(n)是节点n中“不在位”数码的个数。画出使用此函数A算法解题的搜索树，在树上标明各节点的估价函数值及选择扩展节点的次序。
四、已知与/或图，其中n0是初始节点，{n7, n8}是目标节点集，h是启发函数，并假定k-连接符的费用是k。请用AO算法求解其最优解图。
n n0 n1 n2 n3 n4 n5 n6 n7 n8
h(n) 0 2 4 4 1 1 2 0 0
五、试用归结演绎证明公式 是公式集
的逻辑结果。
人工智能原理 xxxx年B
一、简要回答下列问题
1、无信息的图搜索方法主要有哪两种？
2、简述各种搜索策略各自的优缺点。
3、影响A算法启发能力的要素有哪些？
4、一阶逻辑中，公式是怎样定义的？
5、一阶逻辑中，公式的解释是怎样定义的？
6、命题逻辑中，常用哪两种公式范式？
7、一阶逻辑中，常用哪两种公式范式？
8、什么叫子句集的Herbrand域？
二、试述图搜索算法GRAPHSEARCH。
三、已知八数码难题的初始状态和目标状态为：
1 2 3
8 4
7 6 5
2 8 3
1 6 4
7 5
设估价函数：f(n)=d(n)+W(n) ，其中d(n)是节点n在搜索树中的深度，W(n)是节点n中“不在位”数码的个数。画出使用此函数A算法解题的搜索树，在树上标明各节点的估价函数值及选择扩展节点的次序。
四、写出下述公式的Skolem范式：
五、请用归结方法证明子句集 是不可满足的。
六、请使用回溯搜索策略求解四皇后问题。其中规则排序使用对角线函数diag(i, j)，若diag(i, j)＜diag(m, n)，则在排序中把规则Rij放在规则Rmn的前面。diag (i, j)定义为用过单元(i, j)的最长对角线的长度。
基于A算法求解八数码问题是一种规划问题，即用有限步骤把初始状态转换成目标状态的过程。A算法是一种带有启发式函数的搜索算法，用于通过估价函数指导搜索，提高搜索效率。
为了实现上述功能，需要定义若干个变量和函数，如下所示：
定义变量：
init_state：初始状态，即八数码问题的初始排列；
goal_state：目标状态，即八数码问题的最终排列；
f_score：估价函数值，即启发函数和实际代价之和；
g_score：实际代价，即当前状态到起始状态的实际步数；
h_score：启发函数值，即当前状态到目标状态的估计步数。
定义函数：
get_successor_states()：用于获取当前状态的所有后继状态；
get_heuristic_value()：用于计算当前状态到目标状态的估计步数，即启发函数值；
get_g_value()：用于计算当前状态到起始状态的实际步数；
get_f_value()：用于计算当前状态的估价函数值，即启发函数值与实际代价之和；
compare_f_values()：用于比较两个状态的估价函数值的大小；
A_search()：用于执行A搜索算法，求解八数码问题。
在定义了上述变量和函数后，我们就可以编写A搜索算法的代码了。下面是一个可能的实现方式：
Copy code
# 定义估价函数
def get_heuristic_value(state):
h_value = 0
# 计算估价函数值
for i in range(len(state)):
for j in range(len(state[i])):
if state[i][j] != goal_state[i][j]:
h_value += 1
return h_value
# 定义实际代价函数
def get_g_value(state):
g_value = 0
# 计算实际代价值
for i in range(len(state)):
for j in range(len(state[i])):
if state[i][j] != init_state[i][j]:
g_value += 1
return g_value
# 定义估价函数值函数
def get_f_value(state):
# 计算估价函数值
f_value = get_g_value(state) + get_heuristic_value(state)
return f_value
# 定义估价函数值比较函数
def compare_f_values(state1, state2):
# 比较两个状态的估价函数值
f1 = get_f_value(state1)
f2 = get_f_value(state2)
if f1 < f2:
return -1
elif f1 > f2:
return 1
else:
return 0
# 定义A搜索算法
def A_search():
# 初始化OPEN表和CLOSED表
open_list = []
closed_list = []
# 将初始状态加入OPEN表
并更新估价函数值 open_listappend(init_state) f_values[init_state] = get_f_value(init_state)
# 循环执行直到OPEN表为空
while len(open_list) > 0:
# 从OPEN表中选择估价函数值最小的状态
current_state = min(open_list, key=get_f_value)
# 如果当前状态是目标状态，则算法执行成功
if current_state == goal_state:
return True
# 将当前状态从OPEN表中移除，并加入CLOSED表
open_listremove(current_state)
closed_listappend(current_state)
# 获取当前状态的所有后继状态
successor_states = get_successor_states(current_state)
# 遍历所有后继状态
for successor_state in successor_states:
# 如果后继状态已在CLOSED表中，则跳过
if successor_state in closed_list:
continue
# 如果后继状态不在OPEN表中，则加入OPEN表并更新估价函数值
if successor_state not in open_list:
open_listappend(successor_state)
f_values[successor_state] = get_f_value(successor_state)
# 如果新的路径更优，则更新估价函数值
elif get_f_value(successor_state) < f_values[successor_state]:
f_values[successor_state] = get_f_value(successor_state)
# 如果OPEN表为空，则算法执行失败
return False
上面的代码实现了A搜索算法的基本流程，包括初始化、主循环、状态扩展和结束条件判断。它使用了估价函数值来比较
不同状态的优劣，从而决定搜索的方向和顺序。
为了实现上述需求，我们还需要对代码进行一些改进和完善，如下所示：
定义3种不同的启发式函数：我们可以定义3种不同的启发式函数，分别用于计算曼哈顿距离、欧几里得距离和拼图曼哈顿距离。这些启发式函数的实现方式略有不同，但都基于当前状态与目标状态之间的位置关系进行计算。
提供可视化界面：我们可以创建一个可视化界面，用于展示搜索过程。该界面应能够显示搜索树、估价函数值、OPEN表和CLOSED表的动态变化情况。同时，用户应能够选择预定义的启发式函数，随机初始化初始状态，单步执行或连续执行搜索算法。
统计扩展节点数和执行时间：为了对采用不同启发式函数的A算法进行性能对比研究，我们需要统计算法执行过程中的扩展节点数和执行时间。这些信息可以用来评估算法的效率和优劣。
通过上述
改进和完善，我们就可以实现一个能够求解八数码问题的A算法，具有较好的可视化展示和性能分析能力。
根据问题的实际情况不断寻找可利用的知识，从而构造成一条代价较少的推理路线，使问题得到圆满解决的过程称为搜索。
寻找问题的解的一种可靠的方法是首先列出所有候选解，然后依次检查每一个解，即可以找到所需要的问题的答案。这是一种“万能”的方法，理论上，当候选解的数量可以穷尽并且通过检查所有或部分候选解能够得到所需解时，问题就能得到解决。
但是，在实际应用中，因为候选解的数量通常都非常大（比如指数级），并且计算机的速度和内存都有限制，因此对问题不加分析的穷尽算法通常只能解决规模很小的问题。
在实际运用中常采用回溯和分枝定界法对问题进行求解。按照这两种方法对候选解进行系统检查通常会使问题的求解时间大大减少（无论对于最坏情形还是对于一般情形）。这二种方法由于都是按规定的路线进行，基本没有使用与问题有关的启发性信息，属于盲目搜索策略。在涉及人工职能的有些问题如博弈问题时，还会用到启发是搜索策略，如A算法等。
一、回溯法和分枝限界法
问题的表示
状态空间表示法是表示问题及其搜索过程的一种形式表示方法。可以用解空间树来表示问题的结构。 对于一棵树，树中的每一个结点确定所求问题的一个问题状态，由根结点到其它结点的所有路径确定了这个问题的状态空间。解状态是一些问题状态S，对于这些问题状态，由根到S的那条路径确定了这解空间的一个元组。答案状态则是由解状态到根的路径。
对于一种状态空间树，可以先系统地生成问题的状态，接着确定问题状态的解状态，最后确定那些解状态是答案状态从而将这些问题解出。
从根结点开始解问题，如果已经生成一个结点而它的所有儿子结点还没有全部生成，则这个结点叫做活结点。当前正在生成其儿子的活结点叫E结点，不再进一步扩展或者其儿子结点已经全部生成的生成结点就是死结点。
回溯算法使用深度优先方法搜索树结构，而分枝定界一般用宽度优先方法来搜索这些树。
回溯方法的步骤如下：
1) 定义一个解空间，它包含问题的解。
2) 用适于搜索的方式组织该空间。
3) 用深度优先法搜索该空间，利用限界函数避免移动到不可能产生解的子空间。
回溯算法的特性是在搜索执行的同时产生解空间。在搜索期间的任何时刻，仅保留从开始节点到当前E -节点的路径。因此，回溯算法的空间需求为O（从开始节点起最长路径的长度）。
分枝限界法的步骤和回溯的唯一区别是采用了宽度优先的方法来搜索树，因此分枝法消耗的空间比回溯法要多。
这二种搜索策略从本质上来讲都是属于穷尽法的搜索，由于在搜索路径上的不同也造成这二种方法各自都有其优缺点、适用的求解问题也就不同。
宽度优先占有优势的问题：
九宫重排问题
九宫重排问题是一个可以回溯法和分枝法都能解决的问题。但是，对于这个问题运用分枝法是有利的。
九宫重排问题，在33的方格棋盘上放置标由数字1、2、3、4、5、6、7、8共8个棋子，初始状态为S 0 ，目标状态为Sg ，当找到一个解时结束搜索。
从根结点到叶子结点的路径即为解，算法为空格左移，空格上移，空格右移，空格下移。
S0
Sg
2
8
3
1
2
3
1
4
8
4
7
6
5
7
6
5
用宽度优先搜索，如下图：
f'(x) = g(x) + h(x)
2 8 3
1 4
7 6 5
2 8 3
1 4
7 6 5
2 3
1 8 4
7 6 5
3 8 2
1 6 4
7 5
3 8 2
1 4
7 6 5
8 3
2 1 4
7 6 5
3 8 2
1 4
7 6 5
8 2
2 1 4
7 6 5
2 3 4
1 8
7 6 5
1 2 3
8 4
7 6 5
2 3
1 8 4
7 6 5
2 3
1 8 4
7 6 5
2 8 3
1 6 4
7 5
2 8 3
1 6 4
7 5
3 8 2
1 4
7 6 5
2 8 3
1 6
7 5 4
2 8 3
6 4
1 7 5
2 8 3
1 4 5
7 6
2 8
1 4 3
7 6 5
2 8 3
1 4 5
7 6
2 8
1 4 3
7 6 5
2 8 3
7 1 4
6 5
2 8 3
7 4
6 1 5
8 1 3
2 4
7 6 5
8 3 2
2 1 4
7 6 5
1 2 3
8 4
7 6 5
16
26
9
8
7
6
2
1
S0
4
3
5
Sg
图示解的路径是 S0-3-8-16-26(Sg)
宽度优先搜索的盲目性较大，当目标结点距离初始结点较远时将会产生许多无用结点，空间浪费较大，搜索效率低，但是只要问题有解，用宽度优先搜索总可以得到解，而且得到的路径最短的解。
用深度优先策略搜索，如下图：
2 8 3
1 4
7 6 5
2 8 3
1 4
7 6 5
2 3
1 8 4
7 6 5
3 8 2
1 6 4
7 5
3 8 2
1 4
7 6 5
2 8 3
1 6 4
7 5
2 8 3
1 6 4
7 5
2 8 3
1 6
7 5 4
1
S0
2
2 8
1 6 3
7 5 4
2 8 1 6 3
7 5 4
2 8
1 6 3
7 5 4
3
4
5
6
在深度优先搜索中，搜索一旦进入某个分枝，就将沿着该分枝一直向下搜索，如果该节点恰好在此分支上，则可较快地得到解。但是，如果目标节电不在此分支上，而该分支又是一个无穷分支，则就不可能得到解。
显然该问题用宽度优先搜索的策略是较好的。
经典的N皇后问题
N皇后问题要求求出N个皇后在棋盘上的所有摆法，（该问题很多书籍上都有详细介绍，这儿图表省略），该问题是适合用回溯法来描述和解决的问题，通过深度优先搜索至多需要检索N!个元组，而如果用分枝法，因为要生成所有问题的解，则必须储存检索过程中的E结点，造成储存空间的极度膨胀，这类问题明显是用回溯法占优势的。
回溯法和分枝法是基本的搜索策略，大多数情况下如果找不到更好的解决方案，总是可以用这二种方法尝试。
但是它们有一个很大的缺陷就是都是在一个给定的状态空间中穷举。这在状态空间不大的情况下是很合适的算法，可是当状态空间十分大，且不预测的情况下就不可取了。它的效率实在太低，甚至不可完成。
二、启发式搜索算法
通常在搜索中能直接运用回溯、分枝法的问题并不多，回溯和分枝的过程中，施加一定的条件，对搜索过程中出现的结点进行判断，可以提高效率。
启发式搜索就是在状态空间中的搜索对每一个搜索的位置进行评估，得到最好的位置，再从这个位置进行搜索直到目标。这样可以省略大量无畏的搜索路径，提到了效率。在启发式搜索中，对位置的估价是关键。采用了不同的估价可以有不同的效果。
启发式搜索有很多的算法，如：局部择优搜索法、最好优先搜索法等等。A也是。这些算法都使用了启发函数，但在具体的选取最佳搜索节点时的策略不同。
局部择优搜索法，就是在搜索的过程中选取“最佳节点”后舍弃其他的兄弟节点，父亲节点，而一直得搜索下去。这种搜索的结果很明显，由于舍弃了其他的节点，可能也把最好的节点都舍弃了，因为求解的最佳节点只是在该阶段的最佳并不一定是全局的最佳。
局部择优搜索法它是对深度优先搜索方法的一种改进。
全局择优搜索是 局部择优搜索的一种改进，试图克服局部择优搜索的的局限性。再搜索时，每次总是从全体的活结点中选取一个估价值最小的节点，
在搜索过程中，启发式搜索的关键是要确定下一个要考察的节点，用于估价节点重要性的函数称为估价函数
f'(x) = g(x) + h(x)
其中g(x)为从初始节点So到节点X已经实际付出的代价；h(x)是从节点X到节点Sg的最优路径的估计代价。h(x)称为启发函数。
九宫重排
当用全局择优搜索求解该问题时，可以设估价函数为 f'(x) = d(x) + h(x)
d(x)表示节点x的深度，h(x)表示节点x的棋局与目标节点棋局位置不相同的棋子数。
2 8 3
1 4
7 6 5
2 8 3
1 4
7 6 5
2 3
1 8 4
7 6 5
3 8 2
1 6 4
7 5
3 8 2
1 4
7 6 5
8 3
2 1 4
7 6 5
3 8 2
1 4
7 6 5
1 2 3
8 4
7 6 5
2 3
1 8 4
7 6 5
2 3
1 8 4
7 6 5
1 2 3
8 4
7 6 5
4
6
4
6
6
4
1
S0
4
4
5
Sg
1 2 3
7 8 4
6 5
5
5
S3
S2
S1
图中节点旁标明的数字是该节点的估价函数值。
该问题的解路径为： So-S1-S2-S3-Sg
以上论述一些树型问题基本的搜索的策略，当问题的状态空间是有向图时，节点的重复将导致大量冗余的搜索，甚至时搜索过程陷入无效的循环而无法找到解，这时就需要对估价函数进行限制，A算法就是针对图的有序搜索的算法。
问题的求解可以有很多方法，而如何建立数学模型，选择问题的求解方式是十分重要的，方法的好坏是面向一个具体的问题的，需要具体问题具体分析
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）