最短経路

[d]

出発点とゴール地点を打ち込むと、自動的に最短経路を決定してそれを表示するプログラム
を教えてください。右の数字は交差点の数と隣接する町の番号です。
map.dat

1, 0.0, 0.0, Hirosakieki, 2, 2, 4
2, -0.6, 0.15, Daikanntyou, 3, 1, 3, 11
3, -0.83, 0.0, Kamidaikanntyou, 4, 2, 4, 9, 10
4, -0.6, -0.38, Omati, 3, 1, 3, 5
5, -0.38, -0.68, Matumori, 3, 4, 6, 7
6, 6.0, -0.3, Takada, 1, 5
7, -0.18, -1.02, Torikami, 2, 5, 8
8, -0.84, -1.58, Nakano, 3, 7, 9, 18
9, -0.9, -0.98, Hirosakidaigaku, 2, 3, 8
10, -0.98, 0.15, Runesugai, 3, 3, 11, 13
11, -0.78, 0.3, Hirosakiyuubinnkyoku, 3, 2, 10, 12
12, -1.28, 0.68, Motoderamati, 2, 11, 13
13, -1.32, 0.53, Ichibantyou, 4, 10, 12, 14, 15
14, -1.8, 0.98, Hirosakijou, 2, 13, 20
15, -1.43, -0.15, Douyamati, 2, 13, 16
16, -1.73, -0.26, sinntera, 3, 15, 17, 20
17, -1.8, -1.43, Asahigaoka, 3, 16, 18, 19
18, -1.2, -1.73, Nisihirosaki, 2, 8, 17
19, -2.48, -1.2, Shimizu, 2, 17, 20
20, -2.33, -0.51, Jumoku, 3, 14, 16, 19

[ｇ]

出発点とゴール地点を打ち込むと、自動的に最短経路を決定してそれを表示するプログラム
を教えてください。右の数字は交差点の数と隣接する町の番号です。 １行１行プログラムの説明もお願いします。
map.dat

1, 0.0, 0.0, Hirosakieki, 2, 2, 4
2, -0.6, 0.15, Daikanntyou, 3, 1, 3, 11
3, -0.83, 0.0, Kamidaikanntyou, 4, 2, 4, 9, 10
4, -0.6, -0.38, Omati, 3, 1, 3, 5
5, -0.38, -0.68, Matumori, 3, 4, 6, 7
6, 6.0, -0.3, Takada, 1, 5
7, -0.18, -1.02, Torikami, 2, 5, 8
8, -0.84, -1.58, Nakano, 3, 7, 9, 18
9, -0.9, -0.98, Hirosakidaigaku, 2, 3, 8
10, -0.98, 0.15, Runesugai, 3, 3, 11, 13
11, -0.78, 0.3, Hirosakiyuubinnkyoku, 3, 2, 10, 12
12, -1.28, 0.68, Motoderamati, 2, 11, 13
13, -1.32, 0.53, Ichibantyou, 4, 10, 12, 14, 15
14, -1.8, 0.98, Hirosakijou, 2, 13, 20
15, -1.43, -0.15, Douyamati, 2, 13, 16
16, -1.73, -0.26, sinntera, 3, 15, 17, 20
17, -1.8, -1.43, Asahigaoka, 3, 16, 18, 19
18, -1.2, -1.73, Nisihirosaki, 2, 8, 17
19, -2.48, -1.2, Shimizu, 2, 17, 20
20, -2.33, -0.51, Jumoku, 3, 14, 16, 19

[？？]

ちょっと難しくて私にはわかりかねます。すいません。

[たいちう]

あなたの替わりに宿題をやるつもりはないけど、
あなたが宿題をするのを助けるつもりならありますよ。
久しぶりにTSPでも解いてみようかと。

やる気があるなら、まず、map.datを読み込むプログラムを
作ってください。とりあえずできるところまで。

[non]

>1, 0.0, 0.0, Hirosakieki, 2, 2, 4
データの持つ意味を、正確に表してください。

[Ma]

>>1, 0.0, 0.0, Hirosakieki, 2, 2, 4
>データの持つ意味を、正確に表してください。

憶測ですが

町ID, x 座標, y 座標, 町名, 隣接する町の数(移動できる分岐), 分岐できる町IDその1, 分岐できる町IDその2,・・・
というフォーマットかと思われます。


