algorithm - 找到“覆盖所有”路径的开始和结束位置，然后将它们连接起来

Question

我的 2dArray 中有这样的形状（例如）：

已知点 A 和 B（我不知道在哪里）和一条覆盖整个形状的路径（必须穿过每个单元格）必须存在。你能给我一些关于如何确定点 A 和 B 以及“覆盖所有”路径的帮助吗？对于这种情况，也许有一些已知的算法。或者一些关于伪代码算法的帮助。提前致谢。

Answer 1

检查nhahdth的链接以查看您的问题通常是 np-hard。这篇 mathoverflow 文章引用了一篇论文，为带有孔的网格上的图形建立了结果——除非你能提出更多的约束，否则你不会比使用蛮力好得多。

您可能很幸运，通过在底层网格单元图中搜索度数为 1 的顶点来识别至少一个开始和结束节点。