aspirator https://blog.hatena.ne.jp/aspirator/ aspirator’s blog https://aspirator.hateblo.jp/ こんにちは。 平衡二分探索木で2-optを高速化する方法について研究したので、本記事ではそれについて書こうと思います。 2-optとは 2-optは巡回セールスマン問題(TSP)の近似解を求めるヒューリスティックアルゴリズムです。 下図のように、サイクルに対してランダムに二つのパスを選び、パスを組み替えた方がサイクルの長さが短くなる場合、パスを組み替えます。具体的には、A→B + C→D > A→C + B→D の時、辺ABと辺CDを辺ACと辺BDに組み替えます。 しかし、辺を張り直すだけではサイクルにならないので、B~CまたはD~Aの間の順序を逆にする必要があります。 2-opt法では順路を… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Faspirator.hateblo.jp%2Fentry%2F2021%2F03%2F25%2F195611" title="平衡二分探索木を使った2-optの効率化について - aspirator’s blog" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> https://cdn-ak.f.st-hatena.com/images/fotolife/a/aspirator/20210325/20210325193100.jpg Hatena Blog https://hatena.blog 2021-03-25 19:56:11 rich https://aspirator.hateblo.jp/entry/2021/03/25/195611 1.0 100%