タブー探索

「変更して得られたものの中に、S よりも良いものがない」ときに、そこで終了せずに、解が悪くなってもかまわないから、悪いなりにいいほうに移動してしまおう、というものです。ただし、次に、今いるところに戻ってきてしまうと、同じところを行ったり来たりしてしまうので、悪いところに移動するときは、「こっちに戻ってはダメ」という印を付けておきます。この方法はタブー探索と呼ばれています。