はてなブックマーク

概要 マラソンマッチにおける有力なアルゴリズムとして焼きなましとビームサーチがある。 たいていの問題においてこのどちらかのうちより適切な方を実装すれば上位が得られることや、性質や実装の仕方が異なることから、これらの関係は二項対立のようにして理解されている。 しかしこのふたつのアルゴリズムがどちらも貪欲法の延長にあることも知られている。 この記事では、貪欲法を中心に整理して焼きなましとビームサーチの二項対立の構図は適切でないことを示す。 特に、これらの差異が状態空間の間のグラフが有向であるか無向であるかのみであることを明らかにし、下図のような形で整理する。 またその系として、焼きなましとビームサーチの間で互いに知見を流用できることを説明する。 <?xml version=”1.0” encoding=”UTF-8”?> 状態のグラフが有向 状態のグラフが無向 貪欲 / 山登り ビームサーチ