ほんにゃらふにゃぺ: 2015

2015年12月12日土曜日

[C++]HKM勉強したい＠そのいち

始まりました、「～したい」シリーズ。
今回はHKM≪階層的K平均法≫です。

話は変わるんですけど、ワタクシ大変なことに気づいてしまいました・・・。
「～したい」シリーズのタイトルの後ろについてる「＠その～」っていうバックナンバー、

そのいち、そのにぐらいまでしか続かない(^p^)

バックナンバーつける意味あるのかってね。

BBCPマコトの紹介記事とかだと結構続いたんですけどね。

飽きっぽい性格の私は一つの物事に集中して取り組めないのですよ(^p^)

いっそバックナンバー制廃止にしようかな。

まあ、それはさておいて、今回のタイトル「HKM」についてです。

HKMとは本来ならクラスタ分析をする為に使われる手法です。

今回はこれを最近傍探索に使います。

最近傍探索にはいろいろな手法があるのですが、これはKDtreeに似ているかもしれません。

KDtreeという手法は簡単に言えば

空間を分割する。
クエリが分割された空間のどこに属するか調べる。
クエリが属する空間の中に最近傍がある。

という手法です。

それに対してHKMは

データを2つのクラスタ（データの集合）に分ける。
分けられたクラスタの中のデータをさらに2つのクラスタに分ける。
クラスタの中のデータが1つになるまで1.2.を繰り返す。
クエリがどのクラスタに属するか調べる。
クエリが属するクラスタがの中に最近傍がある。

という手法です。

詳しいことは　知　り　ま　せ　ん　。

詳しい人は私にご教授ください。

とりあえず今回HKMを使うために使ったアルゴリズムとその紹介。

KNN（ｋ近傍法）　

クエリの近傍をｋ個求める手法。

アルゴリズム

クエリとデータベース全点の距離を計算。
距離を昇順にソート。
上からｋ個をとる。

Kmeans（ｋ平均法）

ｋ個のクラスタを作る手法。

アルゴリズム

空のクラスタをｋ個作る。
それぞれのクラスタにランダムにデータを割り当てる。
クラスタに含まれるデータの座標の平均をクラスタの中心とする。
各データと各クラスタ中心の距離を計算し、各データを最近傍となる各クラスタに割り当てなおす。
割り当ての変化量が一定の閾値以内になるまで3.4.を繰り返す。

HKM（階層的ｋ平均法）

階層的にｋ個のクラスタを作る手法。

アルゴリズム

ｋ個のクラスタを作る。
クラスタの中でさらにｋ個のクラスタを作る。
クラスタの中のデータが1個になるまで2.を繰り返す。

こんな感じです。

最初にKNNを作って、次にKNNを使ってKmeansを作って、次にKmeansを使ってHKMを作ります。

こういうの楽しいよね。

弱い武器を強化していって最強の武器を作るみたいな感じ。

テンションが上がりますね(^p^)

それでは以下ソース
量がやばい。

	#pragma once
	#include"KMeansClass.h"

	class HKMClass :public KMeansClass
	{
	public:
	static struct vertex
	{
	vertex* left;
	vertex* right;
	vector<CLASTER> claster;
	};

	static enum CONST
	{
	left,
	right,
	hk = 2,
	};

	vertex *node;

	HKMClass() :KMeansClass()
	{}

	HKMClass(const int &t) :KMeansClass(hk,t)
	{
	}

	HKMClass(const vector<DATA> &data, const int &t) :KMeansClass(hk,t)
	{
	this->node = MakeHKM(data);
	}

	~HKMClass(){}



	vertex* R_MakeHKM(const vector<DATA> &data)
	{
	vertex *node = new vertex();

	node->claster = MakeClaster(data, hk);
	if (node->claster[left].data.size() < hk)
	{
	node->left = NULL;
	}
	else
	{
	node->left = R_MakeHKM(node->claster[left].data);
	}

	if (node->claster[right].data.size() < hk)
	{
	node->right = NULL;
	}
	else
	{
	node->right = R_MakeHKM(node->claster[right].data);
	}

	return node;
	}

	vertex* MakeHKM(const vector<DATA> &data)
	{
	this->node = R_MakeHKM(data);
	return this->node;
	}

	vector<DATA> R_Search(const DATA &query,const vertex* node)
	{
	size_t claster_size = node->claster.size();
	if (claster_size < hk)
	{
	return node->claster[0].data;
	}



	vector<DATA> center(claster_size);

	for (int i = 0; i < claster_size;++i)
	{
	center[i] = node->claster[i].center;
	}
	KNNClass knn_obj(center, 1);
	int neighbor=knn_obj.KNN(query)[0].second;

	if ((node->left!=NULL)&&(neighbor == left \|\| node->right==NULL))
	{
	return R_Search(query, node->left);
	}
	else if ((node->right != NULL) && (neighbor == right \|\| node->left == NULL))
	{
	return R_Search(query, node->right);
	}
	else if (node->left == NULL&&node->right == NULL)
	{
	return node->claster[0].data;
	}
	else
	{

	}
	return vector<DATA>();
	}

	DATA Search(const DATA &query,const vertex* node)
	{
	return R_Search(query, node)[0];
	}

	DATA Search(const DATA &query)
	{
	return Search(query, this->node);
	}
	};

