devbox
Cpp五条
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

人工智能导论罗马尼亚问题实验一搜索算法C++实现详解_如图所示的罗马尼亚旅行图列出不同搜索策略

作者：Cpp五条 | 2024-05-20 06:45:39

赞

踩

如图所示的罗马尼亚旅行图列出不同搜索策略

人工智能导论搜索算法实验

使用说明

建立图的代码,下面接上算法代码和主函数代码即可编译运行。

仅供借鉴思路，不建议完全复制粘贴。

给出链接：
六合一搜索算法完整代码

题目要求

一、实验目的
• 了解4种无信息搜索策略和2种有信息搜索策略的算法思想；
• 能够运用计算机语言实现搜索算法；
• 应用搜索算法解决实际问题(如罗马尼亚问题)；
• 学会对算法性能的分析和比较
二、实验的硬件、软件平台
硬件：计算机
软件：操作系统：WINDOWS／Linux
应用软件：C,Java或者MATLAB
三、实验内容及步骤
使用搜索算法实现罗马尼亚问题的求解罗马尼亚路线图
要求分别编写：宽度优先搜索，深度优先搜索，一致代价搜索，迭代加深的深度优先搜索算法以及实现贪婪最佳优先搜索和A*搜索算法。
并使用编写的搜索算法代码求解罗马尼亚问题；

开始写代码之前的思考：

建立图

如何把罗马尼亚问题给出的信息图作为已知信息保存呢？数据结构中学过，存图一般可以有两种方式，邻接表或连接矩阵。对于这个图，有20个节点，我们可以使用较容易实现的连接矩阵（二维数组，将每个城市抽象为数组下标，两个城市之间不可到达的值记为-1，可到达则记录路线长度）。

