HN 日本語サマリー

← 一覧へ戻る
その他

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

My two year old taught me constraint solving (thecomputersciencebook.com)

85 pointsby bambataa28 コメント

要約

筆者は、2歳の息子とのBrio木製トレインセットでの遊びを通じて、制約充足問題(Constraint Solving)の概念を学んだ経験を綴っている。息子が複雑な線路レイアウトを「作る」という行為が、実際には多くの制約(ピースの形状、接続、閉じたループの形成など)を満たす問題解決であることを発見し、そのアルゴリズム的な側面を探求した。息子は直感的に制約を満たすピースを選び、筆者はそれをバックトラッキングや制約充足ソルバーといったコンピュータサイエンスの技術と結びつけて解説している。

全文翻訳

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

メールでご覧になっている場合:視覚的な表現はブラウザで表示するとより効果的です。

私の息子は2歳で、アポロン的な権力欲を持っており、あらゆる種類の機械式輸送機関や土木機械が大好きです。特に彼が喜ぶのは、Brioの木製鉄道セットで「電車ごっこ」をすることです。彼は私が参加することを望んでいますが、私は電車に触れることを明確に許可されていません。そのため、私は面白い線路のレイアウトを組むことで自分を楽しませています。

長い間、私はBrioについてより体系的に考えるようになりました。ピースは明らかに形に合わせて組み合わされるように設計されていますが、そのデザインの根本的な構造は何でしょうか?与えられたピースのセットで、私が構築できる最も手の込んだレイアウトは何でしょうか?

私は正式な数学のバックグラウンドを持っていませんが、これは私の目の前の床に横たわる興味深いアルゴリズムの問題だと分かりました。これを探求するうちに、息子はこれまで知られていなかった制約充足問題解決の専門知識を示しました。この記事の残りは、彼が私に教えてくれたことの、少し編集された記録です。

Brioシステム

Brioは子供向けの木製鉄道玩具ですが、特に興味のある大人たちによって深く文書化されています。私はまず非公式Brioトラックガイドを参照しました。そこでは、各ピースにアルファベットコードと測定値が与えられています。Aは144mmの中間ストレートです。A1とA2はそれぞれ108mmと54mmのバリエーションです。Eは標準的なカーブで、円の8分の1で、内側の縁で182mm強、外側の縁で222mmを測定します。したがって、これらの45度のカーブを8つ組み合わせると、約40cmの円ができます。ほとんどのピースはひっくり返すことができるため、カーブの向きによって左右どちらにも曲がることができます。

[画像:シンプルなBrioレイアウト]

ランプや橋もありますが、それらは無視してシステムを単純化のために二次元として扱います。これは私にとって都合が良いです。なぜなら、橋はかなり不安定で、息子がしょっちゅう倒してしまうので、私はそれらのピースを隠そうとするからです。

まず、トラックを閉じる

ある朝、私は8つのカーブを組み合わせて円を作るところから始めました。

「円!」と息子は歓声を上げます。

よし!『きかんしゃトーマスと仲間たち』の『形であそぼう』を何百回も読んだ甲斐がありました。

しかし、これは最も単純な閉じたBrioループです。ここからどう進むべきでしょうか?私にとって面白いのは、一連のトラックピースを取り、それらすべてを閉じたレイアウト(つまり、すべてのコネクタがペアになっている状態)に配置できるかどうかを見つけることです。

この記事では、3つのソルバー(洗練度を増していく)によって強化された視覚化を紹介します。図1から4はバックトラッキング検索を実行し、図5は制約充足問題解決を使用し、図6はSATソルバーを使用します。

バックトラッキング検索は、幼児がやるようにトラックを構築します:ピースを置く、開いているコネクタを見る、別のピースを試す、うまくいかないときに戻る。ループを作る方法は次のとおりです。

  1. 電車が一周する
    8 Eカーブ
    床の上のピース
    検索トレース
    0ピース配置済み
    0.0秒経過
    0状態探索済み
    0オープンコネクタ
    現在の選択肢
    まだトラックは配置されていません。

