Цитата(sQu1rr @ 14.11.2010, 21:17  ) | Проходить по пустотам можно только по общим граням ( если представить ввиде квадрата ) ( тоесть не по диагонали )
Нужно найти самое дальнее пустое место от начала отсчета и обозначить I |
Я правильно понимаю, что надо найти все кратчайшие пути до всех точек (стартуя от заданной) и самый длинный путь ведёт к ответу?
Если да, то здесь подходит алгоритм A*.
Я как-то bаловался с ним.| Код | #ifndef ASTAR_SEARCH_HPP
#define ASTAR_SEARCH_HPP
#include <set>
#include <vector>
#include <algorithm>
#include <boost/scoped_ptr.hpp>
#include <boost/shared_ptr.hpp>
#include <boost/foreach.hpp>
class AStarHiddenPlace{
template<typename Node>
struct EstimatedNode
{
EstimatedNode(Node const& node, Node const& goal, EstimatedNode const* parent) :
m_node(node), m_parent(parent),
m_hRealCost(parent == NULL ? Node::heurisicCost(node, node) :
parent->m_hRealCost + Node::heurisicCost(parent->m_node, node)),
m_hGoalCost(m_hRealCost + Node::heurisicCost(node, goal))
{}
Node m_node;
EstimatedNode const* m_parent;
typename Node::HCost m_hRealCost;
typename Node::HCost m_hGoalCost;
//! \brief used in std::set
bool operator< (EstimatedNode const& rsh) const {return this->m_node < rsh.m_node;}
//! \brief used to compare with the goal Node
bool operator== (Node const& rsh) const { return this->m_node == rsh; }
//! \brief used to compare with the goal Node
bool operator!= (Node const& rsh) const { return !(this->m_node == rsh); }
};
template<typename T>
struct HCostLess{
bool operator() (T const& lsh, T const& rsh) const {return lsh.m_hGoalCost < rsh.m_hGoalCost;}
};
template<typename Node>
friend boost::shared_ptr<std::vector<Node> > aStarSearch(Node const&, Node const&);
};
/////////////////////////////////////////////////
//! \brief A* algorithm implementation.
//!
//! \tparam
//! The Node type must correspond to STL container requirements.
//! and to the following interface:
//! "bool operator<(Node const&) const" to store in std::set
//! "bool operator ==(Node const&) const" to check equality of node state
//! "std::vector<Node> * expand() const" to expand a node
//! "struct Node::HCost" with "bool operator<", "Node::HCost operator+", "Node::HCost & operator="
//! "static Node::HCost heurisicCost(Node const& from, Node const& to)"
//!
//! \param starting node
//! \param goal node
//! \return path from the starting node to the goal node
/////////////////////////////////////////////////
template<typename Node>
boost::shared_ptr<std::vector<Node> > aStarSearch(Node const& start, Node const& goal)
{
std::set<AStarHiddenPlace::EstimatedNode<Node> > discovered;
typedef std::multiset<AStarHiddenPlace::EstimatedNode<Node>, AStarHiddenPlace::HCostLess<AStarHiddenPlace::EstimatedNode<Node> > > EdgeT;
EdgeT edge;
typename EdgeT::const_iterator bestNode = edge.insert(AStarHiddenPlace::EstimatedNode<Node>(start, goal, NULL));
boost::shared_ptr<std::vector<Node> > result(new std::vector<Node>);
while(!edge.empty())
{
if(*bestNode == goal)
{
AStarHiddenPlace::EstimatedNode<Node> const* resNode = &(*bestNode);
while(resNode != NULL)
{
result->push_back(resNode->m_node);
resNode = resNode->m_parent;
}
std::reverse(result->begin(), result->end());
return result;
}
boost::scoped_ptr<std::vector<Node> > expandedList(bestNode->m_node.expand());
AStarHiddenPlace::EstimatedNode<Node> const* parent = &(*discovered.insert(*bestNode).first);
edge.erase(bestNode);
BOOST_FOREACH(Node const& node, *expandedList)
{
AStarHiddenPlace::EstimatedNode<Node> toEdge(node, goal, parent);
if(discovered.insert(toEdge).second)
{
edge.insert(toEdge);
}
}
bestNode = edge.begin();
}
return result;
} // end of aStarSearch
#endif //ASTAR_SEARCH_HPP
|
Node местоположение на карте. expand, возвращаёт все возможные передвижения из этой точки на один шаг, heuristic функция пусть считает расстояние от текущей точки (from) до цели (to) (лучше манхэтенское = |x2 - x1| + |y2 - y1|). В результате получаем полный путь от точки до цели в std::vector'e, его размер - 1 == длине пути (количеству нодов, по которым надо переходить). Если размер вектора == 0 (т.е. ни одного нода), значит цель недостижима.
Пятнашки, вот, решал. Если хочешь посмотреть результат, то компиляй с включенной оптимизацией, иначе долго придётся ждать. У пятнашек много разных комbинаций, а A* выливается в "поиск в ширину" если цель не достижима. Т.е. он переbерёт все варианты. На карте же, их столько, сколько достижимых пустых мест. За несколько милисекунд bудет решать.| Код | #include <iostream>
#include <iomanip>
#include "astar.hpp"
enum {SIDE = 4, FIELD = SIDE * SIDE};
std::size_t getIndex(std::size_t const (&state)[FIELD], std::size_t item)
{
for(std::size_t i = 0; i < FIELD; ++i)
if(state[i] == item) return i;
return FIELD;
}
struct Node
{
Node(std::size_t(&state)[FIELD]) {
::memcpy(this->m_state, state, FIELD * sizeof(std::size_t));
}
Node(Node const& rhs) {
::memcpy(this->m_state, rhs.m_state, FIELD * sizeof(std::size_t));
}
Node& operator= (Node const& rhs) {
::memcpy(this->m_state, rhs.m_state, FIELD * sizeof(std::size_t));
}
Node() {}
std::size_t m_state[FIELD];
bool operator<(Node const& rsh) const
{
for(std::size_t i = 0; i < FIELD; ++i)
{
if(this->m_state[i] < rsh.m_state[i]) return true;
}
return false;
}
bool operator ==(Node const& rsh) const
{
for(std::size_t i = 0; i < FIELD; ++i)
{
if(this->m_state[i] != rsh.m_state[i]) return false;
}
return true;
}
std::vector<Node> * expand() const
{
std::vector<Node> * result = new std::vector<Node>;
std::size_t index = getIndex(this->m_state, 0);
std::size_t col = index % SIDE;
std::size_t row = index / SIDE;
if(0 < col) // move left
{
std::size_t copyState[FIELD];
::memcpy(copyState, this->m_state, FIELD * sizeof(std::size_t));
std::swap(copyState[index-1], copyState[index]);
result->push_back(Node(copyState));
}
if(col < SIDE-1) // move right
{
std::size_t copyState[FIELD];
::memcpy(copyState, this->m_state, FIELD * sizeof(std::size_t));
std::swap(copyState[index], copyState[index+1]);
result->push_back(Node(copyState));
}
if(0 < row) // move up
{
std::size_t copyState[FIELD];
::memcpy(copyState, this->m_state, FIELD * sizeof(std::size_t));
std::swap(copyState[index-SIDE], copyState[index]);
result->push_back(Node(copyState));
}
if(row < SIDE-1) // move down
{
std::size_t copyState[FIELD];
::memcpy(copyState, this->m_state, FIELD * sizeof(std::size_t));
std::swap(copyState[index], copyState[index+SIDE]);
result->push_back(Node(copyState));
}
return result;
}
typedef std::size_t HCost;
static Node::HCost heurisicCost(Node const& from, Node const& to)
{
std::size_t cost = 0;
for(std::size_t i = 0; i < FIELD; ++i)
{
if(from.m_state[i] != 0 && from.m_state[i] != to.m_state[i])
{
std::size_t fromCol = i % SIDE;
std::size_t fromRow = i / SIDE;
std::size_t index = getIndex(to.m_state,from.m_state[i]);
std::size_t toCol = index % SIDE;
std::size_t toRow = index / SIDE;
cost += fromCol < toCol ? toCol - fromCol : fromCol - toCol;
cost += fromRow < toRow ? toRow - fromRow : fromRow - toRow;
}
}
return cost;
}
void print() const
{
for(std::size_t i = 0; i < FIELD; ++i)
{
if(i % SIDE == 0) std::cout<<'\n';
if(this->m_state[i] == 0)
{
std::cout<<" ";
}
else
{
std::cout<<std::setw(3)<<this->m_state[i];
}
}
std::cout<<"\n";
}
};
std::size_t goal[FIELD] = {1, 2, 3, 4,
5, 6, 7, 8,
9, 10, 11, 12,
13, 14, 15, 0};
std::size_t start[FIELD] = {1, 12, 3, 7,
15, 2, 14, 4,
5, 6, 10, 8,
9, 13, 11, 0};
int main()
{
boost::shared_ptr<std::vector<Node> > result = aStarSearch(Node(start), Node(goal));
std::size_t i = 0;
BOOST_FOREACH(Node const& item, *result)
{
std::cout<<"step "<<i++;
item.print();
}
return 0;
}
|
|
