動物園経路問題に関する新しいアルゴリズム

• Item type: SIG Technical Reports(1)
• 公開日: 1995-01-23
• タイトル: 動物園経路問題に関する新しいアルゴリズム
• タイトル / 言語: en
• タイトル: New Algorithms for the Zoo - keeper Route Problem
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 東海大学開発工学部
• 著者所属(英): en
• 著者所属(英): School of High - Technology for Human Welfare, Tokai University
• 著者名: 譚, 学厚
• 著者名(英): Xuehou, Tan
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: Pを単純多角形とし、p'をPの境界線に付けられる凸多角形の集合とする。動物園経路問題とは、P'の多角形をすべて訪れる最短経路を求めることである。，nを多角形PとP'の各多角形の総辺数とする。本論文では動物園経路問題を解く二つの新しいアルゴリズムを与える。一つは決定的なアルゴリズムであり、0（）の時間を要する。ここでkはP'の多角形の最大サイズである。もう一つは線形時間で近似解法を与える。近似解は最適解のπ/2倍内であることが保証される。これらのアルゴリズムは以前の結果を改良する。
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: Let P be a simple polygon and let P be a set of convex polygons that lie in the interior of P and are attached to the boundary of P. The zoo-keeper route problem asks for a shortest route inside P that visits (but does not enter) each polygon in P. Let n be the total number of vertices of polygon P and polygons in P. We present two new algorithms for the zoo-keeper route problem; one is deterministic and runs in O(kn) time where k is the maximum size of polygons in P', and the other gives an approximate solution that is guaranteed to be within π/2 times the optimal solution value and takes only linear time. Both of our results improve upon the previous results.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 情報処理学会研究報告アルゴリズム（AL）; 巻 1995, 号 10(1994-AL-043), p. 9-16, 発行日 1995-01-23
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会