8.聖徳太子曰く,和を以って貴しと為す


この草稿は1996年3月1日現在までの研究成果の一部を辛うじて成文化したものであり,研究として未完の部分があるというだけでなく,章立てのみでまだ記述されていないかなりの部分を残している.当然まだ後書きを記すような段階にはないので,ここまでの簡単なまとめと今後の見通しを述べてひとまず筆を置くことにする.


○ どこまで進んだのか?

現段階におけるハミルトン検定の大まかな概念図を以下に示す.

□ 端子グラフ分割はグラフを右部分グラフと左部分グラフに分割し,再帰的に検定を進める方法であり,検定コストを劇的に削減する効果がある.探索コスト的な理由からたとえば,2,3端子のみを選択して行なうというような制限付きでインプリメントされる.端子グラフ分割はハミルトン検定の最上層で実行される.

□ 3種検定には,IO分割検定,メッシュ図検定,直並列検定の3種の検定を含み,短絡グラフ法を主に補助する目的で実装される.@3種検定によってある種のグラフを無試行判定により,非ハミルトングラフとして分離することができる.A原グラフないし短絡グラフを対象として3種検定を行なうことによって,因子検定で検出できない段階の矛盾を早期に検出することができる.Bまた,3種検定上の制約条件によって任意選択操作における自動確定プロセスを促進する.

□ IO分割検定はグラフを左右の部分グラフに分割し,2つの部分グラフの通路となる点ないし枝のインタフェースを検査する方法であり,端子分割検定とカットセット分割検定を含む.いずれもコスト的理由からグラフ上のすべての分割を実行することはできないから,任意選択によって確定ないし削除された枝ないし点のみに関る分割のみの検定を実行する.

□ メッシュ図検定はグラフの各点に点ポイントを与え,点スコアと枝スコアを計算することによって,グラフの枝の配分を制約条件に従って規制することができる.端子分割検定困難なグラフの検定に適している.

□ 直並列検定はグラフをハミルトン直並列簡約することによって得られる簡約グラフを検定することによって,グラフのトポロジカルな矛盾を検出する.

□ 短絡グラフ法は因子検定をベースとしたハミルトン検定の基盤となる検定法であり,短絡グラフ法によって,ハミルトン検定の各段階を短絡縮約されたグラフのハミルトン検定として再帰的に実行することが可能となるので,3種検定を検定プロセスに実装することを理論的に可能なものとする.短絡グラフ法は最悪全数検定となる場合があり得る.

□ 復活木による再生変換を用いた無時間検定法は,短絡グラフ法の限界を打破し,決して後戻りしない検定を実現するものである.無時間検定法では短絡グラフのデッドロックする確定パスから半点グラフとして構成される再生マップを生成し,これから矛盾を解消するための復活木を導出して,デッドロックしない再生パスを取得することができる.デッドロックマップの範囲を逸脱する検定になっている場合には,無時間検定は再帰的に実行される.

□ 短絡グラフ法においてハミルトンパスを得られた段階でロックアウトした時,グラフから切り出すことのできる極大なハミルトンパスを取り出した上でこれらの材料からハミルトンタイを求めるために,第1章で紹介したスイッチパネルゲームを実行する.スイッチパネルゲームが実現可能であるか否かは現在のところ明らかではない.スイッチパネルゲームはハミルトン検定の1小問題として定式化される.ハミルトン検定問題は問題を部分問題に分割しても,必ずしも部分問題の規模(計算量)が小さくならないというところにもっとも大きな特徴を有すると考えられる.この意味では,完全に非デカルト的な問題であると考えざるを得ない.しかし,スイッチパネルゲームはハミルトン検定問題とは明らかに次元を異にする問題に転位していると考えられるので,この小問題を解くことは十分有望であると確信している.

□ もし,復活木による無時間検定法によって,真に後戻りすることのない再検定を実施することが可能であるとすると,短絡グラフ法と無時間検定法の組み合わせのみで(3種検定を用いることなく)ハミルトン検定を構成できる可能性がある.現在のところは,無時間検定法の終結局面においてまだ定式化されていない部分を若干残している.

□ ことによれば,スイッチパネルゲーム自体を再生マップ上で行なう(つまり,無時間検定として実装する)ことが可能なのではないか?という発想もあり得るように思われる.スイッチパネルゲームという小問題の構成が,ポストの対応問題として知られる決定不能問題に類似しているように見えるところが,やや気掛かりな点である.

○ この後,何をしなければならないか?

やり残していることは大量に存在する.まだ,解かれていない問題(スイッチパネルゲーム,完全な無試行判定法).まだ未完成の部分を残す問題(デッドロックマップの範囲を逸脱する検定),まだ,定式化されていない問題(無時間検定を含む再検グラフ法,クロスIO矛盾),まだ証明を得られていない問題(ハミルトン直並列簡約,その他,未解決,未完成,未定式化のカテゴリーに属する問題は当然未証明問題である),未整理の問題(無向グラフの検定法),アルゴリズムを定式化していない問題(端子分割,カットセット分割の検出アルゴリズム),その他.これらのすべてを解決することが当面の課題である.

これらの課題のうち,時間があれば解決可能なものと,時間以上のものが必要となるものとの2つのクラスがある.この草稿の章立てからいくと,3章の非決定牲の問題,4章のアルゴリズム,5章の計算コストは一部を除き,基本的には時間さえ得られれば解決可能であると考える.

アルゴリズムの定式化と並行して,それを実証するプログラムを作成し,アルゴリズムの正当性の検証と,その実用性能を測定する作業が同時に行われなくてはならない.クロスIO矛盾のような手書き規模のサンプルではなかなか出現しないようなグラフを対象とする検定も,コンピュータ上であれば容易に実現することができるだろう.コンピュータ上のシミュレーションは,あるいはまだ未発見の特殊な問題を抽出するのに役立つかもしれない.アルゴリズムを最適化する,特にハミルトンタイを持っているグラフの解を可能な限り高速に求めるためのある種の最適化,ないし改良などのことも必要となってくるだろう.

これらのことを行ってハミルトン閉路問題を完全に解決するために,後どのくらいの時間を見積もればよいであろうか?今わかっていることは,少なくともその時間は多項式時間アルゴリズムのオーダーでなくてはならないということだけである.この草稿が完成した段階でやらなくてはならないことは2つある.ひとつはこの草稿を英訳してリリースすることであり,もうひとつは,正式に公表可能な水準の論文を作成して,それを公表することである.現在の最大の困難はこれらのことを遂行するのに必要なすべての基本要素を欠いた状態にあって,なお,これらのことを断念することができないというところにある.

ハミルトン閉路問題が幸運をコントロールする方法と等価な問題であり,ハミルトン閉路が輪=和を表象するものであるとしたとき,我々がこれから証明しなくてはならないことは次の2つの命題に尽きるように思われる.

1.幸運をコントロールするための唯一つの方法は,
■■すべての瞬間において最善の路を選択することである.
2.平和をもたらすために解決しなければならない課題があるとすれば,
■■それは資源の配分問題である.

もしそうであるとすれば,我々がハミルトン閉路問題を解くのは,まさに時間の問題である.