实验记录 | AI 引论（or CS188）Lab 1 吃豆人启发式函数设计

启发式函数（Heuristic Function）

启发式函数和 A 算法的性能息息相关，它用于估算从任意状态 n 到达目标状态的*最低成本，通常记作 $H(n)$。

可以理解为 A* 算法为大号的 Dijkstra，唯一区别为排序的权重为从起始状态到当前状态的代价 + 当前状态的启发式函数。

启发式函数要求

可接受性 / 保守性（Admissibility）

$H(n)$ 必须是乐观的，$H(n)$ 要永远 $\leqslant$ 实际成本。

满足该条件，可以使得 A* 在树搜索上可以保证最优。

一致性（Consistency）

对于 $n \to n’$ 的状态转移，要求 $H(n)\leqslant H(n’)+\mathrm{cost}(n,n’)$。

满足该条件，可以使得 A* 在图搜索上可以保证最优。

问题描述

（对应 AI 引论作业中 Part1 题⽬ 4：启发函数设计 和 CS188 中 Question 6 Corners Problem: Heuristic）

现在吃豆人若干豆子（测试用例中为 4 个，分布在地图各角落）要吃，吃豆人需要找到最短的路径将这些豆子都吃一遍。题目会记录 A 搜素中访问的状态数，对于中型地图，当状态数分别低于 2400 / 1600 / 1200，即可获得 1 / 2 / *3 分。

也就是网格图上的一个类似于旅行商的问题。

启发式函数形式

会给你地图，所有豆子位置，吃过的豆子位置，当前位置，返回代价。

测试维度

本来只会测试函数的，但是搞了大半天最后发现之前的 A* 写错了一点点，具体来说就是从 priority_queue 中取出的时候忘记判断是否之前遍历过了。

因此就有了三个维度：

• 函数
• 边权代价（曼哈顿距离，实际距离）
• A* 算法（劣势版本，正确版本）

实验函数

平凡的启发函数

指的是处处返回 $0$ 的函数（如 UCS 算法 / Dijkstra）和表示真实完成成本的启发式。

前者不会省时间，后者在求解时会超时。暂时不讨论这些函数。

Function 1

返回到当前位置到最近的豆子的距离（真实距离 / 曼哈顿距离）。

结果（后面的结果都以访问节点数代表） ：

（曼哈顿距离，实际距离）	Function 1 劣势版	Function 1 正常版
小型地图	2058,1328	334,260
中型地图	-	1745,1475

Function 2

返回到当前位置到最远的豆子的距离。

结果：

（曼哈顿距离，实际距离）	Function 2 劣势版	Function 2 正常版
小型地图	2192,619	289,150
中型地图	-	1357,978

Function 3

返回当前节点和未访问节点的 MST 大小（边权为曼哈顿距离）。

开始的时候不仅写错了 A*，还写错了 MST，结果非常优秀，中型地图结果不超过 1000，除了 Admissibility 和 Consistency 双双 Failed。

结果：

（曼哈顿距离，实际距离）	Function 3 劣势版	Function 3 正常版
小型地图	664,102	248,60
中型地图	2853,10656	1023,354

Function 4

忽略当前节点，返回剩余代价。

具体来说，考虑所有访问的排列，求出最小访问代价（每次代价以曼哈顿距离 / 实际距离计算）。

但在具体实现时，忽略了当前节点，假设是传送到了一个目标然后走。

结果：

（曼哈顿距离，实际距离）	Function 4 劣势版	Function 4 正常版
小型地图	670,215	307,85
中型地图	8249,5768	1408,754

Function 5

考虑当前节点，返回剩余代价。

结果：

（曼哈顿距离，实际距离）	Function 5 劣势版	Function 5 正常版
小型地图	未测量	223,28
中型地图	未测量	950,246