以尽可能少的转弯发现地图上所有字段的算法

Question

假设我有这样的地图:

#####
..###
W.###

. 是一个被发现的细胞.

# 是一个未被发现的细胞.

W是一个工人.可以有很多工人.每回合都可以移动一次.在一个回合中,他可以在4个方向(向上,向右,向下或向左)移动一个单元格.他发现他周围的所有8个细胞 - 变成#了..在一个回合中,同一个单元格上最多可以有一个工人.

地图并不总是矩形.在开始时,除了邻居之外,所有细胞都是未被发现的W.

目标是尽可能地发现所有细胞.

第一种方法

找到最近的#并走向它.重复.

要找到最近#我开始BFS从W捞起来时首先#发现.

在示例性地图上,它可以提供这样的解

##### ##### ##### ##### ##... #.... ..... 
..### ...## ....# ..... ...W. ..W.. .W... 
W.### .W.## ..W.# ...W. ..... ..... ..... 

6转.远非最佳:

##### ..### ...## ....# .....
..### W.### .W.## ..W.# ...W.
W.### ..### ...## ....# .....

4转.

题

发现尽可能少的所有单元的算法是什么？

Answer 1

这是使用 A* 的基本想法。它可能相当耗时和内存消耗，但它保证返回最佳解决方案，并且绝对比暴力破解更好。

A* 的节点将是各种状态，即工作人员所在的位置以及所有单元的发现状态。每个独特的状态代表一个不同的节点。

边将是所有可能的过渡。一名工人有四种可能的转变。对于更多的工人，您将需要所有可能的组合（大约 4^n 条边）。在这一部分，您可以限制工作人员保留在网格内而不重叠。

成本将是匝数。近似到目标（发现的所有单元格）距离的启发式可以开发如下：

单个工人每回合最多可以发现三个细胞。因此，n个worker最多可以发现3*n个cell。因此，剩余的最小轮数是“未发现的单元数/（3 * 工人数）”。这是要使用的启发式方法。这甚至可以通过确定每个工作人员在下一回合中可以发现的最大单元数（每个工作人员最多 3 个）来改进。因此，总体启发式将是“（未发现的细胞 - 可发现的细胞）/（3 * 工人）+ 1”。

在每个步骤中，您都会检查总体成本最低的节点（到目前为止的轮数+启发式）。对于检查的节点，您计算每个周围节点的成本（所有工人可能的移动）并继续。