以平面的正方形拼接为例，想象一个有限的、连通的和简单连通的子集 D 的瓷砖。 D当然也可以解释为正方形网格的一个特定子图，通过为每个瓦片取一个节点并连接相邻节点。
假设我在 D 中和在 D 的边界中有一个起始节点/图 block A 和一个结束图 block B。
是否有一种简单、直接的算法可以在 D 中的 A 和 B 之间找到相当长的自回避路径？
我发现有关寻找绝对最长路径和次优算法的文献，这些算法虽然性能非常好，但看起来非常复杂。我想知道是否存在性能足够好的 tamer 算法。
我在这里唯一的想法是计算通过 A* 的最短路径，然后通过横向“折叠”来扭曲它以填充尽可能多的空间，但我不确定这是否是个好主意。
另一个想法是是否有一个几乎愚蠢的简单“扫描线”模式填充 A 和 B 之间的空间，因此对于“矩形”D 表现良好。我怀疑它存在，但我找不到它。
最佳答案
对于大于 2 维的方形网格:
最长路径问题被认为是 NP-Hard；它不能在多项式时间内解决，除非 P=NP 对于某些任意图形。
话虽如此，你可以做一个DFS在每个节点上确定最长路径。这一切都是假设图表是加权的(你没有在你的帖子中指出)。请务必注意，您不应允许重复顶点。
在 DFS 结束时，将您当前最长的路径与之前被认为最长的路径进行比较。根据需要用最长的时间替换此结果。
关于特定方格子图中的长路径算法，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/36633030/