2015年11月28日土曜日

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

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



以下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^)


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

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

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

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

教えて偉い人。



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

最適化できそうなところがあったら教えてください。
#pragma once
#include"stdafx.h"
//タブーサーチクラス
template<class T_n>
class TabuSearchClass
{
private:
//現在の解
vector<T_n> current;
//最適解
vector<T_n> optimal;
//最適解のサイズ
size_t optimal_size;
//タブーリスト
vector<pair<T_n, T_n>> tabu_list;
//タブーリストのサイズ
size_t tabu_list_size;
//探索回数
size_t search_num;
//最大評価値
double max_evaluate;
//現在の評価値
double current_evaluate;
//乱数用
mt19937 mt;
//最適解と最大評価値の初期化
void Initialize()
{
optimal = vector<T_n>(this->current.begin(), current.begin() + optimal_size);
max_evaluate = current_evaluate = 0.;
}
//近傍の選択
vector<vector<T_n>> ChoiceNeighbor(const vector<T_n> &current)
{
size_t current_size = current.size();
//size_t data_size = GetDataSize();
vector<vector<T_n>> neighbor(current_size, vector<T_n>(current));
for (size_t i = 0; i < current_size; i++)
{
swap(neighbor[i][0], neighbor[i][i]);
}
return vector<vector<T_n>>(neighbor.begin() + 1, neighbor.end());
}
//優良解の探索
//predにはvector<T_n>の型を引数にした評価関数を渡す
template<class _Pre>
void ChoiceExellence(_Pre pred)
{
vector<vector<T_n>> neighbor = ChoiceNeighbor(this->current);
size_t solve_size = GetSolveSize();
size_t neighbor_size = neighbor.size();
double max = 0.;
double evaluate;
vector<pair<double, int>> better;
for (size_t i = 0; i < neighbor_size; i++)
{
evaluate = pred(vector<T_n>(neighbor[i].begin(), neighbor[i].begin() + solve_size));
/*if (evaluate>=max)
{
max = evaluate;
better = i;
}*/
better.push_back(make_pair(evaluate, i));
}
sort(better.begin(), better.end(), std::greater<pair<double, int>>());
this->current_evaluate = better[0].first;
for (auto &i : better)
{
if (CheckTransition(neighbor[i.second], make_pair(this->current[0], neighbor[i.second][0])))
break;
}
//this->current_evaluate = max;
//CheckTransition(neighbor[better], make_pair(neighbor[better][0], neighbor[better][better]));
//return neighbor[better];
}
//遷移がタブーリストに含まれているか判定
//含まれていたらtrue
bool CheckTabu(const pair<T_n, T_n> &transition)
{
for (auto &i : tabu_list)
{
if (i == transition || i == make_pair(transition.second, transition.first))
{
return true;
}
}
return false;
}
//現在の解を遷移するか判定
//遷移したらtrue
bool CheckTransition(const vector<T_n> &neighbor, const pair<T_n, T_n> &transition)
{
size_t solve_size = this->GetSolveSize();
if (current_evaluate > max_evaluate)
{
this->optimal = vector<T_n>(neighbor.begin(), neighbor.begin() + solve_size);
this->current = neighbor;
max_evaluate = current_evaluate;
if (CheckTabu(transition))
{
tabu_list.erase(find(tabu_list.begin(), tabu_list.end(), transition));
tabu_list.push_back(transition);
}
else
{
tabu_list.push_back(transition);
if (CheckTabuListSizeOver())
{
tabu_list.erase(tabu_list.begin());
}
}
return true;
}
else
{
if (!CheckTabu(transition))
{
this->current = neighbor;
tabu_list.push_back(transition);
if (CheckTabuListSizeOver())
{
tabu_list.erase(tabu_list.begin());
}
return true;
}
else
return false;
}
return false;
}
//タブーリストのサイズが指定のサイズをオーバーしたか判定
//オーバーしたらtrue
bool CheckTabuListSizeOver()
{
return tabu_list.size() > tabu_list_size;
}
//重複回数をカウント、指定回数以上重複でtrueを返す
class CheckConvergence
{
private:
vector<T_n> data;
int count;
int num;
public:
//コンストラクタはコメント表示されない?
CheckConvergence(){}
//dataに初期解、numに何回解が変わらなかったら収束するかを設定
CheckConvergence(const vector<T_n> &data, const int &num)
{
this->data = data;
this->count = 0;
this->num = num;
}
~CheckConvergence(){}
//countがnumを超えたらtrue(収束)
bool operator()(const vector<T_n> &data)
{
if (this->data == data)
{
count++;
}
else
{
this->data = data;
count = 0;
}
return count > num;
}
};
public:
//デフォルト値
//最適解のvectorのサイズ
static const size_t default_optimal_size = 10;
//探索回数
static const size_t default_search_num = 100;
//タブーリストのサイズ
static const size_t default_list_size = 7;
//コンストラクタ
TabuSearchClass()
{
SetMt();
}
//最適解を見つけたいvectorをvに渡す
TabuSearchClass(const vector<T_n> &v)
{
SetMt();
SetData(v);
SetOptimalSize(default_optimal_size);
SetSeachNum(default_search_num);
this->SetTabuListSize(default_list_size);
}
//最適解を見つけたいvectorをvに渡す
//最適解のvectorのサイズをoptimal_sizeに渡す
TabuSearchClass(const vector<T_n> &v, const size_t &optimal_size)
{
SetMt();
SetData(v);
SetOptimalSize(optimal_size);
SetSeachNum(100);
this->SetTabuListSize(7);
}
//最適解を見つけたいvectorをvに渡す
//最適解のvectorのサイズをoptimal_sizeに渡す
//探索回数をsearch_numに渡す
TabuSearchClass(const vector<T_n> &v, const size_t &optimal_size, const size_t &search_num)
{
SetMt();
SetData(v);
SetOptimalSize(optimal_size);
SetSeachNum(search_num);
this->SetTabuListSize(7);
}
//最適解を見つけたいvectorをvに渡す
//最適解のvectorのサイズをoptimal_sizeに渡す
//探索回数をsearch_numに渡す
//タブーリストのサイズをlist_sizeに渡す
TabuSearchClass
(
const vector<T_n> &v, const size_t &optimal_size, const size_t &search_num,
const size_t &list_size
)
{
SetMt();
SetData(v);
SetOptimalSize(optimal_size);
SetSeachNum(search_num);
this->SetTabuListSize(list_size);
}
~TabuSearchClass(){}
////最適解を見つけたいvectorをvに渡す
void SetData(const vector<T_n> &v)
{
this->current = v;
}
//最適解のvectorのサイズをoptimal_sizeに渡す
void SetOptimalSize(const size_t &size)
{
this->optimal_size = size;
}
//メルセンヌツイスタの初期化
void SetMt()
{
random_device rnd;
mt.seed(rnd());
}
//データのサイズを返す
size_t GetDataSize()const
{
return this->current.size();
}
//最適解のサイズを返す
size_t GetSolveSize()const
{
return this->optimal.size();
}
//タブーリストのサイズをsizeに設定する
void SetTabuListSize(const size_t &size)
{
this->tabu_list_size = size;
}
//タブーサーチをする
//predにはvector<T_n>の型を引数にした評価関数を渡す
template<class _Pre>
vector<T_n> TabuSearch(_Pre pred)
{
const size_t convergence_num = 5;
CheckConvergence obj(this->current, convergence_num);
Initialize();
for (int i = 0; !obj(this->current) && i < search_num; i++)
{
ChoiceExellence(pred);
//CheckTransition();
}
return optimal;
}
//探索回数をnumに設定
void SetSeachNum(const size_t &num)
{
this->search_num = num;
}
//最大評価値を返す
double GetMaxEvaluate()const
{
return max_evaluate;
}
};
view raw gistfile1.txt hosted with ❤ by GitHub

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


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