view raw HKMClass.h hosted with ❤ by GitHub

	#pragma once
	#include<vector>
	#include"KNNClass.h"
	#include"../../../Useful/useful.h"
	using namespace std;

	class KMeansClass
	{

	public:
	typedef vector<double> DATA;
	static struct CLASTER
	{
	vector<DATA> data;
	DATA center;
	};

	protected:
	int k;
	vector<CLASTER> claster;
	int threshold;

	void CalcCenter(vector<CLASTER> *claster)
	{

	size_t feature_size = (*claster)[0].data[0].size();

	for (auto &i : *claster)
	{
	i.center = VectorAverage(i.data);
	}

	}

	int ReassignData(vector<CLASTER> *claster, const int &k)
	{
	vector<DATA> center(k);
	for (int i = 0; i < k; ++i)
	{
	center[i] = (*claster)[i].center;
	}

	KNNClass knn_obj(center, 1);

	int difference = 0;

	for (int i = 0; i < k; i++)
	{
	size_t data_size = (*claster)[i].data.size();
	for (int j=0;j<data_size;++j)
	{
	DATA* temp = &(*claster)[i].data[j];
	int neighbor = knn_obj.KNN(*temp)[0].second;
	if (i != neighbor)
	{
	++difference;
	(claster)[neighbor].data.push_back(temp);
	(*claster)[i].data.erase
	(
	remove
	(
	(claster)[i].data.begin(), (claster)[i].data.end(), *temp
	)
	);
	data_size = (*claster)[i].data.size();
	}
	}
	}
	return difference;
	}

	void InitClasterData(vector<CLASTER> *claster)
	{
	for (auto &i : *claster)
	{
	i.data.clear();
	i.center.clear();
	}

	}

	void AllocateForNormal(vector<CLASTER> *claster, const vector<DATA> &data, const int &k)
	{
	int i = 0;

	for (auto &j : data)
	{
	(*claster)[++i%k].data.push_back(j);
	}
	}

	public:

	KMeansClass()
	{
	SetK(1);
	SetThreshold(100);
	}

	KMeansClass(const int &k)
	{
	SetK(k);
	SetThreshold(100);
	}

	KMeansClass(const int &k, const int &t)
	{
	SetK(k);
	SetThreshold(t);
	}

	KMeansClass(const vector<DATA> &data,const int &k, const int &t)
	{
	SetK(k);
	SetThreshold(t);
	MakeClaster(data);
	}

	~KMeansClass(){}


	vector<CLASTER> MakeClaster(const vector<DATA> &data, const int &k)
	{
	auto claster_size = k;
	vector<CLASTER> claster(k);
	AllocateForNormal(&claster, data, k);

	CalcCenter(&claster);
	while (threshold<ReassignData(&claster, k));
	this->claster = claster;
	return claster;
	}

	vector<DATA> Search(const DATA &query)
	{
	int claster_size = this->claster.size();

	vector<DATA> center(claster_size);

	for (int i = 0; i < claster_size; ++i)
	{
	center[i] = this->claster[i].center;
	}

	KNNClass knn_obj(center, 1);
	int neighbor = knn_obj.KNN(query)[0].second;

	return this->claster[neighbor].data;
	}

	vector<CLASTER> MakeClaster(const vector<DATA> &data)
	{
	return MakeClaster(data, this->k);
	}

	void InitClasterData()
	{
	InitClasterData(&this->claster);
	}


	void SetK(const int &k)
	{
	this->k = k;
	}
	void SetThreshold(const int &t)
	{
	this->threshold = t;
	}
	vector<CLASTER> GetClaster()
	{
	return this->claster;
	}

	};

