是否有一种寻路算法不是寻找从 A 点到 B 点的路径，而是 returns 覆盖整个地图的路径？
Is there a pathing algorithm that instead of finding a path from point A to point B, it returns a path that covers the whole map?
我正在寻找一种寻路算法，它可以找到一条路径，而不是常见的 A 到 B 算法，而是找到一条覆盖整个地图的路径（例如，蜿蜒穿过商店的货架）
我试过自己做一个，但效率极低，而且没有分支太远。
我可以使用任何想法或资源吗？
通常很难找到 "reasonable" 在到达某个地方之前访问所有位置的路径。您想要的理想路径称为 哈密尔顿路径 ，不幸的是，no one knows how to find Hamiltonian paths efficiently in the general case。您可能需要满足于执行大量回溯步骤的怪异路径，或者接受在到达目的地之前不会访问所有位置的路径。
"finding a path that covers the whole map," 我假设你的意思是从节点 A 开始，你想遍历 每个 个节点，然后在 B 结束。
您实质上是在尝试为您的图找到一条哈密顿路径，其中起始节点和结束节点分别位于 A 和 B。这个问题是 NP 完全问题，这意味着我们目前还没有计算上可行的算法来解决它（事实上，我们怀疑 是 没有这样的算法）。
蛮力解决方案是从 A 分支并尝试每条 路径，希望找到一个接触每个节点一次并在 B 结束的路径。不幸的是，你如果不修改您要解决的问题的约束，就不可能做得比这更好。
我正在寻找一种寻路算法，它可以找到一条路径，而不是常见的 A 到 B 算法，而是找到一条覆盖整个地图的路径（例如，蜿蜒穿过商店的货架）
我试过自己做一个，但效率极低，而且没有分支太远。
我可以使用任何想法或资源吗？
通常很难找到 "reasonable" 在到达某个地方之前访问所有位置的路径。您想要的理想路径称为 哈密尔顿路径 ，不幸的是，no one knows how to find Hamiltonian paths efficiently in the general case。您可能需要满足于执行大量回溯步骤的怪异路径，或者接受在到达目的地之前不会访问所有位置的路径。
"finding a path that covers the whole map," 我假设你的意思是从节点 A 开始，你想遍历 每个 个节点，然后在 B 结束。
您实质上是在尝试为您的图找到一条哈密顿路径，其中起始节点和结束节点分别位于 A 和 B。这个问题是 NP 完全问题，这意味着我们目前还没有计算上可行的算法来解决它（事实上，我们怀疑 是 没有这样的算法）。
蛮力解决方案是从 A 分支并尝试每条 路径，希望找到一个接触每个节点一次并在 B 结束的路径。不幸的是，你如果不修改您要解决的问题的约束，就不可能做得比这更好。