アリアドネの糸（論理）

アリアドネの糸は、ミノタウロスの迷宮から抜け出す道を見つけるためにテセウスに糸玉（文字通り「手がかり」）を与えたというアリアドネの伝説にちなんで名付けられており、物理的な迷路、論理パズル、倫理的なジレンマなど、複数の進むべき道があるように見える問題を、利用可能なすべてのルートに論理を徹底的に適用することで解決するものです。最終的な位置に到達する、偶発的で順序付けられた探索において、ステップをたどったり、発見された一連の真実をポイントごとに調べたりするまで完全に実行できるのは、使用される特定の方法です。このプロセスは、精神的な記録、物理的な印、さらには哲学的な議論の形を取ることができます。プロセス自体がその名前を冠しています。

実装

アリアドネの糸を問題に適用する上で重要な要素は、問題における利用可能な選択肢と既に利用可能な選択肢の記録（物理的なものも含む）を常に作成し、維持することです。この記録は、実際の媒体に関わらず「糸」と呼ばれます。この記録の目的は、バックトラッキング、つまり以前の決定を取り消して代替案を試すことを可能にすることです。記録があれば、アルゴリズムの適用は簡単です。

選択を迫られたときはいつでも、まだ失敗とマークされていない選択肢の中から任意に 1 つを選び、可能な限り論理的にそれに従ってください。
矛盾が生じた場合は、最後に行った決定まで遡り、それを失敗としてマークし、同じ時点で別の決定を試みます。そこに他の選択肢がない場合は、記録の中で選択肢が存在する最後の場所まで遡り、そのレベルで失敗としてマークし、先に進みます。

このアルゴリズムは、解が見つかるか、すべての初期選択を失敗とマークした時点で終了します。後者の場合、解は存在しません。解が見つかった後も徹底的な検証が必要な場合は、以前の決定に戻り、成功とマークして、解が見つからなかったかのように処理を続行できます。アルゴリズムはすべての決定を尽くし、すべての解を見つけます。

試行錯誤との区別

「アリアドネの糸」と「試行錯誤」という言葉はしばしば同じ意味で使われますが、必ずしも正確ではありません。これらには2つの明確な違いがあります。

「試行錯誤」とは、それぞれの「試行」が何らかの価値を生み出し、それを研究・改善し、各反復から「誤り」を排除することで将来の試行の質を高めることを意味します。しかし、アリアドネの糸にはそのような仕組みがないため、すべての決定は恣意的なものとなります。例えば、科学的手法は試行錯誤であり、パズルを解くことはアリアドネの糸です。
試行錯誤的なアプローチでは、問題に対する解決策がいくつ存在するかはほとんど考慮されず、むしろ正しい解決策は1つしか存在しないと想定されることがほとんどです。しかし、アリアドネのスレッドはそのような前提を持たず、純粋に論理的な問題に対してあらゆる可能な解決策を見つけることが可能です。

つまり、試行錯誤は望ましい解決策に近づくのに対し、アリアドネの糸は盲目的に探索空間を徹底的に探し尽くし、ありとあらゆる解決策を見つけ出すのです。それぞれの糸には適切な用途があり、併用することも可能です。

アプリケーション

アリアドネの糸は、伝説と同じように迷路を解く際にも応用できます。実際の糸を記録として使うこともできますし、チョークなどのマーカーで通路に印をつけることもできます。迷路が紙の上にある場合は、糸の代わりに鉛筆を使うのも良いでしょう。

あらゆる種類の論理問題はアリアドネの糸によって解くことができます。迷路はその一例に過ぎません。現在では、数独パズルにも応用され、未解決のマス目の値を求めるのに利用されています。パズルを解くための糸の媒体は、鉛筆、番号札、コンピュータプログラムなど多岐にわたりますが、いずれも同じ目的を達成します。アリアドネの糸の作成は帰納的なプロセスであり、その徹底的な作業のために実際の検討の余地がないため、演繹的な方法が失敗した場合の最後の手段としてのみ用いられるべき解法として、広く受け入れられていません。

人工知能は、ゲームプレイ、例えばチェスをプレイするプログラムにおいて、アリアドネの糸に大きく依存しています。可能な手は決定、ゲームに勝つ状態は解、ゲームに負ける状態は失敗です。多くのゲームは非常に奥深いため、ほとんどのアルゴリズムは時間的制約から全ての手に対してアリアドネの糸を全面的に適用する余裕がありません。そのため、ゲームの状態を評価し、幅優先探索を最も有利な状態に限定するヒューリスティックと連携して動作し、試行錯誤を繰り返します。

「解決」の概念がそれほど明確に定義されていない状況にも、アリアドネの糸が適用されてきました。たとえば、ワールドワイドウェブのナビゲート、特許法の理解、哲学などです。「アリアドネの糸」は、哲学的または倫理的な議論など、さまざまな目的の Web サイトの一般的な名前です。

参照

ブルートフォース検索
深さ優先探索
ラビリンス
演繹的推論
コンピューターチェス
J. ヒリス・ミラー
ゴルディアスの結び目
Eight_queens_puzzle#Sample_programバックトラッキングの例

参考文献

マイケル・メファムによる数独の解き方ステップバイステップガイド。アリアドネの糸の歴史と応用のデモンストレーションが含まれています。
数独の構築フローチャートは、アリアドネの糸（バックトラッキング技法）を使用して数独を構築し、解く方法を示しています。
アリアドネとミノタウロス：修辞哲学の文化的役割アンドレア・バッティスティニによる、アリアドネの糸を哲学的メタファーとして詳述した記事
迷路の哲学迷路の背後にある論理と意味を研究したもので、アリアドネの糸の文字通りの解釈も含まれています。
マソ、キャロル（2012年）『母と子：小説』カリフォルニア州バークレー：カウンターポイント・プレス、 129頁、ISBN 978-1-58243-818-4。