#include<iostream>
#include <functional>
#include<stack>
#include<vector>
#include<queue>
#include<memory.h>
using namespace std;
//城市名的首字母按照字母顺序进行编号，采用宏定义编译后续代码的理解
#define A 0
#define B 1
#define C 2
#define D 3
#define E 4
#define F 5
#define G 6
#define H 7
#define I 8
#define L 9
#define M 10
#define N 11
#define O 12
#define P 13
#define R 14
#define S 15
#define T 16
#define U 17
#define V 18
#define Z 19
#define visited 1 //标记已访问
#define not_visit 0//标记未访问
string city[20]= {"A","B","C","D","E","F","G","H","I","L","M","N","O","P","R","S","T","U","V","Z"}; //城市名称首字母
int Graph[20][20];
void init() { //初始化图信息 对应城市编号 宏记号 避免出错
	memset(Graph, -1, sizeof(Graph));
	Graph[O][Z]=71,Graph[Z][O]=71;//无向图 对应处赋值
	Graph[O][S]=151,Graph[S][O]=151;
	Graph[Z][A]=75,Graph[A][Z]=75;
	Graph[A][S]=140,Graph[S][A]=140;
	Graph[A][T]=118,Graph[T][A]=118;
	Graph[T][L]=111,Graph[L][T]=111;
	Graph[L][M]=70,Graph[M][L]=70;
	Graph[M][D]=75,Graph[D][M]=75;
	Graph[D][C]=120,Graph[C][D]=120;
	Graph[C][R]=146,Graph[R][C]=146;
	Graph[S][R]=80,Graph[R][S]=80;
	Graph[S][F]=99,Graph[F][S]=99;
	Graph[F][B]=211,Graph[B][F]=211;
	Graph[P][C]=138,Graph[C][P]=138;
	Graph[R][P]=97,Graph[P][R]=97;
	Graph[P][B]=101,Graph[B][P]=101;
	Graph[B][G]=90,Graph[G][B]=90;
	Graph[B][U]=85,Graph[U][B]=85;
	Graph[U][H]=98, Graph[H][U]=98;
	Graph[H][E]=86,Graph[E][H]=86;
	Graph[U][V]=142,Graph[V][U]=142;
	Graph[I][V]=92,Graph[V][I]=92;
	Graph[I][N]=87,Graph[N][I]=87;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58

考虑深度优先搜索策略：

深度优先策略可以采用递归实现，也可以用栈，来模仿递归过程求解，这里给出深度优先递归求解的代码：由于题目只需要找到一条路径，所以在代码中有一个返回条件是控制只搜索一个解的：（由于建图的顺序是不固定的，所以深度优先找到的路径是不唯一的，若把下面代码中一行注释，则可以找出所有的路径。按照上面的图恰找到的是经历节点最少的那一条路线）

给出DFS的代码：
const int start=A,target=B;		//起始城市为Ared，终止城市为Bucharest 该题中不能修改起始点和目标节点的位置，可在此处修改起点可终点

int sum_cost=0,node_num=0;		//记录代价值
int contral=0;//DFS中只输出一条路线的控制
void DFS_Romania(int now_node,stack<int> record,int *flag) {
	node_num++;//递归一次，拓展的节点数++;
	if(flag[start]==not_visit)
		record.push(start);
		flag[now_node]=visited;//节点标记已经访问
	
	//递归结束条件，当前节点为目标节点时输出路径 
	if(now_node==target) { 
		int way_num=0;//路段数
		stack<int> road_line; //  辅助栈  逆序record中的路径，实现路径对正序输出
		while(!record.empty()) {
			road_line.push(record.top());
			record.pop();
		}
		cout<<"深度优先搜索已找到目标节点，节点拓展顺序如上，路径如下："<<endl;
		while(!road_line.empty()) { //输出全部的路径
			int temp =road_line.top();
			road_line.pop();
			cout<<city[temp];

			if(temp!=target) { //不是目标节点时输出符号 --(cost)--》
				cout<<"--（"<<Graph[temp][road_line.top()]<<")-->";//将线路的cost打印出来
				sum_cost+=Graph[temp][road_line.top()];//总价值变化+每条路线的cost  注意这里的pop 和top的应用
				way_num++;
			}
		}
		cout<<endl<<"该路径的总消耗为: "<<sum_cost<<'\t'<<"一共经过了"<<way_num<<"个路段"<<endl;
		cout<<"用该搜索算法找到该路径共访问的节点个数为："<<node_num<<"个"<<endl<<endl;
		sum_cost=0;//清零，下一个算法好直接用
		contral=1; //只输出一条可以到达的路径的控制
		return; //结束
	}
	cout<<"当前拓展节点为："<<city[now_node]<<endl; 
	//未到达目标节点 寻找下一个可拓展的节点，对该节点进行递归
	bool isleaf=true; //递归返回条件 是叶子节点时返回  
	for(int i=0; i<20; i++) { //搜索当前节点相连的未访问的节点
		if(Graph[now_node][i]!=-1&&flag[i]!=visited) { //能到达且未访问
			isleaf=false; //还有能到达的点 不是叶子节点 
			record.push(i);
			DFS_Romania(i,record,flag); //递归访问下一个节点
			if(contral==1) return;// 控制只要找到一条路线就返回 该行注释掉会输出所有的路径
			//递归返回时说明 撤销已访问标记 i的存在会避免重复进某一条 
			flag[i]=0; 
			record.pop();
		}
	}
	if(isleaf==true) return;//到达叶子节点时 返回
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
主函数

简单调用上面的算法即可,不要忘记调用图的初始化函数和标记数组初始化为未访问。

int main() {
	init();//初始化图函数
	sum_cost=0,node_num=0;
	stack<int> rec;
	int sign[20];
	memset(sign,not_visit,sizeof(sign)); //
	DFS_Romania(start,rec,sign);
	return 0;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
运行结果如下：
当前拓展节点为：A
当前拓展节点为：S
当前拓展节点为：F
深度优先搜索已找到目标节点，节点拓展顺序如上，路径如下：
A--（140)-->S--（99)-->F--（211)-->B
该路径的总消耗为: 450   一共经过了3个路段
用该搜索算法找到该路径共访问的节点个数为：4个

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7

考虑宽度优先搜索策略

图已经建立好，宽度优先的搜索过程逐层搜索，队列可以很好的实现宽度优先。但要注意记录访问节点的父节点，便于搜索到目标节点后输出路线。给出搜索算法和主函数，在注释中有详细的思路说明：

