具有条件的图遍历特异性逼真度

Question

null

Vertex To1  Tc1  To2  Tc2
  1    0    260  340  770
  4    0    240  -1   -1 
  5    170  450  -1   -1 

Edge To1  Tc1  To2  Tc2
0-1  0    770  -1   -1 
0-4  0    210  230  770
0-5  0    260  -1   -1 
1-2  0    160  230  770
1-5  40   770  -1   -1 
2-4  80   500  -1   -1 
3-4  60   770  -1   -1 
3-5  0    770  -1   -1 

解决方案1:
0
1 4 5 0 2 5 0 2 3 0 1 3

我所做的是遍历图，通过访问每个邻近的顶点，建立类似树的东西。当:
1时，我停止扩展分支。我有太多的重复，就像我有0 1 0 4 0 1 0-所以我停止了，因为我有一组重复的0值，这是4
2。我找到一条包含所有顶点的路来标记
3。我发现一条路比另一条完整的路耗时更长
4。我无法创建另一个节点，因为边缘已关闭

解决方案2:

Step1: 
{<0, 000>, 0} I can visit - {<1, 100>, 60} - chosen first lowest val
                          - {<4, 010>, 60}
                          - {<5, 000>, 60}
Step2:
{<1, 100>, 60} - {<0, 100>, 120} 
               - {<2, 100>, 110}   - chosen 
               - {<5, 100>, 110}    
Step3:
{<2, 100>, 110} - {<1, 100>, 160} - if I choose 1 again I will have a just go into a loop 
                - {<4, 110>, 170}   
Step4:
{<4, 110>, 170} - {<0, 110>, 230}
                - {<2, 110>, 230} 
                - {<3, 110>, 220}   - chosen

Step5:
{<3, 110>, 220} - {<4, 110>, 270} - again possible loop
                - {<5, 111>, 280} 
Step6:
{<5, 111>, 280} - I stop Path: 0-1-2-4-3-5 cost 280

我最后使用了上面两个解决方案的组合。一切似乎都很好。

Answer 1

我没有看到一个严格的限制数量的顶点或边你有在图中，所以请原谅，如果我的解决方案将不能为您工作。如果你需要任何改进，给出更严格的限制。

一个可能的解决方案是扩展节点的定义。不要只考虑城市作为图中的节点，而是添加一些更多的属性。保持边缘定义隐式，在执行过程中生成传出边缘，以便节省内存。

现在看:
定义一个节点是三个元素的组合：-节点引用的城市。-访问时间-访问目标节点的位图（这样你就可以知道你是否已经访问了所有的目标）。

现在，边缘变得更加复杂--它们将你从一个城市带到另一个城市，但每个边缘也会改变相邻节点的时间。每一步都要不断更新目标节点位图。

下面是一个示例:
从
如果从边缘0-4开始，您会发现自己位于节点

使用Dejkstra算法在节点之间继续以这样的方式移动，您将找到您的解决方案（当您扩展节点定义时，现在甚至可以考虑附近的位置）。只要您发现自己在位图中设置了所有位的节点中，您就找到了解决方案。

在这种解决方案中使用的节点数不太容易计算，但对于相对有限的节点数和相当有限的目标城市数来说，它应该是可行的（问题是结果节点数相对于目标城市是指数级的）。

编辑

下面是您要求的扩展示例：

假设您有这样一个输入（我正在使用您的符号）：

 Vertex To1  Tc1  To2  Tc2
   1    0    40   80  120
   2    40   80   -1   -1
   3    0   400   -1   -1 
   4    30   80   120 190

 Edge To1  Tc1  Weight
 1-2   0    770  50
 1-4  30     70  30
 1-3   0    400  30
 3-4 100    200  50
 2-4   0    400  20

我将以以下形式表示这些顶点:<1,110>意思是：当前顶点是1，第二个：第一个和第二个顶点已经在找到的路径中被访问。到每个顶点的距离是到达这个顶点所需的最小时间。

正如您所知，在Dijkstra算法的过程中，您正在考虑增加路径（即您找到的到达已到达顶点前面每个顶点的最佳路径）。我将按以下方式说明每个增加路径:(<1,110>,400)意味着当前到达顶点<1,110>的最佳时间是400。

您使用一组扩展路径{(<1,1000>,0）}和到所有顶点的距离无穷远开始算法。现在按照下面的步骤进行操作。

以最佳增广路径到达第一个顶点。其中可能的边是1-2和1-3(1-4在第0秒内不可用。它们触发另外两个扩展路径:{(<2,1100>,50）,(<3,1010>,30）}到<1,1000>的距离更改为0。

下一步考虑最佳扩展路径(<3,1010>,30)。但是，可以使用传出边的邻近点添加扩展路径:1-3不能使用，因为在时间60不能访问顶点1。edge3-4也不能使用，因为有时间间隔。因此，扩展路径现在是:{(<2,1100>,50）}。

下一步:(<2,1100>,50)和新的扩展路径:{(<1,1100>,100)，(<4,1101>,70）}。

下一步:(<4,1101>,70)，但它也没有添加新的路径：顶点2不能在时间90被访问，3-4不能再使用。因此，扩展路径是{(<1,1100>,100）}。

下一步:(<1,1100>,100)将增强路径更改为:{(<3,1110>,130）}。

下一步:(<3,1110>,130)，它将增强路径更改为:{(<4,1111>,180）}。

下一步:(<4,1111>,180)，这是最后一步-我们处于访问所有目标顶点的状态。因此总结：您可以访问限制中的所有顶点180秒。

我希望这个例子能帮助你理解我的想法。您可能需要将所有的注意事项写在一张纸上，以使sur eI不与增加的路径有关。