実際、トラックが合わないと息子は電車を怒って投げますが、ソルバーは自己制御ができる人にとって一般的な探索空間の探索方法である再帰的バックトラッキングを実行します。

オープンコネクタはタスクリストを形成します。ソルバーは一度に1つのコネクタだけを処理し、そこに適合するすべてのピースと向きを試してから、それぞれに再帰します。分岐が行き止まりになった場合(適合するピースがない、またはピースをすべて使い切ったのにコネクタが開いたまま)、オプションがまだ残っている最後のコネクタまで戻ります。トラックは、コネクタが残っておらず、かつセット内のすべてのピースが配置された場合にのみ閉じられたとみなされます。ピースが残ったまま早く閉じることは、別の行き止まりとして扱われ、バックトラックされます。Python風の擬似コードでは、次のようになります。

def search(open_connectors, unused_pieces, layout):
    if not open_connectors:
        return layout if not unused_pieces else 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つのストレートピースを追加すると、可能な状態の数が劇的に増加します。

  1. 電車がもっと大きく回る
    8 Eカーブ + 2 Aストレート
    床の上のピース
    検索トレース
    0ピース配置済み
    0.0秒経過
    0状態探索済み
    0オープンコネクタ
    現在の選択肢
    まだトラックは配置されていません。

明白なアプローチは貪欲アルゴリズムを使用することです:最初に適合するピースを取り、そのまま進み、決して振り返らない。しかし、ピースは1つの場所に適合しても、トラックを閉じることを不可能にする可能性があります。特にストレートピースは、数カ所の位置でしか機能しません。貪欲な実行では、それらを間違った場所に1つ使用し、行き詰まり、それについて何もできなくなります。そのため、行き止まりからバックトラックし、行った配置を元に戻して新しいピースを試す能力が必要です。

私はこれを優しく説明します。「指数関数的だね、ダダ」と彼は頷きます。

確かに。開いているコネクタごとに、それに適合する任意のピースで継続できるため、部分的なレイアウトの数はピースの数とともに指数関数的に増加します。これは、ピースn個に対して分岐係数bのO(b^n)に非常に近い値です。この図は前の円よりも2ピース多いだけですが、円の254に対して1,930の状態を試します。これは、追加の2ピースに対して約8倍の状態数です。

では、指数関数的な実行時間を持つアルゴリズムが、ブラウザで合理的に速く実行されているのはなぜでしょうか?このサイズでは、賢くある必要はありません:数千の状態はラップトップが処理するには大したことではありません。そのため、単純な網羅的バックトラッキング(固定順序ですべてのピースとポートを試す、ショートカットなし、賢さなし)はミリ秒で完了します。しかし、それは永遠には続きません。最悪の場合でも指数関数的であり、すぐに壁にぶつかるでしょう。

anyway、円や長方形、楕円、あるいは何と呼んでもいいですが、退屈です。もっと大きなものを作るのは難しくありませんが、電車は同じように回るだけです。面白くするためには、交差や分岐が必要です。

交差が分岐点をもたらす

私の息子は交差ピース(H3)を手に取ります。それは2つの重なり合った円でできており、通過する電車はその溝にとどまるか、別の線に切り替えることができます。

[画像:H3交差]

これで分岐点を持つことができます!息子に示します。「見て、ここに交差ピースがあるよ。」

「グラフに2つのサイクル!」と彼は輝きます。

私は誇らしげに溶けます。私自身の小さなコンピュータ科学者!Hacker Newsのコメント欄の将来の恐怖!

『The Computer Science Book』のグラフのセクションで見たように、グラフは線で結ばれた点の数学的用語(点は頂点、線は辺)であり、サイクルは開始点に戻るグラフ上の任意の経路です。これまでのすべてのトラックピースには2つのコネクタがあったため、トラックは単一のスレッドのようでした。一方の端からもう一方の端まで伸びています。閉じたループを形成した場合、1つのサイクルです。交差ピースには4つのコネクタがあるため、配置すると一度に3つのコネクタが開かれ、検索自体が分岐し始めます。データモデルは次のように変更する必要がありました。

