有序哈密顿电路(给定每个节点的坐标)

Question

对于我学校的ACM-ICPC团队,我们一直难以理解如何解决这个特定的练习问题:

给定位于坐标(X {i},Y {i})的N个节点,计算从节点1,2,3,...,N遍历然后返回到1(按此顺序)所需的最短曼哈顿距离.您只能访问每个节点一次.如果这样的路径不存在,则输出-1.
N由[1,100]
界定X和Y坐标以[1,100,000,000]为界

我们提出了一些样本数据:

N = 4
坐标:
1.(2,2)
2.(2,4)
3.(2,1)
4.(1,3)

在这种情况下,最短路径是从节点1到节点2的12:2单位,从节点2到节点3的5个单元(绕过节点1,在路上),从节点3到节点4的3个单元,然后2个单位返回节点1.

虽然它可能是哈密顿循环.我还认为构建"图形"是问题的主要部分.一旦构建了图形,您就可以走它以找出总体最短距离.我的问题是检测从i到i + 1的路径是否包含一个节点,如果有,那么绕过它的最佳方法是什么(知道重新路由可能还有一个节点)？

更新:我有O(N ^ 2)代码来检测2个节点是否在同一行,诊断或列中,但我不知道重新路由它的方法是什么.

Answer 1

(我已经扩展了这个答案来描述一个不同的,希望更快的算法.结果,一些评论有点过时了.)

首先,我将尝试澄清问题:

我们有一个大格子.100,000,000次100,000,000个节点.这是很多节点.这些节点中的少数N是给定节点.我们要在格子中找到一个循环.循环不必访问晶格中的每个节点,但它必须只访问每个给定节点一次.它必须以给定的顺序访问那些给定的节点.

解:

我们必须找到N条最短的路径.我们必须找到:

• 从最短路径g_1来g_2,避免所有其他给定的节点
• 从最短路径g_2来g_3,避免所有其他给定的节点
• ...
• 从最短路径g_{N-1}来g_N,避免所有其他给定的节点
• 从最短路径g_N来g_1,避免所有其他给定的节点

这些问题彼此独立.我稍后会尝试描述一个快速算法,但首先是一个简单的算法来查找从给定源到给定目标节点的路径:

• 从整个格子开始......
• 对于N个给定节点中的每一个,除了当前源节点和目标节点之外,删除上方,下方,左侧和右侧的4个边缘.
• 使用标准最短路径算法在当前源和当前目标之间找到图中的最短路径.
• 在搜索下一个最短路径之前替换边缘.

这不是一个快速的算法,但我希望它是正确的.这将是很多比它慢可能.我们可以改进标准的BFS最短路径算法,因为我们没有处理任何任意图形,我们正在处理一个格子.

一种快速算法

(我认为这是一个标准的A*搜索算法.感谢我在大学的同事指出这一点.)

假设你和我这么远,现在的目标是要找到一个格子,其中节点(小)数量是两个节点之间的最短路径不可用.

想象一下,晶格中的每个可用节点都有两个与之关联的变量,即"上限"和"下限".这些边界描述了返回源节点的距离的上限和下限.我们将初始化下限与'乐观'曼哈顿距离回到源节点('乐观',因为我们允许使用所有节点).我们将所有节点的上限初始化为无限,除了指定上限为0的源节点.对于单个节点,一旦其上限收敛到其下限,那么这是到达它的正确距离.源节点.算法继续,逐渐增加下限并减小上限,直到目标节点的边界已收敛.

开始时,边界已经为源节点收敛.从源到自身的距离只是0.

(显然,为所有节点存储所有这些数字对是不切实际的,但我们稍后会回答这个问题).

我们如何更新边界？给定任何"当前"节点,其邻居的上限不应超过当前节点的上限1.这允许节点"拉下"其邻居的上界.

此外,如果两个相邻节点的下限存在较大差异,则它们可能会相互影响.如果节点A的下限为5,并且它连接到节点B,其下限为3,那么我们可以将B的下限增加到4.通过矛盾证明:如果只需3步即可达到B ,然后通过B通过最多4步可以达到A但是这与我们的知识相矛盾,即A的下限是5.因此,B的下限应该增加到4.

这显示了节点如何能够提升或压低邻居的界限.我们必须将这个想法变成一种算法.

我们需要保持节点的"前沿".这个边界是一组可能影响其邻居边界的节点.最初,边界是一个单独的集合,只包含源节点.

循环执行以下操作,直到边界收敛到目标节点:

1. 如果边界现在为空,则算法失败.源节点被捕获,无法到达目标.
2. 选择与目标节点最接近的边界节点("乌鸦飞行").(您可以选择任何边界节点,但这是一种乐观的启发式方法).将其称为"当前"节点.
3. 检查此"当前"节点是否能够影响其邻居的边界.(显然忽略了不可用的节点).
4. 如果它无法影响其邻居的边界,则从边界移除当前节点并返回步骤1.(注意:此节点可能稍后再次重新进入边界).
5. 继续修改邻居的界限.对于受影响的每个相邻节点,将其带入边界(如果它尚未存在).
6. 如果我们刚刚看到边界会聚在目标节点上,那么算法就完成了.
7. 现在我们已经考虑了邻居,我们检查边界是否已经收敛到当前节点.如果是这样,我们可以(永久地)从边界移除当前节点.我们知道这个节点的正确距离,并尽力将这些信息合并到邻居的边界.我们不能再做它了.

最后,我们必须设计一个合适的数据结构来存储这些边界.将它显式存储到这个巨大晶格的所有点是不可行的.我会使用C++的地图

// mapping from (x,y) to (upper_bound, lower_bound)
map< pair<int,int>, pair<int,int> > bounds;

最初,此映射仅包含源节点:(source_x, source_y) => (0,0) 当尝试查询当前不存在的节点的此映射时,我们可以如上所述初始化它,并使用下限和无穷大的乐观Manhatten分数(INT_MAX)为上限.请记住,算法只会查询边界节点邻居的节点,因此在很多情况下它不应该变得太大.此外,如果节点已收敛,并且其所有邻居已收敛(或无法使用),则我们可以将其从地图中永久删除.