Regarding the Solution of Hamiltonian Circuit Problem
Using Experimental Graphs or
the Method of How to Control One's Fortune


検定グラフによるハミルトン閉路問題の解法
あるいは幸運をコントロールする方法について
■この論考は，１９９３年に日本経済を突如として襲ったバブル崩壊のもたらした思いもかけぬ産物であったと言えるかもしれない．この深刻でかつ長期にわたる低迷期の到来は筆者の生活にも大きな影響を及ぼすものとなり，１日のうちの１２時間から１６時間をコンピュータのプログラミングに費やすというそれまでのスタイルは否応なく廃止され，自由に処分できるかなりの時間が経済的困窮と引き換えに与えられることになった．１９９５年１１月，故障したエアコンの代わりに急きょ暖房器具に仕立て上げられた古いオーブントースターがささやかな熱を放射する部屋の中で，この研究はスタートした．

■第１章では，本研究を始めることになったいきさつと経緯を延べ，ハミルトン検定法がどのような問題を内包し，それをどのように解決しようとしているかの展望を与える．第２章では定理の証明を含む詳細な説明を行い，ハミルトン検定法の全容を明らかにする．第３章ではハミルトン閉路問題の根底にある非決定性がどのような現象として現れるかを解明し，それを克服するための戦略について論じる．第４章ではハミルトン検定法のアルゴリズムを実装レベルで詳細に検討する．第５章ではハミルトン検定法の計算コストの試算を行なう．第６章には本研究途上で確認されたいくつかの興味ある小問題や失敗例を独立に扱う．第７章ではいくつかの手書きによる解法の例を挙げ，解説する．第８章はまとめと，残された研究課題，今後の展望について述べている．

那須路郎

株式会社 馬場研究所 代表取締役
日本ソフトウェア科学会会員