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

情報処理学会

この論文をさがす

説明

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

収録刊行物

  • 全国大会講演論文集

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

    情報処理学会

詳細情報 詳細情報について

問題の指摘

ページトップへ