我们在解决图问题的时候，通常需要使用DFS和BFS搜索，可是这两种搜索方式的效率较低，我们会遍历到很多空白节点，有没有办法可以优化这种低效问题呢？今天要推出我们的主角：启发式搜索。
一、A*
什么是A*算法？
A* 算法是一种路径搜索算法，用于在图形（如地图）中寻找最短路径。A* 算法基于启发式搜索和贪心搜索的思想，通过估计从起始点到目标点的距离来选择下一步移动。它综合考虑了已走过的路径长度（即实际代价）和估计的剩余路径长度（即启发代价），找到从起始点到目标点的最佳路径。
A*算法使用一个开放列表和一个关闭列表来追踪已探索的节点。它通过计算每个节点的“f值”来确定下一步移动。f值等于从起始点到当前节点的实际代价（即已走过的路径长度）加上从当前节点到目标点的估计代价（即剩余路径长度）。
A*算法在每一步中选择f值最小的节点来移动。当找到目标点或遍历完所有可能的节点时，算法停止。如果找到目标点，路径会被重构，即从目标点沿父节点指针一直回溯到起始点。这样就找到了从起始点到目标点的最短路径。
A*算法在寻找路径问题中被广泛应用，例如在游戏中的AI路径规划、地图导航和机器人路径规划等。它具有较高的效率和准确性，并且可以根据需要进行优化和改进。
在A* 算法中，我们需要构建一个估价函数，简单来说，A*算法就是BFS+优先队列+估价函数
估价函数：
f
(
i
)
=
g
(
i
)
+
h
(
i
)
\ f(i) = g(i) + h(i)
f(i)=g(i)+h(i) 其中g(i)是Dijkstra算法计算的当前i点离起点的最短路径，h(i)是用贪心算法预估当前i点到达终点需要的最短路径，但这里的预测不一定准确，在寻路时碰壁可以回溯到之前节点，重新寻找其他节点
如何设计h函数? (1)曼哈顿距离：只能在四个方向（上下左右）移动
h
(
i
)
=
a
b
s
(
i
.
x
−
t
.
x
)
+
a
b
s
(
i
.
y
−
t
.
y
)
h(i) = abs(i.x - t.x) + abs(i.y - t.y)
h(i)=abs(i.x−t.x)+abs(i.y−t.y) (2)对角线距离：只能在八个方向移动
h
(
i
)
=
m
a
x
(
a
b
s
(
i
.
x
−
t
.
x
)
,
a
b
s
(
i
.
y
−
t
.
y
)
)
h(i) = max(abs(i.x - t.x),abs(i.y - t.y))
h(i)=max(abs(i.x−t.x),abs(i.y−t.y)) (3)欧几里得距离：可以向任何方向移动
h
(
i
)
=
s
q
r
t
(
(
i
.
x
−
t
.
x
)
2
+
(
i
.
y
−
t
.
y
)
2
)
h(i) = sqrt((i.x - t.x)^2 + (i.y - t.y)^2)
h(i)=sqrt((i.x−t.x)2+(i.y−t.y)2)
二、IDDFS
IDDFS（Iterative Deepening Depth-First Search）是一种启发式搜索算法，可用于在图或树上进行深度优先搜索（DFS）。
IDDFS结合了迭代深化和深度优先搜索的特点。它的基本思想是进行一系列深度限制的DFS，从深度为1开始，逐渐增加深度直到找到目标节点或遍历完整个图或树。
IDDFS的过程如下：
以深度为1开始，执行DFS搜索，探索从起始节点出发的深度为1的路径。如果在深度为1的搜索中找到目标节点，搜索结束，返回结果。如果在深度为1的搜索中没有找到目标节点，增加深度限制，将深度限制设为2，然后重复步骤1和2。不断增加深度限制并重复步骤1和2，直到找到目标节点或遍历完整个图或树。
IDDFS的优点是可以控制搜索深度，避免无限循环或过度搜索的问题。它对于搜索空间较大且没有完整的启发式信息时非常有用。然而，IDDFS的时间复杂度较高，可能需要重复许多次深度受限的DFS搜索。
总结起来，IDDFS是一种可以在深度优先搜索中控制搜索深度的算法，适用于在没有完整启发式信息的情况下搜索图或树结构。
三、IDA*
IDA* 是结合A*与IDDFS的算法，即有估价函数的IDDFS，效率很高
下面给出一道IDA*的例题
#include
#include
const int N = 100;//设置最大层次
int num[N];//记录某一条路径上的数字,num[i]即该路径的第i个节点
int n, depth;
bool dfs(int now,int d){//now为当前路径走到的数字，d为now所在的层数
if(d > depth)
return false;
if(now == n)
return true;
if(now << (depth - d) < n)//预估函数,如果最乐观的倍增法都无法在剩余可走层数到达最后结果，直接剪枝
return false;
num[d] = now;
for (int i = 0; i <= d; i++){//继续下一层
if(dfs(now + num[i], d + 1))
return true;//加
else if(dfs(now - num[i],d + 1))
return true;
}
return false;
}
int main(){
while(~scanf("%d",&n) && n != 0){
for (depth = 0;; depth++){//IDDFS
memset(num, 0, sizeof(num));
if(dfs(1,0)){
break;
}
}
printf("%d\n", depth);
}
return 0;
}
精彩链接
发表评论