← 図25 あとで調べるほうには、とりあえず「メモ」。
全探索に使うアルゴリズムについて説明しています。 最初に疑似プログラムを載せてあるので、 プログラミングをちょっとかじった人はこれを見ればおおかた理解できるでしょう。 また、そうでない人のために、文章による直観的な説明もつけました。
それでは、全探索のアルゴリズムを説明しましょう。
といっても、アルゴリズムと言うのもはばかられるような単純なものですが。
まず、Pascal 風の（と言いつつ foreach なんてのがある）
疑似プログラムでアルゴリズムを示します。
ちょっと腕に覚えのある人なら、これでだいたい理解できるでしょう。
procedure bks(nowst: 駅);
begin
foreach e (nowst から出ているすべての枝)
if (まだこれまでに枝 e を通過していない) then
if (枝 e の行き着く先の駅はすでに通過している) then
(* タイプ P もしくはタイプ O の経路が1つできあがり *)
else
bks(枝 e の行き着く先);
if (nowst からどこへも行けなかった) then
(* タイプ L の経路が1つできあがり *)
手続き bks に与えられる引数 nowst は「現在注目している駅」です。
その駅から出ている枝のうち、まだ通っていないものをすべて調べていきます。
そして、枝の先がすでに通過済みの駅なら、
そこで経路を打ち切らないと発売条件を満たさないので、
打ち切ってタイプＯもしくはタイプＰの経路ができあがり。
もし枝の先がまだ通ったことのない駅なら、
注目する駅をそこに移して、今と同じ作業を最初からします。
以上のような作業をしようとしたら、
「まだ通っていない枝」が１本もなくて何もできなかった、ということもあります。
こういうことが起きるのは終端駅に到達したときだけですから、
現在の駅で経路を打ち切って、タイプＬの経路が１つ完成です。
この手続き bks に北海道内のグラフを与え、引数に「長万部」を与えれば、 「長万部を発駅とするすべての経路のうち、発売条件を満たしていて、 しかも着駅側でそれ以上延長することのできない経路」を列挙していきます。
「プログラムは苦手だ！」という人のために、直観的な説明を試みます。
たとえば、北海道内の経路のうち、
本州と出入りできるものの中で最長のものを求めるとしましょう。
北海道と本州の境界は青函トンネル内ですが、
青函トンネルから長万部までは経路の選びかたが自明なので、
長万部以東だけを考えます。
本州と出入りするためには長万部を通らなくてはならないので、
以下では「長万部を発駅とし、東へ向かう経路」を列挙することにします。
その中で最長のものを選び出せばいいわけですね。
長万部から東へ向かうとすると、選べる経路は２通り。函館本線か室蘭本線です。 室蘭本線のほうは「あとで調べる」というメモを残しておくことにして、 ひとまず函館本線から先に調べましょう（図25）。
← 図25 あとで調べるほうには、とりあえず「メモ」。
函館本線を進んでいくと、最初に現れる分岐駅は桑園です。 札沼線新十津川方面と函館本線白石方面のどちらを選ぶこともできますが、 函館本線のほうは「あとで調べる」というメモを残しておいて、 先に札沼線のほうを調べます（図26）。
← 図26 さらにメモを置いて新十津川へ。すると…
札沼線に入ると分岐駅はなく、終端駅である新十津川にぶつかります。
終端駅ですからこれ以上は進みようがありません。
したがって、いま調べている経路はこれでおしまい。
今まで通ってきた駅を思い出して、
「長万部→桑園→新十津川」という現在地までの経路を
「最長候補リスト」に加えます。
このように、いま調べている経路を終わりにしてリストに加えることは、
終端駅に到達したとき（タイプＬ）のほかに、
一度通った駅にふたたび到達したとき（タイプＯ or Ｐ）にもあり得ます。
仕事が１つ終わったので、次にやることを思い出すべく、
一番あとに残したメモを読みます（図27）。この場合は、
桑園で残した「函館本線のほうはあとで調べる」というメモが最新ですね。
メモを読むと、それまでやっていた仕事を思い出すことができるので、
それを読んで仕事を再開します。
← 図27 １つ終わったら、最新のメモのある場所へ復帰。
函館本線を東へ進むと、分岐駅である白石にぶつかります。 函館本線岩見沢方面に関してはメモを残しておいて千歳線に進むと、 次の分岐駅は南千歳です（図28）。 石勝線、千歳線沼ノ端方面に関してはメモを残しておいて新千歳空港に進むと、 ここは終端駅なので１つの仕事が終わり、 「長万部→桑園→白石→南千歳→新千歳空港」という経路が最長候補に加わります （図29）。 最近のメモである「南千歳から沼ノ端方面」を取りにいって（図30）、 今度は沼ノ端へ…
← 図28 メモを置きながら進む。
← 図29 おっ、終端駅だ。一丁上がり〜。
← 図30 で、１つ終わったら最新のメモを取りにいく。
こうやっていると、いつかはすべてのメモを読み尽くします。 そして、メモを読み尽くしたときには、 長万部発で最長候補となる経路がすべてリストに加えられている、 という寸法です。
「でも、こんな方法でほんとうにすべての候補を列挙できているの？」
という疑問もあるかもしれません。
そこで、列挙すべき経路を以下のように書いてみました。
省略せずに書くと何万行にもなるので大幅に省略しましたが、
この箇条書きの図を完成させれば、すべての経路を列挙できていることになる、
というのは納得してもらえるのではないかと思います。
その駅から進めるすべての方向をもらさず列挙しているのですから。
さきほどの「メモを残して先に進む」方法をあらためて見てみると、
この箇条書きの図を上から順にたどっています。
これなら列挙からもれる経路はありませんよね。
箇条書きの図を木に見立てると、分岐駅は枝の分かれ目、
「打ち切り」と書いてあるところは「葉」にあたります。
長万部という「根」からスタートした「仕事人」は、
枝の分かれ目ごとにメモを残しながら、まず最初の葉である新十津川をめざします。
そこで仕事を終えたら、メモが見つかるまで枝を逆戻りし、
メモを読んで次の葉へと向かいます。
全部の葉を訪問し尽くせば「任務完了」です。
このような探索手法はよく用いられますが、賢い方法だと、
「ここを探しても絶対に最適解は出てこない」という望みのない枝を早々に見つけて、
ばっさりと「枝刈り」してしまいます（整数計画法もその一例です）。
私たちが今やっているのは、枝刈りをしない「賢くない」方法ですね。(^^;