経路探索の問題

質問

http://www.i.u-tokyo.ac.jp/edu/course/m-i/pdf/2002imim.pdf
の、問題3について質問なのですが、
問1は、
　(1)
線形リストとして、n回で到達できるセルの情報を与えると、n+1回で到達できる線形リストを返す関数を考える。返すリストの作成方法は、n回で到達できるセルの前後左右を調べて、すでに調べたセルや障害物のセルでなければ、そのセルをn+1回で到達できるセルとしてメモし、返す線形リストに追加する。
　(2)
int l[M][N];//特定のセルまでの距離をメモする配列。最初にすべて-1をいれておく。障害物には-2を入れておく。
class list{
　　int i,j;
　　list *next;
　　list(){
　　　　next=0;
　　}
}
//n回で到達できるセルのリストをpl、n+1階で到達できるセルのリストを返すポインタをnlとする。
void getNextCellsList(list *pl,list *nl){
　　list *tt=pl;
　　list *t;
　　int i,j;
　　nl=0;
　　while(tt){
　　　　i=tt->i;
　　　　j=tt->j;
　　　　if(i>0&&l[i-1][j]==-1){
　　　　　　l[i-1][j]=l[i][j]+1;
　　　　　　t=nl;
　　　　　　nl=new list;
　　　　　　nl->i=i-1;
　　　　　　nl->j=j;
　　　　　　nl->next=t;
　　　　}
　　　　if(j>0&&l[i][j-1]==-1){
　　　　　　l[i][j-1]=l[i][j]+1;
　　　　　　t=nl;
　　　　　　nl=new list;
　　　　　　nl->i=i;
　　　　　　nl->j=j-1;
　　　　　　nl->next=t;
　　　　}
　　　　if(i<M-1&&l[i+1][j]==-1){
　　　　　　l[i+1][j]=l[i][j]+1;
　　　　　　t=nl;
　　　　　　nl=new list;
　　　　　　nl->i=i+1;
　　　　　　nl->j=j;
　　　　　　nl->next=t;
　　　　}
　　　　if(j<N-1&&l[i][j+1]==-1){
　　　　　　l[i][j+1]=l[i][j]+1;
　　　　　　t=nl;
　　　　　　nl=new list;
　　　　　　nl->i=i;
　　　　　　nl->j=j+1;
　　　　　　nl->next=t;
　　　　}
　　　　tt=tt->next;
　　}
}
と、したのですが、このgetNextCellsList関数を一回使う時間計算量は、O(n)としていいのでしょうか？
また、もしそうなら問2の時間計算量は、
(getNextCellsList関数を一回使う時間計算量)*M*N=O(n)*O(n^2)=O(n^3)
空間計算量は、
(セルまでの距離をメモする配列の数)+(n回で到達できるセルの情報)=O(n^2)+O(n)=O(n^2)
となるのでしょうか？
あと、この問題の(M,N,D)のオーダーで評価せよというのはどういう意味として捉えればいいのでしょうか？O(n^3)などと書いておくだけで良いのでしょうか？

問3の時間的及び空間的に効率化する方策としてはどのようなものが考えられるのでしょうか？これは、自力では全然ろくな方法が思い付きませんでした。。。

宜しくお願いします。

回答No.6

Tacosan · ベストアンサー

「A から C へいけばいい」ことがわかるので, それまでの情報は全てなかったことにして改めて A から C への最短経路を探す.

お礼

なるほど、確かにそうすれば解が出ますね。

どうも有り難うございました。

回答No.5

Tacosan

一般に A から B への最短経路上に C があるとすると, 「A から B への最短経路」は「A から C への最短経路」と「C から B への最短経路」をつなげることで得られます.
特に「B の直前が C」なら, 「A から C への最短経路」がわかればすぐに「A から B への最短経路」もわかります.
だから「実行時間が犠牲になる」んです.

お礼

確かに、A→C→Bという経路がA→Bの最短経路なら、A→CとC→Bの最短経路をつなぎ合わせることでA→Bの最短経路が求まるのは分かります。
しかし、「特に「B の直前が C」なら, 「A から C への最短経路」がわかればすぐに「A から B への最短経路」もわかります.」とのことですが、最終目的地に着いたときに2ステップ前までの情報しかないのに、どうやって「A から C への最短経路」を求めるのですか？

回答No.4

Tacosan

