1

ブール関数を最小化するプログラムをPythonで作成する必要がありますが、問題は、たとえばA *またはより単純なアルゴリズムBFSなどの検索アルゴリズムを使用する必要があることです。反復深化を使用してプログラムを作成しました。すべての問題を解決しますが、遅すぎます (各問題の制限は 20 秒です)。

そこで、A* アルゴリズムを使用して別のプログラムを作成しました (より良いグレードが必要な場合は、これを使用する必要があると言われました) が、反復深化を使用するプログラムよりも 10 倍遅くすることができました。アルゴリズムの正しいヒューリスティックを見つけられません。効果的な最小化 (優れたヒューリスティック) の基準となるものを理解できません。

問題：

リストのリスト ([[0,1,0,1],[...],[...],[....],...]) が与えられ、真理値表 (最後の要素内側のリストは関数の値を表します)。検索アルゴリズム (A*、BFS、IDA*、DFS など) のみを使用して、ブール関数の最小選言形式を見つけるプログラムを作成してください。問題ごとに、それを解決するのに 20 秒かかります。

4

1 に答える 1

1

あなたの状態は有効な結合のセットであると仮定します。これは単純な許容可能なヒューリスティックです。U を、現在の状態のどの結合とも一致しない 1 にマッピングされる関数入力のセットとします。U は空ではありませんが、U の入力 x を選択します。x と y に一致する有効な結合が存在するように、U からすべての入力 y を削除します。U から選択された要素の数を返します。

実際、この問題はset coverのインスタンスと見なすことができ、このヒューリスティックは LP 緩和の双対に対する解を貪欲に構築しています。LP ソルバーにアクセスできる場合は、デュアル LP を最適化することで、より高品質の (ただし速度が遅くなる可能性がある) ヒューリスティックを取得できます。

于 2011-11-14T14:53:20.923 に答える