写在前面

A*算法之所以有可变性与其启发函数有密不可分的关系，启发函数可以决定算法在搜索的时候的搜索方式，那么今天就来比较一下不同启发函数（搜索方式）对于算法表现的影响。

绿色：待搜索节点；
浅灰色：搜索过程中的最小Fn数值点；
红色：起点；
绿色：终点；
黄色：最终的生成路径；
黑色：障碍物（不可走坐标）；

下面在做算法演示的时候我还是保留了一个障碍物，也是为了保证算法运行的完整性。

对比

首先以曼哈顿距离（Manhattan_Distance）为例，搜索方式如下所示：

从图示中可以看出，这种方法在搜索的时候只能往上下左右进行，那么用了这种方法的时候算法表现如何呢？一起来看看。

算法测试方式：

#define Manhattan_Distance  0
//#define Euclidean_Distance  1

const int env_nums = 4;
int offset_x[4] = {0, 1, 0, -1};
int offset_y[4] = {-1, 0, 1, 0};

for (int i = 0; i < env_nums; i++) {
    Point* search_p = new Point((*p).x + offset_x[i], (*p).y + offset_y[i]);
}

int A_star::calcu_cost(const Point& p1, const Point& p2)
{
    int dx = abs(p1.x - p2.x);
    int    dy = abs(p1.y - p2.y);
    int cost = 0;
    calcu_type_selection(cost, dx, dy);
    return cost;
}

int A_star::calcu_Hn(const Point& p1)
{
    int dx = abs(p1.x - end.x);
    int    dy = abs(p1.y - end.y);
    int Hn = 0;
    calcu_type_selection(Hn, dx, dy);
    return Hn;
}

void A_star::calcu_type_selection(int& data, const int& dx1, const int& dy1) {
    #ifdef Manhattan_Distance
        data = plane_cost * (dx1 + dy1);
    #elif Euclidean_Distance
        data = plane_cost * sqrt(dx1 * dx1 + dy1 * dy1);
    #endif
}

可以看到在这种启发函数的条件下，搜索效率（灰色+绿色方块都是搜索过的路径）特别低，几乎把整张地图都搜索了一遍才找到路径，而且找到的路径也不是最优路径。

接下来我们来看看欧几里得距离（Euclidean_Distance），这种启发函数的行走方式如图所示：

如图所示，这种启发函数的前进方向是上下左右，左上，左下，右上，右下这8个方向，那么这种启发函数最终会如何影响算法呢？如下图所示：

可以看到欧几里的启发函数作用下，算法的表现发生了极大的改善，不但搜索路径（灰色+绿色方块）变少了，而且得到的最终路径也比之前那个更好了。

算法测试方式：

//#define Manhattan_Distance  0
#define Euclidean_Distance  1

const int env_nums = 8;
int offset_x[8] = {-1, 0, 1, 1, 1, 0, -1, -1};
int offset_y[8] = { -1, -1, -1, 0, 1, 1, 1, 0};

for (int i = 0; i < env_nums; i++) {
    Point* search_p = new Point((*p).x + offset_x[i], (*p).y + offset_y[i]);
}

int A_star::calcu_cost(const Point& p1, const Point& p2)
{
    int dx = abs(p1.x - p2.x);
    int    dy = abs(p1.y - p2.y);
    int cost = 0;
    calcu_type_selection(cost, dx, dy);
    return cost;
}

int A_star::calcu_Hn(const Point& p1)
{
    int dx = abs(p1.x - end.x);
    int    dy = abs(p1.y - end.y);
    int Hn = 0;
    calcu_type_selection(Hn, dx, dy);
    return Hn;
}

void A_star::calcu_type_selection(int& data, const int& dx1, const int& dy1) {
    #ifdef Manhattan_Distance
        data = plane_cost * (dx1 + dy1);
    #elif Euclidean_Distance
        data = plane_cost * sqrt(dx1 * dx1 + dy1 * dy1);
    #endif
}

总结

可以看到优秀的启发算法能够很好的优化算法的表现。