Lord of Walkureの討伐戦団最適化したい
タブー探索使ってみた
でも遅いから違う方法これから探す(^p^)

2015年11月21日土曜日

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

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

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

調べてみるも

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


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

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

まずはクラスを宣言しなければ始まりません。
class ClassClass
{
};
view raw gistfile1.txt hosted with ❤ by GitHub

これで宣言は終わりです。

~中身を充実させる~

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

と、その前に
クラスにはコンストラクタデストラクタ絶 対 に 必 要 で す !
コンストラクタとはクラスが使われるとき一番最初に実行される関数です。
デストラクタとはクラスが使われなくなる時に実行される関数です。
なんだそれ、と思う方もいるでしょう。というか、私がおもっています。
ですがそういうお約束なのです。
ここでは「おまじない」ということで納得しましょう。
コンストラクタはクラスと同じ名前、デストラクタはクラス名の前に~をつけます。
どちらも戻り値はありません。
class ClassClass
{
public:
ClassClass(){}
~ClassClass(){}
};
view raw gistfile1.txt hosted with ❤ by GitHub

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

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

コンストラクタもデストラクタも作りました。
今度こそクラスの中身を充実させていきましょう。
とりあえずhello worldでも表示させてみますか。
クラスの中に関数を作っちゃいましょう。
ユーザ関数と作り方は同じです。
戻り値 名前 引数 の順番ですね。
class ClassClass
{
public:
ClassClass(){}
~ClassClass(){}
void Hello()
{
cout << "hello world" << endl;
}
};
view raw gistfile1.txt hosted with ❤ by GitHub
printfじゃなくてcoutを使ってみました。
個人的にはcoutのほうが好きです。いろいろ便利ですし。

