平面グラフの初等閉路による最小被覆を求めるヒューリスティック・アルゴリズム
スポンサーリンク
概要
- 論文の詳細を見る
本論文では, 平面グラフの初等閉路による最小被覆を求める一つのヒューリスティック・アルゴリズムを提案している.「初等閉路による最小被覆を求める問題」は, 工学的応用に関連が深いが, 従来のアルゴリズムは, 最適解を与えるかわりに計算量の点で問題があった. 本論文では工学的観点より, 比較的大規模な実用規模のグラフに対する近似解を与えるためのヒューリスティック・アルゴリズムを開発し, それについて述べている. 本アルゴリズムは, 次のようなグラフの性質を利用している. (1)グラフを被覆する初等閉路の最適解の個数の下限は「D<max>/2」である. ここでD_<max>とは与えられたグラフの頂点次数の中で最大のもの. (2)グラフ上のD<max>を有するすべての頂点(ただし, D_<max>が偶数であれば, D<max-1>を有するあらゆる頂点も同時に含む)を通過する初等閉路が一つも存在しなければ, グラフを被覆する初等閉路の数の下限が増加する. なお, 本アルゴリズムは, 平面グラフにおいて一つの初等閉路が一連の連結した面に対応することに着目し, 解となる初等閉路を発見するために, グラフの面を連結する手法を用いており, その計算量はfをグラフの面の数とするとΟ(f^4)である.
- 一般社団法人情報処理学会の論文
- 1979-05-15
著者
関連論文
- ロボット技術はOA化に使えるか
- ランダムグラフの高速生成について
- 平面グラフの初等閉路による最小被覆を求めるヒューリスティック・アルゴリズム
- 平面グラフの単純閉路による最小被覆を求めるアルゴリズム
- グラフの関節点の発見と2連結性判定のための1アルゴリズム
- 一方通行路の存在する道路網におけるある種の最適経路問題
- 複数の移動ロボットの協調
- 交通ルールの適用による複数の移動ロボットの協調行動
- 未定係数法を用いたクリーネ代数の有限モデルの導出(多値論理及びその応用(4))
- 意識ネットを用いたロボットのヒューマンインターフェース
- 移動のためのロボット・ビジョン技術(ロボットビジョン)
- 移動のためのロボット・ビジョン技術
- 移動のためのビジョンセンサー技術
- 遠隔ステレオ視覚を用いたロボットにおけるヒューマンインターフェースについて
- 「感性とロボット」特集について
- 見果てぬ夢の中で
- 2連結ランダムグラフの生成アルゴリズムとの収束性と完全性の証明
- 人間におけるドットパターンの識別能力について
- ランダムグラフの高速生成とランダムネスについて
- FPLAのワンカット行畳み込み
- インバータを用いたPLA畳み込み
- ロボットビジョン、感性、意識の創生 (特集 ロボットビジョン--認識)
- ディジタル情報伝送のためのFM方式を用いた送受信装置の試作とその応用
- 超音波センサを用いた迷路探索ロボットMS-2の製作
- ロボットのためのZ-80アセンブラ言語を用いた迷路探索アルゴリズムとそのプログラム
- 迷路探索ロボットMS-1の製作
- 移動ロボットの経路探索(基盤技術とシステム化技術,機械工業におけるAI応用)
- ハンドアイ行動シミュレータ: HEAVENシステムに基づく視覚センサのオクルージョン回避
- 自己鏡映像認知への温故知新
- 安全作業におけるインタロックの構造と実現 (最近の電気機器・設備・システムにおける安全性・信頼性の高度化技術)
- 安全作業システムの原理とその論理的構造 (最近の電気機器・設備・システムにおける安全性・信頼性の高度化技術)
- 専門別情報へのアプローチ [第4回] 電気 I:ロボット－研究開発における文献調査ケーススタディ－
- Intelligence in ALV. (1). Behavior planning.
- 移動ロボットの移動障害物に対する衝突回避問題について