A*寻路算法

最近需要解决一个寻路问题，在知道起始坐标和终止坐标的前提下找到能够避开障碍物的最优正交路径，要求路线总长尽量短同时避免线路弯折，算是一种Manhattan Layout，类似于EDA软件中的自动布线。最终采用了A*寻路算法(A-star algorithm)。这里简要记录一下原理。

A*算法

A*算法是一种启发式算法(Heuristic Algorithm)。相比于传统DFS、BFS之类的盲目搜索，A*算法能够通过启发函数引导搜索从而缩小搜索范围降低问题复杂度。在对节点的遍历过程中采用启发值优先原则，启发值更优的节点会被优先遍历。

算法描述

首先定义一个启发函数, ，其中表示预估损失，即从当前状态x到达成目标的预计损失。表示起始状态到当前状态x已经花费的代价。

从和的定义可以看出：

当时就是一个等代价搜索，完全依据当前花费的代价做决策，例如BFS和Dijkstra算法。

当时就相当于贪心算法，每次都朝着预估代价最小的状态靠近。

这里对有一个限制，要求，不大于x到目标的最优代价。

然后是具体步骤

1、Build empty OPEN and CLOSE list and insert start point into OPEN list
2、
while (OPEN not empty) {
    pop vertex x from OPEN which has the minimum H(x);

    if (x == target) {
        break;
    }
        
    for (each neighbour nx of n which is accessible) {
        calculate H(nx);

        if (nx in OPEN) {
            if (new H(nx) < H(nx) from OPEN) {
                make x the parent of nx;
                update H(nx) in OPEN;
            }
        }
            
        if (nx in CLOSE) {
            continue;
        }
            
        if (nx in neither OPEN nor CLOSE) {
            make x the parent of nx;
            calculate H(nx);
            insert nx into OPEN; 
        }
    } // end for

    insert x into CLOSE;
    sort OPEN based on H(x);
} // end while

3、reconstruct route from target based on parent pointer

实际应用

本例中设计的启发函数如下：

预估损失，其中为当前节点到目标节点的Manhattan Distance，为Penalty Function

P(x) = 0 when next bending direction is straight
       step / 2 when current bending direction is different from the previous bending direction 
       step when current bending direction is the same as the previous bending direction

这里step表示每次移动一步的相距其父节点的距离。bending direction即线路弯折的方向，有向前直走、向左和向右三种。因为要求尽量避免弯折，因此若向前直行即straight时不用受惩罚。如果拐弯的话，因为本例都是拐直角弯，如果连续两次向相同的方向拐弯，比如连续两次向左拐，那么最后的方向与两次拐弯前的方向是相反的，即走了回头路，那肯定要给一个较大的penalty；如果两次方向相反则给一个较小的penalty。

这样就定义完了。就比较简单了，直接设定成起始点到当前位置的路径的总长。Open列表可以考虑采用Priority Queue

---

本文章使用limfx的vscode插件快速发布