ダイクストラ法の計算量の求め方を知ってらっしゃる方いますか?
できれば、ダイクストラ法のプログラムも教えてください。

A 回答 (2件)

ここにソースが載ってます。


参考になるといいですね。


http://www-or.amp.i.kyoto-u.ac.jp/members/ibarak …
    • good
    • 0

これですか?



アルゴリズム辞典で調べた方が詳しいかもしれません。

参考URL:http://www.yilab.tutics.tut.ac.jp/aki/ZEMI/dijks …
    • good
    • 0

お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!

このQ&Aを見た人が検索しているワード

このQ&Aと関連する良く見られている質問

QA*アルゴリズムとダイクストラ法について

A*アルゴリズムとダイクストラ法について質問です。

(1)A*アルゴリズムは万能のように思えるのですが、どのようなデメリットがありますか?
(2)ダイクストラ法がA*より優れている点はありますか?

A*アルゴリズムを調べてみたのですが主なデメリットは見つけられなかったので疑問に思いました。

回答よろしくお願いします

Aベストアンサー

 先日久しぶりに、ダイクストラ法のサブルーティンを書いたばかりです^^。
 A*に関しては、

  http://www.weblio.jp/content/A*%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0

を参考にしています。

 ダイクストラさんのオリジナルでは、探索パスを現時点での既知の最最短経路に絞る事で、不要に遠い点への探索を避け、効率化をはかっていると思います。特にそういう事をせず、現時点で行ける点を全て探索し、最小コストのパスを選んでも、ダイクストラ法は成立するはずです。これを勝手に、基本ダイクストラと呼んでます(こっちの方が、論理がわかりやすいので)。

 ダイクストラ法は、A*のヒューリスティック関数h*を、現時点での既知の最最短経路評価が最適と仮定するのと、等価と思えます。h*をどうやって推定するかをおいとけば、もっと最適なh*があるなら、不要に遠い点をより無視できて、もっと探索効率は上がるはずです。というわけで効率は、


  基本ダイクストラ(最適化なし)<ダイクストラ(暫定最適化)<A*(もっと最適化)

となり、理屈の上では、A*のデメリットはない気がします。

 とすれば後は、実際上の問題です。

(1)単純な最短路検索の場合
 参考URLによれば、この場合、h*として2点間の直線距離でもとれば良いと書いてますので、是非A*という事になりますが、自分は何故かダイクストラ(オリジナルの)をとりたいです。理由は次で述べます。

(2)時間最短経路の場合
 例えば道路ネットワークを考えた場合、距離最短に従ってドライバーの皆さんがある道路に集中すると、その道路は混んで渋滞し、走行速度が下がります。ご存知かも知れませんが、幹線道路には設計交通量というのがあり、それを越えた場合の走行速度降下曲線みたいなものまで用意されてます。

 こういう場合は、時間最短です。この時、h*の推定はかなり鬱陶しい気がします(サブルーティンが数個増える!)。対して、ダイクストラを時間最短用にするのは、きわめて簡単です。というか、距離最短でも時間最短でも、そのまんまダイクストラが使えます。

 自分はもともと土木系で、現在は、上流から下流までたった一人のApplicationプログラマーをやってますが(つまり、この部署はたった一人^^)、状況に応じて方法を切り替えるApplicationというのは、嫌です。コーディング量,Bugの量,テスト量,仕様書の文書量,メンテナンス量まで全部増加するからです。単純明解がいい~~!。

(3)対話型Application
 (1)と(2)の答えは、どんな方法を使っても一つです。そうでない場合は対話型になります。例えば「この道路を通ると、何故か速いんだよね~」といった経験事実がある場合です。これh*に使えますよね?。しかも(1)と(2)のような紋切り型の解でなく、現場の状況をより反映した応答を出せます。この時は、A*だと思います。

参考URL:http://www.weblio.jp/content/A*%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0

 先日久しぶりに、ダイクストラ法のサブルーティンを書いたばかりです^^。
 A*に関しては、

  http://www.weblio.jp/content/A*%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0

を参考にしています。

 ダイクストラさんのオリジナルでは、探索パスを現時点での既知の最最短経路に絞る事で、不要に遠い点への探索を避け、効率化をはかっていると思います。特にそういう事をせず、現時点で行ける点を全て探索し、最小コストのパスを選んでも、ダイクストラ法は成立するはずです。これを勝手に、基...続きを読む

Q計算量の少ないn乗根の求め方

現在C++であるクラスのインスタンスaのN乗根を求める関数を作成中なのですが、どうしても実行時間が長くなってしまいます。
現在ニュートン法に則って
X(m+1)=((N-1)(Xm)^N+a)/(N*(Xm)^(N-1))
という漸化式を回して変化量が一定値以下になったら終了という関数なのですが、
値によっては累乗計算のところで時間を大幅にロスしてしまうようです。
原因としては累乗計算が同じ数をN回掛けるという単純な仕組みなため、
Nが大きすぎるとループがなかなか終わらないということがわかっています。
もしご存知であれば
1.極力累乗計算を使わないN乗根の求め方
2.計算量の少ない累乗計算の仕方
のどちらかを教えていただけないでしょうか?
なお、クラスを使っている関係上powなどの既存の関数は使えません。
よろしくお願いいたします。

