分散制約充足問題：特定の制約網に特化した変数順序付けヒューリスティックの提案

• Item type: Journal(1)
• 公開日: 2011-11-15
• タイトル: 分散制約充足問題：特定の制約網に特化した変数順序付けヒューリスティックの提案
• タイトル / 言語: en
• タイトル: Effect of DisCSP Variable-ordering Heuristic for Particular Network Structure
• 言語: jpn
• キーワード / 主題Scheme: Other
• キーワード / 主題: 一般論文
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_6501
• 資源タイプ: journal article
• 著者所属: 九州大学大学院システム情報科学府情報学専攻横尾研究室
• 著者所属: 九州大学大学院システム情報科学府情報学専攻横尾研究室
• 著者所属: 九州大学大学院システム情報科学府情報学専攻横尾研究室
• 著者所属(英): en
• 著者所属(英): Graduate School of ISEE, Kyushu University
• 著者所属(英): en
• 著者所属(英): Graduate School of ISEE, Kyushu University
• 著者所属(英): en
• 著者所属(英): Graduate School of ISEE, Kyushu University
• 著者名: 沖本, 天太; 岩崎, 敦; 横尾, 真
• 著者名(英): Tenda, Okimoto; Atsushi, Iwasaki; Makoto, Yokoo
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 分散制約充足問題とは，制約充足問題における変数および制約が複数のエージェントに分散された問題である．既存の分散制約充足アルゴリズムのほとんどは，任意の制約網で動作することを保証している．しかし，特定の制約網，たとえば，ハブを含むようなスケールフリー的な制約網を対象とする場合，対象とする制約網に特化したアルゴリズム/ヒューリスティックが有効となることが予想される．我々の研究は，特定の制約網に特化したアルゴリズムの開発を目的とする．本論文では，その第1歩として，スケールフリー的な制約網に特化した静的な変数順序付けヒューリスティックを提案し，その有効性を示す．実験では，非同期バックトラッキングを用い，エージェントの優先順位の決定法が，スケールフリー的な制約網ではランダム構造の制約網より，アルゴリズムの性能に大きな影響を与えることを示す．さらに，エージェントの優先順位を提案手法と次数順に基づくヒューリスティックによって決定した，非同期バックトラッキングの性能を比較し，提案手法では最大29%の性能向上が得られることを示した．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: A Distributed Constraint Satisfaction Problem (DisCSP) is a constraint satisfaction problem in which variables and constraints are distributed among multiple agents. Various algorithms for solving DisCSPs have been developed, which are intended for general purposes, i.e., they can be applied to any network structure. However, if a network has some particular structure, e.g., the network structure is scale-free, we can expect that some specialized algorithms or heuristics, which are tuned for the network structure, can outperform general purpose algorithms/heuristics. In this paper, as an initial step toward developing specialized algorithms for particular network structures, we examine variable-ordering heuristics in scale-free networks. We use the classic asynchronous backtracking algorithm as a baseline algorithm and examine the effect of variable-ordering heuristics. First, we show that the choice of variable-ordering heuristics is more influential in scale-free networks than in random networks. Furthermore, we develop a novel variable-ordering heuristic that is specialized to scale-free networks. Experimental results illustrate that our new variable-ordering heuristic is more effective than a standard degree-based variable-ordering heuristic. Our proposed heuristic reduces the required cycles by 29% at the critical point.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN00116647
• 書誌情報: 情報処理学会論文誌; 巻 52, 号 11, p. 3018-3029, 発行日 2011-11-15
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 1882-7764