piece = geometric move

からこれへ:

piece = connectors + geometry + internal grooves

検索アルゴリズムは変わりませんが、より複雑な空間を探索するようになります。

覚えておいてください、目標は、セット内のすべてのピース(交差ピースを含む)が1つの閉じたネットワークに収まるかどうかを確認することです。そして、それは収まります。交差ピースを通して接続された2つの完全な円、すべてのコネクタがペアになり、電車が単一のラップで両方の溝をたどります。

  1. これは自己交差する
    14 Eカーブ + 1 H3カーブ交差
    床の上のピース
    検索トレース
    0ピース配置済み
    0.0秒経過
    0状態探索済み
    0オープンコネクタ
    現在の選択肢
    まだトラックは配置されていません。

興味深い補足は衝突検出です。当初、ソルバーがピースを互いに重ねて配置しようとするのを防ぐために、制約として追加しました。正確性のために追加しましたが、追加の制約は検索の高速化にも役立ちました。制約が増えると、探索する必要のある検索空間のサイズが縮小します。

無料の45ページCSロードマップを入手

購読すると、コンピュータサイエンスの無料の45ページロードマップ(何を、どの順序で学び、何をスキップするか)と、時折のCS深掘り記事をお送りします。

スパムなし。いつでも解除できます。

分岐がループをネットワークに変える

L分岐は、1つのコネクタを共有するストレートとカーブです。電車はまっすぐ進むことも、カーブの周りに曲がることもできます。Mはその鏡像です。

[画像:LとMの分岐]

ソルバーはより興味深いレイアウトを見つけることができるようになります。2つの分岐の間に内側のループを作成し、外側に長方形、内側に円があり、分岐の3つのコネクタすべてがペアになっています。

  1. これは選択肢がある
    10 Eカーブ + LとMの分岐
    床の上のピース
    検索トレース
    0ピース配置済み
    0.0秒経過
    0状態探索済み
    0オープンコネクタ
    現在の選択肢
    まだトラックは配置されていません。

「ダダ!次数3。オイラー回路なし。」

ChatGPTと相談した後、息子の言っていることが理解できました。

次数は、1つの点にいくつものトラックの端が集まっているかを数えるだけなので、交差ピース(コネクタ4つ)は次数4、分岐ピース(コネクタ3つ)は次数3です。息子が説明したように、グラフ理論家はトラックの形状をシータグラフと呼びます。それは文字θのように見えるからです。オイラーは1736年に、奇数次の頂点があると、単一のラップではすべてのトラックピースを正確に1回カバーできないことを証明しました(オイラーは木製列車ではなく橋を念頭に置いていましたが、数学の美しさはその洞察が転移することです)。交差ピースは偶数次の次数を持ち、これは電車が完全な図形8を単一のラップでたどることができることを意味します。分岐を使用すると、トラックは完全に閉じられますが、電車は1回のラップで完全なパスをカバーできません。

制約問題に変換する

私のトラックレイアウトは息子を感心させなくなりました。必死になって、最も印象的なトラックを作ろうとします:たくさんの交差、たくさんの分岐、すべてを盛り込みます。

私はピースのセット全体を床にひっくり返し、超すごい複雑なレイアウトを作ろうとします。かなりひどく失敗します。そこまで到達しても、ピースが離れすぎて接続できないことがわかります。検索空間はピースの数に対して指数関数的であり、私はピースを追加しています。

息子は容赦のない視線で私を見て、ついに2歳特有の重さでため息をつきます。

「ダダ、これは制約充足問題だよ、このバカ!」と彼は言います。

「どういう意味?」と私は、彼がポイントを持っていることをかすかに疑っているので、いくらかの不満を抱きながら尋ねます。

「変数がオープンコネクタ。ドメインはまだ適合するピース。制約はすべてのコネクタがペアになること!」

