2026-04-14T12:52:28Z https://ipsj.ixsq.nii.ac.jp/oai

oai:ipsj.ixsq.nii.ac.jp:00241893 2025-01-19T07:30:22Z 1164:2592:11887:11888

木分解を用いた組合せ最適化問題に対する局所探索の高速化 後出, 祥臣 儀間, 達也 小林, 靖明 グラフ上のNP困難な組合せ最適化問題に対しては，グラフの木幅が小さいときには理論的にも実用的にも高速な解放が知られている．しかしながら，現実世界の様々なデータをグラフとしてみなしたとき，そのグラフの木幅が小さいとは限らず，そのようなグラフ上で問題を実用的な時間で解くためには，発見的解法を用いることが一般的である．本研究では，多くの発見的解法において重要な部分問題である，組合せ最適化問題に対する局所改善解に対して，木分解を用いた高速化について議論する． 情報処理学会 2025-01-07 jpn technical report https://ipsj.ixsq.nii.ac.jp/records/241893 2188-8566 AN1009593X 研究報告アルゴリズム（AL） 2025-AL-201 5 1 8 https://ipsj.ixsq.nii.ac.jp/record/241893/files/IPSJ-AL25201005.pdf application/pdf 319.2 kB 2027-01-07