2歳の息子が私に制約充足問題を教えてくれた

メールで読んでいますか？ブラウザの方が視覚化がうまく機能します。 私の息子は2歳で、それは彼がアポロ的な権力への意志を持ち、あらゆる種類の機械的な輸送手段や土木機械を愛していることを意味します。彼の特別な喜びは、Brioの木製トレインセットで「電車ごっこ」をすることです。 彼が私に関与することを好む一方で、私は電車に触れることを明確に許可されていないため、私は面白い線路レイアウトを構築することで自分を楽しませています。長い間、私はBrioについてより体系的に考え始めました。ピースは明らかに形状に合わせて作られているので、その背後にある構造は何でしょうか？与えられたピースのセットで、私が構築できる最も手の込んだレイアウトは何でしょうか？私は正式な数学のバックグラウンドを持っていませんが、これは私の目の前の床に横たわる興味深いアルゴリズムの問題であることがわかりました。私がこれを探求するにつれて、私の息子はこれまで検出されていなかった制約充足問題の専門知識を示しました。この投稿の残りは、彼が私に伝えたことの、軽く編集された記録です。 Brioシステム Brioは子供向けの木製トレインのおもちゃですが、特に興味のある大人たちによって詳細に文書化されています。私は最初に非公式のBrioトラックガイドを参照しました。これは各ピースに文字コードと測定値を与えています。Aは144mmの中間ストレートです。A1とA2は108mmと54mmのバリアントです。Eは標準的なカーブで、円の8分の1を測定し、内側で182mm強、外側で222mmです。したがって、8つの45度カーブは、直径約40cmの円を囲みます。ほとんどのピースは反転できるため、カーブはどのように配置するかによって左または右に曲がることができます。 シンプルなBrioレイアウト ランプや橋もありますが、それらは無視して、システムを単純化のために二次元として扱います。これは私にとって都合が良いです。なぜなら、橋はかなりぐらついており、息子がそれらを倒し続けるので、私はそれらのピースを隠そうとするからです。 まず、トラックを閉じる ある朝、私は8つのカーブを組み合わせて円を形成することから始めます。「円！」と息子は歓声を上げます。良い！トーマス・ザ・タンク・エンジンとその仲間たちで形を学ぶことを何百回も読んだことが報われました。しかし、これは最も単純な閉じたBrioループです。ここからどこへ行けばいいのでしょうか？私が楽しいと思うのは、一連のトラックピースを取り、それらすべてを閉じたレイアウト（つまり、すべてのコネクタがペアになっている）に配置できるかどうかを見つけることです。この投稿では、ますます洗練されていく3つのソルバーによって強化された視覚化を紹介します。図1から4はバックトラッキング検索を実行し、図5は制約充足問題ソルバーを使用し、図6はSATソルバーを使用します。 バックトラッキング検索は、幼児がトラックを構築する方法でトラックを構築します。ピースを置き、開いているコネクタを見て、別のピースを試して、うまくいかない場合はバックアップします。ループを作成する方法は次のとおりです。 1. 電車が8つのEカーブを周回する Slack Step Auto Reset 床のピース 検索トレース 0ピース配置済み 0.0秒経過 0状態探索済み 0開いているコネクタ 現在の選択 まだトラックは配置されていません。 実際、息子はトラックが合わないと電車を怒って投げますが、ソルバーは代わりに再帰的なバックトラッキングを実行します。これは、自己制御ができる人にとって、探索空間を探索するための一般的な方法です。開いているコネクタはタスクリストを形成します。ソルバーは一度に1つのコネクタだけを処理し、そこに適合するすべてのピースと向きを試して、それぞれに再帰します。ブランチが行き止まりに達した場合（適合するピースがない、またはコネクタが開いたままピースがすべて使い果たされた場合）、それはまだオプションがあった最後のコネクタまでバックアップします。トラックは、コネクタが残っておらず、セット内のすべてのピースが配置された場合にのみ閉じられたと見なされます。ピースがまだ残っているのに早く閉じることは、別の行き止まりとして扱われ、バックアウトされます。 Python風の擬似コードでは、次のようになります。 ```python def search(open_connectors, unused_pieces, layout): if not open_connectors: return layout if not unused_pieces: return None connector = open_connectors[0] for piece in unused_pieces: for port in piece.ports: placement = mate(piece, port, connector) if collides(placement): continue found = search(update(open_connectors, placement), unused_pieces - piece, layout + placement) if found is not None: return found return None ``` 8つのEカーブの場合、すべてのカーブを同じ方向に配置しておけば、問題は非常に単純です。しかし、ソルバーはそれを知りません。上記の図をステップ実行して「探索済み状態」のカウントを見ると、非常に速くジャンプします。これは、検索が最初に間違った方向に曲がるカーブを試してから、その行き止まりをピースがなくなるまで追いかけ、バックアウトして実際に機能するカーブを配置するためです。「状態」カウントは、その無駄なサブツリー全体を追跡します。 「もっと、ダダ！」と彼は言います。 トラックを大きくする 私は円を分割し、反対側にいくつかの平行な直線セクションを追加してトラックを大きくします。「楕円！」と私は幾何学を発見したかのように言います。「いいえ、ダダ、長方形」と彼は直線部分を指して言います。私は見つめます。彼は正しいです。彼の保育園の先生は、彼が素早いように見えたと言っていました。おそらく、授業料はそれだけの価値があったのでしょう。 権威を素早く回復しようとして、私はアルゴリズムへの影響を考慮します。2つの直線ピースを追加すると、可能な状態の数が劇的に増加します。 2. 電車がより大きな円を周回する 8つのEカーブ + 2つのAストレート Slack Step Auto Reset 床のピース 検索トレース 0ピース配置済み 0.0秒経過 0状態探索済み 0開いているコネクタ 現在の選択 まだトラックは配置されていません。 明らかなアプローチは、貪欲なアルゴリズムを使用することです。つまり、最初に適合するピースを取り、そのまま進み、決して振り返らないということです。しかし、ピースは1つの場所に適合しても、トラックを閉じることを不可能にする可能性があります。特に直線ピースは、数カ所でしか機能しません。貪欲な実行は、それらを間違った場所で使用し、行き詰まり、それについて何もできなくなります。したがって、行き止まりからバックトラックし、行った配置を巻き戻して新しいピースを試す能力が必要です。 私はこれを穏やかに説明します。「指数関数的だ、ダダ」と彼はうなずきます。確かに。開いている各コネクタは、それに適合する任意のピースで継続できるため、部分的なレイアウトの数はピースの数とともに指数関数的に増加します。非常に大まかに言えば、b個のピースがある場合、b^n（bは分岐係数、nはピース数）です。この図は前の円よりも2つのピースが多いだけですが、円の254に対して1,930の状態を試しています。これは、追加の2つのピースに対して約8倍の状態です。 したがって、指数関数的な実行時間を持つアルゴリズムである場合、なぜブラウザで合理的に速く実行されているのでしょうか？このサイズでは、賢くある必要はありません。数千の状態は、ラップトップが処理するのに何もありません。そのため、単純な網羅的なバックトラッキング――すべてのピースとポートを固定順序で試す、ショートカットなし、賢さなし――はミリ秒で完了します。それは永遠に真実であり続けるわけではありません。最悪の場合でも指数関数的であり、すぐに壁にぶつかるでしょう。 anyway 、円や長方形、あるいは楕円、あるいはあなたがそれを何と呼ぶにしても、退屈です。より大きなものを作るのは難しくありませんが、電車は同じように周回するだけです。面白くするためには、交差や分岐が必要です。 交差は分岐点を追加します 私の息子は交差ピース（H3）を手に取ります。それは2つの重なり合った円から作られており、通過する電車は溝にとどまるか、別の線に切り替えることができます。 H3交差 これで分岐点があります！私は息子に見せます。「見て、ここに交差ピースがあるよ。」 「2つのサイクルのグラフ！」と彼は輝きます。私は誇りで溶けます。私自身の小さなコンピュータサイエンティスト！ハッカーニュースのコメントセクションの将来の恐怖！ The Computer Science Bookのグラフセクションで見たように、グラフは線で結ばれた点の数学的な用語です（点は頂点、線は辺）、そしてサイクルは出発点に戻るグラフを通る任意の経路です。これまでのすべてのトラックピースには2つのコネクタがあったため、トラックは単一のスレッドのようであり、一方の端からもう一方の端へと周回していました。閉じたループを形成した場合、1つのサイクルです。交差には4つのコネクタがあるため、それを配置すると一度に3つのコネクタが開かれ、検索自体が分岐し始めます。 データモデルはこのように変更する必要がありました。 ``` piece = geometric move to this: piece = connectors + geometry + ```