实现代码
const int start=A,target=B;		//起始城市为Ared，终止城市为Bucharest 该题中不能修改起始点和目标节点的位置，可在此处修改起点可终点
int sum_cost=0,node_num=0;		//记录代价值
int contral=0;//DFS中只输出一条路线的控制


void BFS_Romania(queue<int> record,int *parent,int *flag){
        record.push(start);//起始节点加入队列
        
        while(!record.empty()){
            int temp=record.front();//拓展节点的值
			node_num++;//访问节点的个数；
            if(temp==target){//目标节点
                int way_num=0;//路段数
                stack<int> road;
                road.push(temp);
        		int i=temp;
                    while(road.top()!=start){//将父节点压入站，达到顺序输出的目的，直到栈顶元素是开始节点为止
                            i=parent[i];
							road.push(i);
                    }
                cout<<"宽度优先搜索找到目标节点，路径如下："<<endl;
                while(!road.empty()){
                        i=road.top();
                        road.pop();
                        cout<<city[i];

                        if(i!=target){//不是目标节点时输出符号 --(cost)--》
                        cout<<"--（"<<Graph[i][road.top()]<<")-->";//将线路的cost打印出来
                         sum_cost+=Graph[i][road.top()];//总价值变化+每条路线的cost
                        way_num++;
                        }
                }
                cout<<endl<<"该路径的总消耗为: "<<sum_cost<<'\t'<<"一共经过了"<<way_num<<"个路段"<<endl;
                        cout<<"用该搜索算法找到该路径共访问的节点个数为："<<node_num<<"个"<<endl<<endl;
                        sum_cost=0,node_num=0;//清零，下一个算法好直接用
                break; //输出一条路径后就结束
            }
           	cout<<"当前拓展节点为："<<city[temp]<<"   其子节点有：";
			 
            record.pop();
            flag[temp]=visited;
            for(int i=0;i<20;i++){ //不是目标 搜索当前所有的子节点
                if(Graph[temp][i]!=-1&&flag[i]!=visited){  //能到达且未访问
                    record.push(i);
                    parent[i]=temp;//更新记录父节点信息
                    flag[i]=visited;//已经加入队列 总会访问 不能再其他节点的子节点加入
                    cout<<city[i]<<' '; 
                }
           }
           cout<<endl; 
        }
}
int main() {
	init();//初始化 
	sum_cost=0,node_num=0;
	queue<int> rec;
	int sign[20];// 标记数组
	int parent[20];//记录每个节点的父亲节点
	memset(parent,-1,sizeof(parent));
	memset(sign,not_visit,sizeof(sign));
	BFS_Romania(rec,parent,sign);
	return 0;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
输出结果：
当前拓展节点为：A   其子节点有：S T Z
当前拓展节点为：S   其子节点有：F O R
当前拓展节点为：T   其子节点有：L
当前拓展节点为：Z   其子节点有：
当前拓展节点为：F   其子节点有：B
当前拓展节点为：O   其子节点有：
当前拓展节点为：R   其子节点有：C P
当前拓展节点为：L   其子节点有：M
宽度优先搜索找到目标节点，路径如下：
A--（140)-->S--（99)-->F--（211)-->B
该路径的总消耗为: 450   一共经过了3个路段
用该搜索算法找到该路径共访问的节点个数为：9个

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12

考虑迭代加深的深度优先搜索

迭代加深的深度优先算法与深度优先算法大同小异，这个算法是为了避免由于树深度过高，而目标节点又在较浅的层数，从而导致深度优先算法难以找到目标节点，但这个算法有个致命的缺点，就是如何确定受限层数。受限层数如果选择不恰当，会导致重复目标节点以上层数的点重复搜索。

代码如下：

该算法分为两个函数实现，一个是深度搜索指定层数内的点。
另一个负责不断的修改限制层数，知道搜到目标节点或整个树完全遍历；

const int start=A,target=B;		//起始城市为Ared，终止城市为Bucharest 该题中不能修改起始点和目标节点的位置，可在此处修改起点可终点
int sum_cost=0,node_num=0;		//记录代价值
int contral=0;//DFS中只输出一条路线的控制

