**
简介
**个人感觉，算是数据结构的内容不算是人工智能的范围，但不管怎么说这几种算法确实是最基本的算法了，且先不去管这属不属于AI（在蔡自兴的《人工智能及其应用》中在搜索策略中详细介绍了这几种算法的思想）只是尽量去做吧！
班主任讲这节课的时候只是理解了搜索是怎样概念，可当他让我们做这个作业时我还是慌了神，因为我还是一个学习编程半年多的菜鸡，而且当时的数据结构还没有讲图，所以我就更懵了，实在是想不明白他是怎么把这个图搞到计算机里边去的…
然后经过一星期的苦思冥想，终于在交作业的前一晚搞定了宽度优先，说起来都是泪啊！写这篇博文是想帮助广大的像我一样刚刚学完编程的基本而不知道怎么进一步运用的童鞋们(这几个简单的算法想了半个多月)，希望对你的学习有所帮助吧！
有任何问题欢迎留言提问，我们一起学习，一起进步（而且我感觉我的贪婪优先有问题，希望明白的大佬能教教我）
因为我一开始也不明白，就是参考的网上搜的文档，自己实现的时候感觉逻辑上没有问题，但结果就是不一样（后来发现，从最后一个号节点开始遍历的结果与网上的文档结果相同就保留了如下图所示）
如果有哪位大佬看到了也麻烦能教我一下
感谢中国地质大学赵曼老师弄的这个课程设计（我班主任直接从网上搜的这个地大的设计报告…）
**
预备知识
**
因为期望的主要读者是像我这样的编程小白，所以先提前说一下里边用到的东西
1.邻接矩阵，数据结构，图这一章会详细的讲（当时真的是非常困扰我，不过看懂了第一次就好了）拿罗马尼亚度假问题为例，有20个城市，所以可以用一个20*20的矩阵表示这个图，如果计这个矩阵为｛aij｝20**20那么每一个位置的值表示从城市i到城市j的距离，所以对角线元素都是0（从自己到自己）对于图中不连接的城市，将邻接矩阵中的值设置为1000（这里设置为1000，通常为无穷大），也就是说如果这个位置的值为1000，那么这两个城市不相邻，那么寻找某个城市的后继结点就简单了，只要遍历邻接矩阵的这一行，找到元素在0~1000之间的，即为后继结点
2.栈，可以用数组或者链表实现，其操作特性是先进后出，可以百度一下有很详细的介绍
3.队列，这里用的是循环队列，操作特性是后进先出，这里也不在赘述了
可直接用百度云盘下载源文件及头文件
源文件和头文件下边
源文件和头文件***在这***：[提取码 li7c]
(https://pan.baidu.com/s/10UBbYA_H60EcVRnZ91Q7sA)
源文件和头文件上边
运行结果如图（个别地方与网上的地大的运行结果不一样，也请大神能指教我一下）：
#include<iostream>
#include<string.h>
#include<time.h>
#include"罗马尼亚度假问题专用.h"
#include"我的栈和队列.h"
using namespace std;
const int End = 2;
//设置城市，包含名称和启发式函数值
struct City
{
char name[20];
int F; //有信息搜索用到
};
//图，用邻接矩阵保存图内容
class Graph
{
public:
Graph();
//private:
City city[20];
int graph[20][20];
};
Graph::Graph()// 赋值
{
int i, j;
for (i = 0; i < 20; i++)
{
for (j = 0; j < 20; j++)
{
graph[i][j] = g[i][j];
}
strcpy_s(city[i].name, 20, name_[i]);
city[i].F = Founation[i];
}
}
void Print(int *father,int count)
{
Graph G;
int cost = 0;
int Road[20];
int x = End;
int i = 0;
while (1)
{
cost += G.graph[x][father[x]];
Road[i] = x;
i++;
x = father[x];
if (x == 0)
{
Road[i] = x;
break;
}
}
for (; i > 0; i--)
{
cout << G.city[Road[i]].name << "->";
}
cout << "Bucharest" << endl << endl;
cout << "访问节点数：" << count << endl;
cout << "访问路径总长度：" << cost << endl;
return;
}
/*宽度优先算法*/
void BFS()
{
long long int time1 = clock();
long long int time2;
int count = 0;
Graph G;//建立一个图
int father[20] = { 0 };//记录每个城市的“父节点”的位置
bool seek[20] = { false };// 记录此节点是否访问过，访问过就设置成true
CirQueue<int> OpenList; //Open表，保存将要访问的节点
/*将初始点Arad所在的位置“0”压入队列*/
OpenList.EnQueue(0);
seek[0] = true;
int n = 0;
while (OpenList.Empty())//只要队列里还有元素就继续访问
{
int x = OpenList.DeQueue();
count++;
//cout << "#" << "第：" << ++n << "次：" << G.city[x].name << endl;//可在调试程序时运行，显示访问的各节点
if (x == End)//找到了Bucharest
break;
for (int i = 0; i < 20; i++)//寻找x的后继结点
{
if (G.graph[x][i] > 0 && G.graph[x][i] < 1000 && seek[i]==false)//如果i号城市是x的后继结点并且没被访问过
{
OpenList.EnQueue(i);//将其添加入队尾
father[i] = x; //标记i号城市的“父节点”是城市x
seek[i] = true; //i已经访问过，以后不再访问了
}
}
}
//------打印---------
/*这里用栈来打印应该是比较好，大家可以改进一下*/
int cost=0;
int Road[20];//顺序保存从Arad到Bucharest的访问路径
int x = End;
int i = 0;
while (1)
{
cost += G.graph[x][father[x]];
Road[i] = x;
i++;
x = father[x];//找x的父节点，并将其保存到Road中
if (x == 0)//找到头了
{
Road[i] = x;
break;
}
}
time2 = clock();
cout << "————————宽度优先算法————————" << endl;
for (; i >0; i--)//打印出来即可
{
cout << G.city[Road[i]].name << "->";
}
cout << "Bucharest"<<endl;
cout << "访问节点数：" << count << endl;
cout << "访问路径总长度：" << cost<<endl;
cout << "耗时：" << time2 - time1 << "ms" << endl<<endl;
return;
}
//————————深度优先算法————————
/*与宽度优先差不多，只不过这里用栈储存
后入栈的节点先出栈访问，标记重复位置的数组用二维，表示从i位置到j位置是否被访问过*/
void DFS()
{
long long int time1,time2;
time1 = clock();
int count = 0;
Graph G;
int father[20] = { 0 };
bool From_to[20][20] = { false };
SeqStack<int> OpenList;
OpenList.Push(0);
int n = 0;
From_to[0][0] = false;
while (OpenList.Empty())
{
int x = OpenList.Pop();
count++;
//cout << "#" << "第：" << ++n << "次：" << G.city[x].name << endl;
if (x == End)
break;
for (int i =19; i >=0; i--)
{
if (G.graph[x][i] > 0 && G.graph[x][i] < 1000 && From_to[x][i]== false)
{
OpenList.Push(i);
father[i] = x;
From_to[x][i]= true;
From_to[i][x] = true;
}
}
}
time2 = clock();
cout << "————————深度优先算法————————" << endl;
Print(father, count);
cout << "耗时：" << time2 - time1 << "ms" << endl<<endl;
return;
}
//---------UCS-等代价搜索------------
/*等代价算是是宽度搜索的升级版
每次选择下一个访问的节点以前要将队列中的元素按照从小到大排列
队头元素就是当前访问花费最少的*/
struct Data//存放城市的位置和花费
{
int location;
int cost;//花费是迭代的即从初始位置到该为置的每条道路的花费之和
};
void Initialize(Data *x,int location,int c)//将位置，和花费保存在结构体变量x中
{
x->location = location;
x->cost = c;
}
void arrang(CirQueue<Data>* P)//将队列中的元素按照花费从小到大排列，队头元素即为花费最少的
{
for (int i=(P->front+1)%Size;i<=P->rear;i++)//冒泡排序（因为这里用的是循环队列，所以front的下一个位置是front+1%Size）
{
for (int j = (P->front + 1) % Size; j<P->rear; j++)
{
if (P->data[j].cost > P->data[j+1].cost)
{
Data t = P->data[j];
P->data[j] = P->data[j + 1];
P->data[j + 1] = t;
}
}
}
}
void UCS()
{
long long int time1, time2;
time1 = clock();
int count = 0;
Graph G;
int father[20] = { 0 };
bool seek[20] = { false };
CirQueue<Data> OpenList;
Data X; Initialize(&X, 0, 0);
OpenList.EnQueue(X);
seek[0] = true; int y = 0;
while (OpenList.Empty())
{
arrang(&OpenList);//访问之前先调用这个函数将队列重排
Data x = OpenList.DeQueue();
count++;
//cout << "#" << ++y << "次：" << G.city[x.location].name <<" 代价："<<x.cost<< endl;
if (x.location == End)
break;
for (int i = 0; i < 20; i++)
{
if (G.graph[x.location][i] > 0 && G.graph[x.location][i] < 1000 && seek[i] == false)
{
Data I; Initialize(&I, i, x.cost + G.graph[x.location][i]);// x.cost + G.graph[x.location][i]，花费是迭代的
OpenList.EnQueue(I);
father[i] = x.location;
seek[i] = true;
}
}
}
//------打印---------
int cost = 0;
int Road[20];
int x = End;
int i = 0;
while (1)
{
cost += G.graph[x][father[x]];
Road[i] = x;
i++;
x = father[x];
if (x == 0)
{
Road[i] = x;
break;
}
}
time2 = clock();
cout << "————————UCS-等代价搜索————————" << endl;
Print(father, count);
cout << "耗时：" << time2 - time1 << "ms" << endl<<endl;
return;
}
//-------------IDS-迭代加深搜索--------------
/*设置最大访问层数，每次访问的节点的层数必须小于当前的最大层数，如果
在当前的最大层数没访问到目标节点最大层数就加一，再搜索*/
int Get_layer(int *f,int x)//找位置x的层数
{
int n = 0;
for (int i = x; x != 0; x = f[x])//找父节点，再找父节点的父节点......
{
n++;
}
return n;
}
void IDS()
{
long long int time1, time2;
time1 = clock();
int count_,count = 0;
int layer = 1;//最大层数
Graph G;
SeqStack<int> OpenList;
int father[20] = { 0 }; int t = 0;
while (layer<20)//设置最大层数
{
int fathe[20] = { 0 };
bool From_to[20][20] = { false };
OpenList.Push(0);
int n = 0;
count_ = 0;
while (OpenList.Empty())
{
int x = OpenList.Pop();
count++; count_++;
//cout << "#" <<"layer等于"<<layer<<"时--"<< "第：" << ++n << "次：" << G.city[x].name << endl;
if (x == End)
{
t = 1;//找到就退出这两个循环
break;
}
for (int i = 19; i >= 0; i--)
{
if (Get_layer(fathe, x) >= layer)//判断是否达到最大层数
break;
if (G.graph[x][i] > 0 && G.graph[x][i] < 1000 && From_to[x][i] == false)
{
OpenList.Push(i);
fathe[i] = x;
From_to[x][i] = true;
From_to[i][x] = true;
}
}
}
for (int e = 0; e < 20; e++)//father是最终用于打印的数组
{
father[e] = fathe[e];
}
if (t == 1)
break;
layer++;//说明在刚才的层数下没找到，所以最大层数加一，再重新循环
}
cout << "————————IDS-迭代加深搜索————————" << endl;
time2 = clock();
Print(father, count);
cout << "最终层数：" << layer << " 下访问节点数:" << count_ << endl;
cout << "耗时：" << time2 - time1 << "ms" << endl<<endl;
return;
}
//------------A算法--有信息搜索------------
/*与等代价搜索类似，只不过是排序的参数发生了变化，仅使用启发式函数值*/
void A()
{
long long int time1, time2;
time1 = clock();
int count = 0;
Graph G;
int father[20] = { 0 };
bool seek[20] = { false };
CirQueue<Data> OpenList;
Data X; Initialize(&X, 0, G.city[0].F);
OpenList.EnQueue(X);
seek[0] = true; int y = 0;
while (OpenList.Empty())
{
arrang(&OpenList);
Data x = OpenList.DeQueue();
count++;
//cout << "#" << ++y << "次：" << G.city[x.location].name <<" F:"<<x.cost<< endl;
if (x.location == End)
break;
for (int i = 0; i < 20; i++)
{
if (G.graph[x.location][i] > 0 && G.graph[x.location][i] < 1000 && seek[i] == false)
{
Data I; Initialize(&I, i,G.city[i].F);
OpenList.EnQueue(I);
father[i] = x.location;
seek[i] = true;
}
}
}
time2 = clock();
cout << "————————A算法--有信息搜索————————" << endl;
Print(father, count);
cout << "耗时：" << time2 - time1 << "ms" << endl<<endl;
return;
}
//------------A*算法-----------
/*A算法的升级版，同时使用启发式函数值和每条路程的代价，同时A*算法是静态搜索的最优算法*/
void A_()
{
long long int time1, time2;
time1 = clock();
int count=0;
Graph G;
int father[20] = { 0 };
bool seek[20] = { false };
CirQueue<Data> OpenList;
Data X; Initialize(&X, 0, G.city[0].F+0);
OpenList.EnQueue(X);
seek[0] = true; int y = 0;
while (OpenList.Empty())
{
arrang(&OpenList);
Data x = OpenList.DeQueue();
count++;
//cout << "#" << ++y << "次：" << G.city[x.location].name << " F:" << x.cost << endl;
if (x.location == End)
break;
for (int i = 0; i < 20; i++)
{
if (G.graph[x.location][i] > 0 && G.graph[x.location][i] < 1000 && seek[i] == false)
{
Data I; Initialize(&I, i, G.graph[x.location][i]+G.city[i].F);
OpenList.EnQueue(I);
father[i] = x.location;
seek[i] = true;
}
}
}
time2 = clock();
cout << "————————A*算法————————" << endl;
Print(father, count);
cout << "耗时：" << time2 - time1 << "ms" << endl<<endl;
return;
}
//————————贪婪优先————————
/*（其实我也不太理解）百度是说每一步只是找当前的最优解，不考虑全局
所以，这里搜索初始节点的后继结点，（直接相邻的有三个）所以可以先探索cost最小的一个
在探索最小的后面的最小的，依次循环，直到找到目标节点
（这样搜索的后果是有可能找不到解！！）
*/
void arr(CirQueue<int> *p,int x)//将Openlist里的元素按照cost的大小排列
{
Graph G;
for (int i = (p->front + 1)%Size; i <= p->rear; i++)
{
for (int j = (p->front + 1) % Size; j < p->rear; j++)
{
if (G.graph[x][p->data[j]] > G.graph[x][p->data[j+1]])
{
int t = p->data[j];
p->data[j] = p->data[j + 1];
p->data[j + 1] = t;
}
}
}
}
int Seek(int x,int seek[][20])//找到城市x的cost最小的后继结点，并且做标记
{
Graph G;
int min,n=0;
int a[20];
int count = 0;
for (int i = 0; i < 20; i++)
{
if (G.graph[x][i] > 0 && G.graph[x][i] < 1000 && seek[x][i] == false)
{
count++;
a[n] = i;
n++;
seek[x][i] = true;
seek[i][x] = true;
}
}
min = a[0];
for (int i = 0; i < n; i++)//找最小
{
if (G.graph[x][a[i]] < G.graph[x][min])
{
min = a[i];
}
}
if (count == 0)//如果没有后继结点，返回0
return 0;
return min;
}
void Best()
{
long long int time1, time2;
int count = 0;
time1 = clock();
Graph G;
int father[20] = { 0 };
int seek[20][20] = { false };
CirQueue<int> Openlist;
for (int i = 0; i < 20; i++)
{
if (G.graph[0][i] > 0 && G.graph[0][i] < 1000 && seek[0][i] == false)
{
Openlist.EnQueue(i);
seek[0][i] = true;
seek[i][0] = true;
father[i] = 0;
}
}
arr(&Openlist, 0);
int rz = 0;
while (Openlist.Empty())//Openlist里边存放了直接与初始节点相邻的三个节点
{
int x = Openlist.DeQueue();
int t;
while (t=Seek(x,seek),t!=0)//只要x有未探索过的后继结点就循环
{
if (x == End)
{
break;
rz++;
}
count++;
father[t] = x;
x = t;
}
if (rz != 0)
{
break;
}
}
time2 = clock();
cout << "————————Best_Frist-贪婪优先算法————————" << endl;
Print(father, count);
cout << "耗时：" << time2 - time1 << "ms" << endl << endl;
return;
}
int main(void)
{
BFS();
DFS();
UCS();
IDS();
A();
A_();
Best();
cout << "输入任意键以继续......";
getchar();
}
具体解释都注释在代码里了，如果还不明白（其实明白了宽度优先或者广度优先就好明白了）就将就着看一下下边几张图片吧，可以当动态图看（本来想弄成gif，，可惜能力有限，将就看吧）
（这其实是我班主任PPT上的（由于设计版权问题只能帮到这了【手动捂脸】）
广度与深度优先遍历的不同主要就在于后来遍历到的节点是先访问还是后访问，先访问(后来的节点)就是深度优先，后访问(后来的)就是宽度优先
如果发现程序有问题也欢迎留言交流，谢谢支持。
最后附带中国地质大学的课程设计报告下载链接提取码：b8ev