以下のような無向グラフがあります。グラフ走査アルゴリズムを実装する必要があります。
例： http:
//i.imgur.com/15L6m.png
各頂点が都市であり、各エッジが道路であるという考え方です。
エッジの重みは、指定されたエッジを通過するのに必要な時間を表します。
条件は次のとおりです。
- 各エッジは、指定された時間枠 (Time Open1、Time Open2、TimeClose1、Time Close2) でトラバーサル用に開いています。エッジをトラバースするには、現在の時間がこれらの間隔内にある必要があります。
- 一部の頂点のみを訪問する必要があります。頂点は、それぞれ指定された時間枠内で少なくとも 1 回訪問する必要があります: Time Open1、Time Open2、TimeClose1、Time Close2 - 頂点を訪問済みとしてマークするには、現在の時間がこれらの間隔内にある必要があります。
- 始点は常に頂点 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から開始します。最短時間でマークする最も近い頂点を見つけます（修正されたダイクストラアルゴリズムを使用します）。必要なすべての頂点をマークするまでこれを行います。問題
は
、私がすべての可能性を見つけているとは思わないことです.0-1-0-1-5の組み合わせのように動き回ることもでき、最終的にはより短いルートになる可能性があるためです. .
より明確にするために、エッジとターゲット頂点に課せられた条件を考慮して、他のすべてのターゲット頂点を少なくとも 1 回訪れながら、頂点 0 から開始し、1 つのターゲット頂点で終了するように、最短パスを見つける必要があります。
例:
考えられる解は 0 - 4 - 3 - 5 - 1 で、合計時間は 60+50+60+50=220
0 から 5 に直接行くこともできますが、頂点 5 をマークするための条件に記載されているとおりです。累積時間は 170 から 450 の間でなければなりません。また、0-4 にすると、エッジ 4-2 を使用できません。これは、80 で開き、累積時間が 60 であるためです。4 であるため、0-4-3 を使用できることに注意してください-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 をその間隔で少なくとも 1 回訪問する必要があります。間隔外の訪問は許可されますが、マークは付けられません。頂点の場合、{(< 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
編集：
上記の2つのソリューションを組み合わせて使用することになりました。すべてがうまくいくようです。