int contral2=0;
/*深度受限的子函数
    Iterative Deepening
*/
//对深度优先稍加修改，作为迭代加深的深度优先的子函数
void ID_DFS_Romania1(int now_node,stack<int> record,int *flag,int deeps,int now_deep) {
	now_deep++;//记录节点深度
	node_num++;//递归一次，拓展的节点数++;
	if(flag[start]==not_visit)record.push(start);

	flag[now_node]=visited;//节点标记已经访问
	if(now_node!=visited)cout<<"当前拓展节点为："<<city[now_node]<<endl;
	if(now_node==target) { //递归结束条件，当前节点为目标节点时

		int way_num=0;//路段数
		stack<int> road_line; //  辅助栈  逆序record中的路径，实现路径对正序输出
		while(!record.empty()) {
			road_line.push(record.top());
			record.pop();
		}

		cout<<"深度受限的深度优先搜索已找到目标节点，受限深度为 "<<deeps<<" 时，路径如下："<<endl;
		while(!road_line.empty()) { //输出全部的路径
			int temp =road_line.top();
			road_line.pop();
			cout<<city[temp];

			if(temp!=target) { //不是目标节点时输出符号 --(cost)--》
				cout<<"--（"<<Graph[temp][road_line.top()]<<")-->";//将线路的cost打印出来
				sum_cost+=Graph[temp][road_line.top()];//总价值变化+每条路线的cost  注意这里的pop 和top的应用
				way_num++;
			}
		}
		cout<<endl<<"该路径的总消耗为: "<<sum_cost<<'\t'<<"一共经过了"<<way_num<<"个路段"<<endl;
		cout<<"用该搜索算法找到该路径共访问的节点个数为："<<node_num<<"个"<<endl<<endl;

		sum_cost=0,node_num=0;//清零，下一个算法好直接用
		contral2=1; //只输出一条可以到达的路径的控制
		return; //结束
	}

	//未到达目标节点 寻找下一个可拓展的节点，对该节点进行递归
	bool isleaf=true; //递归返回条件
	if(now_deep<=deeps) {// 这里是关键，深度限制由这里实现。
		for(int i=0; i<20; i++) { //搜索当前节点相连的未访问的节点
			if(Graph[now_node][i]!=-1&&flag[i]!=visited) { //能到达且未访问
				isleaf=false;
				flag[i]=visited;//已经加入队列 总会访问 不能再其他节点的子节点加入
				record.push(i);
				ID_DFS_Romania1(i,record,flag,deeps,now_deep);//递归访问下一个节点
				if(contral2==1) return;// 控制只要找到一条路线就返回 该行注释掉会输出所有的路径
				//递归返回时说明
				record.pop();
			}
		}
	}
	if(isleaf==true) {
		now_deep--;
		return;//到达叶子节点时 返回
	}
}
void ID_DFS_Romania(int now_node,stack<int> record,int *flag,int deeps,int now_deep) {
	for(int i=0; i<20; i++) { //最多20层 因为只有20个节点 最开始写成 while（没找到）这里如果目标不存在则会有问题
		ID_DFS_Romania1(now_node,record,flag,deeps,now_deep);
		if(contral2==0) { //找到了
			sum_cost=0;//
			cout<<"迭代加深的深度优先算法：深度限制为 "<<deeps<<"没有成功找到目标节点"<<endl<<endl;
			memset(flag,not_visit,20*sizeof(int));//这里一定记得初始化 否则会少一个节点
			deeps++;
		} else break;
	}
}
int main() {
	init();//初始化
	sum_cost=0,node_num=0;
	stack<int> rec;
	int sign[20];
	memset(sign,not_visit,sizeof(sign));
	ID_DFS_Romania(start,rec,sign,1,1);//
	return 0;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
输出结果：
当前拓展节点为：A
迭代加深的深度优先算法：深度限制为 1没有成功找到目标节点

当前拓展节点为：A
当前拓展节点为：S
当前拓展节点为：T
当前拓展节点为：Z
迭代加深的深度优先算法：深度限制为 2没有成功找到目标节点

当前拓展节点为：A
当前拓展节点为：S
当前拓展节点为：F
当前拓展节点为：O
当前拓展节点为：R
当前拓展节点为：T
当前拓展节点为：L
当前拓展节点为：Z
迭代加深的深度优先算法：深度限制为 3没有成功找到目标节点

当前拓展节点为：A
当前拓展节点为：S
当前拓展节点为：F
深度受限的深度优先搜索已找到目标节点，受限深度为 4 时，路径如下：
A--（140)-->S--（99)-->F--（211)-->B
该路径的总消耗为: 450   一共经过了3个路段
用该搜索算法找到该路径共访问的节点个数为：17个

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26

