A *アルゴリズムのブール関数ヒューリスティックを最小化する

Question

ブール関数を最小限に抑えるプログラムをPythonで書く必要がありますが、キャッチするにはA *やより単純なアルゴリズムBFSなどの検索アルゴリズムを使用する必要があります。反復深化を使ってプログラムを書いたが、それはすべての問題を解決したが、遅すぎる（各問題の限界は20秒）。

私はA *アルゴリズムを使って別のプログラムを書いていましたが（私たちはより良いグレードを望むならこのプログラムを使用しなければならないと言われましたが）、反復深化を使うプログラムよりも10倍遅くしました。アルゴリズムの正しいヒューリスティックを理解することができないからです。私は、効果的な最小化のための基準となるもの（良い経験則）が何かを理解することはできません。

問題は：

あなたはリストのリストを与えられている（[[0,1,0,1]、[...]、[...]、[...]、... ]））（内部リストの最後の要素は関数の値を表す）。検索アルゴリズム（例A *、BFS、IDA *、DFS、..）のみを使用して、ブール関数の最小論理和形式を検出するプログラムを作成します。それぞれの問題について、それを解決する20年があります。

Answer 1

私はあなたの州が有効な組み合わせのセットであると仮定します。ここでは単純な許容ヒューリスティックです。 Uを、現在の状態のいずれかの結合によって一致しない1へマッピングする関数入力の集合とする。 Uは空ではないが、Uの入力xを選ぶ。すべての入力yを削除して、xとyと一致する有効な結合が存在するようにする。

実際には、この問題はset coverのインスタンスとみなすことができ、このヒューリスティックはLPリラクゼーションの2つの解決法を貪欲に構築しています。 LPソルバにアクセスできない場合は、デュアルLPを最適化することで、より高品質な（ただし、速度は遅くなる可能性があります）ヒューリスティックを得ることができます。