分散制約充足の高速化と通信網回線設定への適用

西部 喜康  桑原 和宏  石田 亨  横尾 真  

誌名
電子情報通信学会論文誌 D   Vol.J76-D2   No.10   pp.2204-2214
発行日: 1993/10/25
Online ISSN: 
DOI: 
Print ISSN: 0915-1923
論文種別: 論文
専門分野: 人工知能,認知科学
キーワード: 
分散協調問題解決,  制約充足,  順序付け,  通信網制御,  

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


あらまし: 
分散制約充足は分散人工知能のさまざまな問題を形式的に扱うための基盤として最近注目され始めている.我々は,文献(18)で,分散制約充足を形式的に定義すると共に,解の完全性(複数のエージェントが非同期に動作しても最終的には解を導くこと)を保証するアルゴリズムを示した.本論文では,分散制約充足アルゴリズムに対しヒューリスティックに基づいた順序付けを導入し,その処理の高速化を図る.この順序付けとは,変数,値の割当に順序を付けることによって探索空間の拡大を抑止する手法である.次いで,分散制約充足の適用問題として通信網回線設定を取り上げ,通信網回線設定がどのように分散制約充足問題に定式化されるかを示すと共に,実際の通信網データより生成した問題を用いた評価を示し,順序付けが有効であることを示す.