[C++]タブーサーチ作りたい

タブーサーチクラスを作れたと思ったのでアップ。
２，３回動かしてうまくいっただけなのでもしかしたらバグがあるかもしれない。
まあ、今回はそれなりに満足いけたものを作れた気がする。
あと、今忙しくて全然書くことまとめれてないから今度暇なときにこの記事修正する。 
未来の自分へ
お前は次に「こんなの使わねえよｗｗ」と言う。
・・・ハッ！？



以下2015/11/30追記

いやー、やっとひと段落しました。いや、してないんですけどね。とりあえずはゆっくり記事書けるぐらいの時間は確保できたと。

それじゃあ、今回作ったタブーサーチの紹介でもしますか。

タブーサーチとは（ﾃﾞﾃﾞﾝ!

探索アルゴリズムの手法の一つだそうです。詳しいことはあまり知りません(^p^)

DMMのLord　of　Walkureというゲームでですね、討伐戦団というコンテンツがありまして。

主人公とワルキューレ（味方）×10人がボスを倒す、という内容です。

この討伐っていうのがすごく難しくて、ワルキューレの隊列の組み方で勝率に影響が出るんですよね。

例えば、A、B、C、D、Eというワルキューレがいたとして、隊列を[ABCDE]にして戦うと勝率が30%だったとします。

これを[BACDE]としただけで勝率が50%まで跳ね上がる、なんてことがあるんですよ。

ボスとは無限に戦えるわけじゃないからできるだけ勝率を高くしたい・・・。

そんなわけでシミュレータを作りました。（今回はシミュレータの方のプログラムは載せません＾＾；理由は後述）

Lord　of　Walkureは課金をしなかった場合、最大で50枚ほどのワルキューレを仲間にすることができます。その中から一番効率よくボスを倒せる10人を選ぶわけです。数式で表すと50P10です。

とりあえず4P4でシミュレーションしてみることにしました。べ、別にデータ入力が面倒だったわけじゃないんだからね(^p^)

計算結果は4秒。まあ、こんなもんかな。次に10P10で計算。

・・・計算が終わらないだと？

そうなんです。計算が終わらなかったんです。ブレークポイントを作って確認してみると計算自体はしているようでした。不思議に思いながら何も考えずに10P10を計算してみると

3628800！

300万回も計算する必要があったわけです。4P4を計算すると24になったので、一秒に6回計算できるわけです。300万回の計算には50万秒必要なわけで、50万秒はおよそ8000分で、8000分はおよそ140時間で、140時間はおよそ5日という計算になります。

本当は50P10の計算をしたいんです。

しかし、この値を計算すると37.27604302[P]となります。［P]って知ってますか？10の15乗のことらしいですよ。

僕もよくわからないんですけど、多分私が生きている間に計算を終えることが不可能なんじゃないかなと思います。

あほらしくなりましたね(^p^)

しかし、ここであきらめるほど私はヤワじゃない！

ここからようやくタブーサーチの話に入るわけです。

全件探索するから遅いんです。効率よく探索すれば早いはず！

ということで探索アルゴリズムを使うことに。

個人的には遺伝アルゴリズムなんかに興味があったのですが、「タブー探索勉強中！」といっている友人がいたのでタブー探索を使うことにしました。

アルゴリズムの内容に関してはwikipediaで調べたものを基本的に使っています。

私の日本語力がないからかもしれませんが、一部よくわからないところがあったのでそこは自分で補完しました。

以下、探索の流れ

1.初期解の生成

2.解の近傍生成

3.優良解の判定

4.現在解の更新判定

5.タブー判定

6.2.～5.を現在解が収束するか、任意の計算回数になるまでループ

とりあえずテスト。

任意の個数の数値をn個組み合わせて総和が最大になるものを探索します。

評価関数は素直に総和を返すようにします。

ちょっと何言ってるかわからないと思うので実際に見せます。

総和が一番大きくなる組み合わせになっていそうですね。

ただ、今回は並び方も考慮したいので、並び順も評価関数に組み込みたいですね。

場所によって重みをつけることにしましょう。後ろにあるほうがより重くなるということです。

7,8,9,10,11と出力してくれればうれしいです。

されたっぽいですね。

じゃあテスト終わり。

いよいよ討伐シミュレータに組み込みます。

まずは4P4をどれだけ高速化できるか・・・！

（正確には4個のデータの組み合わせです。）

計算結果・・・8秒

(#^p^)

(#^p^)(#^p^)

普通に計算した時より遅いし。

ｷﾚｿｳ(#^p^)

というわけでシミュレータ機能せず・・・。

タブー探索の収束条件とかもうちょっといじれそう。

ほかにも最適化できそうなところがちらほら・・・。

これを直せば早くなるんでしょうか？

教えて偉い人。

とりあえず動作はしているのでタブー探索のソースをあげます。

最適化できそうなところがあったら教えてください。

あと、だれかもっと効率のいいアルゴリズム教えてください。ってかワルキューレのシミュレータ作ってください。

長すぎるんだよ！3行でまとめろよ！

Lord　of　Walkureの討伐戦団最適化したい

タブー探索使ってみた

でも遅いから違う方法これから探す(^p^)