[logo] Web連載「数学ガールの秘密ノート」
Share

第417回 シーズン42 エピソード7
次の一歩はどっちかな?(前編)

$ \newcommand{\TEXT}[1]{\textbf{#1}} \newcommand{\REMTEXT}[1]{\textbf{#1}} \newcommand{\GEQ}{\geqq} \newcommand{\LEQ}{\leqq} \newcommand{\NEQ}{\neq} \newcommand{\ABS}[1]{|#1|} \newcommand{\SET}[1]{\{#1\}} \newcommand{\TRUE}{\textbf{true}} \newcommand{\FALSE}{\textbf{false}} $

登場人物紹介

:数学が好きな高校生。

テトラちゃんの後輩。 好奇心旺盛で根気強い《元気少女》。言葉が大好き。

リサ:自在にプログラミングを行う無口な高校生。コンピュータを自在に操る赤い髪の《プログラミング少女》。

図書室にて

テトラちゃんリサと共に最短経路問題に取り組んでいた(第416回参照)。

正確には、彼女たちの議論にが後から加わった形になる。

リサの提案ではまず最短経路の距離を求める問題に取り組んだけれど、 テトラちゃんは具体的なアルゴリズムを提示して、 のスケッチに駄目出しをした。

いったいどこにバグがあるんだろう?

問題(再掲)

グラフ $G$ と二頂点 $s,g$ が与えられているとき、 $s$から$g$までの最短距離を求めるアルゴリズム$\text{SHORTEST-PATH-LENGTH}$を考えてください。

  • グラフの頂点と辺は有限個とします。
  • 辺の重みはすべて $1$ とします。
  • グラフ $G$ から頂点全体の集合を得たり、頂点に隣接している頂点全体の集合を得たりする手続きは適宜与えられているものとします。その他、必要な手続きは補って考えてください。

入力

  • グラフ $G$
  • スタートの頂点 $s$
  • ゴールの頂点 $g$

出力

  • $s$ から $g$ までの最短距離

グラフ $G$ の例(この場合の出力は $3$)

「……テトラちゃんはすでにアルゴリズムをちゃんと清書していたんだね!」

テトラ「はい……でも、 でも、これじゃうまくいかないんです!」

テトラちゃんが提示した$\text{SHORTEST-PATH-LENGTH-TETRA}$を読む。

テトラちゃんの$\text{SHORTEST-PATH-LENGTH-TETRA}(G,s,g)$

「A2からA4では、初期化を行っているんだね。 つまり、グラフ $G$ のすべての頂点 $v$ について、 $$ v.\text{visited}\leftarrow\FALSE $$ とすることで未訪問であることを表した。 そしてA5ではスタートとなる頂点 $s$ に対して、 $$ s.\text{visited}\leftarrow\TRUE $$ とすることで訪問したことを表した。 これは間違っていないよね?」

テトラ「はい、少なくともその処理自体は間違っていません。 そして$\text{LENGTH-TETRA}$で再帰的に$s$から$g$までの最短距離を得ています……得ようとしていますが、 実際のところ、これでは最短距離は得られないんです……」

テトラちゃんの$\text{LENGTH-TETRA}(G,s,g)$

「ざっと見た感じではうまく行きそうなんだけどなあ……。 どこかにバグがあるってことだよね。 ええと——」

テトラ「……」

「うーん……アルゴリズムは難しいね。 具体的なグラフを見れば少し試すだけで最短距離はわかる。 たとえば、さっきのグラフの例だと最短距離は $3$ になる。 でも、アルゴリズムは、どんなグラフでも最短距離が得られるようにしなくちゃいけないんだよね」

テトラ「そうなんです。ところで先輩はあたしの$\text{LENGTH-TETRA}$をどのように読みましたか」

「読み方が悪い」——とテトラちゃんあおってきたように感じて、 は、ほんの少しムッと来た。

でも、彼女の真面目な顔を見ては気持ちを落ち着ける。 考えてみればテトラちゃんが意地悪で煽ってくるはずがない。 彼女は真摯に尋ねているのだ。

「どのように読んだか? そりゃ、B1の行から順に読んでいったよ。 そして、おおよそこういう動きなんだなとつかんだけど、僕にはどこにバグがあるか、まだわからない」

B2からB4

テトラ「アルゴリズムは、 さらさらっと読むのではなく、 自分がコンピュータになった気持ちで読むのだそうです(『数学ガール/乱択アルゴリズム』参照)」

「それは僕も聞いたことがある。まだピンと来てないところはあるけど……順番に読んでいくとして、 たとえば、$\text{LENGTH-TETRA}$のB2からB4までは、 『もしも $s = g$ なら出力は $0$』ということだと思う」

B2からB4

テトラ「そうですね。プログラムの文面を文字通り読めばそうですし、 少し抽象度を高くすると『もしもスタートとゴールが一致しているなら、最短距離は $0$』と読むこともできます」

「なるほど。『$s = g$』よりも『スタートとゴールが一致』の方が具体的なのに『抽象度が高い』っておもしろいね」

テトラ「ああ、言われてみればそうですね! なぜでしょう……たぶんですけれど、 機械に近い方が抽象度が低くて、意味や解釈が加わるほど抽象度が高いんでしょう」

B5からB15

「$\text{LENGTH-TETRA}$のB5からB15までは、 スタートの $s$ に隣接した頂点 $v$ 一つ一つに対して、 $v$ から $g$ までの最短距離を再帰的に調べていて……うん、 B12で $l + 1$ を出力しているのは『$v$ から $g$ までの最短距離 $l$ に、 $s$ から $v$ までの $1$ を加えている』 ってことだよね。 $l$ がどうして $v$ から $g$ までの最短距離かというと、 B8で $$ l\leftarrow\text{LENGTH-TETRA}(G,v,g) $$ と代入してるから。 ここで$\text{LENGTH-TETRA}$を再帰的に使っていることになる。 うん、だから何がバグってるかよくわからない」

B5からB15

テトラ「この$\text{LENGTH-TETRA}$では深さ優先探索になってしまうんです」

「深さ優先探索?」

テトラ「はい。先輩がおっしゃるように、 B5からB15までは $s$ に隣接した頂点 $v$ 一つ一つを調べていき、 $v$ から $g$ までの最短距離を再帰的に得るんですけれど、 再帰的に$\text{LENGTH-TETRA}$を呼び出すときの呼び出し方が重要になります」

「ははあ……そういえば、深さ優先探索の話も聞いたことがあったなあ(第296回参照)」

テトラ「$s$ に隣接した頂点 $v$ を一つ選んで(B5)、 もしもその頂点 $v$ が未訪問だったら(B6)、 まず訪問済みの印を付けます(B7)、 そして次です! 次にB8で$\text{LENGTH-TETRA}$を呼び出してしまいます。 つまり、 $v$ から先の経路を調べ始めてしまいます。より深い探索に入ってしまうんですね。 だからこのアルゴリズムは深さ優先探索になります」

はそこでちょっと考える。

深さ優先探索だと何がまずいのか……。

「そうか! 深さ優先探索だと、見つかった距離が最短距離になっている保証がないんだね!」

テトラ「ですです。たとえば先ほどの例だと、 最短経路はこっちで距離は $3$ なんですが——」

最短距離の経路(距離は $3$)

「……」

テトラ「深さ優先探索だと、 こういう経路が見つかってしまって $5$ を最短距離としてしまう間違いになるかもしれません」

深さ優先探索で見つかってしまうかもしれない経路(距離は $5$)

「確かにね……なるほど。 テトラちゃんがいう『B8で$\text{LENGTH-TETRA}$を呼び出してしまう』という感覚がわかったよ。 頂点 $v_1,v_2,v_3,v_4$ のどれが最短経路の一歩目になるか、まだわかってないうちから、 $v_1$ から先に深く $x$ へ進んで $g$ までの経路が最短だと決めつけて進むのは、そりゃまずいね。 最短経路を探すのに深さ優先探索はまずい……」

頂点 $v_1,v_2,v_3,v_4$ のどれが最短経路の一歩目になるかはわからない

テトラ「もちろん、深さ優先探索をしてたまたま・・・・最短距離が見つかることもあります。 でもそれは偶然そうなっただけですし、 与えられたグラフ $G$ と、 $s$ に隣接した頂点集合から頂点を取り出す実装に依存する話です」

「実装に依存するというのは、どういうこと?」

テトラ「あっ、すみません。 動作するプログラムを実際に作る場合には、 $s$ に隣接した頂点集合の中から頂点をどのような順番で選んでくるかを決めなくてはいけません。 同じグラフ $G$ であっても、最短距離になるかどうかは、その選ぶ順番に依存してしまうという意味です」

「なるほど」

テトラ「あたしも深さ優先探索のアルゴリズムを最初に書いてしまったんです。 探索の方向性がまちがっていることはリサちゃ……リサに指摘されました」

は、リサを見た。

テトラちゃんが話を続けている間、 彼女はずっと無言でタイピングを続けている。

「深さ優先探索じゃなくて——」

リサ幅優先探索

リサは、僕たちにノートブック・コンピュータの画面を見せた。

幅優先探索

「これが……幅優先探索で $s$ から $g$ までの最短距離を求めるアルゴリズムになるの?」

リサ「そう」

無料で「試し読み」できるのはここまでです。 この続きをお読みになるには「読み放題プラン」へのご参加が必要です。

ひと月500円で「読み放題プラン」へご参加いただきますと、 434本すべての記事が読み放題になりますので、 ぜひ、ご参加ください。


参加済みの方/すぐに参加したい方はこちら

結城浩のメンバーシップで参加 結城浩のpixivFANBOXで参加

(2024年2月23日)

[icon]

結城浩(ゆうき・ひろし) @hyuki


『数学ガール』作者。 結城メルマガWeb連載を毎週書いてます。 文章書きとプログラミングが好きなクリスチャン。2014年日本数学会出版賞受賞。

Twitter note 結城メルマガ Mastodon Bluesky Threads Home