假设我有这样的 map :
#####
..###
W.###
. 是一个已发现的单元格。
# 是一个未被发现的单元格。
W 是一个 worker 。可以有很多 worker 。他们每个人每回合可以移动一次。在一轮中，他可以在 4 个方向(上、右、下或左)上移动一个单元格。他发现了他周围的所有 8 个细胞 - 将 # 变成了 .。在一个回合中，同一个单元最多可以有一个 worker 。
map 并不总是矩形的。一开始，除了 W 的邻居之外，所有单元格都未被发现。
目标是在尽可能少的轮次内发现所有细胞。
第一种方法
找到最近的 # 并朝它走去。重复。
为了找到最近的 # 我开始 BFS从 W 开始，并在找到第一个 # 时结束。
在示例 map 上它可以给出这样的解决方案:
##### ##### ##### ##### ##... #.... .....
..### ...## ....# ..... ...W. ..W.. .W...
W.### .W.## ..W.# ...W. ..... ..... .....
6 回合。远非最佳:
##### ..### ...## ....# .....
..### W.### .W.## ..W.# ...W.
W.### ..### ...## ....# .....
4 圈。
问题
用尽可能少的轮次发现所有单元格的算法是什么？
最佳答案
这是一个使用 A* 的基本思想。这可能是相当耗时和耗内存的，但它可以保证返回一个最优解，并且绝对优于暴力破解。
A* 的节点将是各种状态，即 worker 所在的位置和所有单元格的发现状态。每个独特的状态代表一个不同的节点。
边将是所有可能的过渡。一名 worker 有四种可能的转变。对于更多的 worker ，您将需要所有可能的组合(大约 4^n 条边)。这是您可以将工作人员限制在网格内而不重叠的部分。
成本将是转数。可以按如下方式开发近似到目标(发现的所有单元格)距离的启发式:
一个 worker 每回合最多可以发现三个细胞。因此，n 个 worker 最多可以发现 3*n 个单元格。因此，剩余的最小轮数是“未发现的单元数/(3 * worker 数)”。这是要使用的启发式方法。这甚至可以通过确定每个 worker 在下一回合可以发现的最大单元数(每个 worker 最多 3 个)来改进。所以整体启发式将是“(未发现的细胞 - 可发现的细胞)/(3 * worker )+ 1”。
在每一步中，您都会检查总成本最低的节点(到目前为止的转数 + 启发式)。对于检查的节点，您计算每个周围节点的成本(所有 worker 的可能移动)并继续。
关于以尽可能少的转弯发现 map 上所有字段的算法，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/25304783/