最適系列分割問題に対するDPとBBアルゴリズム

IPSJ

Search this article

Description

本論文はノードが番号順に列をなし、あるサイズP以下の部分集合に、カットされるエッジのコストの総和を最小分割する問題である。応用例としてはページングにおける仮想アドレスへのプログラムの最適配置などがある。この問題に対してKernighan[l]はダイナミックプログラミング(DP)によるアルゴリズムを示している。本論分ではこれに対して、DPにおける計算量の再検討と、さらにBranch-and-Bound法(B&B)法をもちいたアルゴリズムを提案し、その計算量を比較検討する。

Journal

  • 全国大会講演論文集

    全国大会講演論文集 第41回 (基礎理論及び基礎技術), 79-80, 1990-09-04

    情報処理学会

Details 詳細情報について

Report a problem

Back to top