「ダイクストラ法」が何を指すかは微妙なところですが, 実際には最短距離さえ求まってしまえば線形時間で最短経路も分かるので「最短距離を求める」アルゴリズムを「ダイクストラ法」と読んでもいいのではないでしょうか＞#3. いずれにしても本質的に同じ (今の場合にはさらに幅優先探索とも同等) ですから, 時間的に効率化できるわけではありません. そも線形時間アルゴリズムをどうやってこれ以上効率化しろというのか.
なお, 空間的に効率化することは特に難しくありません... と思ったけど, このアルゴリズムそのままでは不可能だな. 「始点からの距離が明らかになったセルにはその距離を記録する」というのがネックで, ここに MN の空間を使うからには全体でも O(MN) は必須.
実は, 実行時間を犠牲にしていいなら「始点からの距離を記録しない」という選択肢があります. つまり, 今の場合「距離 d のセルに隣接するセルの距離は d-1, d, d+1 のいずれか」であることが保証できますから, 距離 d のセルに対してその隣接セルを調べる」ときには「距離が d-1 であるようなセルのリスト」があれば十分です. 言い換えると, 「距離 d-1 のセルのリスト」と「距離 d のセルのリスト」から「距離 d+1 のセルのリスト」を作る, ということです. そして, 距離が d+1 であるようなセルのリストができれば「距離 d-1 のセルのリスト」は不要なので破棄してかまいません.
このようにすると, 「目標点までの距離」と「目標点までの最短経路上で目標点の直前のセル」が分かります. まじめに考えてないけど「特定の距離を持つセルの数」はたぶん線形だと思う.

お礼

＞距離 d のセルに対してその隣接セルを調べる」ときには「距離が d-1 であるようなセルのリスト」があれば十分
それは確かにそうですが、それだと、最後に目標のセルに到達したとき持っている情報は、目標のセルを見付けた2ステップ前までの情報しか持ってないことになりますよね？そこからどうやって、最短経路を辿るのですか？

回答No.3

Interest

ANo.1 = Interest です。
ご指摘の通り、「すでに調べたセル」のチェックは正しく網羅されていますね。すみません、私の間違いでした。

それから、

> これ自体が特殊な場合のダイクストラ法に当たると思うのですが、

問３の（１）の方法では全セルに対してスタート地点からの距離を埋める探索過程と最短ルートを求める経路決定過程がありますが、ダイクストラ法では探索過程の途中で最短ルートが決まります。したがって、別物だと思います。

ダイクストラ法以外だと、深さ優先探索と幅優先探索くらいしか思いつきませんでした。＜空間計算量、時間計算量のトレードオフを狙っているので

お礼

＞問３の（１）の方法では全セルに対してスタート地点からの距離を埋める探索過程と最短ルートを求める経路決定過程がありますが、
この方法も、n+1階で到達できるセルのリストとして、返ってくるリストの中に、目標とするセルがはいっているかを調べて、もし入っていたらその時点で終了するので、探索過程の途中で終了しますよ。

＞ダイクストラ法以外だと、深さ優先探索と幅優先探索くらいしか思いつきませんでした。
深さ優先探索と幅優先探索は、経路を辿る手法ですよね？
ここに挙げているプログラム自体の探索方法は、幅優先探索に該当すると思うのですが、深さ優先探索で経路を辿る場合、どのようにして最短経路であるということを調べていくことになるのでしょうか？

回答No.2

Tacosan

かなり問題に特化してはいますがダイクストラ法ですね.
で「効率化」ですが, とりあえず「オーダの意味で時間的に効率化する」ことは不可能です. 現時点で時間計算量は #1 で示されている通り O(MN) ですが, この問題においてベストでも Ω(MN) 時間かかる入力が存在することは容易に示せます (2点間の距離 D が Θ(MN) となる入力が存在する).
逆に空間的に効率化することは (時間計算量を犠牲にすれば) 可能です.
なお, 変数名についてですが「length」というと「隣接する 2点間の距離 (= 長さ)」の意味で使うことが多いと思います. 今のような場合には距離 (distance) を使う方が自然でしょう.

お礼

＞「オーダの意味で時間的に効率化する」ことは不可能です.
とすると、この問題的には、どのように時間的に効率化することを要求されているのでしょうか？

＞逆に空間的に効率化することは (時間計算量を犠牲にすれば) 可能です.
動的に生成する変数の型を変更するか、intなら、32ビットの情報を格納できるので、これをフルに使い切るようにする整数クラスをつくるか、PNGのような可逆圧縮をマップにうまく適用してやるのか、位しか思い付かないのですが、どのような有効な方法があるでしょうか？

回答No.1

Interest

問１の(1)の答案について。

考え方は要点を押さえていて概ねよいと思います。しかし、仕様として考えた場合表現上曖昧な部分がいくつかあります。

> n+1回で到達できる線形リストを返す関数を考える。

n+1回で到達できる「セルの」線形リストを返す関数、ですよね。

> n回で到達できるセルの前後左右を調べて、

問題文にはどちらが前後左右なのか指定されていません。前後左右とはどういう意味でしょうか？　私なら例えば「現在着目しているセルを(Ci,Cj)として、(Ci-1,Cj), (Ci+1,Cj), (Ci,Cj-1), (Ci,Cj+1)について～」のような表現にします。同様に、「すでに調べたセル」や「そのセルをn+1回で到達できるセルとしてメモし」というのも、どういう意味なのか誤解を生まないよう定義して使った方がよいのではないかと思います。

