Reduced Ordered Binary Decision Diagram (ROBDD) で 8 クイーン パズル問題を解く方法がわかりません。私はそれをグーグルで検索しましたが、問題の適切な説明を見つけることができません。したがって、ここでの問題 - これまでのところ、n*n の入力変数または ROBDD の状態が存在することがわかりました。では、8 クイーン パズルを解く ROBDD を実際に作成するにはどうすればよいでしょうか。
説明は、問題をよりよく理解するのに役立ちます。
あなたの質問は少し誤解を招くものです。ROBDD は、ブール関数を表現および操作する手段にすぎません。したがって、まず、問題を表すブール関数を作成する必要があります。n-queen 問題については多くの資料があるため、この回答では説明しません。
関数を作成したら、それを ROBDD で表すことができます。各ノードは、おそらく「この正方形に女王がいますか?」という質問に答えるでしょう。はい・いいえ"。reduce と reordering に関しては、問題自体とは直接関係ありません。Reduce は標準的なアルゴリズムであり、並べ替えのためのさまざまなアルゴリズムとヒューリスティックが多数あります (たとえば、CUDD パッケージでは多数のアルゴリズムが提供されています)。繰り返しになりますが、これらのことを詳細に説明することは、この回答の範囲ではありません。また、インターネット上で調べる資料がたくさんあります. ただし、reduce アルゴリズムはすべての変数を保持することがわかります。これは、正方形にクイーンがあるかどうかが同じになることはほとんどないためです。
解決策を探す時が来ました。問題に実際に解決策がある場合は、1 につながるパスが少なくとも 1 つ見つかります。そのパス (またはそれらのパスが複数存在する可能性があります) をたどると、どの変数が 1 または 0 に設定されているかがわかります (つまり、女王がいる場所といない場所です)。