我有一个类似于下面的无向图，我需要实现一个图遍历算法。
示例 :
http://i.imgur.com/15L6m.png
这个想法是每个顶点是一个城市，每个边缘是一条道路。
边的权重表示遍历指定边所需的时间。
条件是:
对于 我的例子我有:
必须访问的顶点及其时间窗口(不考虑 -1 的值):
Vertex To1 Tc1 To2 Tc2
1 0 260 340 770
4 0 240 -1 -1
5 170 450 -1 -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
所以基本思路是从顶点0开始，找到最短的路线遍历
考虑到指定时间的顶点 1、4 和 5。
此外，例如，如果您完成了 0-1 但不能使用 1-5，则可以执行 0-1-0-1-5。
我现在正在使用的一个可能的解决方案是:
从 0 开始。在最短的时间段内找到最近的顶点进行标记(我使用
修改的 Dijkstra 算法)。这样做直到我标记了所有需要的顶点。
问题 是我认为我没有找到所有的可能性，因为正如我所说
你也可以像 0-1-0-1-5 组合一样四处走动，最后你可能会得到一条更短的路线。
为了使它更清楚，我必须找到最短路径，以便我从顶点 0 开始，以一个目标顶点结束，同时我已经访问了所有其他目标顶点至少一次，尊重施加在边缘和目标顶点上的条件。
例如:
一个可能的解决方案是 0 - 4 - 3 - 5 - 1，总时间为 60+50+60+50=220
从 0 我也可以直接转到 5 但如条件中所述以标记顶点 5
我必须有 170 到 450 之间的累积时间。另外，如果我去 0-4，我不能使用边缘 4-2，因为它在 80 处打开并且我的累积时间是 60。注意我可以使用 0-4-3，因为 4 -3 在 60 处打开，而执行 0-4 所需的时间等于 60。
首先，我将使用最多 20 个顶点和
最大约 50 条边。
解决方案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:
应用@Boris Strandjev 示例，但我有一些问题:
我必须在其间隔内至少访问节点 1,4 和 5 一次，允许在间隔外访问但不标记。对于一个顶点，我有 {(< id1, id2id3id4>, time)}，其中 id1 是当前顶点的 ide，id2-4 表示 1,4,5 的 bool 值，如果在指定的时间间隔内访问，时间 -路径中的当前时间
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
编辑:
我最终使用了上述两种解决方案的组合。一切似乎都很好。
最佳答案
我没有看到对图中顶点或边数的严格限制，所以如果我的解决方案不适合你，请原谅。如果您需要任何改进，请给予更严格的限制。
一种可能的解决方案是扩展节点的定义。不要只将城市视为图表中的节点，而是添加更多属性。保持边缘定义隐式，随时随地生成传出边缘，从而节省内存。
立即查看 :
您将节点定义为三件事的组合:
- 节点所指的城市。
- 访问时间
- 访问过的目标节点的位图(这样您就可以知道您是否已经访问过所有目标)。
现在边缘有点复杂——它们会引导你从一个城市到另一个城市，但每条边缘也会改变相邻节点的时间。还要不断更新每一步的目标节点位图。
这是一个示例 :
您从 <city:=0, time:=0, bitmap:= (0 - true, 1...k - false)> 开始
如果您通过边缘 0-4，您会发现自己位于节点 <city:=4, time:=60, bitmap:= ({0,4} - true, {1...k} / {4} - false)>
继续以这种方式在节点之间移动，使用 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,1100>含义:当前顶点为1，第二个:第一个和第二个顶点已经在找到的路径中访问过。到每个顶点的距离将是到达该顶点所需的最短时间。
如您所知，在 Dijkstra 算法的过程中，您正在考虑增加路径(意味着您找到的到达已到达顶点前面的每个顶点的最佳路径)。我将按如下方式表示每个增广路径:
(<1,1100>, 400)表示您可以到达顶点的当前最佳时间<1,1100>是 400。你从一组增广路径开始算法
{(<1, 1000>, 0)}以及到所有顶点的距离 infinity .现在按照以下步骤操作。以最佳增广路径到达第一个顶点。从它可能的边缘是
1-2和 1-3 ( 1-4 在第 0 秒内不可用。它们触发了另外两个增强路径:{(<2, 1100>, 50), (<3, 1010>, 30)} 到 <1, 1000> 的距离更改为 0。下一步考虑最佳增广路径
(<3, 1010>, 30) .但是，可以使用较近的输出边来添加增广路径:1-3不能使用，因为在时间 60 不能访问顶点 1。边 3-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秒内访问所有的顶点。我希望这个例子能帮助你理解我的想法。您可能需要在纸上写下所有注意事项，以确保我不会与增广路径有关。
关于algorithm - 图遍历具有条件的特定顶点，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/12437083/