カーナビの劣化プログラム？みたいなのかな？

このような問題は解いたことがないので、まったくの素人の考えですが私なりの考え方を書いてみます。
と、おもったのですが、これって１点（出発地点か到着地点）から隣町へ移動したときおもう1点までの直線距離の変化を比べるだけじゃだめそうですね・・・。
（理由：その直線距離にして近いと思われた町からの分岐が結局遠くなることも、ありそうだから。）

実際どのようなマップになっているのか描画してみて、↑の方法でいけるかどうか判断できるかも。
もしくは、移動回数（町から町まで）を複数回ぐらい調査するとか。

といっても、ぱっと思いついた方法なので最良の方法ではないでしょうが・・・。

（町が増えたとき）重くてもいいなら、ルートを全部割り出して比べあうとか。
ただし、途中で同じ町にたどりついときにはぶつかったもう一方のルートとの距離を比べて短い方のみ残すとか。


ともかく、この手の問題は（私のように）解いたことがないなら実際に書いてみて試行錯誤するべきだと思います。
（あと実行結果をチェックする際はプログラムか手書きで視覚的に見たほうがいいでしょう。）

[non]

>町ID, x 座標, y 座標, 町名, 隣接する町の数(移動できる分岐), 分岐できる町IDその1, 分岐できる町IDその2,・・・
>というフォーマットかと思われます。

なるほど。わかりました。

再帰呼び出しの、課題ですね。

[mats]

投稿者さんからの情報が少ないため何とも言えませんが、

・たいちうさんの仰るようなTSPの課題
（正確にはスタートとゴールが異なるようなので最短ハミルトン経路問題）

・nonさんの仰るような再起呼び出しの課題
（深さ優先探索等でしょうか）

・Maさんの仰るようないわゆる経路探索の課題
（ダイクストラ法（ダイキストラ法）、幅優先探索、A*探索等）

等が考えられますね

……大学の課題だとするならTSPの可能性は低いとは思いますが

[たいちう]

> ……大学の課題だとするならTSPの可能性は低いとは思いますが

kwsk


それはともかく、TSPではなかったですね。
フォーマットについてはMaさんと同じ憶測をしていましたが、
接続が決まっているとすると、TSPで解くような自由度の高い問題ではなかったです。
失礼しました。

[mats]

>>たいちうさん

TSPだとすると、投稿者さんのサンプルにあるような頂点数20というのは多すぎます

スパコンでも使えば別ですが、市販されているコンピューターですと、
工夫したアルゴリズムを用いても頂点数22～23程度が限界だったと記憶しています
（『現実的な時間で解ける』という意味での限界）

学生によっては解くのに数日～数週間を要するプログラムを作成する危険性があるので、
検証にそれだけ時間を要する課題は出題しにくいはずです

[たいちう]

> スパコンでも使えば別ですが、市販されているコンピューターですと、
> 工夫したアルゴリズムを用いても頂点数22～23程度が限界だったと記憶しています
> （『現実的な時間で解ける』という意味での限界）

なるほど論点が判りました。しかし、遺伝的アルゴリズムの課題等という可能性は？

いずれにしろTSPではないだろうということは納得しています。
ありがとうございました。

[lbfuvab]

にしても最近は質問しっ放しの人が増えましたねぇ。
自己解決したにせよ連絡するのが筋でしょうに。

しかも名前を変えてますし。

[mats]

> なるほど論点が判りました。しかし、遺伝的アルゴリズムの課題等という可能性は？

確かに…その可能性もありますね．
このくらいの問題ならば，他にもたくさん解法があるかもしれません．

ただ，課題だとするなら，ランダム性が絡む遺伝的アルゴリズムも評価がしにくいのでは……．



と，ここまで書いた所で

サンプルから弘前大学の課題かとアタリをつけて検索してみたら引っ掛かりました．
どうやら，C言語でダイクストラ法を実装する課題のようですね．

質問者さんが戻ってこられるかわかりませんが……

ダイクストラ法ならば，様々なサイトにソースが掲載されています．
それを見てもわからないようなら，その時に改めて『ちゃんとした態度で』質問して頂けたら，
解答が得られるのではないかと思います．

[ｄ]

遅くなって申し訳ありません。
いろいろ調べてみたのですがなんかよくわかりません。
ダイクストラ？だかってのを使うらしいのですが・・・。
わかりません。