[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^)

[C++] クラス使いこなせるようになりたい＠その１

C++を使うようになってから初めて聞いた言葉　クラス。

便利だよ、すごいんだよ、と聞かされてきた　オブジェクト指向。

調べてみるも

さ　っ　ぱ　り　わ　か　ん　ね　ぇ　(#^p^)


というわけで今回からクラスの勉強を始めようと思います。
将来C++のことをきれいさっぱり忘れ去ってしまった時のためになるべくわかりやすいようにしたいですね。
では早速

～とりあえずクラス宣言～

まずはクラスを宣言しなければ始まりません。
これで宣言は終わりです。

～中身を充実させる～

クラス宣言が終わりました。
これは「こんなクラスがあるよ！」と主張しているのです！
では次に「こんなことができるんだよ！」と主張しましょう。

と、その前に
クラスにはコンストラクタとデストラクタが絶　対　に　必　要　で　す　！
コンストラクタとはクラスが使われるとき一番最初に実行される関数です。
デストラクタとはクラスが使われなくなる時に実行される関数です。
なんだそれ、と思う方もいるでしょう。というか、私がおもっています。
ですがそういうお約束なのです。
ここでは「おまじない」ということで納得しましょう。
コンストラクタはクラスと同じ名前、デストラクタはクラス名の前に~をつけます。
どちらも戻り値はありません。

public:ってなんだ？
「おまじない」です。(^p^)
(　){　}ってなんだ？
これはですね、(　)が引数です。今回はありません。{　}が関数の中身です。これも今回はありません。
つまりなにもしません。(^p^)

～今度こそ中身を充実させる～

コンストラクタもデストラクタも作りました。

今度こそクラスの中身を充実させていきましょう。

とりあえずhello　worldでも表示させてみますか。

クラスの中に関数を作っちゃいましょう。

ユーザ関数と作り方は同じです。

戻り値　名前　引数　の順番ですね。

printfじゃなくてcoutを使ってみました。
個人的にはcoutのほうが好きです。いろいろ便利ですし。

さて、あとはこれを実行するだけです。
とりあえずソースを貼りましょう。
まずobjという名前でクラスを宣言します。
objの中のHelloにアクセスするためにobj.Hello()と書きます。
_getch()は一時停止だと思ってください。
これでhello　worldと表示されましたね。

～何回も表示させる～

C言語入門だと最初のほうでループを勉強するので、こっちも対抗してループを勉強しましょう。

内容は

hello　worldを任意の回数表示させる

for文でくくっちゃえば一発ですね。

せっかくクラスの勉強してるんだからクラスの中でループさせましょう。

ところでさっき作ったHelloという関数、クラスの中でも使えます。

ということは新しく関数を作って、その中でループを回してHelloを実行する、ということができそうです。

じゃあ関数名は何にしましょうか・・・。

じつはC++にはオーバーライドという機能があります。

簡単に言っちゃえば同じ名前で違う機能をもった関数を定義することができる機能です。

今回みたいに似たような内容の関数を作るときに役立ちますね。

というわけで、新しい関数の名前もHelloにけって～い！

ただ、オーバーライドにもルールがあります。

同じ名前の関数がいっぱいあって、しかもそれぞれで内容が違うとなるとややこしいですよね？

だから、オーバーライドするときは引数を変えて、区別する必要があります。

最初に作ったHelloは引数なしなので、今回作るHelloにはint型の引数を与えましょう。

引数で与えられた回数だけhello　worldを表示する、というわけですね。
というわけで、どん。
この一文をクラスの中に追加するだけです。
これであとはmain文で呼んでいるHelloに好きな数字を渡せば、その回数分だけ表示してくれるってわけです。

～好きな文字を表示させる～

クラスの世界にもなじんできたことですし、いつまでもhello　worldと言っている場合ではありません。

なにかかっこいいことを言わせてみましょう。I'll　be　back　とかどうです？

というわけで、I'll　be　back　と表示するようにしましょう。

Helloの中でI'll　be　back　と表示するように書き換えればいいですね。

いやいや、せっかくクラスの(ry

というわけで、何を表示させるかを取得する関数を作りましょう。

ところで、今まではクラスの中では関数しか宣言していませんでしたが、実は変数も宣言できます。

しかも、その変数（メンバ変数と呼ぶ）はクラスの中の関数（メンバ関数と呼ぶ）で使うことができます。
じゃあ、何を表示させるか取得する関数、取得したものを表示する関数を作ってみましょう。

というわけで、

SetWordの中で使われているthis->ですが、これは「こいつはこのクラスのメンバですよ」という意味です。無くてもいいけど、あると見やすいかもしれないです。
Sayの中は特に説明しなくても大丈夫ですね。余裕のある方は任意の回数表示できるように拡張してみてください。

～最初に取得～

これで好きな文字を表示できるようになったわけですが、毎回毎回SetWordを呼ぶのはめんどくさいですね。

最初に初期化みたいなことができればいいのに・・・。

・・・ハッ！？

最初に・・・。最初に・・・？

最初にといえばコンストラクタとかいうものがありましたね。

これを使って初期化してみましょう。

コンストラクタの引数をstring型にして・・・。というのはアウトです。

これも「おまじない」なのですが、引数なしのコンストラクタは絶対に必要です。

新しくstring型の引数を持つコンストラクタを作りましょう。コンストラクタのオーバーロードですね。

コンストラクタの中ではSetWordを呼び出せばよさそうです。

ついでなんで引数なしのコンストラクタではwordに空白を与えましょう。

というわけで、コチラ

おいおい、private:ってなんだよ！

はい、勝手に増やしてすみません＾＾；

privateっていうのはクラスの中でしか使えない、という目印です。これでwordを変更できるのはこのクラスの中だけになりました。

～加減乗除の鐘の声～

さあさあ、どんどん便利になってまいりました。

この調子でどんどん便利にしていきましょう。

次はですねー、表示する文字の付け足しでもやってみましょうか。

「醤油とってー。あ、あとマヨネーズも。」

日常ではよくある一言ですね。言った言葉に付け加える。これを実現しましょう。

Say呼んでSetWord呼んでSay呼んで、ハイ終わり。

いやいや、せっかく（ｒｙ

足し算をできるようにしましょう！

あらかじめ言わせたい言葉で初期化したクラスを二つ作り、二つの言葉を足して表示できるようにします。

ちょっと自分でも何言ってるのかわからなくなってきたので先にソースを載せましょう。

これをクラスの中に加えたあとはmain文で

これでいいですね。

だがしかし・・・見づらい。

これは気持ち悪い。何とかしましょう。
そもそも足し算したいんだから＋が使えると嬉しい。
じゃあ使えばいいんですよ。
クラスにはオペレータという機能があります。
クラスにとっての＋とか－の意味を変える機能です。なんと強そうな。
早速使ってみましょう。
static　const　ってなんですか？(#^p^)
これはクラス間で共有できる定数という意味です。今回は二語を足すとき、間に空白を入れるために使ってみました。
operator+のほうはAddの結果を返してるだけですね。
operator=のほうは戻り値とかが複雑で・・・。まあ、慣れてくれば意味が分かるようになると思うのでここでは「おまじない」ということにしておきます。
あとはmain文のほうですね。
どうですか？だいぶすっきりしたでしょ？

～おわり～

今回はこれで終了とします。どうですか？クラスの便利さをわかってもらえましたか？

クラスにはほかにもいろいろな機能があるのですが私自身使いこなせていないので紹介は省きました＾＾；

もうすこしスキルアップしたらクラスの隠された機能についても触れていこうと思います。

じゃあ、今回はこれで終わり！

今回作ったクラスの中身