グラフ3彩色問題におけるEHIの組織的生成(<特集>「自動推論:帰納,演繹,モデル検査/生成,学習,発見,仮説推論,論理プログラム,プランニングetc.」及び一般)(一般及び自動推論)
スポンサーリンク
概要
- 論文の詳細を見る
本報告では,解を求める(可解性を判定する)のに非常に手間のかかるグラフ3彩色問題のインスタンス(EHI)を組織的に生成する方法を提案する.従来のランダムに生成したインスタンスの中から困難なものを選びとるというアプローチとは異なり,本方法は,初期グラフに対して,グラフ3彩色問題の極小非可解構造を繰り返し埋め込むことによって,困難な問題を確実に生成することを目指すものである.生成されたインスタンスは,従来より指摘されてきた解探索が非常に困難となる問題の諸条件に合致している.また,胤ヴ数の指数オーダの手間を要することを実験的に確認する.
- 社団法人電子情報通信学会の論文
- 2003-05-22
著者
-
西原 清一
筑波大学電子・情報工学系
-
水野 一徳
拓殖大学工学部情報工学科
-
水野 一徳
筑波大学電子・情報工学系
-
西原 清一
筑波大学非数値処理アルゴリズム研究室
-
西原 清一
筑波大学工学研究科電子・情報工学系
関連論文
- 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 制約充足問題における制約構造に注目した計算複雑さの考察
- グラフ色塗り問題の制約構造に基づく探索効率の解析
- 制約充足問題研究支援システム
- 適応的ノード選択による遺伝的プログラミングの効率改善 (ITSとモバイルコンピューティング)
- 5C-1 相互相関係数を用いたオプティカルフローによる内視鏡画像の奥行き情報抽出(画像処理基礎,一般セッション,人工知能と認知科学)
- 稜線の配置に制約を持つメッシュモデルの変形手法(セッション1:モデリング)
- 1ZF-2 B-spline曲面の制御点の削減手法と削減後の制御点を用いた曲面生成手法(CG:面,学生セッション,インターフェース)
- 2F-4 コンピュータマネキンを用いた高齢者の歩行時における転倒動作のシミュレーション(CG:一般,一般セッション,インターフェース)
- FFDを用いた3次元足部モデルの解剖学的特徴点抽出(コンピュータグラフィックス)
- 確率的制約充足アルゴリズムにおける局所最適構造
- プリミティブ合成による概略三面図からの3次元モデルの復元
- L-systemを用いた仮想都市のための道路網生成手法
- 遺伝的アルゴリズムを用いた仮想都市のための建物配置方式 (知能情報メディア論文特集)
- セルの相互作用とGAを用いた仮想都市の生成
- 3S-8 セルの相互作用に基づく仮想都市の創発
- 仮想都市生成システムのための建物配置手法の検討
- 4M-1 点字用分かち書きへの表層解析と形態素解析による事例ベース推論の導入
- 知識ベースに基づく点字翻訳のための日本語文節区切り手法
- ヒューマンインタフェースのための2点入力による相対運動認識方法
- 制約充足問題の多項式時間全解探索について
- 制約充足問題の多項式時間全解探索について
- 制約充足問題の計算複雑さについて(1)
- 曲線形状を含む部品図面の解釈
- 超並列ビジュアライゼーションマシーンの検討
- 拘束条件の構造を考慮した整合ラベリング問題の解法
- 制約に基づく対話型時間割編成システム
- 制約違反最少化戦略による対話型時間割編成システム
- 制約違反最少化戦略による対話型時間割編成システム
- 面の組合せ探索による三面図の解釈
- 曲げ加工機能を有する板金図面生成システム
- 曲げ加工機能を有する対話型図面生成システム
- 制約違反最少化戦略に基づくハイブリッドGAによる制約充足問題の解法
- ウイルス感染を用いたハイブリッドGAによるリアルタイム経路探索
- 遺伝的アルゴリズムによる制約充足問題の解法
- 遺伝的アルゴリズムによる制約充足問題の解法
- 1W-3 連結度に注目した難しい3彩色インスタンスの組織的生成(最適化,学生セッション,人工知能と認知科学,情報処理学会創立50周年記念)
- 仮想都市のためのL-systemによる道路網生成手法の検討
- F-023 制約充足問題のためのランク付け機能を有するACOの局所探索による解候補育成(F分野:人工知能・ゲーム,一般論文)
- 1W-2 制約充足に基づく勤務シフトスケジューリング(最適化,学生セッション,人工知能と認知科学,情報処理学会創立50周年記念)
- F-017 Binary CSPのための制約違反最小化戦略のハイブリッド型Ant Systemの効果(人工知能・ゲーム,一般論文)
- 拡張制約表現による時間割編成システム
- 整合ラベリングのための改良拘束伝播法
- 局所的手続きによる画像の偽輪郭の除去
- 三面図を対象とした知的CADシステム
- 制約充足問題の並列化効率に基づく分類
- 制約条件の構造に着目したCSPの分類方法
- 制約充足問題の併合解法における並列化の効率解析
- 知的仮想空間設計とボトムアップ型のシミュレーション(シミュレーション&プロトタイプ-工学知とデザイン知-)
- ニューラルネットワークの集団を用いた制約充足問題の解法
- 制約充足に基づく三面図理解システム
- 高速化の知識を取り入れた制約充足問題の一般解法
- 図面の直線形状による細線化歪みの除去
- 動的環境を対象とした遺伝的アルゴリズムによる実時間径路探索
- 対話的図形描画のための幾何制約ソルバ
- 特徴的幾何パターンに基づく不完全三面図の概略理解
- ニューラルネットワークを用いたオンラインハングル文字の適応認識
- あいまいな三面図の概略理解手法
- 面間の局所的拘束関係を用いた三面図解釈
- ハッシュ技術を用いた集合関数の処理法
- 制約知識ベースに基づく三面図理解
- 制約充足に基づく三面図理解
- 省略のある板金三面図からの3次元モデルの復元
- 省略の含まれる三面図からの3次元モデルの復元
- 省略の含まれる三面図からの3次元モデルの復元
- 地形を考慮したLシステムに基づく仮想都市のための道路網の生成
- 角運動量変化を利用した力覚提示デバイス(ウエアラブルVR)
- 板金向き三面図入力システムの開発曲げ加工におけるコーナーの自動生成
- 知識ベースにもとづく三面図の矛盾解消
- 図面の生成・理解によるモデリングのためのCADシステム : 画面理解および一般 : 画像処理・コンピュータビジョン
- 曲面を含む三面図の矛盾の検出と理解
- 図面の生成・理解によるモデリングのためのCADシステム
- 整合ラベリング問題における併合解法の並列化について
- 概整合ラベリング問題における併合法の最適化と効率評価
- 曲げ加工機能を有する板金図面生成システム
- 適応型確率探索による制約充足問題の解法
- 補助線を用いない三面図からの曲面物体の復元
- DLを使いこなそう:電子図書館のススメ