![](https://www.acri.c.titech.ac.jp/wordpress/wp-content/uploads/2020/10/top-image-1-300x180.png)
FPGAを用いた「組合せ問題」の高速計算(3)
前回は、MaxSAT の一種である Partial MaxSAT の定義、最大クリーク問題の Partial MaxSAT への変換、局所探索法に基づく Parital MaxSAT の発見的解法である Dist アルゴリズムについて述べました。 今回は、Dist の FPGA 実装に当たっての難点と、それを回避するためにどのようにアルゴリズムの簡略化を行ったかについて説明します。 Dist アルゴリズム 図1に、Dist アルゴリズムの全体像を再掲します (ステップ5 〜 ...