1

我有一个类似于下面的无向图，我需要实现一个图遍历算法。 示例：http:
//i.imgur.com/15L6m.png

这个想法是每个顶点是一个城市，每个边缘是一条道路。
边的权重表示遍历指定边所需的时间。
条件是：

  1. 每条边都在指定的时间窗口中打开以进行遍历：Time Open1、Time Open2、TimeClose1、Time Close2 - 当前时间必须在这些时间间隔内才能遍历边。
  2. 只有一些顶点必须被访问。每个顶点必须在指定的时间窗口内至少访问一次：Time Open1、Time Open2、TimeClose1、Time Close2 - 当前时间必须在这些时间间隔内，以便将顶点标记为已访问。
  3. 起点始终是顶点 0

对于我的示例，我有：
必须访问的顶点及其时间窗口（不考虑 -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 的布尔值，如果在指定的时间间隔内访问，时间 -路径中的当前时间

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

编辑：

我最终使用了上述两种解决方案的组合。一切似乎都很好。

4

1 回答 1

1

我没有看到对图中顶点或边数的严格限制，所以如果我的解决方案不适合你，请原谅。如果您需要任何改进，请给予更严格的限制。

一种可能的解决方案是扩展节点的定义。不要只将城市视为图表中的节点，而是添加更多属性。保持边缘定义隐式，随时随地生成传出边缘，从而节省内存。

现在看：
您将节点定义为三件事的组合： - 节点所指的城市。- 访问时间 - 访问过的目标节点的位图（这样您就可以知道您是否已经访问过所有目标）。

现在边有点复杂——它们会引导你从一个城市到另一个城市，但每条边也会改变相邻节点的时间。还要不断更新每一步的目标节点位图。

这是一个示例：
您从<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秒内访问所有的顶点。

我希望这个例子能帮助你理解我的想法。您可能需要在纸上写下所有注意事项，以确保我不会与增广路径有关。

于 2012-09-16T10:09:31.090 回答