考虑一致代价搜索

这个搜索方式以及后面的两中方式都涉及到根据某个条件对所有的节点进行排序，这里使用优先队列（priority_queue），便于实现排序：
定义结构体，包含自己的名称，一个键值（排序的根据），一个父节点信息（便于输出路线）；后面的两种算法结构与这里一致，只需要改变键值的赋值。故后面不给出解释，

代码

 struct nod//自定义结构体 便于使用优先队列
 {
     int name;//节点名称 
     int qifa_value;// f值 或 h值 或 g值  在不同的算法里对应不同的值 
     int father;//父节点 
     friend bool operator < (nod a,nod b)//排序的关键值 
      {
        return a.qifa_value>b.qifa_value;
      }
};
nod node[20]; //下面三种式搜索都要用到排序 使用优先队列实现排序 
priority_queue<nod>road;//优先队列
stack<nod> way;

void UCS_Romania(int *flag){
     memset(node,-1,20*sizeof(nod));
     //node[start]={name:start,qifa_value:0,father:-1};//开始节点；距离开始节点长度为0 无父节点
		node[start].name=start;
		node[start].qifa_value=0;
		node[start].father=-1;
     road.push(node[start]); //加入优先队列

		nod temp;
     while(!road.empty()){
         temp=road.top();
		cout<<"当前拓展节点为： "<<city[temp.name]<<" 其子节点有：";
            if(temp.name==target){//目标节点
               int way_num=0;//路段数
                way.push(temp);
        		nod i=temp;
                    while(way.top().name!=start){//将父节点压入站，达到顺序输出的目的，直到栈顶元素是开始节点为止
                            i=node[i.father];// 不要写成temp.father  debug了3个小时
							way.push(i);
                    }
                cout<<endl<<endl<<"一致代价搜索找到目标节点，路径如下："<<endl;
                while(!way.empty()){
                        i=way.top();
                        way.pop();
                        cout<<city[i.name];
                        if(i.name!=target){//不是目标节点时输出符号 --(cost)--》
                        cout<<"--（"<<Graph[i.name][way.top().name]<<")-->";//将线路的cost打印出来
                        sum_cost+=Graph[i.name][way.top().name];//总价值变化+每条路线的cost
                        way_num++;
                        }
                }
                cout<<endl<<"该路径的总消耗为: "<<sum_cost<<'\t'<<"一共经过了"<<way_num<<"个路段"<<endl;
                        cout<<"用该搜索算法找到该路径共访问的节点个数为："<<node_num<<"个"<<endl<<endl;
                        sum_cost=0,node_num=0;//清零，下一个算法好直接用
                break; //输出一条路径后就结束
            }
            node_num++;
            	road.pop();
            flag[temp.name]=visited;
        for(int i=0;i<20;i++){ //不是目标 搜索当前所有的子节点
                if(Graph[temp.name][i]>=0&&flag[i]!=visited){  //能到达且未访问
                		node[i].name=i;
						node[i].qifa_value=Graph[temp.name][i]+temp.qifa_value;//父节点的已花代价+本身代价
						node[i].father=temp.name;
					cout<<city[i];
                   	road.push(node[i]);
                }
     }
		cout<<endl;
 }
 }
 int main() {
	init();//初始化 
	sum_cost=0,node_num=0;
	stack<int> rec;
	int sign[20];
	memset(sign,not_visit,sizeof(sign));
    UCS_Romania(sign);//一致代价搜索 
	return 0;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
一致代价输出结果：
当前拓展节点为： A 其子节点有：STZ
当前拓展节点为： Z 其子节点有：O
当前拓展节点为： T 其子节点有：L
当前拓展节点为： S 其子节点有：FOR
当前拓展节点为： O 其子节点有：
当前拓展节点为： R 其子节点有：CP
当前拓展节点为： L 其子节点有：M
当前拓展节点为： F 其子节点有：B
当前拓展节点为： O 其子节点有：
当前拓展节点为： M 其子节点有：D
当前拓展节点为： P 其子节点有：BC
当前拓展节点为： C 其子节点有：D
当前拓展节点为： D 其子节点有：
当前拓展节点为： B 其子节点有：

一致代价搜索找到目标节点，路径如下：
A--（140)-->S--（80)-->R--（97)-->P--（101)-->B
该路径的总消耗为: 418   一共经过了4个路段
用该搜索算法找到该路径共访问的节点个数为：13个

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19

