極小非可解構造に基づく3COLインスタンスの組織的生成

水野 一徳  西原 清一  

誌名
電子情報通信学会論文誌 D   Vol.J87-D1   No.11   pp.1012-1019
発行日: 2004/11/01
Online ISSN: 
DOI: 
Print ISSN: 0915-1915
論文種別: 論文
専門分野: 人工知能,認知科学
キーワード: 
グラフ彩色,  探索,  相転移,  NP完全,  ヒューリスティクス,  

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


あらまし: 
本論文では,解を求める(可解性を判定する)のに非常に手間のかかるグラフ3彩色問題(3COL)の具体的問題(インスタンス)を組織的に生成する方法を提案する.従来のランダムに生成したインスタンスの中から困難なものを選びとるというアプローチとは異なり,本方法は,初期グラフに対して,3COLの極小非可解構造を繰り返し埋め込むことによって,困難な問題を確実に生成することを目指すものである.生成されたインスタンスは,従来より指摘されてきた解探索が非常に困難となる問題の諸条件に合致している.また,いくつかの解探索アルゴリズムを用いて,頂点数の指数オーダの手間を要することを実験的に確認する.