続いて、問１の(2)の答案について。

ソースコード全体では、class を使っていてオブジェクト指向な設計かと思いきや、全然そうじゃない。C++を使うのであれば、標準ライブラリに list があるので、わざわざ自分で書く必要が無いでしょう。

> int l[M][N];

l（エル）は誤読しやすいので map や cell など意味のわかる名前がいいですね。私の個人的な好みの話ですが。その他、ちゃんと検証してはいませんが演算子の優先順にや、newがあってdeleteが無いなど、非常に危険な臭いのする個所が多々あって、おそらく狙い通りには動かないんじゃないかと思います。コンパイルも通らない可能性あり。

そういえば、このソースコードだと「すでに調べたセル」についてチェックしてませんね。

なので問２については、問１のアルゴリズムを正しく表現できていないので、時間計算量のオーダーも違うんじゃないかと思います。おそらく、ベタなやり方で問１のアルゴリズムを実現すると計算量のオーダーは、
　（探索過程の計算量）＋（経路決定過程の計算量）＝ O(MN)＋O(D)
で、MN > D は明らかなので、最終的には O(MN) になるんじゃないでしょうか。また、問２は空間計算量（メモリの使用量）についても見積もるよう指示しているので、こちらも書かないと片手落ちになりますね。

問３について。
よく知らている最短経路問題の解法では、ダイクストラ法があります。
http://www.deqnotes.net/acmicpc/dijkstra/

お礼

>そういえば、このソースコードだと「すでに調べたセル」についてチェックしてませんね。
この問題の場合、初期位置で前後左右(明確性を欠いていると指摘されましたが、表記の簡易のため、この問題に該当する意味で使います)を調べ、その調べたセルに障害物などもなくいける場合そこは、調べたセルは1回で行ける場所なので、初期位置からその調べられたセルへの最小距離は明らかに1となる。そして、この距離をl[M][N]に記録する。
次に、この1回で行けるセルから、更にもう1回で行ける場所を調べる。1回で行ける場所は線形リストとして、補完されているから、そのリストに該当する、i,jを調べることを考える。ここで、l[i-1][j]が1なら、1回で到達したセルということになる。逆に、-1なら、1回では到達できなかったセルということになるので2回で到達できることが確定する。i,ｊについて同様に前後左右を調べる。当然これを1回で到達できるセルとして記録されたリスト全体で行う。
この処理をずっと続けていくことを考えると、n回目でl[i-1][j]が-1なら、n回未満では到達できないセルということになるので、l[i-1][j]はn+1回で到達するセルということになる。
つまり、l[M][N]の中で-1でない場所はすでに確定されたセルとなる。

ということです。

>よく知らている最短経路問題の解法では、ダイクストラ法があります。
これ自体が特殊な場合のダイクストラ法に当たると思うのですが、時間的に効率化するにはどのようにすればいいでしょうか？

空間的に効率化する方法は、M,Nの値によって、動的に使用する変数の型を変える位しか思い付きません。
こちらの方も何か良い方法があれば教えていただけると幸いです

補足

書ききれなかったので、補足とお礼に分割して書かせていただきます。

>n+1回で到達できる「セルの」線形リストを返す関数、ですよね。
その通りです＾＾；
「セルの」ってのが抜けてましたね

>私なら例えば「現在着目しているセルを(Ci,Cj)として、(Ci-1,Cj), (Ci+1,Cj), (Ci,Cj-1), (Ci,Cj+1)について～」のような表現にします。
確かに明確な表現としては、前後左右より、(Ci,Cj)と表記すべきですね。

>標準ライブラリに list があるので
C++にlistクラスがあるのは知ってたのですが、このクラスについて私が余りよく知らないもので、作ってしまいました^^；
標準のlistは双方向リストとして作られていますが、今回の場合は、片方向でも計算量は変わらずにメモリ空間の量を減らせるのでこっちの方が多少メリットあるかな？
まあ、テストで記述を簡略化できるという点では、listクラスを勉強した方が良いのかな・・・

>l（エル）は誤読しやすいので map や cell など意味のわかる名前がいいですね。
今回のはlengthの意味で手っ取り早く思い付いたので、変数にlを使いましたが、見にくいといわれれば、確かに、見にくいですねー

>newがあってdeleteが無いなど、
これは、n+1回で到達できる座標をnlに返す関数だけを示している状態なので、deleteは無いのです。
まあ、今考え直すと、class listはdataにでも名前を変えて、新しく作り直したclass listを考えた場合、listのデストラクタで、listが持っているdataをdeleteするような形で作り、void getNextCellsList(list *pl,list *nl)をこの新しいlistのメンバ関数として設計する方がスマートだったかなー