極小非可解構造に基づく3COLインスタンスの組織的生成(人工知能,認知科学)
スポンサーリンク
概要
- 論文の詳細を見る
本論文では,解を求める(可解性を判定する)のに非常に手間のかかるグラフ3彩色問題(3COL)の具体的問題(インスタンス)を組織的に生成する方法を提案する.従来のランダムに生成したインスタンスの中から困難なものを選びとるというアプローチとは異なり,本方法は,初期グラフに対して,3COLの極小非可解構造を繰り返し埋め込むことによって,困難な問題を確実に生成することを目指すものである.生成されたインスタンスは,従来より指摘されてきた解探索が非常に困難となる問題の諸条件に合致している.また,いくつかの解探索アルゴリズムを用いて,頂点数の指数オーダの手間を要することを実験的に確認する.
- 社団法人電子情報通信学会の論文
- 2004-11-01
著者
-
西原 清一
筑波大学大学院システム情報工学研究科
-
水野 一徳
拓殖大学工学部情報工学科
-
水野 一徳
筑波大学大学院工学研究科電子・情報工学専攻:(現)筑波大学ベンチャービジネスラボラトリー
-
西原 清一
筑波大学非数値処理アルゴリズム研究室
-
西原 清一
筑波大学工学研究科電子・情報工学系
-
水野 一徳
拓殖大 工
-
西原 清一
筑波大学大学院コンピュータサイエンス専攻
関連論文
- 3C-7 連続断面画像集合からの3次元領域抽出のためのシステム開発(画像処理・認識,一般セッション,人工知能と認知科学)
- 5Z-3 実世界指向の3D形状データ変換手法の提案(モデリング,学生セッション,インタフェース)
- 事例・ルール間変換による知識編成方式と日本語点字翻訳の分かち書き問題への適用
- 5C-4 セルオートマトンによる仮想都市空間内の土地利用変化シミュレーション(複雑系,一般セッション,人工知能と認知科学)
- 5S-5 Binary CSPのための制約違反最小化戦略に基づくハイブリッド型Ant Systemの提案(認知・推論・探索,学生セッション,人工知能と認知科学)
- 5S-4 極小非可解構造の埋め込み操作による3COLインスタンスの組織的生成(認知・推論・探索,学生セッション,人工知能と認知科学)
- 極小非可解構造の埋め込みによる難しい3-COLインスタンスの組織的生成 (特集 「機械学習の諸科学への応用」および一般)
- 1ZE-4 制約充足に基づく図面理解システムのGUI開発(CG:モデリング,探索,学生セッション,インターフェース)
- 3V-1 マルチエージェント型交通シミュレータと歩行者エージェントの導入(マルチエージェント(1),学生セッション,人工知能と認知科学)
- 1V-5 蟻の集団を用いたBinaryCSPの解法(学習・推論,学生セッション,人工知能と認知科学)
- 6C-7 仮想都市における交通シミュレーションによる動的経路選択の有用性の検証(ニューラルネット・マルチエージェント,一般セッション,人工知能と認知科学)
- 資源割当てを伴う複数経路探索における対話的制約充足
- 極小非可解構造に基づく3COLインスタンスの組織的生成(人工知能,認知科学)
- 時間変化する仮想都市における道路網の自動生成
- 図面理解システムにおける制約充足に基づくプロトタイピング
- 事例知識を用いた日本語点字翻訳とエラー修正支援
- グラフ3彩色問題におけるEHIの組織的生成(「自動推論:帰納,演繹,モデル検査/生成,学習,発見,仮説推論,論理プログラム,プランニングetc.」及び一般)(一般及び自動推論)
- 非常に難しいグラフ3彩色問題の組織的生成法と考察
- 事例ベース推論と制約充足に基づく室内レイアウト変更計画(自動推論 : 演繹, 帰納, モデル検査/生成, 仮説推論アブダクション, 論理プログラム, プランニング, 時相論理, etc.)
- 確率的制約充足アルゴリズムにおける局所最適構造
- 1N-3 制約充足問題における制約構造に注目した計算複雑さの考察
- グラフ色塗り問題の制約構造に基づく探索効率の解析
- 極小非可解構造に基づく連結度を考慮した3COLインスタンスの組織的生成 (特集 「知識発見の生命科学への応用」および一般)
- 点連結度に注目した難しい3COLインスタンスの組織的生成 (特集 「ベイジアン・ネットワークと応用」および一般)
- 3K-2 遺伝的プログラミングによる3次元仮想人間の歩行生成 : ターミナルの適応選択手法
- 適応的ノード選択による遺伝的プログラミングの効率改善 (ITSとモバイルコンピューティング)
- 適応ターミナル選択による遺伝的プログラミングの性能向上
- 5C-1 相互相関係数を用いたオプティカルフローによる内視鏡画像の奥行き情報抽出(画像処理基礎,一般セッション,人工知能と認知科学)
- 稜線の配置に制約を持つメッシュモデルの変形手法(セッション1:モデリング)
- 1ZF-2 B-spline曲面の制御点の削減手法と削減後の制御点を用いた曲面生成手法(CG:面,学生セッション,インターフェース)
- 2F-4 コンピュータマネキンを用いた高齢者の歩行時における転倒動作のシミュレーション(CG:一般,一般セッション,インターフェース)
- 2F-3 特徴点・特徴ライン位置を用いた個人用人台作成ソフトの開発(CG:一般,一般セッション,インターフェース)
- 3次元情報抽出のための疑似透視投影モデル因子分解法と透視投影モデル最小二乗法の比較(セッション1:CG一般,テーマ:エンターテイメントのためのCGおよびCG一般)
- FFDを用いた3次元足部モデルの解剖学的特徴点抽出(コンピュータグラフィックス)
- 確率的制約充足アルゴリズムにおける局所最適構造
- バブル・メッシュ法によるメッシュ制御法の提案(セッション4:製品設計への応用,テーマ:エンターテイメントのためのCGおよびCG一般)
- L-systemを用いた仮想都市のための道路網生成手法
- 制約充足問題の解探索アルゴリズムおよび効率評価に関する研究(問題解決手法)(人工知能分野における博士論文)
- 特別講演 : メディア情報の処理とCV
- メディア情報の処理とCV
- A Novel Thinning Scheme for Reducing Thinning Distortions
- 1W-3 連結度に注目した難しい3彩色インスタンスの組織的生成(最適化,学生セッション,人工知能と認知科学,情報処理学会創立50周年記念)
- F-023 制約充足問題のためのランク付け機能を有するACOの局所探索による解候補育成(F分野:人工知能・ゲーム,一般論文)
- 1W-2 制約充足に基づく勤務シフトスケジューリング(最適化,学生セッション,人工知能と認知科学,情報処理学会創立50周年記念)
- F-017 Binary CSPのための制約違反最小化戦略のハイブリッド型Ant Systemの効果(人工知能・ゲーム,一般論文)
- 知的仮想空間設計とボトムアップ型のシミュレーション(シミュレーション&プロトタイプ-工学知とデザイン知-)
- ニューラルネットワークの集団を用いた制約充足問題の解法
- 交通信号制御のための分散制約充足方式の提案 (テーマ:知能・適応と社会,ネットワーク) -- (マルチエージェントシステム)
- 対話的図形描画のための幾何制約ソルバ
- 対話的図形描画のための幾何制約ソルバ
- 特徴的幾何パターンに基づく不完全三面図の概略理解
- 特徴的幾何形状マッチングによる不完全三面図からの3次元モデル復元
- 事例を用いたオンライン点字翻訳支援システム
- 地形を考慮したLシステムに基づく仮想都市のための道路網の生成
- 適応型確率探索による制約充足問題の解法
- 適応型確率探索による制約充足問題の解法
- Swarmを用いたデマンドバスのシミュレーション環境の構築
- エッシャー風タイリング画像作成支援システム
- F-034 グラフ彩色インスタンス生成のためのGAに基づく極小非可解構造の導出(知能システム,F分野:人工知能・ゲーム)
- DLを使いこなそう:電子図書館のススメ
- Finding Minimal Unsolvable Structures for Constructive Generation of Graph 3-Colorability Instances