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