分枝限定法による系列分割問題の算法構成と効率

• Item type: SIG Technical Reports(1)
• 公開日: 1992-07-17
• タイトル: 分枝限定法による系列分割問題の算法構成と効率
• タイトル / 言語: en
• タイトル: Algorithm and Efficiency of Branch -and- Bound for Optimal Sequential Partitions
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 北海道情報大学
• 著者所属: 北海道大学
• 著者所属(英): en
• 著者所属(英): Hokkaido Information University
• 著者所属(英): en
• 著者所属(英): Hokkaido University
• 著者名: 加地, 太一; 大内, 東
• 著者名(英): Taichi, Kaji; Azuma, Ohuchi
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 最適系列グラフ分割は系列グラフに対して、各頂点に与えられた重みの総和がブロックサイズP（>）以下であり、かつ、部分集合の頂点番号が連続的に保持される条件のもとで、カットされる辺のコストの和が最小となるよう分割する問題である。著者等はこの系列分割問題の特殊性を有効に利用した分枝限定法による構成を明らかにする。算法の効率性を考察するために、次の6つの構成要素である分枝規則、探索規則、削除規則、優越関係、下限値関数、上限値に着目して算法を構成する。さらに上記の規則のもとて非活性化された節点をクローズド・リストに管理し最良優先探索法を用いることによって、確定性が得られることを明らかにする。以上の確定性が得られる算法の構成法による効率性の関係を示し、さらに0(oglo)の計算量が得られることを示す。
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: Optimal sequential partitions of graphs is to find a minimum cost partition of the nodes of a graph into subsets of a given size, subjecting to the constraint that the sequence of the nodes may not be changed, that the nodes in the a subset must be of consecutive numbers. We apply the Branch-and-Bound algorithm to the problem. Branch-and-Bound implicit enumeration algorithm has recently emerged as the principal general method for finding optimal solutions for discreat optimization problems. We give an efficient sixtuple characterization for this problem. So, we evaluate the performance of the proposed algorithm, and show that the computing complexity of the algorithm has O(nloglog N) time and O(n) space. We present the results of the performance of the algorithm.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 情報処理学会研究報告アルゴリズム（AL）; 巻 1992, 号 58(1992-AL-028), p. 25-32, 発行日 1992-07-17
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会