さて、あとはこれを実行するだけです。
とりあえずソースを貼りましょう。
int _tmain(int argc, _TCHAR* argv[])
{
ClassClass obj;
obj.Hello();
_getch();
return 0;
}
view raw gistfile1.txt hosted with ❤ by GitHub
まずobjという名前でクラスを宣言します。
objの中のHelloにアクセスするためにobj.Hello()と書きます。
_getch()は一時停止だと思ってください。
これでhello worldと表示されましたね。

~何回も表示させる~

C言語入門だと最初のほうでループを勉強するので、こっちも対抗してループを勉強しましょう。
内容は
hello worldを任意の回数表示させる
for文でくくっちゃえば一発ですね。
せっかくクラスの勉強してるんだからクラスの中でループさせましょう。
ところでさっき作ったHelloという関数、クラスの中でも使えます。
ということは新しく関数を作って、その中でループを回してHelloを実行する、ということができそうです。
じゃあ関数名は何にしましょうか・・・。
じつはC++にはオーバーライドという機能があります。
簡単に言っちゃえば同じ名前で違う機能をもった関数を定義することができる機能です。
今回みたいに似たような内容の関数を作るときに役立ちますね。
というわけで、新しい関数の名前もHelloにけって~い!
ただ、オーバーライドにもルールがあります。
同じ名前の関数がいっぱいあって、しかもそれぞれで内容が違うとなるとややこしいですよね?
だから、オーバーライドするときは引数を変えて、区別する必要があります。
最初に作ったHelloは引数なしなので、今回作るHelloにはint型の引数を与えましょう。
引数で与えられた回数だけhello worldを表示する、というわけですね。
というわけで、どん。
void Hello(int num)
{
for (int i = 0; i < num; i++)
{
Hello();
}
}
view raw gistfile1.txt hosted with ❤ by GitHub
この一文をクラスの中に追加するだけです。
これであとはmain文で呼んでいるHelloに好きな数字を渡せば、その回数分だけ表示してくれるってわけです。

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