Aベストアンサー

ああ, そういうことですね.... じゃあ, (非負整数乗に限定して) べき乗を高速化する方法で:
普通は 2乗と乗算を組合せる方法を使うと思います. 「ロシア乗算」などと言われる方法のべき乗版です.
例えば
double pow2(double x, unsigned int n)
{
double ans = 1;
while (n) {
if (n % 2) {
ans *= x;
}
x *= x;
n >>= 1;
}
return ans;
}
でしょうか. 全ての n に対して最適ということではない (n = 15 だと「3乗してから 5乗」の方が速い) のですが, たかだか log n 回の 2乗と同じくたかだか log n 回の乗算からなり, ほぼ最適です.

Qダイクストラ法の解説ページ

ダイクストラ法の内容を分かりやすく説明しているホームページなどあれば教えてください。
よろしくお願いします。

Aベストアンサー

これなんか追っかけてみればいいかも。
デモも有るようです。

参考URL:http://www.me.sophia.ac.jp/or/lab/ishizuka/OC/spath_00.html

Q時間計算量、空間計算量とは何でしょうか?

時間計算量、空間計算量とは何でしょうか?
大学の課題ででた問題ですが全く分からないのでお力を貸していただきたいです。
時間計算量、空間計算量とは何かを調べまた、バブルソートの時間計算量と空間計算量を求めよという問題が出たのですがさっぱり分かりませんでした・・・
どこか分かりやすいサイトなどに誘導してもらえるとうれしいです。

Aベストアンサー

「計算量」で検索したら3つ目にありましたけど・・・?
調べただけで中を読まなかったら何もわかりませんよー

http://akademeia.info/index.php?%B7%D7%BB%BB%CE%CC

Qインターネット上でのローカル線の路線検索!

ヤフーの路線検索で例えば、秋葉原から新横浜へ検索すると、秋葉原→東京→新横浜(新幹線)というかたちになります。
新幹線でなく、普通の急行料金かからない形で検索したいのですが、Yahoo路線ではそういう検索ができないのでしょうか。なにかそれ以外の路線検索で急行料金かからない路線を検索するサイトはないでしょうか。ご存知の方、よろしくお願い致します。

Aベストアンサー

MSNの路線検索がよいと思います。
新幹線・特急・飛行機を使わないようにできますし、経路指定できます。出発地の履歴の機能もあります。

参考URL:http://transit.jp.msn.com/

Q最近隣法を求めるプログラム。

データを配列に入れる所まではいったのですがうまくできません。お願いします。

Aベストアンサー

なんとかなるって。

というのは冗談で、

入力データは、どういうもので、どういうものを出力したいのかぐらいは書いてください。

Q京都~津(三重)までの路線検索

よろしくお願い致します。

近々、京都から三重県の津に行こうと思っていて、
路線検索をしています。

ですが、津はJRでなく近鉄のようで、gooのようなポータルサイトで
路線検索すると名古屋の方に行くような経路になり、遠回りになります。

そこで質問なのですが、京都から三重県の津駅までの路線検索
ができるページはないでしょうか。つまりJRと近鉄両方の路線を
ごっちゃで検索するということです。

どなたかアドバイスをお願いします!!!

Aベストアンサー

#2です。

ふと気付いたのですが、gooの路線検索は私が紹介した駅探のエンジンを使っていますね。
出てこないのは、表示件数がデフォルトで3つになっているからでしょう。
条件設定のところで件数を5件にすれば出てきます。

Qニュートン法を使って解を求めるC言語プログラム

C言語を使って y=x^2-4x のyの解をニュートン法を使って求める
プログラムを作る課題を出されたんですが、ニュートン法が良く分かっていないので、いろいろ調べたり、人に聞いたりしたところ
#include<stdio.h>
#include<math.h>
void main()
{
int counter=0;
double an,g,f,sh=0.0001;
printf("初期値を入力して下さい==>");
scanf("%ld",&an);
do{
g=(an*an)/(2*an-4);
f=2*an-4;
counter++;
}while(fabs(f)>sh);
printf("反復回数 %d 回 y=%lf \n",counter,g);
}
でプログラムがこんな感じになったんですが、結局ニュートン法がどうなのかがわかりません。 なんか微分とかやるとか言われたんですが、工業系の学校で数学の授業が無いので微分についてがわかりません。
このプログラムは、コンパイルはできるんですが、動きません。
ニュートン法についてよくわからないのでどこが間違ってるかわかりません。 ニュートン法についてできるだけ分かりやすく解説してほしいです。