考虑贪婪优先搜索

键值为到目的地的直线距离（可以自己给出）：也有如下的距离信息：
在这里插入图片描述

贪婪优先代码

该与一直代价策略的不同在于，需要给他提供一些信息，这里是到目标节点的直线距离。所以是有信息的搜索策略。

nod node[20]; //下面三种式搜索都要用到排序 使用优先队列实现排序
priority_queue<nod>road;//优先队列
stack<nod> way;
int h[20] ={366,0,160,242,161,178,77,151,226,244,241,234,380,98,193,253,329,80,199,374 };//直线距离，用于启发式搜索 顺序为表对应的顺序
void GFS_Romania(int *flag) {
	memset(node,-1,20*sizeof(nod));
	//node[start]={name:start,qifa_value:0,father:-1};//开始节点；距离开始节点长度为0 无父节点
	node[start].name=start;
	node[start].qifa_value=h[start];
	node[start].father=-1;
	road.push(node[start]); //加入优先队列

	nod temp;
	while(!road.empty()) {
		temp=road.top();
		cout<<"当前拓展节点为： "<<city[temp.name]<<" 其子节点有：";
		node_num++;
		if(temp.name==target) { //目标节点
			int way_num=0;//路段数
			way.push(temp);
			nod i=temp;
			while(way.top().name!=start) { //将父节点压入站，达到顺序输出的目的，直到栈顶元素是开始节点为止
				i=node[i.father];// 不要写成temp.father  debug了3个小时
				way.push(i);
			}
			cout<<endl<<endl<<"贪婪优先搜索找到目标节点，路径如下："<<endl;
			while(!way.empty()) {
				i=way.top();
				way.pop();
				cout<<city[i.name];
				if(i.name!=target) { //不是目标节点时输出符号 --(cost)--》
					cout<<"--（"<<Graph[i.name][way.top().name]<<")-->";//将线路的cost打印出来
					sum_cost+=Graph[i.name][way.top().name];//总价值变化+每条路线的cost
					way_num++;
				}
			}
			cout<<endl<<"该路径的总消耗为: "<<sum_cost<<'\t'<<"一共经过了"<<way_num<<"个路段"<<endl;
			cout<<"用该搜索算法找到该路径共访问的节点个数为："<<node_num<<"个"<<endl<<endl;
			sum_cost=0,node_num=0;//清零，下一个算法好直接用
			break; //输出一条路径后就结束
		}
		
		road.pop();
		flag[temp.name]=visited;
		for(int i=0; i<20; i++) { //不是目标 搜索当前所有的子节点
			if(Graph[temp.name][i]>=0&&flag[i]!=visited) { //能到达且未访问
				node[i].name=i;
				node[i].qifa_value=h[i];
				node[i].father=temp.name;
				cout<<city[i];
				road.push(node[i]);
			}
		}
		cout<<endl;
	}
}
int main() {
	init();//初始化
	sum_cost=0,node_num=0;
	stack<int> rec;
	int sign[20];
	memset(sign,not_visit,sizeof(sign));
	GFS_Romania(sign);//一致代价搜索
	return 0;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
贪婪优先输出结果：
当前拓展节点为： A 其子节点有：STZ
当前拓展节点为： S 其子节点有：FOR
当前拓展节点为： F 其子节点有：B
当前拓展节点为： B 其子节点有：

贪婪优先搜索找到目标节点，路径如下：
A--（140)-->S--（99)-->F--（211)-->B
该路径的总消耗为: 450   一共经过了3个路段
用该搜索算法找到该路径共访问的节点个数为：4个

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9