もちろん!どうして見落としていたんだろう?普通の言葉で言うと、制約充足問題とは、次の3つのことを言えるときに得られるものです。

  • どのような選択が行われているか
  • 各選択肢が何になれるか
  • どの選択肢が一緒に生きられないか

例えば、数独は基本的に制約充足ゲームです。どの行、列、ボックスも数字を繰り返すことはできません。そのため、それらがどこに収まるかを突き止める必要があります。これが制約ソルバーが行うことです。

Brioに翻訳すると、選択肢はピースがどこに配置されるかです。許容される値は、それらが取ることができる位置、回転、反転です。制約は、私たちが収集してきた物理的なルールです:コネクタは一致しなければならない、トラックはトラックを通過できない、など。

バックトラッキングがどのように機能するかを考えると、2つの点でばかばかしく無駄に思えます。それは先見性がありません:ピースを使い果たすことによってのみ、配置からずっと後に分岐が絶望的であることを発見します。そして、それは目的がありません:失敗した場合、最も最近の配置を元に戻し、次を試します。たとえ実際のミスが10ピース前に作られ、全く新しい方向を試すべきだったとしてもです。

「伝播が必要だよ」と息子はブロックから目を離さずに言います。「そしてバックジャンプも。」

私は実際、伝播とバックジャンプが必要であることを知りませんでした。

制約ソルバーでは、トラックは依然として一度に1つのオープンコネクタで成長しますが、各オープンコネクタは、そこに合法的に配置できるピースとポートの組み合わせの短いリストを保持するようになりました。その短いリストがそのドメインです。

フォワードチェックは、短いリストを最新の状態に保ちます。ピースが配置されるたびに、ソルバーはレイアウトと衝突する可能性のあるオプション、またはすでに使用したピースを必要とするオプションをすべて削除します。コネクタの短いリストが空になると、その分岐は決して閉じることができないため、ソルバーはすぐにそれを諦めます。衝突指示バックジャンプは、どこまで元に戻すかを決定します。一度に1つのピースを元に戻すのではなく、失敗を引き起こした以前の配置を突き止め、そこに直接ジャンプします。

比較のために、図4と同じ12個のピース(カーブ10個と分岐2個)を与えました。これは、プレーンバックトラッキングで既に測定した問題に対して直接比較するためです。

予期せぬことに、私の最初のバージョンは事態を悪化させました。図4の434,791に対して853,186の状態を試しました。ほぼ2倍です。信じられなかったので、他の12セットのピースでも実行しましたが、フォワードチェックは毎回検索を遅くしました。

なぜでしょうか?私の2歳児は、結局制約充足問題解決についてあまり知らないのでしょうか?

理由はそのフォワードチェックが見たり見なかったりすることにあります。それは、一部のコネクタの短いリストが空になった場合にのみ分岐を放棄しますが、それはその1つのコネクタのすべてのオプションを排除するピースを配置する必要があります。しかし、Brioの行き止まりはほとんど局所的ではありません。ほぼすべてのピースがほぼすべてのオープンコネクタに適合するため、短いリストはピースがなくなるまで満杯のままです。実際に分岐を殺すのは、残りのピースがすべてをペアにするのに十分なコネクタを供給できない場合、または開いている端が箱に残っているものすべてが橋渡しできるよりも遠く離れてしまった場合です。そのため、フォワードチェックはプレーンバックトラッキングと同じ瞬間に問題しか検出しないため、労力に見合いません。

「コネクタをチェックしているよ、ダダ」と息子はため息をつきます。「すべてのピースをチェックして。」

彼はグローバル制約、つまり単一のコネクタではなく、レイアウト全体を見るものを意味します。配置ごとに、ソルバーは現在2つの全体レイアウトの事実を直接チェックします:まだ開いているすべてをペアにするのに十分なコネクタが残っているか、そして残りのピースはギャップを越えて届くことができるか?どちらかの答えがノーであれば、レイアウトは決して閉じることができないため、分岐はすぐに放棄されます。

