この論文では、分散 np 完全問題の効率的な解決法を検討します。これを行うために、csp 形式主義の拡張を提示します。有限領域における分散制約満足問題 (dcsp) と呼ばれるこの拡張により、パラダイムを分散制約満足問題の処理に拡張することが可能になります。情報システムを特徴づける情報の分布は問題の分布と密接に関係しているため、問題に効果的に対処する新しいアルゴリズム ツールを提供することが重要です。この論文は、古典的な csp ソリューション手法を新しいフレームワークに拡張したもの以上のものを構成します。分散フレームワークに固有の制約、特に情報の局所性と交換コストの制約を統合することにより、解像度の最適性の条件を再適切化します。これらの考慮事項により、この新しい枠組みで効果的な治療法を提示できるようになります。交換されるメッセージの数とサイズの両方において最適な、アーク一貫性によって制約ネットワークをフィルタリングするための最初の分散アルゴリズムを紹介します。このフィルタリング方法は、非指数関数的な空間消費の最初の完全な分散検索方法によって補完されます。分散ソリューション検索を拡張してインターリーブ化します。分散アーク一貫性フィルタリングにより、分散フレームワークにおける相転移現象の最初の特徴付けを行うことができます。最後に、これらのアーキテクチャに対するメタヒューリスティックの最初の適応を提示することにより、再構成可能なアーキテクチャ上のSat問題の処理に問題を拡張します。
#分散制約充足問題の処理