週に一回は書きますよ 月に4つ記事を書けばノルマは満たされます。
上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。
迷路を解くアルゴリズムとしてDijkstra法があります。迷路の形と始点を指定すると、始点からほかの各点までの距離を答える、というアルゴリズムです。

これの複数人版を考えます。人がN人いて、それぞれが始点から終点まで動きます。複数人いるので、特定の道は同時には通れないとか何人までしか通れないとかしましょう。この条件で、人の合計移動距離を最小化してください、というのが問題です。

この問題は最小コストフローに帰着できます。わき出し点から始点に容量N、コスト負の大きい値となる道を引き、各道の距離をコストに割り当てればよい、という感じです。
ただし、それぞれの人がそれぞれ別々の始点から別々の終点に向かう場合はこれだけではうまくいきません。そのままだと、ある二人が終点を交換してしまった場合も解として認めてしまいます。

ところで、ダイクストラ法は、それぞれの道の距離が1で固定されている単純な幅優先探索による最短距離判定の拡張とみることができます。すると、道の距離が固定されている簡単な問題を人が複数人いるように改造したら、これは最小コストフローよりもう少し簡単な問題に帰着できるのでしょうか。

幅優先探索からダイクストラ法への展開がコスト1からコスト可変だったので、類推で最小コストフローから最大フローとかに変わるのでしょうか。
この類推はしかし、私には到底発展させられませんでした。最大フローはそもそもコストとかを全く考慮しないので、最大でどのくらい流れるかしかわかりません。一方元の問題は幅優先にしてもコストを常に意識し、最小コストを答えさせます。全く変換可能に見えません。
「N人を始点から終点まで運ぶことが可能でしょうか」、という問題にすれば最大フローに変換可能です。でもこの問題はそもそも最大フローです。やはり最短距離を求めないともとの問題とは似ても似つかなくなる気がします。
スポンサーサイト
コメント
この記事へのコメント
コメントを投稿する
URL:
Comment:
Pass:
秘密: 管理者にだけ表示を許可する
 
トラックバック
この記事のトラックバックURL
http://gusmachine.blog49.fc2.com/tb.php/174-c787c4b2
この記事にトラックバックする(FC2ブログユーザー)
この記事へのトラックバック
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。