view raw KMeansClass.h hosted with ❤ by GitHub

	#pragma once
	#include<vector>
	#include<utility>
	#include<algorithm>
	using namespace std;

	typedef vector<double> DATA;
	typedef vector<pair<double, int>> SOLVE;

	class KNNClass
	{

	private:
	vector<DATA> data_base;
	int k;

	double Sqare(const double &x)
	{
	return x*x;
	}

	double Distance(const DATA &a, const DATA &b)
	{
	auto size = a.size();
	double sum = 0.;
	for (auto i = 0; i < size; ++i)
	{
	sum += Sqare(a[i] - b[i]);
	}
	return sum;
	}

	public:
	KNNClass()
	{
	SetK(1);
	InitDataBase();
	}
	KNNClass(const int &k)
	{
	SetK(k);
	InitDataBase();
	}
	KNNClass(const vector<DATA> &data_base)
	{
	SetK(1);
	SetDataBase(data_base);
	}
	KNNClass(const vector<DATA> &data_base, const int &k)
	{
	SetK(k);
	SetDataBase(data_base);
	}
	~KNNClass(){}


	vector<pair<double, int>> KNN(const DATA &query, const vector<DATA> &data_base, const int &k)
	{
	auto size = data_base.size();
	vector<pair<double, int>> distance(size);

	for (auto i = 0; i < size; ++i)
	{
	distance[i] = make_pair(Distance(query, data_base[i]), i);
	}
	sort(distance.begin(), distance.end());


	return vector<pair<double, int>>(distance.begin(), distance.begin() + k);
	}

	vector<pair<double, int>> KNN(const DATA &query, const vector<DATA> &data_base)
	{
	return KNN(query, data_base, this->k);
	}

	vector<pair<double, int>> KNN(const DATA &query, const int &k)
	{
	return KNN(query, this->data_base, k);
	}

	vector<pair<double, int>> KNN(const DATA &query)
	{
	return KNN(query, this->data_base, this->k);
	}

	void SetK(const int &k)
	{
	this->k = k;
	}

	void SetDataBase(const vector<DATA> &data_base)
	{
	this->data_base = data_base;
	}

	void InitDataBase()
	{
	this->data_base.clear();
	}
	};

view raw KNNClass.h hosted with ❤ by GitHub

説明はきっといらないよね・・・？
アルゴリズムの紹介してるしね？

