algorithm - SPOJ FISHERのアイデア

Question

SPOJ でこの問題を解決しようとしています:

                  http://www.spoj.pl/problems/FISHER/

私はこれに対する解決策を思いつくことができませんでした。トップコーダーでいくつかのスレッドを見つけましたが、DP が使用されると推測することしかできませんでした。誰かがこれについて私を導くことができれば、それは非常に役に立ちます。

Answer 1

動的計画法を使用して通常の最短経路の問題を解決すると、http://en.wikipedia.org/wiki/Bellman%E2%80%93Ford_algorithmが得られます. もちろん、これは時間の制約を無視します。状態空間を拡張することで、動的計画法のアルゴリズムをいつでもより柔軟にすることができます。この場合、各ノードで、これまでに見つかったそのノードへの最も安価なパスのコストを追跡する代わりに、i = 1,2,3,4.. の最も安価なパスのコストを追跡できます。そのノードまでの時間は最大で i です。単一のコストを計算するために使用される再帰の変種を使用して、このコストの配列を更新できるはずです。各エッジの緩和は、指定された時間で最も安いコストのベクトルを取り、各オフセットでそのエッジの時間とコストを追加することを考慮して、結果として得られる延長されたパスは、これまでのところそのエッジで終わる最もよく知られているパスよりも優れています。

ダイクストラのアルゴリズムを同じように変換することで、時間を節約できるのではないでしょうか? 少なくとも、ダイクストラのアルゴリズムを最初に実行してから、時間制約よりも長い最短時間パスを持つすべてのノードを破棄できます。

Answer 2

問題を解決する別の方法は、ダイクストラのアルゴリズムhttp://www.geeksforgeeks.org/greedy-algorithms-set-6-dijkstras-shortest-path-algorithm/を使用することです。制約はn<=50とtime<=1000です。与えられた時間 = T とします。したがって、各ノードを T 個のノードに展開します。これdist[node][i]は、与えられた時間 i でのノードへの最短パスを表します。n * Tしたがって、エッジを持つノードでアルゴリズムを実行します。n * n * Tエッジは、複雑さの指定された時間制約内に十分収まりますO((n * T + n * n *T) * log( N * T) )。私の受け入れた解決策: http://ideone.com/H8UUMf

Answer 3

動的計画法を使用します。

ノードへのパスを追跡するのは、それよりも時間がかからないすべてのパスのコストが高い場合のみです。新しいパスが表示されたら、バイナリ検索を使用して同じ時間以下の最長の時間パスを見つけ、そのパスよりもコストが低く、制限時間を超えていない場合にのみ新しいパスを追加できます。追加するときは、時間がかかり、安くはない既存のパスをすべて削除します。

最終的に、時間順に並べられた最終ノードへのパスの配列を取得します。時間の制約に合う最も安いものを選んでください。

おそらくノードのtodoリストを検討する必要があり、ノードはそのtodoリストに複数回巻き込まれる可能性があることに注意してください（新しい安価なパスを見つけるたびに、ノードに巻き戻されます）。