問題タブ [binary-decision-diagram]

そこにx、yの概念を実装することが可能かどうかを判断するために、BDDのアプリケーションを調べています。

説明させてください。

x、y座標平面に分布する何かのzがあるとしましょう。制約は次のとおりです。

• すべての z 項目は、x、y 座標平面に配置する必要があります。
• z 項目の中には、互いに一定の距離を離す必要があるものがあります。

整数線形計画法はこれを整理できると思います。たとえば、一連の方程式を使用して、上記の制約を表し、線形計画法を実行して正確な位置を解くことができます。

しかし、私が求めているのは、BDD がこれに役立つかどうかです。

言い換えると、二分決定図は x,y 座標を表すことができ、上記の制約をブール関数 (上記の一連の方程式と同等) で表すことができますか? BDD を操作して、線形計画法のように正確な位置の上記の制約を整理できますか?

表示する具体的な例はありませんが、バイナリで同等の x、y 座標を表すことから始めるべきだと思いますか?

ここから N クイーン問題のブール式を見ました。

私の変更された N クイーン ルールはより単純です。

ap*p chessboard の場合、次のように N 個のクイーンを配置したいと考えています。

1. クイーンは隣接して配置され、行が最初に埋められます。
2. p*p チェス盤のサイズは、N 個のクイーンを保持できるようになるまで調整されます

たとえば、N = 17 とすると、5*5 のチェス盤が必要で、配置は次のようになります。

問題は、この問題のブール式を考え出そうとしているということです。