|
> ひとつ問題点をみつけたので提示しておきます。確定済みの経路の最後(端)の地点へ新しい地点がつながらない場合に > 確定済みの地点から新しくつなげた経路への経路が存在するとき繋ぎなおしたほうが最短になるケースがあります。 > 確定済みの経路への接合点以降の地点について次の地点より新しい経路への経路の方が短い場合つなぎなおす必要がありそうです。そのとき接合点からのつなぎ直したところまでの間に指定地点がなければその辺は不要となりそうです。 > 何かいい感じですね、その考え方。 十分に理解できてませんが、原理的な感じがします。
私の方ではワーシャルフロイド法+Bの組み合わせを確定した後、プリム法がなぜ最善経路を見落とすかというと点について考えてみました。
S1 繋げる必要がないBに辺を繋げてしまう S2 電線を重複して数えてしまう。
S1は明白です、プリム法は全部の抽出点を使いますがBは使わなくてもいい点なのですからBを使わない最小木が可能性として存在します。
S2は簡単な場合を考えればわかります。 地点1,2,3が目的地と発電所、4,5がその他の地点とします。 B={空集合}としてmap[1][3]とmap[2][3]をつなげるのが最短と出た場合、
map[1][3]が1,4,5,3という経路に,map[2][3]が2,5,3という経路なら 5,3という経路が重複しておりこれを足してしまいます。 これがグラフnewGからBを選び、これにプリム法を適用した後プリム法が最善経路を見落とす原因になります。
これを改善できればもしかしたら直接解を見つけられるかもしれません。
newGには特徴が一つあります。 newGは、ある地点iからjを直接結びますが、iからjへの最短経路なので,iから他の点を通ってjに向かう経路は全てi,jより遠回りになります。 この特徴を上手く使えるかもしれません。
色々考えてはいますが、グラフ理論をきちんと学んだ人からみたら私は滑稽なのかも? ちゃんと勉強すればこの問題教科書に書いてあったりして? とかは少し考えたりします。
|