擬似的な木を用いた分散制約最適化手法のための木の幅を考慮した空間複雑度の削減

松井　俊浩  松尾　啓志  

誌名
電子情報通信学会論文誌 D   Vol.J89-D   No.12   pp.2637-2647
発行日: 2006/12/01
Online ISSN: 1881-0225
DOI: 
Print ISSN: 1880-4535
論文種別: 論文
専門分野: 分散協調とエージェント
キーワード: 
分散制約最適化問題,  分散制約充足問題,  マルチエージェント,  擬似的な木,  

本文: PDF(566.6KB)>>
論文を購入



あらまし: 
分散制約最適化問題は分散制約充足問題を最適化問題に拡張したものとして，マルチエージェントシステム，分散協調問題解決の基礎的な分野として研究されている．近年，制約網に対する深さ優先探索木などの擬似的な木(pseudo-tree)による変数順序付けと動的計画法に基づく分散制約最適化手法が提案された．本論文では，この分散制約最適化手法の補助的な手段として，擬似的な木の幅が制限される値を超える部分について各エージェントが必要とする記憶及びメッセージのサイズについての空間複雑度を制限するための基本的な手法を提案する．一部の変数について部分的にバックトラックを導入する手法，及び，貪欲戦略の一つとして一部の変数の値をあらかじめ固定する手法を示す．また，提案手法の有効性について評価する．