最短経路探索、巡回セールスマン問題のソースコード


この記事から読む場合はまずは[問題編](http://qiita.com/izmktr/items/eb2aae1c544ca6f17b88)を見てください

アルゴリズムの解説は以下の記事を見てください。
[最短経路の求め方](http://qiita.com/izmktr/items/e93d58af5de0306a8278#_reference-b82099d1969dcea1c110)
[巡回セールスマン問題](http://qiita.com/izmktr/items/7eb574588b6c66dbaa96#_reference-5257ee87e826898d0743)

「電脳体「キュラゲタム」を討伐せよ」で提出したプログラムを若干コメントを入れつつ掲載します。

```cpp

#include <iostream>
#include <string>
#include <vector>
#include <deque>
#include <algorithm> 
#include <map> 
#include <limits.h>
#include <boost/format.hpp>   

#define PRINT(A) {std::cout << __FILE__ << "(" << __LINE__ << ") " << (#A) << ":" << (A) << std::endl;}

// 巡回セールスマン問題用のキャッシュ 
std::map<int, int> cache;

// x, y の座標クラス
class Position{
public:
	int x, y;
	Position(int x, int y):x(x), y(y){}
	Position operator+(const Position &p) const {return Position(x + p.x, y + p.y);}
	bool operator==(const Position &p) const {return x == p.x && y == p.y;}

	Position Adjacent(int n) const {
		switch(n){
		case 0: return *this + Position( 1, 0);
		case 1: return *this + Position( 0, 1);
		case 2: return *this + Position(-1, 0);
		case 3: return *this + Position( 0,-1);
		}
		return *this;
	}
};

// マップ、経路探査用の二次元vector 
class Field{
public:
	int width, height;
	std::vector<int> v;

	int GetIndex(const Position &p) const { return p.y * width + p.x; }
	bool IsInner(const Position &p) const {
		if (p.x < 0 || width <= p.x) return false;
		if (p.y < 0 || height <= p.y) return false;
		return true;
	}
	void Set(const Position &p, int time){ v[GetIndex(p)] = time; }
	int Get(const Position &p) const{ return v[GetIndex(p)]; }
	void Fill(int n){
		for (auto &i : v){ i = n; }
	}

	Field(int w, int h) :width(w), height(h), v(w * h){}

	int GetTime(const Position &now, const Position &move) const {
		if (!IsInner(move)) return 0;

		int nh = Get(now), mh = Get(move);
		if (nh == mh) return 3;
		if (nh == mh - 1) return 11;
		if (nh == mh + 1) return 2;
		return 0;
	}

	void Print(){
		for (int y = 0; y < height; y++){
			for (int x = 0; x < width; x++){
				std::cout << (boost::format("%3d") % Get(Position(x, y))) << " ";
			}
			std::cout << std::endl;
		}
		std::cout << std::endl;
	}
};

// 山頂とそこから経路探査した地図を格納するクラス 
struct Atlas {
	Position start;
	Field distance;
	int index;
	Atlas() :start(0, 0), distance(0, 0), index(0){}
	Atlas(const Position &p, Field field, int index) :start(p), distance(field), index(index){}
};

// 経路探索関数
// 引数 field:高さマップ position スタート地点
// 返り値 スタート地点からの時間
Field Calc(const Field &f, const Position &s){
	std::deque<Position> queue;
	queue.push_back(s);
	Field work(f.width, f.height);

	int maxtime = 999999;
	work.Fill(maxtime);
	work.Set(s, 0);

	while (!queue.empty()){
		auto npos = queue.front();
		queue.pop_front();
		for (int i = 0; i < 4; i++){
			Position next = npos.Adjacent(i);
			int time = f.GetTime(npos, next);
			int total = time + work.Get(npos);
			if (0 < time && total < work.Get(next)){
				work.Set(next, total);
				queue.push_back(next);
			}
		}
	}

	return work;
}

// begin～endの区間で、limitより大きく最も小さい要素を探す関数
template<typename T, typename U>
T limitminimum(T begin, T end, U limit){
	T result = end;
	for (T it = begin; it != end; ++it){
		if (limit < *it){
			if (result == end || *it < *result) result = it;
		}
	}
	return result;
}

// begin～endの区間で、最も小さい要素を探す関数
template<typename T>
T minimum(T begin, T end){
	T result = end;
	for (T it = begin; it != end; ++it){
		if (result == end || *it < *result) result = it;
	}
	return result;
}

// 残りの山頂とスタートの山頂を32bitに変換する関数
int GetBit(std::vector<Atlas *>::iterator begin, std::vector<Atlas *>::iterator end){
	int result = 0;

	for (std::vector<Atlas *>::iterator it = begin; it != end; it++){
		result |= 1 << (*it)->index;
	}

	result |= (*begin)->index << 20;

	return result;
}

// 巡回セールスマン問題を解く関数
int GetMinTime(std::vector<Atlas *> &atlasarray, std::vector<Atlas *>::iterator now){
	if (now + 1 == atlasarray.end()){
		return (*now)->distance.Get(atlasarray.front()->start);
	}

	int bit = GetBit(now, atlasarray.end());
	auto it = cache.find(bit);
	if (it != cache.end()) return it->second;

	auto top = minimum(now + 1, atlasarray.end());
	std::swap(*(now + 1), *top);

	int mintime = INT_MAX;
	for (;;){
		auto next = now + 1;
		int time = (*now)->distance.Get((*next)->start);

		if (time < mintime){
			int resttime = GetMinTime(atlasarray, next);
			time += resttime;
			if (0 < resttime && time < mintime){
				mintime = time;
			}
		}

		auto swapit = limitminimum(next, atlasarray.end(), *next);

		if (swapit == atlasarray.end()) break;
		std::swap(*next, *swapit);
	}

	cache[bit] = mintime;
	return mintime;
}

int main(){
	int w = 5, h = 4;
	
	//標準入力から高さマップの大きさを読み込み
	std::cin  >> h >> w;
	std::string str;
	std::getline(std::cin, str);

	Field f(w, h);

	// 高さマップを読み込みながら最も高い地点を検索
	int maxheight = 0;
	for (int y = 0; y < h; y++){
		std::string str;
		std::getline(std::cin, str);
		if (str.empty()) return 1;
		for (int x = 0; x < w; x++){
			int height = str[x] - '0';
			f.Set(Position(x, y), height);
			if (maxheight < height) maxheight = height;
		}
	}

	std::vector<Atlas *> atlasarray;
	atlasarray.push_back(new Atlas(Position(0, 0), Calc(f, Position(0, 0)), 0));

	// 山頂を探し、見つけたら経路探索したマップを作成
	for (int y = 0; y < h; y++){
		for (int x = 0; x < w; x++){
			Position p(x, y);
			if (f.Get(p) == maxheight){
				Atlas *atlas = new Atlas(p, Calc(f, p), atlasarray.size());
				atlasarray.push_back(atlas);
			}
		}
	}

 	// 巡回セールスマン問題を解く
 	int time = GetMinTime(atlasarray, atlasarray.begin());
 
 	// 結果を表示
 	std::cout << time << std::endl;

 	for(auto it = atlasarray.begin(); it != atlasarray.end();++it) delete *it;

	return 0;
}

```

最短経路探索で今回は座標をdequeに入れていますが、
アルゴリズムの解説にあったとおり、priority_queueを使ったほうが良いでしょう。

巡回セールスマン問題では、スタート地点と経路を事前に求めてキャッシュすると説明しましたが、
今回の場合は自前に15個以下と提示されていましたので、32bitのうち下位20bitを通る地点、
上位の12bitにスタート地点を入れて一つのint型で表せるようにしています。
(GetBit関数の部分です。)