考虑A*优先搜索

代码实现与一致代价和贪婪优先相似，只需修改键值为 已花费的cost+直线距离值
注意由于 父节点的key值
每个节点的key值都增加了由其父节点到该节点的cost，故要先减去这个cost，才是从起点到父节点已花费的cost，再加到本节点的直线距离才是key值

代码

nod node[20]; //下面三种式搜索都要用到排序 使用优先队列实现排序
priority_queue<nod>road;//优先队列
stack<nod> way;

void ASS_Romania(int *flag) {
	memset(node,-1,20*sizeof(nod));
	//node[start]={name:start,qifa_value:0,father:-1};//开始节点；距离开始节点长度为0 无父节点
	node[start].name=start;
	node[start].qifa_value=h[start];
	node[start].father=-1;
	road.push(node[start]); //加入优先队列

	nod temp;
	while(!road.empty()) {
		temp=road.top();
		cout<<"当前拓展节点为： "<<city[temp.name]<<" 其子节点有：";
		if(temp.name==target) { //目标节点
			int way_num=0;//路段数
			way.push(temp);
			nod i=temp;
			while(way.top().name!=start) { //将父节点压入站，达到顺序输出的目的，直到栈顶元素是开始节点为止
				i=node[i.father];// 不要写成temp.father  debug了3个小时
				way.push(i);
			}
			cout<<endl<<endl<<"A*搜索找到目标节点，路径如下："<<endl;
			while(!way.empty()) {
				i=way.top();
				way.pop();
				cout<<city[i.name];
				if(i.name!=target) { //不是目标节点时输出符号 --(cost)--》
					cout<<"--（"<<Graph[i.name][way.top().name]<<")-->";//将线路的cost打印出来
					sum_cost+=Graph[i.name][way.top().name];//总价值变化+每条路线的cost
					way_num++;
				}
			}
			cout<<endl<<"该路径的总消耗为: "<<sum_cost<<'\t'<<"一共经过了"<<way_num<<"个路段"<<endl;
			cout<<"用该搜索算法找到该路径共访问的节点个数为："<<node_num<<"个"<<endl<<endl;
			sum_cost=0,node_num=0;//清零，下一个算法好直接用
			break; //输出一条路径后就结束
		}
		node_num++;
		road.pop();
		flag[temp.name]=visited;
		for(int i=0; i<20; i++) { //不是目标 搜索当前所有的子节点
			if(Graph[temp.name][i]>=0&&flag[i]!=visited) { //能到达且未访问
				node[i].name=i;
				node[i].qifa_value=Graph[temp.name][i]+temp.qifa_value+h[i]-h[temp.name];//f=h+g 其中 g=上一个的启发值-上一个的h 
				node[i].father=temp.name;
			//	flag[i]=visited;
				cout<<city[i];
				road.push(node[i]);
			}
		}
		cout<<endl;
	}
}
int main() {
	init();//初始化
	sum_cost=0,node_num=0;
	stack<int> rec;
	int sign[20];
	memset(sign,not_visit,sizeof(sign));
	ASS_Romania(sign);//一致代价搜索
	return 0;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
A*输出结果：
当前拓展节点为： A 其子节点有：STZ
当前拓展节点为： S 其子节点有：FOR
当前拓展节点为： R 其子节点有：CP
当前拓展节点为： P 其子节点有：BC
当前拓展节点为： F 其子节点有：B
当前拓展节点为： B 其子节点有：

A*搜索找到目标节点，路径如下：
A--（140)-->S--（80)-->R--（97)-->P--（101)-->B
该路径的总消耗为: 418   一共经过了4个路段
用该搜索算法找到该路径共访问的节点个数为：5个

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11

性能对比图

在这里插入图片描述

算法为博主手工码出，难免有错误之处，请留言更正!

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/Cpp五条/article/detail/596583
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号