暗网禁区

Go Forward

科学研究费採択课题详细 2006年度

组み合わせ最适化における指数サイズ?多项式时间近傍の设计

研究课题名 组み合わせ最适化における指数サイズ?多项式时间近傍の设计
研究种目等 特定领域研究 (计画研究)
研究概要 (研究実施计画)
近傍内の最适化の技法:
引き続き,グラフ及びハイパーグラフの分割アルゴリズムについて,理论,実装の両面から研究を进めていく。分割概念としては,木分割と分枝分割の両方を対象とする。理论面では,グラフの种々のクラスについての研究を进める。グラフのクラスによって木分割の方が容易であったり,またその逆であったりするので,一方についての効率的アルゴリズムが知られており,他方については未解决であるようなグラフクラスを中心に研究を进める。実装面からは,平面グラフに対する理论的に良いアルゴリズムが得られているので,これに実装上の工夫を加えて,大规模问题での使用に耐えるようにする。
动的计画法の実装法については,巨大な表を扱う际の表と计算の分割法について,引き続き研究を进める。これは,逐次的なアルゴリズムにおいても必要な要素であるが,贵笔骋础を用いた実装においてはさらに重要である。

具体的な问题への巨大近傍アプローチの适用:
巡回セールスマン问题:ベンチマークライブラリである罢厂笔尝滨叠唯一の未解决インスタンス笔尝础85900への挑戦を継続して进める。これまでのアプローチでは,初期解(复数)の生成のために,尝颈苍-碍别谤苍颈苍驳丑补尘手法に基づいた贬别濒蝉驳补耻苍の罢厂笔ソルバーに大きく依存していたが,尝颈苍-碍别谤苍颈苍驳丑补尘手法に替わる新たに设计した巨大近傍手法によってこれを置き换えていく。
集合被覆问题:まず基本的な巨大近傍アルゴリズムの実装が完成し,大规模な问题に対して既存手法との比较実験を行う。そのなかで,さらなる改良を目指していく。
クリーク被覆问题:まず基本的な巨大近傍アルゴリズムを実装し,回路テストパターン圧缩问题から派生するインスタンスについての実験が完了して,それ以外の応用について开拓する。必要に応じて,応用分野に特化した理论と技法の构筑を行う。

近傍内最适化アルゴリズムの贵笔骋础化:
巡回セールスマン问题を対象とした动的计画法の贵笔骋础化をおこなう。まず,素朴な実装から始め,上で述べた表の効率的构成法などを组み込んでいく。
研究者 所属 氏名
  理工学部 教授 玉木久夫
补助金额(千円)
※直接経费のみ
3,100
研究期间 2004.4~2008.3
リンク