目录

概念

BFS

DFS

DFS-ID

概念

盲目搜索算法指的是不使用领域知识的不知情搜索算法。主要包括三种算法：深度优先搜索（DFS）、广度优先搜索（BFS）和迭代加深（DFS-ID）的深度优先搜索。

当树很深、分支因子不大、在树中解出现的位置相对较深时，选择深度优先搜索。

当搜索树的分支因子不太大、在树中解出现的位置在合理的深度级别、路径不是非常深的时候，选择广度优先搜索。

在深度优先和广度优先的基础上，结合二者形成了一种全新的算法：迭代加深的深度优先

PS： 简单的说就是不断扩大搜索深度的深度优先。

使用DFS-ID若没有找到目标，就会执行另一个DFS，深度界限为1，每次迭代深度界限加1，搜索都要重新开始。

BFS是完备和优选的（在各种约束下），但过量的空间需求使其在应用上受到阻碍。

DFS既不是完备也不是优选的，DFS可能变得非常长或迷失在无限的路径中，但是空间需求合理。

DFS-ID同时具备DFS和BFS的有利性，即DFS的合理空间以及BFS的完备和优选，但是每次深度更新都需要把之前探索过的路径重新探索一遍，会存在非常大的时间浪费。

BFS

思路

BFS和DFS都需要准备一个close 标志，表示哪些点已经走过了，不需要再走了，也叫visit 图。

BFS 的基本逻辑就是，遍历周边的4个点，然后把4个点都放在队列里，然后出队首，重新把新的节点的周围4个点放进去，直到遍历到结束点。

代码

#define MaxSize 1000// 边节点
typedef struct ANode
{// 边所指的终点顶点int adjvex;// 下一条边，邻域，指向下一个邻接点struct ANode * nextarc;// 权值int weight;
}ArcNode;// 顶点
typedef struct Vnode
{// 数据域int data;	// 指向的第一条边ArcNode * firstarc;
}VNode;// 邻接表
typedef struct
{VNode adjlist[MaxSize];// n为顶点数，e为边数int n;int e;	
}Graph;// G为邻接点指针，V为初始访问节点
void BFS(Graph * G, int v)
{// 边节点ArcNode * p;// 访问数组int visited[MaxSize];// 队列int Qu[MaxSize];// 初始化循环队列int front = 0, rear = -1;// 当前节点的下标int w;// 初始化访问数组for(int i = 0; i < G->n; i++){visited[i] = 0;}// 访问第一个节点printf("%d\n", v);visited[v] = 1;// 第一个节点入队rear = (rear + 1) % MaxSize;Qu[rear] = v;// 开始广度优先遍历while(front != rear){front = (front + 1) / MaxSize;// 出队w = Qu[front];// 使p指向顶点的第一个边节点p = G->adjlist[w].firstarc;// 循环访问完w的所有边节点while(p != NULL){if(visited[p->adjvex] == 0){// 访问节点printf("%d\n", p->adjvex);visited[p->adjvex] = 1;// 入队rear = (rear + 1) % MaxSize;Qu[rear] = p->adjvex;}p = p -> nextarc;}}}

DFS

思路

深度优先算法的核心是栈，就是说把一个点周围4个节点先放在栈里，然后出栈顶，重新把周围的4个节点放在栈里，直到找到结束点。

代码

//利用C++实现深度优先搜索算法，如有疑问请联系
//作者：cclplus 邮箱：maxwell970710@gmail.com
#include
#include
#include
#includeusing namespace std;vector> tree;//声明一个二维向量
int flag[10];//用于搜索到了节点i的第几个节点
stack stk;//声明一个堆栈
int ar_tree[8] = { 1,1,1,3,5,3,5,7 };
void DFS(int node) {cout << node <<" ";if (flag[node] == 0) {stk.push(node);}int temp;//判断node的子节点是否搜索完成if (flag[node] < tree[node].size()) {temp = tree[node][flag[node]];flag[node]++;DFS(temp);}else {//若已经完成stk.pop();//弹出子节点if (!stk.empty()) {//若堆栈不为空temp = stk.top();//取此时的栈顶元素，即为node的上一级节点DFS(temp);}}
}
int main() {ios::sync_with_stdio(false);memset(flag, 0, sizeof(flag));register int i,temp;tree.resize(10);//图中的数共有九个节点//生成树for (i = 2; i <=9; i++) {temp = ar_tree[i - 2];tree[temp].push_back(i);//表示第i个节点为第temp个节点的子节点}//DFScout << "DFS过程：" << endl;DFS(1);cout << endl;return 0;
}

DFS-ID

思路

所谓深度迭代，就是设置一个深度tag，一旦超过该深度就不再将新节点入栈，如果没有找到结束节点就深度tag++，然后重来一遍。

代码

bool DLS(GrapheMat* graphe, Node* source, NomSom but, int limit) {bool found = false;printf("%s\n", (char*)source->etat);if (strcmp((char*)source->etat, (char*)but) == 0) {return true;}if (limit > 0) {List* listSon = nodeSon(graphe, source);while(!listEpmty(listSon)) {Node* son = (Node*)popList(listSon);if (DLS(graphe, son, but, limit-1)) {return true;}}}return false;
}bool IDDLS (GrapheMat* graphe, NomSom goal, int limit) {bool found = false;node* source = createNode(graphe, graphe->nomS[0]);for (int i = 0; i <= limit; i++) {printf("/nLimit : %d\n", i);DLS(graphe, source, goal, i);}return false;
}