C言語を使って y=x^2-4x のyの解をニュートン法を使って求める
プログラムを作る課題を出されたんですが、ニュートン法が良く分かっていないので、いろいろ調べたり、人に聞いたりしたところ
#include<stdio.h>
#include<math.h>
void main()
{
int counter=0;
double an,g,f,sh=0.0001;
printf("初期値を入力して下さい==>");
scanf("%ld",&an);
do{
g=(an*an)/(2*an-4);
f=2*an-4;
counter++;
}while(fabs(f)>sh);
printf("反復回数 %d 回 y=%lf \n",counter,g);
}
でプログラムがこんな感...続きを読む

Aベストアンサー

ニュートン法を理解するには、せめて微分の初歩の初歩は理解して下さい。
とりあえず、必要なところだけ。

y=x^2-4x
の解をもとめるには、次のようにします。
計算途中の近似解をa(n)とすると、それを元に得られる、より精度の良い近似解a(n+1)は、
a(n+1)=(a(n)*a(n))/(2*a(n)-4)
として求められます。(ニュートン法の理論から)
これを繰り返していって、
|a(n+1)-a(n)| < 0.0001
となったときに、十分精度の良い解が得られたと判断し、計算を終了します。
(計算終了の閾値0.0001は提示されたプログラムから取りました。)

プログラムの間違いは、下記の2点。
誤:scanf("%ld",&an);
正:scanf("%lf",&an);

誤:f=2*an-4;
正:f=g-an; an=g;

上記を修正し、初期値が2より大きい場合は4.000000が、初期値が2未満のときは
0.000000が求められることを確かめて下さい。

Qダイクストラ法の処理過程表なんですが・・・

ダイクストラの処理過程表を書けという問題があるのですが
参考書にも表が書かれたものがないので書き方が分かりません。
ダイクストラ法自体は分かるのですが・・・・
例えば以下のようなネットワークの場合
(数値は点までの距離です)
  b
4/ \2
a   d---------e
1\ /2 3
  c
ダイクストラ法を使って点aから各点までの最短距離を
求まる順に書き出すと
c(1,a)
d(3,c)
b(4,a)
e(6,d)
となりますが、この場合問題の表は

...点...|...a.|...b..|...c..|...d..|...e..|.........U.......|
初期|0/a|∞/ф|∞/ф|∞/ф|∞/ф.|.{a,b,c,d,e}|
操....|.....a..|.....|......|......|......|.......|...................|
作....|.....b..|.....|......|......|......|.......|...................|
点....|.....c..|.....|......|......|......|.......|...................|
........|.....d..|.....|......|......|......|.......|...............|
........|.....e..|.....|......|......|......|.......|...............|

と与えられていました。どのように書き込んでいけば
いいのか分からないのでどなたかアドバイスお願いします。
(表がわかりにくいかもしれませんがお願いします。)

ダイクストラの処理過程表を書けという問題があるのですが
参考書にも表が書かれたものがないので書き方が分かりません。
ダイクストラ法自体は分かるのですが・・・・
例えば以下のようなネットワークの場合
(数値は点までの距離です)
  b
4/ \2
a   d---------e
1\ /2 3
  c
ダイクストラ法を使って点aから各点までの最短距離を
求まる順に書き出すと
c(1,a)
d(3,c)
b(4,a)
e(6,d)
となりますが、この場合問題の表は

...点...|...a.|...b..|...c..|...d..|...e..|.........U...続きを読む

Aベストアンサー

最後の「U」の欄は, 何を意味しているんでしょうかねぇ. 普通の Dijkstra法だと, 最初は { b, c, d, e } にするような気がする (その方が 1ステップ分だけ処理が短かくてすむから) けど....
その欄を除けば簡単で, 各ステップごとの「その点までの (わかっている範囲内での) 最短距離」と「その最短距離が得られるような経路での, その点の直前に来る点の名前」を書けばいいんでしょう, きっと.

Q文字列探索KMP法の計算量について。

KMP法の計算量についての質問です。
(1)計算量がO(M+N)になるのは何故か?
(2)この計算量は漸近的には改善できない最善のものであると記載されているが、それは何故か?
※テキストの長さ=N、キー(パターン)の長さ=M

参考書を見て勉強していたのですが、計算量については省略されてしまっていたために不明なままです。どなたかご存知の方がいらっしゃいましたらよろしくお願いします。

Aベストアンサー

> (1)

メインな文字列の検索処理についてみると、テキストの個々の文字について1回しか比較を行いませんから、O(N)になります。
ですが、KMPではその前にテーブルを作る必要があります。こちらの処理はO(M)になります。
両方あわせるとO(M+N)です。

> (2)
文字列検索をするためには、「テキストの全ての文字を調べる」必要があり、そのためには最低でもO(N)は必要です。
O(N)より小さい、O(log N) や O(√N) では、全ての文字を調べることができません。
同様に、検索パターンの方も全ての文字を調べる必要があるから、こちら側では最低でもO(M)が必要です。
つまり、両方あわせると、最低でもO(M+N)は必要、ということになります。


人気Q&Aランキング

おすすめ情報