alabama_country @Wiki
CPP-assign-2009-10-27
最終更新:
alabama_country
-
view
A*アルゴリズム
ソース
#include <iostream>
#include <vector>
#include <queue>
inline int abs(const int x)
{
return (x >= 0) ? x : -x;
}
struct Point
{
int x,y;
Point(){};
Point(int x, int y)
: x(x), y(y)
{
};
};
class EightPazzle
{
private:
int path;
std::vector<std::vector<int> > number;
public:
EightPazzle(const EightPazzle &obj);
EightPazzle(std::vector<std::vector<int> > array);
int cost_to_goal() const;
const int get_path() const{return path;};
int cost() const{ return cost_to_goal() + path; };
Point zero() const
{
for(unsigned int i=0; i<number.size(); ++i)
for(unsigned int j=0; j<number[i].size();++j)
if(number[i][j] == 0)
return Point(i, j);
return Point(-1,-1);
};
void older_age(){++path;};
void restore_age(){--path;};
void next(std::priority_queue<EightPazzle>& task);
friend std::ostream &operator<<(std::ostream &st, const EightPazzle& obj)
{
for(std::vector<std::vector<int> >::const_iterator i = obj.number.begin();
i != obj.number.end(); ++i)
{
for(std::vector<int>::const_iterator j = i->begin();
j != i->end(); ++j)
st << *j;
st << std::endl;
}
return st;
};
friend bool operator<(const EightPazzle &a, const EightPazzle &b)
{
return a.cost() > b.cost();
};
};
EightPazzle::EightPazzle(const EightPazzle &obj)
: path(obj.path), number(obj.number)
{
};
EightPazzle::EightPazzle(std::vector<std::vector<int> > array)
: path(0)
{
number = array;
};
int EightPazzle::cost_to_goal() const
{
int distance = 0;
for(unsigned int i=0; i<number.size(); ++i)
for(unsigned int j=0; j<number[i].size(); ++j)
if(number[i][j] == 0)
distance += (number.size() - i - 1) + (number.size() - j - 1);
else
distance += abs( (number[i][j] - 1)/3 - i)
+abs( (number[i][j] - 1)%3 - j);
return distance;
}
void EightPazzle::next(std::priority_queue<EightPazzle>& task)
{
typedef std::vector<int>::iterator itr;
std::vector<int> vx, vy;
Point z = this->zero();
if(z.x != 0) vx.push_back(-1);
if(z.y != 0) vy.push_back(-1);
if(z.x != number.size() - 1) vx.push_back(1);
if(z.y != number.size() - 1) vy.push_back(1);
for(itr i = vx.begin(); i != vx.end(); ++i)
{
std::swap(number[z.x][z.y], number[z.x + *i][z.y]);older_age();
task.push(*this);
std::swap(number[z.x][z.y], number[z.x + *i][z.y]);restore_age();
}
for(itr i = vy.begin(); i != vy.end(); ++i)
{
std::swap(number[z.x][z.y], number[z.x][z.y + *i]);older_age();
task.push(*this);
std::swap(number[z.x][z.y], number[z.x][z.y + *i]);restore_age();
}
}
int main()
{
std::vector<std::vector<int> > init_array;
int temp[3][3] = {{1, 3, 5}, {7, 0, 2},{8, 4, 6}};
for(int i=0; i<3; ++i)
init_array.push_back(std::vector<int>(temp[i], temp[i]+3));
EightPazzle start(init_array);
std::cout << "start\npath:" << start.get_path()
<< ",cost:" << start.cost_to_goal() << "\n" << start;
std::priority_queue<EightPazzle> task;
task.push(start);
int i=0;
while(task.top().cost_to_goal() != 0)
{
EightPazzle working(task.top());
task.pop();
std::cout << i << "------------\npath:" << working.get_path()
<< ",cost:" << working.cost_to_goal() << "\n"
<< working;
working.next(task);
++i;
}
std::cout << "-----END-----\npath:" << task.top().get_path() << "\n"
<< task.top();
}