Approach Vanilla beam search を改善しました。
Vanilla beam search
- 評価関数 : 転倒数
- 近傍 : reverse 全部
改善
- 近傍 : 小さい数字が reverse の左端にならないものに限定する
- X が小さいときの評価関数 : 端からソート済みの数
- X が小さいときの近傍 : ソートされていない部分の端をソート済みにする reverse (1~3手、3手のときは3つソート済みになる)
- selection sort のスコアと比べて悪いときは、selection sort を使う。
Example scores:
1) 12.0
2) 843.0
3) 3065.0
4) 6736.0
5) 869.0
6) 208641.0
7) 12026.0
8) 22540.0
9) 34990.0
10) 549.0
Approach(その他)
- 分割統治(RotatingNumbers の Psyho さんの解に引っ張られた)
- 中央で大きい reverse を使ったが、それ以外が雑だったかも。
- koyumeishi さんがヨシ!とかやってそう。
- bubble sort で初期解(reverse の列)を作って、reverse の順序入れ替え、分解、合併を近傍とする焼きなまし
- bubble sort の初期解からだと、合併があまりできなかった。 selection sort から分解の方が良かったか?