2024-03-29T08:58:41Zhttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_oaipmhoai:ipsj.ixsq.nii.ac.jp:000320202023-04-27T10:00:04Z01164:02592:02640:02642
禁止領域を持つ格子スタイナー木問題の発見的解法DRA heuristic algorithm DR for the rectilinear Steiner problem with rectangular obstaclesjpnhttp://id.nii.ac.jp/1001/00032020/Technical Reporthttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_action_common_download&item_id=32020&item_no=1&attribute_id=1&file_no=1Copyright (c) 2001 by the Information Processing Society of Japan広島大学大学院工学研究科情報工学専攻広島大学大学院工学研究科情報工学専攻広島大学大学院工学研究科情報工学専攻広島大学大学院工学研究科情報工学専攻橋目, 昭彦高藤, 大介田岡, 智志渡邉, 敏正格子スタイナー木問題とは,格子グラフH=(N A),禁止領域集合族Dと指定点集合Pが与えられたとき,H-D=(V E)$において,指定点をすべて含み,辺重みの総和が最小となる格子スタイナー木Rstを求める問題である.但し,H-DはHからDの各点とそれに接続する辺を取り除いたグラフである.本稿では,Dが空集合なる場合については,既存手法を組み合わせた改良手法を提案するとともに,既存手法で禁止領域が存在する場合を扱うための拡張法を述べる.一方,禁止領域が存在する場合については,まず高速解法DD を提案し,領域(格子グラフである部分グラフ)分割して,次に,各領域にDD を適用する手法DR を提案する.さらに,それらの手法の性能を実験的に評価する.The rectilinear Steiner tree problem with a family D of rectangular obstacles is defined as follows: given a rectilinear graph H=(N,A), a set P of terminal points, and a family D of rectangular obstacles, find a minimum cost rectilinear Steiner tree connecting P in the graph H-D which is a graph obtained by removing from H all points in D and all edges incident to points in D. For D = emptyset, we propose an improved algorithm by combining existing ones, and then describe how to extend it to be used in the case with D \ne emptyset. For D \ne emptyset, we first propose a fast heuristic algorithm DD . Also proposed is a heuristic algorithm DR based on partitioning H into some regions (rectilinear subgraphs), followed by applying DD to each region. Evaluating the performance of these algorithms through experimental results is also given."AN1009593X情報処理学会研究報告アルゴリズム(AL)200193(2001-AL-080)17242001-09-252009-06-30