クラスの世界にもなじんできたことですし、いつまでもhello worldと言っている場合ではありません。
なにかかっこいいことを言わせてみましょう。I'll be back とかどうです?
というわけで、I'll be back と表示するようにしましょう。
Helloの中でI'll be back と表示するように書き換えればいいですね。
いやいや、せっかくクラスの(ry
というわけで、何を表示させるかを取得する関数を作りましょう。
ところで、今まではクラスの中では関数しか宣言していませんでしたが、実は変数も宣言できます。
しかも、その変数(メンバ変数と呼ぶ)はクラスの中の関数(メンバ関数と呼ぶ)で使うことができます。
じゃあ、何を表示させるか取得する関数、取得したものを表示する関数を作ってみましょう。
というわけで、
string word;
void SetWord(string str)
{
this->word = str;
}
void Say()
{
cout << word << endl;
}
view raw gistfile1.txt hosted with ❤ by GitHub

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

~最初に取得~

これで好きな文字を表示できるようになったわけですが、毎回毎回SetWordを呼ぶのはめんどくさいですね。
最初に初期化みたいなことができればいいのに・・・。
・・・ハッ!?
最初に・・・。最初に・・・?
最初にといえばコンストラクタとかいうものがありましたね。
これを使って初期化してみましょう。
コンストラクタの引数をstring型にして・・・。というのはアウトです。
これも「おまじない」なのですが、引数なしのコンストラクタは絶対に必要です。
新しくstring型の引数を持つコンストラクタを作りましょう。コンストラクタのオーバーロードですね。
コンストラクタの中ではSetWordを呼び出せばよさそうです。
ついでなんで引数なしのコンストラクタではwordに空白を与えましょう。
というわけで、コチラ
class ClassClass
{
private:
string word;
public:
ClassClass()
{
SetWord("");
}
ClassClass(string str)
{
SetWord(str);
}
~ClassClass(){}
void Hello()
{
cout << "hello world" << endl;
}
void Hello(int num)
{
for (int i = 0; i < num; i++)
{
Hello();
}
}
void SetWord(string str)
{
this->word = str;
}
void Say()
{
cout << word << endl;
}
};
view raw gistfile1.txt hosted with ❤ by GitHub

おいおい、private:ってなんだよ!
はい、勝手に増やしてすみません^^;
privateっていうのはクラスの中でしか使えない、という目印です。これでwordを変更できるのはこのクラスの中だけになりました。

~加減乗除の鐘の声~

さあさあ、どんどん便利になってまいりました。
この調子でどんどん便利にしていきましょう。
次はですねー、表示する文字の付け足しでもやってみましょうか。
「醤油とってー。あ、あとマヨネーズも。」
日常ではよくある一言ですね。言った言葉に付け加える。これを実現しましょう。
Say呼んでSetWord呼んでSay呼んで、ハイ終わり。
いやいや、せっかく(ry
足し算をできるようにしましょう!
あらかじめ言わせたい言葉で初期化したクラスを二つ作り、二つの言葉を足して表示できるようにします。
ちょっと自分でも何言ってるのかわからなくなってきたので先にソースを載せましょう。
string GetWord()
{
return this->word;
}
string Add(ClassClass obj)
{
return this->word + obj.GetWord();
}
view raw gistfile1.txt hosted with ❤ by GitHub

これをクラスの中に加えたあとはmain文で
int _tmain(int argc, _TCHAR* argv[])
{
ClassClass obj1("oh"),obj2("yeah");
obj1.SetWord(obj1.Add(obj2));
obj1.Say();
_getch();
return 0;
}
view raw gistfile1.txt hosted with ❤ by GitHub

これでいいですね。
だがしかし・・・見づらい。
これは気持ち悪い。何とかしましょう。
そもそも足し算したいんだから+が使えると嬉しい。
じゃあ使えばいいんですよ。
クラスにはオペレータという機能があります。
クラスにとっての+とか-の意味を変える機能です。なんと強そうな。
早速使ってみましょう。
static const char space=' ';
string Add(ClassClass obj)
{
return this->word + space + obj.GetWord();
}
string operator+(ClassClass obj)
{
return Add(obj);
}
ClassClass& operator=(ClassClass obj)
{
SetWord(obj.GetWord());
return *this;
}
view raw gistfile1.txt hosted with ❤ by GitHub
static const ってなんですか?(#^p^)
これはクラス間で共有できる定数という意味です。今回は二語を足すとき、間に空白を入れるために使ってみました。
operator+のほうはAddの結果を返してるだけですね。
operator=のほうは戻り値とかが複雑で・・・。まあ、慣れてくれば意味が分かるようになると思うのでここでは「おまじない」ということにしておきます。
あとはmain文のほうですね。
int _tmain(int argc, _TCHAR* argv[])
{
ClassClass obj1("oh"),obj2("yeah");
obj1 = obj1 + obj2;
obj1.Say();
_getch();
return 0;
}
view raw gistfile1.txt hosted with ❤ by GitHub
どうですか?だいぶすっきりしたでしょ?

~おわり~

今回はこれで終了とします。どうですか?クラスの便利さをわかってもらえましたか?
クラスにはほかにもいろいろな機能があるのですが私自身使いこなせていないので紹介は省きました^^;
もうすこしスキルアップしたらクラスの隠された機能についても触れていこうと思います。
じゃあ、今回はこれで終わり!

今回作ったクラスの中身
#include<iostream>
#include<string>
using namespace std;
class ClassClass
{
private:
string word;
static const char space = ' ';
public:
ClassClass()
{
SetWord("");
}
ClassClass(string str)
{
SetWord(str);
}
~ClassClass(){}
void Hello()
{
cout << "hello world" << endl;
}
void Hello(int num)
{
for (int i = 0; i < num; i++)
{
Hello();
}
}
void SetWord(string str)
{
this->word = str;
}
void Say()
{
cout << word << endl;
}
void Say(int num)
{
for (int i = 0; i < num; i++)
Say();
}
string GetWord()
{
return this->word;
}
string Add(ClassClass obj)
{
return this->word + space + obj.GetWord();
}
string operator+(ClassClass obj)
{
return Add(obj);
}
ClassClass& operator=(ClassClass obj)
{
SetWord(obj.GetWord());
return *this;
}
};
view raw gistfile1.txt hosted with ❤ by GitHub