お世話になります。
以下のようなファイルを利用して、最短経路を求めるスクリプトをご教示いただけないでしょうか。
Metricがもっともすくないものが良。
可能な限りC言語以外で実現したいと考えております。
## 検索してみたのですが、どうもC言語のプログラムが多そうです。
(snip)
SourceDestMetric
121
131
415
434
451
461
475
484
492
4107
4116
41214
4139
41412
41523
41627
41720
18191
1974
20184
20192
21192
242
231
272
・・・・・・
・・・・・
・・・・
・・・
・・
(snip)
A 回答 (4件)
- 最新から表示
- 回答順に表示
No.4
- 回答日時:
source/dest/metric などの情報をどのように入手するかは全く考えていません. 最終的に $metric{$i}{$j} に $i から $j への metric が入っていれば OK です.
ああ, 1点言っておくべきことがあります. 実際にはこれは「最短経路」を見つけていないので, 「最短経路」を見つけるためにはもうちょっと処理が必要です. $dist{$i}{$j} を更新するときに $via{$i}{$j} = $k も実行して, 「$i から $j への最短経路は $k を通る」ということを記録しておくんでしょう.
No.3
- 回答日時:
ちょいと調べましたら, Warshall-Floyd あたりが安全そうです.
ある程度プログラムが書けるなら調べたものをプログラムにした方がよいと思いますが一応 Perl で. $metric{$i}{$j} が $i から $j への metric とします (存在しなければ undef). あと, $n がソース (デスティネーションでも同じだけど) の個数です:
my %dist;
for my $i (1 .. $n) {
for my $j (1 .. $n) {
$dist{$i}{$j} = $metric{$i}{$j};
}
$dist{$i}{$i} = 0;
}
for my $k (1 .. $n) {
for my $i (1 .. $n) {
for my $j (1 .. $n) {
# Calculate the distance from $i to $j with at most $k hops
my $s = (defined $dist{$i}{$k} && defined $dist{$k}{$j}) ? $dist{$i}{$k} + $dist{$k}{$j} : undef;
if (! defined $dist{$i}{$j} || (defined $s && $s < $dist{$i}{$j})) {
$dist{$i}{$j} = $s;
}
}
}
}
多分動くと思うけど, あんまり自信なし. ちなみに, n^3 くらいの時間がかかります.
ご親切にどうもありがとうございます。
このスクリプトですが、"Source Dest Metric"等の情報を外部ファイルとして取り込む必要があるのでしょうか。
(snip)
Source Dest Metric
1 2 1
1 3 1
・・・
(snip)
No.2
- 回答日時:
ああ, 「1点から他の点への最短経路」と「全点間の最短経路」ではアルゴリズムが違う (同じでもいいんだけど変えた方が効率的) ので, どちらかによって方針が変わります.
「1点から他の点への最短経路」だと Dijkstra のアルゴリズムがいいと思います. それほど難しくありませんし, ほぼベストに近い時間でできると思います.
「全点間の最短経路」の方は, Dijkstra のアルゴリズムを繰り返してもいいけど他にもやりかたはあったはずです. 忘れましたが.
そうそう, 言語を決めてもらえると話が楽になります.
なるほどです。勉強になります。
言語は非コンパイル言語であれば、何でも良いと思っております。
PERL,SHELLとかのスクリプトで実現可能でしょうか。
「全点間の最短経路」を見つけたいと思っております。
参考サイトとかないでしょうか。。
No.1
- 回答日時:
「できれば C 以外」という理由がよくわからんのだけど, 「C で書かれたものを別の言語にコンバートする」のはダメ?
metric に負のものがなければ Dijkstra の方法でできそうなんだけど, どうやって優先順位キュー (ヒープ) を作りますかねぇ.
"C"で書かれたものを別の言語にコンバートすることでも、問題ありません。「できれば C 以外」というのは、私が理解できない分野なので、、、すみません。
metricに負の値ものはありません。
Bestな経路が1つ抽出されれば良いのですが、むずかしそうですね。
お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!
関連するカテゴリからQ&Aを探す
おすすめ情報
- ・漫画をレンタルでお得に読める!
- ・街中で見かけて「グッときた人」の思い出
- ・「一気に最後まで読んだ」本、教えて下さい!
- ・幼稚園時代「何組」でしたか?
- ・激凹みから立ち直る方法
- ・1つだけ過去を変えられるとしたら?
- ・【あるあるbot連動企画】あるあるbotに投稿したけど採用されなかったあるある募集
- ・【あるあるbot連動企画】フォロワー20万人のアカウントであなたのあるあるを披露してみませんか?
- ・映画のエンドロール観る派?観ない派?
- ・海外旅行から帰ってきたら、まず何を食べる?
- ・誕生日にもらった意外なもの
- ・天使と悪魔選手権
- ・ちょっと先の未来クイズ第2問
- ・【大喜利】【投稿~9/7】 ロボットの住む世界で流行ってる罰ゲームとは?
- ・推しミネラルウォーターはありますか?
- ・都道府県穴埋めゲーム
- ・この人頭いいなと思ったエピソード
- ・準・究極の選択
- ・ゆるやかでぃべーと タイムマシンを破壊すべきか。
- ・歩いた自慢大会
- ・許せない心理テスト
- ・字面がカッコいい英単語
- ・これ何て呼びますか Part2
- ・人生で一番思い出に残ってる靴
- ・ゆるやかでぃべーと すべての高校生はアルバイトをするべきだ。
- ・初めて自分の家と他人の家が違う、と意識した時
- ・単二電池
- ・チョコミントアイス
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
正しい五十音順について
-
携帯のパスワードについてです。
-
アルゴリズム習得方法
-
期間重複チェックがわかりません
-
多変数関数の最小値を求めるプ...
-
アルゴリズムの学習サイト
-
ランダムサーチ(改)!!
-
連立方程式を解く
-
ライントレース アルゴリズム
-
プログラミング
-
アルゴリズムとプロトコールの違い
-
退化木をバランス木にしたい
-
最短経路を計算するプログラム
-
詰め将棋をとくのは、アルゴリ...
-
最短経路問題を1つ算出するスク...
-
65536は2の何乗なのでしょうか?
-
VBAにてメール作成した際、一部...
-
ゲーミングPCに入っているAlris...
-
Excelで4096点以上のFFTの方法
-
excelのexe化について
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
正しい五十音順について
-
SNSをやらない理由ってなんです...
-
アルゴリズムとプロトコールの違い
-
[ EXCEL VBA ] 図形を読み込む...
-
BCDについて
-
期間重複チェックがわかりません
-
最大公約数を求めたい!
-
c言語で画像から文字を認識 キ...
-
C♯で電卓を作成しています。演...
-
多変数関数の最小値を求めるプ...
-
画像から文字を認識してテキス...
-
ハッシュアルゴリズム
-
偏りのある乱数のアルゴリズム
-
乗換案内の作り方が知りたいです。
-
JPEG圧縮で8×8に分割する理由に...
-
書籍のソースコードを別言語に...
-
グループを均等に分けるには?...
-
複数の点を最短距離で全て繋ぐ...
-
gooという検索エンジンの後にGo...
-
シードを考慮したトーナメント...
おすすめ情報