未来の俺はこう言う。
「コメント文ぐらい書けよ(#^p^)」

ってか、あれ、これ・・・

そのに、そのさんに分ければよかったんじゃね？？

2015年12月9日水曜日

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

なんかタブーサーチ改良することになったのでもう一度あげます。

～～変更点～～

・近傍生成方法を選べるようになったよ！
今のところ
・データを入れ替える
・bitを反転させる

の二つが選べます。

説明するのは面倒なので後日暇があったら画像付きで説明します。
まぢつかれたょ。。。

以下ソース


	#include <iostream>
	#include <vector>
	#include <algorithm>
	#include<random>
	#include<utility>
	#include<functional>

	using namespace std;


	//タブーサーチクラス
	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;

	//近傍生成方法
	public:
	static const enum Neighbor
	{
	DATASWAP,
	BITINVERT,
	};
	private:
	Neighbor neighbor;



	//探索回数
	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>> DataSwap(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());
	}
	vector<vector<T_n>> BitInvert(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++)
	{
	neighbor[i][i] = (neighbor[i][i] + 1) % 2;
	}
	return vector<vector<T_n>>(neighbor.begin() , neighbor.end());
	}

	//優良解の探索
	//predにはvector<T_n>の型を引数にした評価関数を渡す
	template<class _Pre>
	void ChoiceExellence(_Pre pred)
	{
	vector<vector<T_n>>(TabuSearchClass::*ChoiceNeighbor[])(const vector<T_n>&) =
	{
	&TabuSearchClass::DataSwap,
	&TabuSearchClass::BitInvert,
	};
	vector<vector<T_n>> neighbor = (this->*ChoiceNeighbor[this->neighbor])(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);
	SetNeighborMethod(DataSwap);
	}

	//最適解を見つけたい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);
	SetNeighborMethod(DataSwap);
	}

	//最適解を見つけたい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);
	SetNeighborMethod(DataSwap);
	}

	//最適解を見つけたいvectorをvに渡す
	//最適解のvectorのサイズをoptimal_sizeに渡す
	//探索回数をsearch_numに渡す
	//近傍生成方法をneighborに渡す
	TabuSearchClass
	(
	const vector<T_n> &v, const size_t &optimal_size, const size_t &search_num,const Neighbor &neighbor
	)
	{
	SetMt();
	SetData(v);
	SetOptimalSize(optimal_size);
	SetSeachNum(search_num);
	this->SetTabuListSize(7);
	SetNeighborMethod(neighbor);
	}

	//最適解を見つけたい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);
	SetNeighborMethod(DataSwap);
	}
	~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;
	}

	void SetNeighborMethod(const Neighbor &neighbor)
	{
	this->neighbor = neighbor;
	}
	};

	void main()
	{
	struct ITEM
	{
	public:
	int num;
	int income;
	int weight;

	bool operator==(const ITEM &i)const
	{
	return i.num == this->num;
	}
	};

	ITEM a[5] =
	{
	{ 0, 1, 2 },
	{ 1, 3, 4 },
	{ 2, 5, 6 },
	{ 3, 7, 8 },
	{ 4, 9, 0 },
	};

	vector<ITEM> v(5);
	for (int i = 0; i < 5;i++)
	{
	/*v[i].num = i;
	cout << "価格:" << flush;
	cin >> v[i].income;
	cout << "重さ:" << flush;
	cin >> v[i].weight;*/
	v[i] = a[i];
	}
	const int max_w = 10;
	vector<int> vv(5,0);
	{
	int weight = 0;
	for (int i = 0; i < 5; i++)
	{
	if (v[i].weight + weight < max_w)
	{
	vv[i] = 1;
	weight += v[i].weight;
	}
	}
	}
	TabuSearchClass<int> obj(vv, 5, 100,TabuSearchClass<int>::Neighbor::BITINVERT);
	//obj.SetWeight(100);
	vector<int> opt = obj.TabuSearch(
	[&](vector<int> &vv)
	{
	int sum = 0;
	int weight = 0;
	int max_w = 10;
	for (int i = 0; i < vv.size(); i++)
	{
	if (vv[i])
	{
	if (weight + v[i].weight < max_w)
	{
	weight += v[i].weight;
	sum += v[i].income;
	}
	}
	}
	return sum;
	}
	);
	for (int i = 0; i < opt.size();i++)
	{
	if (opt[i])
	cout << v[i].num << endl;
	}

	}

view raw gistfile1.txt hosted with ❤ by GitHub

今回はナップサック問題（？）を解いてみました。だって友達がやれやれうるさいんだもん。
ちゃんと解けてるはず。たぶん。

2015年11月28日土曜日

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

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

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

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

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

教えて偉い人。

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

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

	#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++]　クラス使いこなせるようになりたい＠その１

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呼んで、ハイ終わり。

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

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

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

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

	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

登録: 投稿 (Atom)

2015年12月12日土曜日

[C++]HKM勉強したい＠そのいち

KNN（ｋ近傍法）

Kmeans（ｋ平均法）

HKM（階層的ｋ平均法）

2015年12月9日水曜日

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

2015年11月28日土曜日

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

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

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

3628800！

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

計算結果・・・8秒

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

2015年11月21日土曜日

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

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

～中身を充実させる～

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

～何回も表示させる～

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

～最初に取得～

～加減乗除の鐘の声～

～おわり～

KNN（ｋ近傍法）　

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