今回はうまくいきました。図4と同じピースとルールですが、検索は現在53,484の状態を要し、プレーンバックトラッキングが必要とした状態の約8分の1です。グローバルチェックは、測定した他のほとんどのピースセットで、検索を2倍から9倍削減しましたが、すべてではありません。1つのセットでは、ストレートと両方の分岐を混ぜた場合、このソルバーはプレーンバックトラッキングよりも約10倍遅くなります。追加のチェックは通常、より多くの作業を節約しますが、コストに見合うだけの保証はありません。

  1. これは制約問題になった
    図4と同じ12ピース、伝播、バックジャンプ、グローバル実現可能性チェックで解決
    床の上のピース
    検索トレース
    0ピース配置済み
    0.0秒経過
    0状態探索済み
    0オープンコネクタ
    現在の選択肢
    まだトラックは配置されていません。

1つの追加の弱点が残っています。このソルバーがバックジャンプするとき、着地するとすぐに失敗を忘れるため、検索の別の部分で同じ行き止まりが発生した場合、ゼロから再発見されます。私が望むのは、失敗をルールとして記憶するソルバーであり、同じ間違いが他のどこでも禁止されることです。

他に気になることもあります。これらの検索はどちらも、1つの正確なピースセットに対してはい/いいえの答えしか返しません。最も複雑なレイアウトを作成したい場合、どのピースを試すかを推測するのはまだ私次第であり、一度に1つのセットです。

「最高のレイアウトをどうやって作れるか不思議だ」と私は自問します。

「ソルバーにピースを選ばせなよ、ダダ」と彼は静かに言います。彼が私に失望しているのがわかります。

SATソルバーに任せる

当初、私はトラックレイアウト問題をグラフ理論の問題と考えていましたが、それはすでに解決した後でのみ真実でした。ピースが配置されたら、はい、レイアウトをグラフとして記述できます。それ以前はグラフはなく、リビングルームの床にあるピースの山と、その上をよろめく小さな子供がいるだけです。

実際、問題はタイリング問題に近いです。そこでピースを選択し、配置し、何も重ならないようにします。既存のグラフから辺を選択しているわけではありません。辺を作成するためにピースを配置しています。

息子はピースを山に分けてこれを実演します。「カーブはここ。大きいのはここ。小さいのはここ。」次に、彼は4つのカーブを四角い塊に並べて、「ポリオーミノみたい」と言います。

「ポリ何?」

「ポリオーミノだよ、ダダ。だからSATソルバーが使えるんだ」と彼は私を見ずに呟きます。私はもはや彼が思っていた父親ではありません。

ポリオーミノはテトリスのような形をしており、それらを隙間なく、重なりなく組み合わせることは古典的なタイリングパズルです。タイリングもSATソルバーに与えられる標準的な問題の1つであり、それが彼が作った関連です。Brioは、正方形のピースの代わりに湾曲したピースを使用し、何も衝突しないように配置するという点で、同じ種類の問題です。

もちろん!私は額を叩きます。「タスクをSAT問題に変換すると、解決がずっと簡単になるよ!」と私は言います。彼は頷きます。

ブール充足可能性問題は、ブール変数を持つ式(例:a && (b || !c))を取り、式の値を真にする変数割り当てのセットがあるかどうかを尋ねます。例えば、a := true, b := true, c := false はその式を真に評価します。式は、少なくとも1つの有効な割り当てがあれば充足可能です。ブール充足可能性問題は、NPで証明された最初の問題であり、NPのすべての問題はBool SATに還元できます(もし私があなたを困惑させたなら、計算理論の章を読んでください)。

私たちにとっての実用的な結果は、SATソルバーの最適化に多大な努力が費やされており、NP完全であっても、それらを利用して最適なレイアウトを迅速に見つけることができるということです。しかし、SATソルバーは真と偽しか理解しないため、可能なすべての配置が独自のイエス/ノーの質問になります。「このピースが、この場所で、この角度で使われているか?」ソルバーは、これらの質問すべてが開始前に書き留められる必要があります。これは、ピースが占める可能性のあるすべての位置をリストアップすることを意味します。

