巡回カメラマン問題とその自動光学的検査への応用
スポンサーリンク
概要
- 論文の詳細を見る
巡回カメラマン問題とは,平面上に互いに素な有限個の領域が与えられた時,それらの全ての領域の単位正方形による集合被覆を考え,それらの中心点をめぐる巡回路の経路長を最小に問題である.つまり,集合被覆と巡回セールスマン問題を組み合わせた問題になっている.この問題は,プリント基盤の自動光学的検査から派生したものである.当論文では,この問題に対する定数比率を持つ近似アルゴリズムを提唱する.また,各領域が異なる長方形の場合や,被覆に用いる正方形のサイズが可変だが,各領域毎に被覆に用いる正方形の最大サイズが決められている変種も考察する.最後の問題は,プリント基盤の自動光学的検査におけるズーム機能に相当する.
- 一般社団法人情報処理学会の論文
- 1994-07-22
著者
-
岩野 和生
日本IBM株式会社大和ソフトウェア開発研究所
-
玉木 久夫
明治大学理工学部情報科学科
-
Raghavan Prabhakar
米国IBMワトソン研究所
-
玉木 久夫
米国IBMワトソン研究所
-
Tamaki Hisao
The School Of Science And Technology Meiji University
-
Tamaki Hisao
Department Of Computer Science Meiji University
-
Hisao Tamaki
Department Of Computer Science Meiji University.
-
岩野 和生
日本アイ・ビー・エム株式会社東京基礎研究所
-
岩野 和生
日本ibm
関連論文
- 1-D-4 経路長を短くする一方通行決定(離散・組合せ最適化(2))
- 大学における情報化戦略と理工系情報学科の貢献
- 最小カット問題に対するKargerのランダムアルゴリズムの新しい確率的評価について
- 点集合の距離重複度列のノルムと最大部分集合問題
- 密な部分グラフ問題の貪欲解法
- 放物線のアレンジメントの組合せ複雑度について
- 平面グラフの刻み幅決定アルゴリズムの小交差数グラフへの拡張に向けて
- 頂点彩色問題に対する列生成法アプローチの高速化
- テストパターンの静的圧縮における厳密解と貧欲解の比較(上流テスト・テスト圧縮,VLSI設計とテスト及び一般)
- 平面ユークリッドTSPの分割統治法ヒューリスティツクス
- 平面グラフの分枝幅決定アルゴリズムの効率的実装
- グラフ及び領域空間に関する大域丸めの幾何学的性質について
- 合成数のAKS witnessに関する実験的研究
- 小さな碁盤における囲碁の厳密解アルゴリズム
- TD-1-12 アルゴリズムデモ発見的動的計画法 : 巡回セールスマン問題を例として
- ハイパーキューブ上の順列の同形を反復しない網羅的生成
- 平面巡回セールスマン問題に対するアローラの近似アルゴリズムの効率的実装
- Spanning Trees Crossing Few Barriers (Algorithm Engineering as a New Paradigm)
- 障害物との交差数が少ない全域木
- パラメトリックなポリマトロイドとその幾何学的応用
- 平面点集合のk巡回路被覆問題: kが定数の場合の多項式時間近似スキーム
- 巡回カメラマン問題とその自動光学的検査への応用
- TSP解法の実験的解析とそれに基づく2-Optと相性のよいツアー構築法の提案
- 教育を目的としたC言語ソース管理APIの作成とその応用(e-learning/一般)
- JavaのeラーニングのためのEclipseプラグインの開発(e-learning/一般)
- 極小横断列挙のメモリ効率の良いアルゴリズム
- 2H-7 耐故障トーラス構成の一方式とシミュレーションによる評価
- Voronoi Diagrams with Respect to Criteria on Vision Information
- 単一根有向グラフと対称変換に基づいた囲碁の棋譜管理・閲覧システムの開発(セッション(1) : ゲーム情報学(1))
- 巡回セールスマン問題の近似アルゴリズム:天才アローラによる20年ぶりの急進展(近似アルゴリズムに関する最近の話題)
- 経路最適化問題の近似アルゴリズム : 幾何学的/非幾何学的場合の対比
- ハイパーキューブ上の単距離置換のルーティング
- 組合せ的解析における確率的手法
- 製造業における巡回セールスマン問題の応用
- サーキットボード穴開け問題
- 最大流アルゴリズムの最近の発展とその背景 : II
- 最大流アルゴリズムの最近の発展とその背景 : I
- 「情報アクセシビリティー : 高齢者, 障害者からはじまる新しい情報パラダイム」
- A New Probabilistic Evaluation of Karger's Randomized Algorithm for Minimum Cut Problems
- A New Randomized Approach to the Minimum Cut Problem and Its Variants by Minimum Range Cut Algorithms
- 大学における情報化戦略と理工系情報学科の貢献(パネル討論)
- Graph Orientation Problems for Multiple st-Reachability
- k-cyclic Orientations of Graphs
- グラフの自動描画における交差を考慮した巨大近傍探索
- 良い『メモリ図』の生成
- Routing a Permutation in the Hypercube by Two Sets of Edge-Disjoint Paths
- 最大格差最小k-カットアルゴリズムによる最小k-カット問題の近似解法 (組合せ最適化)
- 物理的世界とデジタルの世界の融合がもたらすもの Smarter Planet の目指す世界
- マネジメント最前線1 新技術が社会と企業にもたらすもの (特集 グリッド・コンピューティング)
- シミュレーション技術への期待
- 巡回セールスマン問題をめぐる最近の話題
- 理論と実際の邂逅の場としての情報処理学会
- Algorithms for the Maximum Subarray Problem Based on Matrix Multiplication
- Approximation Algorithms for Geometric Optimization Problems(Special Issue on Algorithm Engineering : Surveys)
- Computing directed pathwidth in O(1.89n) time
- A Fast and Simple Subexponential Fixed Parameter Algorithm for One-Sided Crossing Minimization
- A Linear Edge Kernel for Two-Layer Crossing Minimization
- Search space reduction through commitments in pathwidth computation: an experimental study