- 著者
-
加地 太一
大内 東
- 出版者
- 社団法人情報処理学会
- 雑誌
- 情報処理学会論文誌 (ISSN:18827764)
- 巻号頁・発行日
- vol.35, no.3, pp.364-372, 1994-03-15
- 被引用文献数
-
5
頂点が連続的な番号を保持し、始点が初期番号、終点が最終番号となり、両端点が異なるグラフをG(V、E)とする。本論文に右ける最適系列グラフ分割問題はグラフGに対して、各頂点に与えられた重みの総和がブロックサイズP(>0)以下であり、かつ、部分集合の頂点番号が連続的に保特される条件のもとで、カットされる辺のコストの和が最小となるよう分割する問題である。本問題の一つの応用例としては、プログラムを一定の大きさの単位で記億頒域に割当を行うぺ一シングの手法が考えられる。本論文では動的計算による最適系列分割問題に対して、探索法為よび限定操作の観点から改善の余地があるものと考え、分技限定法の手法を導入することによりて効率的算法を構成する。さらに得られた算法の数値実験にもとづいて算法の特性と性能評価を行い、理論的計算量についても論じる。以上より、漸近的計算量は等しいが、細分化禁止則、反復回数の減少、同レベルの優越関係による削除、下界値こよる限定などの探索空間の実際の絞り込みによって計算量の負担を軽減することが可能であることを示す。