タイリングパズルでは、位置がグリッドを形成するため、位置の固定セットがあるため、そのリストは簡単です。Brioはそのようには機能しません。2歳児なら誰でも知っているように、合わない場合は無理やり押し込むことができます。Brioの設計者は、(やや大げさな名前の)vrio flexシステムでこの動作を賢く許容しました。コネクタのペグはコネクタの穴よりもわずかに小さく、各ピースに数ミリメートルの遊びがあります。Brioのピースはグリッドにスナップしません。

固定されたピースのセットがあれば、到達可能な位置は有限なので、原理的にはリストアップできます。しかし、それを見つける唯一の方法は、それに到達するレイアウトを構築することであり、最後のすべてを見つけることは、私たちが避けようとしているのと同じ指数関数的な検索全体を歩くことを意味します。

私の回避策はチートすることでした。SATソルバーを実行する前に、検索はさまざまな開始ピースセットからレイアウトを構築し、その過程で訪れたすべてのコネクタ位置を記録します。これらの記録された位置が、SATソルバーが構築できる唯一の場所になります。このアプローチは、SATソルバーの回答の意味を制限します。「いいえ」は、どこにも閉じたレイアウトが存在しないという意味ではなく、記録された位置を使用したレイアウトが存在しないという意味です。より長く実行された検索は、答えを変える可能性のある位置をさらに見つけるかもしれません。

収集された位置に着地する各配置は、1つのブール変数です。

x[placement] = true if this exact piece, here, in this orientation, is used

ルールは節になります。節は、SATソルバーが受け入れる唯一の種類のステートメントです。それは、リストからの少なくとも1つの主張が保持されなければならないと言います。各主張は、「この配置を使用する」または「この配置を使用しない」のいずれかです。トラックが必要とするすべては、そのように表現する必要があります。

each used port mates exactly one opposing port
no two crossing placements are both used
at most as many of each junction as the inputs allow
as many junctions as possible, demand relaxed until it closes

これらの節をソルバーに与えると、すべての節を同時に満たす真/偽の割り当てを探します。ソルバーが「いいえ」と言う場合、それは与えられた変数を使用した可能な割り当てがないことを証明しました。それは、他の2つのソルバーと同じ5秒のタイマーで実行されますが、このページでの実行は快適にその時間内に完了します。

私がつまずいたのは接続性の要件でした。「『これらすべてが1つのレイアウトに収まる』という単一の節はありません」と私は言いました。「それをSATソルバーにどうやって与えるのですか?」

息子は巧妙なループを使ったアプローチを説明してくれました。単一の節「これらすべてが1つのレイアウトに収まる」がないため、一連のローカルルールでも2つの別々の鉄道を生成できます。ループでは、一度解決し、答えが2つの別々の鉄道として返ってきた場合、その正確な組み合わせを禁止する節を追加し、カウンターエグザンブルごとに解決し直します。息子は、分岐点の最大化も同様に機能すると主張しました。多くのジャンクションを要求し、それが充足不可能であれば、1つ減らして、何かが閉じるまで要求します。

接続ループは、最初は怪しいハックのように思えましたが、息子は整数計画ソルバーが、切断されたサブツアーが現れるたびにそれを禁止することで、巡回セールスマン問題を同じように処理すると保証してくれました。検証担当者は、一般的なパターンをカウンターエグザンブル誘導型リファインメントと呼んでいます。

  1. SATソルバーがピースを結合する
    スカウトされた位置、節としてエンコード、解決済み
    床の上のピース
    検索トレース
    0ピース配置済み
    0.0秒経過
    0状態探索済み
    0オープンコネクタ
    現在の選択肢
    まだトラックは配置されていません。

SATソルバー自体は、舞台裏で何か賢いことをしています。変数を推測し、節が含意するすべてを伝播します。矛盾に遭遇すると、それを引き起こした推測を特定し、その間違いを新しい節として書き留めるため、後続のどのブランチもそれを繰り返すことは許されません。その後、ソルバーは新しい節が必要とする範囲までしかジャンプバックせず、続行します。時々再起動しますが、学んだすべてを保持します。息子はこれを衝突駆動型節学習またはCDCLとカジュアルに参照しました。

