2024-09-24-人工智能导论-启发式搜索难-头歌平台答案
人工智能导论 启发式搜索（难） （头歌平台答案）
第1关：启发式搜索算法
任务描述
本关任务：编写一个基于启发式算法的解决八数码问题的小程序。
相关知识
启发式搜索的一般算法是最佳优先搜索（best-first search），此为树搜索和图搜索算法的一个实例，节点是基于评估函数f(n)被选择扩展的。可以注意到盲目搜索中有个一致代价搜索，也用了一个函数叫做g(n)，二者的区别如下。
1）启发式搜索通过f(n)对优先级队列排队，一致代价搜索通过g(n)对优先级队列排队；
2）启发式搜索的f(n)定义比g(n)要更加内涵丰富些,g(n)仅仅是代表从初始状态到当前状态的开销，但是f(n)可以是从当前状态到目标状态的估计。
启发式函数（对于大多数最佳优先搜索）：h(n)=节点n到目标节点的最小代价路径的代价估计值
启发式搜索：采用了f(n)（即启发式函数）的搜索策略。
为了完成本关任务，你需要掌握：1.如何获取数组的长度，2.如何遍历数组。
#####问题描述
例：3×3九宫棋盘，放置数码为1-8的8个棋牌，剩下一个空格，只能通过棋牌向空格的移动来改变棋盘的布局。要求：根据给定初始布局（即初始状态）和目标布局（即目标状态），如何移动棋牌才能从初始布局到达目标布局，找到合法的走步序列。
代码：
using namespace std;
struct Node{
int state[9];
struct Node* parent;
int value;
int depth;
friend bool operator < (Node A, Node B) //按照value值小的方案构造优先级队列
{
return A.value > B.value;
}
};
priority_queue<Node> openTable; //open表
queue<Node> closeTable; //close表
stack<Node> Path; //最终路径
int count1=0,count2=0;
int read(Node& S,Node& G){
/*初始化*/
S.parent=NULL; S.depth=0; S.value=0;
G.parent=NULL; G.depth=0; G.value=0;
int a[]={1,2,3,4,5,6,7,0,8};
int b[]={1,0,2,4,6,3,7,5,8};
//cout<<"Please enter the initial state\n";
for(int i=0;i<num;i++)
S.state[i]=a[i]; //cin>>S.state[i];
//cout<<"Please enter the target status\n";
for(int i=0;i<num;i++)
G.state[i]=b[i];//cin>>G.state[i];
for(int i=0;i<=num-2;i++)
for(int j=i+1;j<num;j++)
if(S.state[i]>S.state[j]&&S.state[i]*S.state[j]!=0)
count1++;
for(int i=0;i<=num-2;i++)
for(int j=i+1;j<num;j++)
if(G.state[i]>G.state[j]&&G.state[i]*G.state[j]!=0)
count2++;
if(count1%2!=count2%2)
{
return 0;
}
return 1;
}
int value1(Node A,Node G){
int count=8;
for(int i=0;i<num;i++)
if(A.state[i]==G.state[i]&&G.state[i]!=0)
count--;
return count +A.depth;
}
int value2(Node A,Node G){
int count=0,begin[3][3],end[3][3]; //count记录所有棋子移动到正确位置需要的步数
for(int i = 0; i < num; i++){
begin[i/3][i%3]=A.state[i];
end[i/3][i%3]=G.state[i];
}
for(int i = 0; i < 3; i++) //检查当前图形的正确度
for(int j = 0; j < 3; j++)
{
if(begin[i][j] == 0)
continue;
else if(begin[i][j] != end[i][j])
{
for(int k=0; k<3; k++)
for(int w=0; w<3; w++)
if(begin[i][j] == end[k][w])
count = count + fabs(i-k*1.0) + fabs(j-w*1.0);
}
}
return count +A.depth;
}
bool judge(Node S, Node G)
{
for (int i = 0; i <= 8; i++)
{
if (S.state[i] != G.state[i])
{
return false;
}
}
return true;
}
//产生新节点，加入OPEN表
void creatNode(Node& S, Node G)
{
/* 计算原状态下,空格所在的行列数，从而判断空格可以往哪个方向移动 */
int blank; //定义空格下标
for(blank=0;blank<9&&S.state[blank]!=0;blank++) ;//找到空白格
int x =blank / 3, y = blank % 3; //获取空格所在行列编号
for (int d = 0; d < 4; d++) //找到S扩展的子节点，加入open表中
{
int newX=x,newY=y;//新空白格坐标
Node tempNode;
/*移动空白格*/
if(d==0) newX = x -1;
if(d==1) newY = y -1;
if(d==2) newX = x +1;
if(d==3) newY = y +1;
int newBlank = newX * 3 + newY; //空格新的位置
/**********Begin**********/
if (newX >= 0 && newX < 3 && newY >= 0 && newY < 3){
tempNode = S;
tempNode.state[blank] = S.state[newBlank];
tempNode.state[newBlank] = 0;
if (S.parent != NULL && (*S.parent).state[newBlank] == 0){
continue;
}
tempNode.parent = &S;
tempNode.value = value2(tempNode,G);
tempNode.depth = S.depth +1;
openTable.push(tempNode);
}
/**********End**********/
}
}
第2关：贪婪最佳优先搜索(GBS)
任务描述
本关任务：根据实例，编写一个使用贪婪最佳优先搜索算法的小程序。
相关知识
贪婪最佳优先搜索（GBS）试图扩展离目标最近的节点。所以只用启发式信息，f(n)=h(n)。
在罗马尼亚问题中，使用的是当前地点到目的地的直线距离（这个信息不能由问题本身的描述计算得到，而且这个信息是有用的——因为和实际路程相关，所以是一个有用的启发式），在此问题中，GBS搜索代价最小，但是不是最优。
GBS可能陷入死循环，但是它在有限状态空间的图搜索下是完备的，其他情况则不是。其时间和空间复杂度都是O(bm)O(bm)，其中m是搜索空间的最大深度。
问题描述
例:钱币找零问题
这个问题在我们的日常生活中很普遍。假设1元、2元、5元、10元、20元、50元、100元的纸币分别有c0, c1, c2, c3, c4, c5, c6张。现在要用这些钱来支付K元（假设为K=130），至少要用多少张纸币？用贪心算法的思想，很显然，每一步尽可能用面值大的纸币即可。在日常生活中我们自然而然也是这么做的。在程序中已经事先将Value按照从小到大的顺序排好。
贪心分析
贪心算法是指在对问题求解时，总是做出在当前看来是最好的选择。
当前最好的选择，首先是使用面值最大的钱，比如总共要130元，则第一步肯定是选择100元面值的，第二步选择20元面值的，第三步选择10元面值的。
代码：
using namespace std;
//当前的钱库，面值以及对应数量
int single_money[7] = {1,2,5,10,20,50,100};
int number_money[7] = {2,5,0,3,4,0,4};
//每种面值使用贪心算法后需要使用的张数
int count[7] = {};
int total_count;
int tanxin(int money)
{
/**********Begin**********/
if (money >=0){
for (int i = 6; i >= 0;i--){
count[i] = min(number_money[i],money/single_money[i]);
money = money - count[i]*single_money[i];
}
return 0 ;
}
else{
return money;
}
/**********End**********/
}
第3关：贪婪最佳优先搜索(GBS) 首付的烦恼
任务描述
本关任务：编写一个解决西红柿烦恼问题的小程序。
相关知识
为了完成本关任务，你需要掌握：
1.了解贪心算法核心思想；
2.熟练掌握C++编程能力。
问题描述
例:西红柿首富的烦恼问题：
王多鱼获得了一笔的奖金X，要求购买最少的商品把钱花光，即没有零钱剩下，否则奖金会被没收。
贪心分析
贪心算法是指在对问题求解时，总是做出在当前看来是最好的选择。
根据要求,输入奖金金额整数m,设商品的种类为k（每个种类商品个数不限）,用a[i]存放第i类商品的价值，尝试找出最少商品数量。
编程要求
根据提示，在右侧编辑器补充代码，得出贪心最优结果方案。
using namespace std;
int tanxin(int k,int a[],int m){
int n=0,cnt=0;
/**********Begin**********/
for(int i=k;i>=1;i--){
if(m>=a[i]){
n = m/a[i];
m = m - n*a[i];
cnt =cnt+n;
cout<<"Price of the items is "<<a[i]<<": "<<n<<endl;
if(m==0)
break;
}
}
cout<<"The minimum number of items: "<<cnt<<endl;
/**********End**********/
}
第4关：贪婪最佳优先搜索(GBS) 首富烦恼升级版
任务描述
本关任务：编写一个解决西红柿首富烦恼问题的小程序。
相关知识
为了完成本关任务，你需要掌握：
1.了解贪心算法核心思想；
2.熟练掌握C++编程能力。
问题描述
例:西红柿首富的烦恼升级版问题：
王多鱼获得了一笔的奖金X，要求购买最少的商品把钱花光，即没有零钱剩下，否则奖金会被没收。
贪心分析
贪心算法是指在对问题求解时，总是做出在当前看来是最好的选择。
根据要求,输入奖金金额整数m,设商品的种类为k（每个种类商品个数有限）,用a[i]存放第i类商品的价值，b[i]存放第i类商品的数量，尝试找出最少商品数量。
编程要求
根据提示，在右侧编辑器补充代码，得出贪心最优结果方案。
using namespace std;
int tanxin(int k,int a[],int b[],int m){
int n,cnt=0,p;
/**********Begin**********/
for(int i=k;i>=1;i--){
if(m>=a[i]){
n = m/a[i];
p = min(n,b[i]);
m = m - p*a[i];
cnt +=p;
cout<<"Price of the items is "<<a[i]<<": "<<p<<endl;
if(m==0)
break;
}
}
cout<<"The minimum number of items: "<<cnt<<endl;
/**********End**********/
}
第5关：贪婪最佳优先搜索(GBS) 排队打水
任务描述
本关任务：编写一个基于启发式算法的解决八数码问题的小程序。
相关知识
启发式搜索的一般算法是最佳优先搜索（best-first search），此为树搜索和图搜索算法的一个实例，节点是基于评估函数f(n)被选择扩展的。可以注意到盲目搜索中有个一致代价搜索，也用了一个函数叫做g(n)，二者的区别如下。
1）启发式搜索通过f(n)对优先级队列排队，一致代价搜索通过g(n)对优先级队列排队；
2）启发式搜索的f(n)定义比g(n)要更加内涵丰富些,g(n)仅仅是代表从初始状态到当前状态的开销，但是f(n)可以是从当前状态到目标状态的估计。
启发式函数（对于大多数最佳优先搜索）：h(n)=节点n到目标节点的最小代价路径的代价估计值
启发式搜索：采用了f(n)（即启发式函数）的搜索策略。
为了完成本关任务，你需要掌握：1.如何获取数组的长度，2.如何遍历数组。
#####问题描述
例：3×3九宫棋盘，放置数码为1-8的8个棋牌，剩下一个空格，只能通过棋牌向空格的移动来改变棋盘的布局。要求：根据给定初始布局（即初始状态）和目标布局（即目标状态），如何移动棋牌才能从初始布局到达目标布局，找到合法的走步序列。
其中，八数码初始状态如下：
八数码目标状态如下：
搜索过程示例
算法步骤设计
1、读取初始状态和目标状态，并判断二者能否通过变换到达。
2、将初始节点压入OPEN表
3、取出OPEN表中估计值最小的节点，并放入CLOSE表
4、如果该节点不是目标节点，扩展该节点，将子节点放入OPEN表，并返回到第三步。
5、将该节点压入栈中，并将指针指向其父节点。
6、如果该节点的父节点不为空，返回到第五步。
7、如果栈不为空，出栈并输出该节点，直到栈为空。
using namespace std;
struct Node{
int state[9];
struct Node* parent;
int value;
int depth;
friend bool operator < (Node A, Node B) //按照value值小的方案构造优先级队列
{
return A.value > B.value;
}
};
priority_queue<Node> openTable; //open表
queue<Node> closeTable; //close表
stack<Node> Path; //最终路径
int count1=0,count2=0;
int read(Node& S,Node& G){
/*初始化*/
S.parent=NULL; S.depth=0; S.value=0;
G.parent=NULL; G.depth=0; G.value=0;
int a[]={1,2,3,4,5,6,7,0,8};
int b[]={1,0,2,4,6,3,7,5,8};
//cout<<"Please enter the initial state\n";
for(int i=0;i<num;i++)
S.state[i]=a[i]; //cin>>S.state[i];
//cout<<"Please enter the target status\n";
for(int i=0;i<num;i++)
G.state[i]=b[i];//cin>>G.state[i];
for(int i=0;i<=num-2;i++)
for(int j=i+1;j<num;j++)
if(S.state[i]>S.state[j]&&S.state[i]*S.state[j]!=0)
count1++;
for(int i=0;i<=num-2;i++)
for(int j=i+1;j<num;j++)
if(G.state[i]>G.state[j]&&G.state[i]*G.state[j]!=0)
count2++;
if(count1%2!=count2%2)
{
return 0;
}
return 1;
}
int value1(Node A,Node G){
int count=8;
for(int i=0;i<num;i++)
if(A.state[i]==G.state[i]&&G.state[i]!=0)
count--;
return count +A.depth;
}
int value2(Node A,Node G){
int count=0,begin[3][3],end[3][3]; //count记录所有棋子移动到正确位置需要的步数
for(int i = 0; i < num; i++){
begin[i/3][i%3]=A.state[i];
end[i/3][i%3]=G.state[i];
}
for(int i = 0; i < 3; i++) //检查当前图形的正确度
for(int j = 0; j < 3; j++)
{
if(begin[i][j] == 0)
continue;
else if(begin[i][j] != end[i][j])
{
for(int k=0; k<3; k++)
for(int w=0; w<3; w++)
if(begin[i][j] == end[k][w])
count = count + fabs(i-k*1.0) + fabs(j-w*1.0);
}
}
return count +A.depth;
}
bool judge(Node S, Node G)
{
for (int i = 0; i <= 8; i++)
{
if (S.state[i] != G.state[i])
{
return false;
}
}
return true;
}
//产生新节点，加入OPEN表
void creatNode(Node& S, Node G)
{
/* 计算原状态下,空格所在的行列数，从而判断空格可以往哪个方向移动 */
int blank; //定义空格下标
for(blank=0;blank<9&&S.state[blank]!=0;blank++) ;//找到空白格
int x =blank / 3, y = blank % 3; //获取空格所在行列编号
for (int d = 0; d < 4; d++) //找到S扩展的子节点，加入open表中
{
int newX=x,newY=y;//新空白格坐标
Node tempNode;
/*移动空白格*/
if(d==0) newX = x -1;
if(d==1) newY = y -1;
if(d==2) newX = x +1;
if(d==3) newY = y +1;
int newBlank = newX * 3 + newY; //空格新的位置
/**********Begin**********/
if (newX >= 0 && newX < 3 && newY >= 0 && newY < 3){
tempNode = S;
tempNode.state[blank] = S.state[newBlank];
tempNode.state[newBlank] = 0;
if (S.parent != NULL && (*S.parent).state[newBlank] == 0){
continue;
}
tempNode.parent = &S;
tempNode.value = value2(tempNode,G);
tempNode.depth = S.depth +1;
openTable.push(tempNode);
}
/**********End**********/
}
}
第6关：A*搜索：搜索最小总评估代价
任务描述
本关任务：使用A*算法编写一个实现八数码问题的小程序。
相关知识
不同于GBS，A*搜索对节点的评估结合了g(n)，即到达此节点已经花费的代价，和h(n)。故f(n)=g(n)+h(n)，即经过节点n的最小代价。
A搜索与一致代价搜索类似，除了A使用g+h而不是g。
A*搜索既是完备的也是最优的。
A*算法搜索过程的描述问题
1、把初始节点S0放入Open表中，f(S0)=g(S0)+h(S0)；
2、如果Open表为空，则问题无解，失败退出；
3、把Open表的第一个节点取出放入Closed表，并记该节点为n；
4、考察节点n是否为目标节点。若是，则找到了问题的解，成功退出；
5、若节点n不可扩展，则转到第(2)步；
6、扩展节点n，生成子节点ni(i=1,2,……)，计算每一个子节点的估价值f(ni) (i=1,2,……)，并为每一个子节点设置指向父节点的指针，然后将这些子节点放入Open表中；
7、根据各节点的估价函数值，对Open表中的全部节点按从小到大的顺序重新进行排序；
8、转第(2)步。
using namespace std;
const int ROW = 3;
const int COL = 3;
const int MAXDISTANCE = 10000;
const int MAXNUM = 10000;
typedef struct _Node{
int digit[ROW][COL];
int dist; // distance between one state and the destination
int dep; // the depth of node
// So the comment function = dist + dep.
int index; // point to the location of parent
} Node;
Node src, dest;
vector<Node> node_v; // store the nodes
bool isEmptyOfOPEN() {
for (int i = 0; i < node_v.size(); i++) {
if (node_v[i].dist != MAXNUM)
return false;
}
return true;
}
bool isEqual(int index, int digit[][COL]) {
for (int i = 0; i < ROW; i++)
for (int j = 0; j < COL; j++) {
if (node_v[index].digit[i][j] != digit[i][j])
return false;
}
return true;
}
ostream& operator<<(ostream& os, Node& node) {
for (int i = 0; i < ROW; i++) {
for (int j = 0; j < COL; j++)
os << node.digit[i][j] << ' ';
os << endl;
}
return os;
}
void PrintSteps(int index, vector<Node>& rstep_v) {
rstep_v.push_back(node_v[index]);
index = node_v[index].index;
while (index != 0) {
rstep_v.push_back(node_v[index]);
index = node_v[index].index;
}
for (int i = rstep_v.size() - 1; i >= 0; i--)
cout << "Step " << rstep_v.size() - i<< endl << rstep_v[i] << endl;
}
void Swap(int& a, int& b) {
int t;
t = a;
a = b;
b = t;
}
void Assign(Node& node, int index) {
for (int i = 0; i < ROW; i++)
for (int j = 0; j < COL; j++)
node.digit[i][j] = node_v[index].digit[i][j];
}
int GetMinNode() {
int dist = MAXNUM;
int loc; // the location of minimize node
for (int i = 0; i < node_v.size(); i++) {
if (node_v[i].dist == MAXNUM)
continue;
else if ((node_v[i].dist + node_v[i].dep) < dist) {
loc = i;
dist = node_v[i].dist + node_v[i].dep;
}
}
return loc;
}
bool isExpandable(Node& node) {
for (int i = 0; i < node_v.size(); i++) {
if (isEqual(i, node.digit))
return false;
}
return true;
}
int Distance(Node& node, int digit[][COL]) {
int distance = 0;
for (int i = 0; i < ROW; i++) {
for (int j = 0; j < COL; j++) {
if (node.digit[i][j] != 0) { // 忽略空格
for (int x = 0; x < ROW; x++) {
for (int y = 0; y < COL; y++) {
if (digit[x][y] == node.digit[i][j]) {
// 计算当前位置和目标位置之间的曼哈顿距离
distance += abs(i - x) + abs(j - y);
break; // 找到了就跳出内层循环
}
}
}
}
}
}
return distance;
}
int MinDistance(int a, int b) {
return (a < b ? a : b);
}
void ProcessNode(int index) {
int x, y;
bool flag;
for (int i = 0; i < ROW; i++) {
for (int j = 0; j < COL; j++) {
if (node_v[index].digit[i][j] == 0) {
x =i; y = j;
flag = true;
break;
}
else flag = false;
}
if(flag)
break;
}
Node node_up;
Assign(node_up, index);
int dist_up = MAXDISTANCE;
if (x > 0) {
Swap(node_up.digit[x][y], node_up.digit[x - 1][y]);
if (isExpandable(node_up)) {
dist_up = Distance(node_up, dest.digit);
node_up.index = index;
node_up.dist = dist_up;
node_up.dep = node_v[index].dep + 1;
node_v.push_back(node_up);
}
}
Node node_down;
Assign(node_down, index);
int dist_down = MAXDISTANCE;
if (x < 2) {
Swap(node_down.digit[x][y], node_down.digit[x + 1][y]);
if (isExpandable(node_down)) {
dist_down = Distance(node_down, dest.digit);
node_down.index = index;
node_down.dist = dist_down;
node_down.dep = node_v[index].dep + 1;
node_v.push_back(node_down);
}
}
Node node_left;
Assign(node_left, index);
int dist_left = MAXDISTANCE;
if (y > 0) {
Swap(node_left.digit[x][y], node_left.digit[x][y - 1]);
if (isExpandable(node_left)) {
dist_left = Distance(node_left, dest.digit);
node_left.index = index;
node_left.dist = dist_left;
node_left.dep = node_v[index].dep + 1;
node_v.push_back(node_left);
}
}
Node node_right;
Assign(node_right, index);
int dist_right = MAXDISTANCE;
if (y < 2) {
Swap(node_right.digit[x][y], node_right.digit[x][y + 1]);
if (isExpandable(node_right)) {
dist_right = Distance(node_right, dest.digit);
node_right.index = index;
node_right.dist = dist_right;
node_right.dep = node_v[index].dep + 1;
node_v.push_back(node_right);
}
}
node_v[index].dist = MAXNUM;
}
68747470733a2f2f626c6f:672e6373646e2e6e65742f323330315f37373132343635332f:61727469636c652f64657461696c732f313432343939393737