[PR] LRTA* 搜索算法

一、理论

1、基础：A*

LRTA算法是A算法的进一步改进方法，所以在介绍LRTA前要先简单介绍下A算法 详细介绍请点这里

A*算法的核心是其 判断公式 $f(n)=g(n)+h(n)$， 其中 $g(n)$ 代表当前节点到初始节点的距离， $h(n)$ 代表当前节点到目标节点的距离。

2、进阶：LRTA*

(1)、关键理解：h(n)

跟A类似，LRTA搜索算法的核心公式也是 $f(n)=g(n)+h(n)$，不同之处在于，$g(n)$表示从上一节点到现在节点的距离， $h(n)$ 表示从当前节点到目标节点的距离，同时 $h(n)$ 是会根据该节点访问次数的增加而增加。

$h(n)$ 这样的设计，是为了防止之前A算法在搜索时陷入局部最小值，在LRTA搜索中，如果陷入了局部最小值，算法会根据访问附近节点的次数增加h(n)，即增加总成本f(n)，从而经过h(n)的多次叠加后，跳出局部最小值。

关于h(n)的解释，原论文是这么说的：

h(n) is a heuristic value stored with node n the last time it was visited by LRTA*.

h(n) 的更新是这样的：

例如从 n 节点到 n’ 节点，假设路程g(n, n’) = 1，已知 h(n’) = 2（这个初始的时候就是已知的，代表了从该节点到目标节点的距离），那么从 n 节点访问 n’ 节点后，是对n节点的h(n)进行更新的，h(n) = g(n) + h(n’) = 1 + 2 = 3。

另外，如果想从 n’ 再回到 n节点的话，那么就要对 h(n’) 更新，h(n’) = g(n’, n) + h(n) = 1 + 3 = 4。

该算法的精髓就在 h(n) 的更新上，理解了 h(n) 的更新，LRTA*算法就基本理解了。下面做两个例题练练手

二、简单例子练练手

来自《人工智能：一种现代的方法》第4.5.3节

初始如 (a) 所示，灰色代表当前所处位置，方便起见我用红色为每个节点标注了序号。

f 表示总代价，g(1, 2) 表示节点1和节点2之间的路程代价，h(0)=8表示0节点到达目标节点的代价为8

• 第一次更新：
  当前位置 在 2号节点时
  向左移动的话，代价 f = g(1, 2) + h(1) = 1+9 = 10
  向右移动的话，代价 f = g(2, 3) + h(3) = 1+2 = 3
  所以向总代价更小的右侧移动到节点3，同时要更新h(2) = h(3) + g(2, 3) = 2 + 1 = 3

• 第二次更新：
  当前位置 在 3号节点时
  向左移动的话，代价 f = g(2, 3) + h(2) = 1+3 = 4
  向右移动的话，代价 f = g(3, 4) + h(4) = 1+4 = 5
  所以向总代价更小的左侧移动到节点2， 同时更新h(3) = h(2) + g(2, 3) = 3+1 = 4

• 第三次更新：
  当前位置 在 2 号节点时
  向左移动的话，代价 f = g(1， 2) + h(1) = 1+9 = 10
  向右移动的话，代价 f = g(2， 3) + h(3) = 1+4 = 5
  所以向总代价更小的右侧移动到节点3， 同时更新h(2) = h(3) + g(2, 3) = 4+1 = 5

• 第四次更新：
  当前位置 在 3 号节点时
  向左移动的话，代价 f = g(2， 3) + h(2) = 1+5 = 6
  向右移动的话，代价 f = g(3， 4) + h(4) = 1+4 = 5
  所以向总代价更小的右侧移动到节点4， 同时更新h(3) = h(4) + g(3， 4) = 4+1 = 5

这样就跳出了局部最小值！