SATは、これまでに見た検索よりも必ずしも速いわけではありません。この多くのピースでは、実際には遅く、はるかに多くのメモリを使用します。では、なぜ気にするのでしょうか?バックトラッキングとCSPは、1つの正確なピースセットに対してはい/いいえに答えます。SATソルバーは、指定された数のピースを取り、一部のピースを省略することさえできる、可能な限り複雑なレイアウトを見つけることができます。なぜなら、それらは何も省略することを許可されていないからです。

視覚化の数値入力は上限であり、必須条件ではありません。すべての実行は、収集された位置が保持できる最も多くのジャンクションを要求し、それが不可能であることが証明されるまでのみ減少します。分岐をそれぞれ2つに増やすと、ソルバーは49個のピースの7ジャンクションネットワークを構築します。代わりに交差をゼロに設定すると、分岐のみを中心にネットワークを再構築します。

小さな固定ピースセットでは、バックトラッキングとCSPは5秒の予算内で応答します。それらは高速で、シンプルで、メモリ消費が少ないですが、どちらも何を省略すべきかを教えてくれません。なぜなら、どちらも何も省略することを許可されていないからです。SATはすべての候補配置を一度にメモリに保持し、1つの行き止まりから学んだルールは、それが発見されたブランチだけでなく、どこでも同じ間違いが記憶されます。それはメモリと速度を犠牲にしますが、ソルバーが検証するだけでなくピースを選択することを可能にします。

「ダダ、実際のプランナーは、同じ理由で、時間割、チップレイアウト、ルーティングにSATとその関連技術を使用するんだ。」

学んだこと

懲りて、私はSATソルバーの出力に従って木製鉄道のピースを配置します。私はBrioが息子に基本的な形を見せる機会になると思っていましたが、結局、彼の保育園では加速アルゴリズムプログラムを受けており、彼は私を指導しました。(それが、彼が下校時にバックパックを詰めるのが上手な理由を説明しています。)

私の本当の間違いはアルゴリズムではなく、1つの質問があると思い込んでいたことでした。「この正確なピースセットは閉じますか?」と「最も複雑なネットワークを作るピースはどれですか?」は異なる質問であり、私は最初の質問のために作られたツールで2番目の質問に答えようとしていました。

再帰的バックトラッキングは最も少ないことを約束します:指数関数的な最悪ケースと、行き止まり間のメモリなし。その代わりに、シンプルで、ほとんどメモリを必要とせず、この記事のサイズでは瞬時に感じられます。

CSPソルバーは同じ質問を保持しますが、よりインテリジェントに検索します。有用な部分はレイアウト全体の実現可能性チェックでした。なぜなら、このパズルの失敗状態は、ローカルチェックでは早期に検出できないグローバルな事実がほとんどだからです。ここでの教訓は、制約充足問題解決が検索を魔法のように改善するわけではないということです。それは、可能な検索空間を劇的に削減する有用な制約を見つけることを必要とします。

SATソルバーは質問を変更するだけで、検索は変更しません。節学習は、CSPのバックジャンプが欠いている永続的なメモリをそれに与えるため、1つの行き止まりはどこでも同じ間違いを排除します。コストはメモリ、速度、および範囲です:それはすべての配置とすべての学習された節を一度に保持し、他の2つがミリ秒かかる間に数秒かかり、その証明は与えられた入力空間のみをカバーします。

『The Computer Science Book』を続けましょう。

この記事のような投稿の背後にあるコンピュータサイエンスの基本原則を、コンピュータアーキテクチャからアルゴリズム、最新のAIまで、ガイド付きで意見のあるウォークスルーです。自己学習開発者のために構築された13章。

電子書籍を購入 - $19.99

電子書籍にはPDFおよびEPUB形式と28日間の返金保証が含まれます。

または無料の45ページCSロードマップを入手 →