VPF::Реализация алгоритма A* - Форум программистов

Леопольд

Дата 21.11.2010, 22:40 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 943
Регистрация: 17.6.2009

Репутация: 10
Всего: 13

Цитата(Master01 @ 21.11.2010, 21:23

)

Списки open и close реально не нужны вообще.

Есть только те, что уже известны, и те, которые, возможно, ведут к ещё неизвестным состояниям. У пятнашек пространство поиска 15! / 2 = 653 837 184 000 различных состояний (вторая половина недостижима из первой, и наоbорот). Достаточно много и для современных машин...

Цитата(Master01 @ 21.11.2010, 21:23

)

время определения есть ли узел в одном из "списков" = O(1)

Это как?

В пятнашках, из одного состояния можно получить от двух, до четырёх других состояний. Как они могут bыть промаркированы beз использования списка уже открытых?
На дискретной карте (с количеством состояний менее чем M x N), для поиска пути, можно сделать O(1), не спорю. Если карта не слишком bольшая...

Цитата(Isaev @ 21.11.2010, 22:15

)

(при чём у меня это 18 сек, а не 10)

Запускал на решение код из "твоей" книги? Интересно за сколько у теbя решит...

Вот, по моему, самое узкое место:

Код

    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;
    }

я не заморачивался на производительности... Оптимизация может дать ощутимый прирост.

Это сообщение отредактировал(а) Леопольд - 22.11.2010, 00:18

--------------------

вопросов больше чем ответов

mes

Дата 22.11.2010, 00:19 (ссылка)

(нет голосов)

Загрузка ...

любитель

Профиль
Группа: Участник Клуба
Сообщений: 7954
Регистрация: 14.1.2006

Репутация: 144
Всего: 250

из интереса: ИИ должен найти самое лучшее решение или любое, но быстро ?

--------------------

http://opendots.net

Master01

Дата 22.11.2010, 00:26 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 89
Регистрация: 22.8.2007

Репутация: 2
Всего: 2

Простите, я говорил, про A* приминительно к своей задаче, а касательно его применение к 15-шкам? я не очень силён... каким боком его тут прикрутить пока не представляю ...

Я, конкрено, использовал A* для решения задачи нахождения пути на некоторой карте, где карта представляла собой именно непрерывное пространство, а объекты в нём (препятствия) - простые полигоны (простые - значит без дыр) любой формы с любым количеством вершин.

На самом деле, A*-ра там было всего 10% от всей работы. Всё остальное было связано именно с представлением в памяти этого непрывного пространства. Непрывное оно было в том смысле что в нём было возможно перемещение в любом направлении, на любое предельно малое расстояние и любая координата могла быть взята с любой степенью точности (на практике, конечно, существовали ограничения, накладываемые самой ЭВМ).

Леопольд,

я не имел ввиду что не нужно вести учёт "открытых/закрытых". Я хотел сказать, что не нужны сами списки - как структура данных (ну или деревья и пр.) потому что поиск в них - минимум логарифм (тут уж лучше хэш таблицы, там сложность - таже константа). Правельнее делать отметки в самих узлах. Для этого, конечно, ваша карта должна хранить узлы в виде объектов. В свой класс node вы добавляете поле bool is_in_close и is_in_open. Далее обращение к этим полям, при условии что сам объект-узел у вас уже есть - тривальная операция.

Другой вопрос - какое время потребуется вашей карте, чтобы вернуть вам этот объект-узел? (на самом деле, тоже можно получить константу) Поэтому я и упомянул - "самая большая оптимизация - это правильно организовать само пространство поиска и чтение/запись в это пространство. "

mes,

Эвристика не гарантирует наилучшего решения, но зато работает быстро.

Леопольд

Дата 22.11.2010, 08:24 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 943
Регистрация: 17.6.2009

Репутация: 10
Всего: 13

Цитата(Master01 @ 22.11.2010, 00:26

)

Для этого, конечно, ваша карта должна хранить узлы в виде объектов.

Это не карта...

Добавлено @ 08:26

Цитата(mes @ 22.11.2010, 00:19

)

самое лучшее решение или любое, но быстро ?

Решение оптимальное. Тот же подход используется в методе ветвей и границ в задаче коммивояжёра. Эвристическая функция нужна, что-bы попытаться изbежать полного переbора.

Это сообщение отредактировал(а) Леопольд - 22.11.2010, 11:07

--------------------

вопросов больше чем ответов

Master01

Дата 22.11.2010, 12:28 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 89
Регистрация: 22.8.2007

Репутация: 2
Всего: 2

Цитата(Леопольд @ 22.11.2010, 08:24)

Цитата(Master01 @ 22.11.2010, 00:26

)

Для этого, конечно, ваша карта должна хранить узлы в виде объектов.

Это не карта...

Не, я тут правильно сказал.

Надо различать карту - как сущность, хранящую пространство, и сам Astar - механиз, осуществляющий в нём поиск. Их связывает лишь тонкий мостик - интерфейс, через, который Astar получает всю необходимую информацию о пространстве. А так, это две независимые сущности. К примеру, это значит, что вы можете менять методы представления пространства и при этом совершенно не нарушать работу самого Astar-а. (до тех пор, конечно, пока неизменным остаётся интерфейс)

Я привёл выше книги, в которых, это очень хорошо описано, включая архитектуру подобных систем и пр.

Леопольд

Дата 22.11.2010, 12:53 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 943
Регистрация: 17.6.2009

Репутация: 10
Всего: 13

Isaev, я сейчас С++0x осваиваю, на нём код алгоритма понятнее:

Код

#ifndef ASTAR_SEARCH_HPP
#define ASTAR_SEARCH_HPP

#include <set>
#include <vector>
#include <algorithm>
#include <memory>

/////////////////////////////////////////////////
//! \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 (this critical part should be so fas as possible)
//! "bool operator ==(Node const&) const" to check equality of node state
//! "std::unique_ptr<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>
std::unique_ptr<std::vector<Node>> aStarSearch(Node const& start, Node const& goal)
{
    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); }
    };

    struct HCostLess{
        bool operator() (EstimatedNode const& lsh, EstimatedNode const& rsh) const {return lsh.m_hGoalCost < rsh.m_hGoalCost;}
    };

    typedef std::multiset<EstimatedNode, HCostLess>  EdgeT;

    std::set<EstimatedNode> discovered;
    EdgeT edge;

    auto bestNode = edge.insert(EstimatedNode(start, goal, NULL));

    std::unique_ptr<std::vector<Node>> result(new std::vector<Node>);
    while(!edge.empty())
    {
        if(*bestNode == goal)
        {
            EstimatedNode const* resNode = &(*bestNode);
            while(resNode != NULL)
            {
                result->push_back(resNode->m_node);
                resNode = resNode->m_parent;
            }
            std::reverse(result->begin(), result->end());
            return move(result);
        }

        std::unique_ptr<std::vector<Node>> expandedList(bestNode->m_node.expand());

        EstimatedNode const* parent = &(*discovered.insert(*bestNode).first);

        edge.erase(bestNode);

        for(auto it = expandedList->begin(); it != expandedList->end(); ++it)
        {
            EstimatedNode toEdge(*it, goal, parent);
            if(discovered.insert(toEdge).second)
            {
                edge.insert(toEdge);
            }
        }

        bestNode = edge.begin();
    }

    return move(result);
} // end of aStarSearch

#endif //ASTAR_SEARCH_HPP

Цитата(Master01 @ 22.11.2010, 12:28

)

Не, я тут правильно сказал.

Я имел ввиду что здесь речь про пятнашки, а не про карту.

Цитата(Master01 @ 22.11.2010, 12:28

)

А так, это две независимые сущности

Если посмотришь код, то увидишь что сам алгоритм реализован отдельно.

Это сообщение отредактировал(а) Леопольд - 22.11.2010, 14:26

--------------------

вопросов больше чем ответов

Леопольд

Дата 22.11.2010, 13:32 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 943
Регистрация: 17.6.2009

Репутация: 10
Всего: 13

Узкое место оказалось в Node::operator<
Так решает меньше чем за секунду...

Код

#include <cstring>
#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(std::initializer_list<std::size_t> initList) {
        std::copy(initList.begin(), initList.end(), this->m_state);
    }

    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));
        return *this;
    }

    Node() {}

    std::size_t m_state[FIELD];

    bool operator< (Node const& rsh) const
    {
        return ::memcmp(this->m_state, rsh.m_state, FIELD * sizeof(std::size_t)) < 0;
    }

    bool operator== (Node const& rsh) const
    {
        return ::memcmp(this->m_state, rsh.m_state, FIELD * sizeof(std::size_t)) == 0;
    }

    std::unique_ptr<std::vector<Node>> expand() const
    {
        std::unique_ptr<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 move(result);
    }

    typedef std::size_t HCost;

    static Node::HCost heurisicCost(Node const& from, Node const& to)
    {
        std::size_t cost = 0;

        for(int currentPos = 0; currentPos < FIELD; ++currentPos)
        {
            if(from.m_state[currentPos] != 0 && from.m_state[currentPos] != to.m_state[currentPos])
            {
                int goalPos = getIndex(to.m_state, from.m_state[currentPos]);
                cost += ::abs(goalPos - currentPos) / SIDE + ::abs(goalPos - currentPos) % SIDE;
            }
        }
        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()
{
    auto result = aStarSearch(Node(start), Node(goal));

    std::size_t i = 0;
    for(auto it = result->begin(); it != result->end(); ++it)
    {
        std::cout<<"step "<<i++;
        it->print();
    }

    return 0;
}

Это сообщение отредактировал(а) Леопольд - 22.11.2010, 14:22

--------------------

вопросов больше чем ответов

Isaev

Дата 22.11.2010, 17:19 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 125
Регистрация: 8.11.2007
Где: Germany

Репутация: нет
Всего: нет

Цитата(Леопольд @ 21.11.2010, 22:40

)

Запускал на решение код из "твоей" книги? Интересно за сколько у теbя решит...

из книги 450 сек, твой вариант из соседней темы 30 сек.

Цитата(Master01 @ 22.11.2010, 00:26

)

Эвристика не гарантирует наилучшего решения, но зато работает быстро.

Что значит не гарантирует, это поиск минимального пути, конечно если говорить о картах минимальный путь не всегда лучший, но в данном случае это гарантирует минимальное решение

Цитата(Леопольд @ 22.11.2010, 13:32

)

Узкое место оказалось в Node::operator<
Так решает меньше чем за секунду...

Да! я чувствовал smile

только собрать не могу, может что-то в инклюдах нету?

Код


Node(std::initializer_list<std::size_t> initList) {
        std::copy(initList.begin(), initList.end(), this->m_state);

19 D:\Programme\Dev-Cpp\Game15_Leo\main.cpp expected `)' before '<' token

Леопольд

Дата 22.11.2010, 17:39 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 943
Регистрация: 17.6.2009

Репутация: 10
Всего: 13

Isaev, тут нужен С++0x (предполагаемый bудующий стандарт). Выкинь конструктор с std::initializer_list.
Измени мой код из соседней темы, он для текущего стандарта.

Это сообщение отредактировал(а) Леопольд - 22.11.2010, 17:41

--------------------

вопросов больше чем ответов

Isaev

Дата 22.11.2010, 18:11 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 125
Регистрация: 8.11.2007
Где: Germany

Репутация: нет
Всего: нет

Леопольд, а как отвязать этот код от boost
при трансляции на другой язык очень мешает

Master01

Дата 22.11.2010, 19:29 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 89
Регистрация: 22.8.2007

Репутация: 2
Всего: 2

Цитата(Isaev @ 22.11.2010, 17:19)

Цитата(Master01 @ 22.11.2010, 00:26

)

Эвристика не гарантирует наилучшего решения, но зато работает быстро.

Я рискну не поверить smile

Эвристические алгоритмы по своему определению не могут ничего гарантировать для общего случая, а Astar использует эвристику. Фактически это алгоритм Дейкстры (для которого, минимальность найденного пути гарантируется) с добавлением эвристики с целью сделать его быстрее.

Насчёт путей на карте, тоже, простите, не верно - [стоимость пути] != [длина пути]. Лучший путь (он же минимальный) не обязательно самый короткий, но стоимость его всегда минимальна. Под стоимостью тут понимайте что угодно - от банального расстояния, до денежной стоимости проезда по различным участкам.

Isaev

Дата 22.11.2010, 20:20 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 125
Регистрация: 8.11.2007
Где: Germany

Репутация: нет
Всего: нет

Master01, из определения

A* (произносится «А со звездой») является лучшим из известных алгоритмов поиска пути. Он гарантирует поиск пути с наименьшим счетом, из всех возможных путей между двумя точками.
Хотя он и является лучшим алгоритмом поиска пути, A* также требует интенсивных вычислений процессора и работает медленно.
A* может обрабатывать многие виды поверхностей и находить лучший путь к цели через эти поверхности.

Цитата(Master01 @ 22.11.2010, 19:29

)

[стоимость пути] != [длина пути]. Лучший путь (он же минимальный) не обязательно самый короткий, но стоимость его всегда минимальна. Под стоимостью тут понимайте что угодно - от банального расстояния, до денежной стоимости проезда по различным участкам.

Мы об одним и том же, только с разных сторон smile

Именно если под стоимостью понимать банальное расстояние, то [стоимость пути] = [длина пути].
В общем это не столь важно...

Леопольд, я тоже помешан на оптимизации, это привито ещё спектрумом, где каждый байт был на счету...
У тебя был пример решения в 36 ходов, вот матрица для решения в 51 ход.
12, 2, 9, 13,
3, 11, 1, 10,
5, 14, 0, 4,
7, 15, 8, 6
оптимизированный вариант я пока так и не собрал, а старый её не тянет, т.к. после минут 5 вылетает по переполнению памяти. При чём странно работает, т.к. грузит процессор только вначале на полную, при этом используемая память быстро растёт до 860Мб потом быстро вниз до 50Мб и занятость процессора 10-20% так работает довольно долго, но потом вылетает... Странно.
У тебя он отработает? и за сколько?

Master01

Дата 22.11.2010, 21:24 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 89
Регистрация: 22.8.2007

Репутация: 2
Всего: 2

Цитата(Isaev @ 22.11.2010, 20:20)

Master01, из определения

A* (произносится «А со звездой») является лучшим из известных алгоритмов поиска пути. Он гарантирует поиск пути с наименьшим счетом, из всех возможных путей между двумя точками.
Хотя он и является лучшим алгоритмом поиска пути, A* также требует интенсивных вычислений процессора и работает медленно.
A* может обрабатывать многие виды поверхностей и находить лучший путь к цели через эти поверхности.

Цитата(Master01 @ 22.11.2010, 19:29

)

Мы об одним и том же, только с разных сторон smile

Именно если под стоимостью понимать банальное расстояние, то [стоимость пути] = [длина пути].
В общем это не столь важно...

Isaev, я вам уже наверно надоел, да? smile

Все эти прекрасные свойства, описанные вами выше, выполняются только если ваша эвристическая функция h(x) всегда равна 0 (но тогда это уже алгоритм Дейкстры). Иными словами, если она гарантировано не привышает реально оставшегося расстояния до точки останова! т.е. когда мы можем ткнуть пальцем в небо и сказать, мол, до финиша не более N единиц стоимости.
Если это возможно, то всё что вы написали выше - правда smile

Но это возможно не всегда т.е. не для любой задачи. В моём случае и, я допускаю, в вашем тоже это реально, но это не значит, что так оно всегда.

Поэтому я и сказал, что в общем случае Astar (да и вообще эвристические алгоритмы) не гарантирует оптимальность решения, ровно как и что решение будет найдено, если даже оно существует.

Цитата

Эвристические алгоритмы по своему определению не могут ничего гарантировать для общего случая, а Astar использует эвристику.

http://ru.wikipedia.org/wiki/%D0%AD%D0%B2%...%B8%D1%82%D0%BC

Леопольд

Дата 22.11.2010, 21:40 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 943
Регистрация: 17.6.2009

Репутация: 10
Всего: 13

Цитата(Isaev @ 22.11.2010, 20:20

)

У тебя был пример решения в 36 ходов, вот матрица для решения в 51 ход.
12, 2, 9, 13,
3, 11, 1, 10,
5, 14, 0, 4,
7, 15, 8, 6

Видимо нерешаемый, мой на нём тоже зависает наглухо, памяти не хватает. А если решаемый, то очевидно памяти надо bольше.

Код

 12 13 15  7
  5  3  4  8
  9 14  1  0
 10  2  6 11

Для решения в 51 ход пришлось оптимизировать по памяти. Отъедало всю доступную (1.6 GB), потом , видимо, начинала юзать swap, и нагрузка на процессор падала до 1-5%. Теперь юзает ~400 MB .

Код

#include <cstring>
#include <iostream>
#include <iomanip>

#include "astar.hpp"

enum {SIDE = 4, FIELD = SIDE * SIDE};

typedef unsigned char Item;

std::size_t getIndex(Item const (&state)[FIELD], Item item)
{
    for(std::size_t i = 0; i < FIELD; ++i)
        if(state[i] == item) return i;
    return FIELD;
}

struct Node
{
    Node(Item (&state) [FIELD]) {
        ::memcpy(this->m_state, state, FIELD * sizeof(Item));
    }

    Node(Node const& rhs) {
        ::memcpy(this->m_state, rhs.m_state, FIELD * sizeof(Item));
    }

    Node& operator= (Node const& rhs) {
        ::memcpy(this->m_state, rhs.m_state, FIELD * sizeof(Item));
        return *this;
    }

    Node() {}

    Item m_state[FIELD];

    bool operator< (Node const& rsh) const
    {
        return ::memcmp(this->m_state, rsh.m_state, FIELD * sizeof(Item)) < 0;
    }

    bool operator== (Node const& rsh) const
    {
        return ::memcmp(this->m_state, rsh.m_state, FIELD * sizeof(Item)) == 0;
    }

    std::unique_ptr<std::vector<Node>> expand() const
    {
        std::unique_ptr<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
        {
            Item copyState[FIELD];
            ::memcpy(copyState, this->m_state, FIELD * sizeof(Item));
            std::swap(copyState[index-1], copyState[index]);
            result->push_back(Node(copyState));
        }
        if(col < SIDE-1) // move right
        {
            Item copyState[FIELD];
            ::memcpy(copyState, this->m_state, FIELD * sizeof(Item));
            std::swap(copyState[index], copyState[index+1]);
            result->push_back(Node(copyState));
        }
        if(0 < row) // move up
        {
            Item copyState[FIELD];
            ::memcpy(copyState, this->m_state, FIELD * sizeof(Item));
            std::swap(copyState[index-SIDE], copyState[index]);
            result->push_back(Node(copyState));
        }
        if(row < SIDE-1) // move down
        {
            Item copyState[FIELD];
            ::memcpy(copyState, this->m_state, FIELD * sizeof(Item));
            std::swap(copyState[index], copyState[index+SIDE]);
            result->push_back(Node(copyState));
        }
        return move(result);
    }

    typedef std::size_t HCost;

    static Node::HCost heurisicCost(Node const& from, Node const& to)
    {
        std::size_t cost = 0;

        for(int currentPos = 0; currentPos < FIELD; ++currentPos)
        {
            if(from.m_state[currentPos] != 0 && from.m_state[currentPos] != to.m_state[currentPos])
            {
                int goalPos = getIndex(to.m_state, from.m_state[currentPos]);
                cost += ::abs(goalPos - currentPos) / SIDE + ::abs(goalPos - currentPos) % SIDE;
            }
        }
        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)<<static_cast<std::size_t>(this->m_state[i]);
            }
        }
        std::cout<<"\n";
    }
};

Item goal[FIELD] = {1, 2, 3, 4,
                    5, 6, 7, 8,
                    9, 10, 11, 12,
                    13, 14, 15, 0};

Item start[FIELD] = {12, 13, 15, 7,
                    5, 3, 4, 8,
                    9, 14, 1, 0,
                    10, 2, 6, 11};

//Item start[FIELD] = {12, 2, 9, 13,
//                    3, 11, 1, 10,
//                    5, 14, 0, 4,
//                    7, 15, 8, 6};

int main()
{
    auto result = aStarSearch(Node(start), Node(goal));

    std::size_t i = 0;
    for(auto it = result->begin(); it != result->end(); ++it)
    {
        std::cout<<"step "<<i++;
        it->print();
    }

    return 0;
}

execution time : 16.759 s (AMD Athlon X2 4000+, Ubuntu 10.10, g++4.5)

Код

step 0
 12 13 15  7
  5  3  4  8
  9 14  1   
 10  2  6 11
step 1
 12 13 15  7
  5  3  4   
  9 14  1  8
 10  2  6 11
step 2
 12 13 15  7
  5  3     4
  9 14  1  8
 10  2  6 11
step 3
 12 13     7
  5  3 15  4
  9 14  1  8
 10  2  6 11
step 4
 12    13  7
  5  3 15  4
  9 14  1  8
 10  2  6 11
step 5
 12  3 13  7
  5    15  4
  9 14  1  8
 10  2  6 11
step 6
 12  3 13  7
  5 14 15  4
  9     1  8
 10  2  6 11
step 7
 12  3 13  7
  5 14 15  4
  9  1     8
 10  2  6 11
step 8
 12  3 13  7
  5 14     4
  9  1 15  8
 10  2  6 11
step 9
 12  3     7
  5 14 13  4
  9  1 15  8
 10  2  6 11
step 10
 12     3  7
  5 14 13  4
  9  1 15  8
 10  2  6 11
step 11
    12  3  7
  5 14 13  4
  9  1 15  8
 10  2  6 11
step 12
  5 12  3  7
    14 13  4
  9  1 15  8
 10  2  6 11
step 13
  5 12  3  7
 14    13  4
  9  1 15  8
 10  2  6 11
step 14
  5     3  7
 14 12 13  4
  9  1 15  8
 10  2  6 11
step 15
  5  3     7
 14 12 13  4
  9  1 15  8
 10  2  6 11
step 16
  5  3  7   
 14 12 13  4
  9  1 15  8
 10  2  6 11
step 17
  5  3  7  4
 14 12 13   
  9  1 15  8
 10  2  6 11
step 18
  5  3  7  4
 14 12 13  8
  9  1 15   
 10  2  6 11
step 19
  5  3  7  4
 14 12 13  8
  9  1    15
 10  2  6 11
step 20
  5  3  7  4
 14 12     8
  9  1 13 15
 10  2  6 11
step 21
  5  3  7  4
 14    12  8
  9  1 13 15
 10  2  6 11
step 22
  5  3  7  4
 14  1 12  8
  9    13 15
 10  2  6 11
step 23
  5  3  7  4
 14  1 12  8
  9  2 13 15
 10     6 11
step 24
  5  3  7  4
 14  1 12  8
  9  2 13 15
 10  6    11
step 25
  5  3  7  4
 14  1 12  8
  9  2    15
 10  6 13 11
step 26
  5  3  7  4
 14  1     8
  9  2 12 15
 10  6 13 11
step 27
  5  3     4
 14  1  7  8
  9  2 12 15
 10  6 13 11
step 28
  5     3  4
 14  1  7  8
  9  2 12 15
 10  6 13 11
step 29
  5  1  3  4
 14     7  8
  9  2 12 15
 10  6 13 11
step 30
  5  1  3  4
 14  2  7  8
  9    12 15
 10  6 13 11
step 31
  5  1  3  4
 14  2  7  8
  9  6 12 15
 10    13 11
step 32
  5  1  3  4
 14  2  7  8
  9  6 12 15
    10 13 11
step 33
  5  1  3  4
 14  2  7  8
     6 12 15
  9 10 13 11
step 34
  5  1  3  4
     2  7  8
 14  6 12 15
  9 10 13 11
step 35
     1  3  4
  5  2  7  8
 14  6 12 15
  9 10 13 11
step 36
  1     3  4
  5  2  7  8
 14  6 12 15
  9 10 13 11
step 37
  1  2  3  4
  5     7  8
 14  6 12 15
  9 10 13 11
step 38
  1  2  3  4
  5  6  7  8
 14    12 15
  9 10 13 11
step 39
  1  2  3  4
  5  6  7  8
 14 10 12 15
  9    13 11
step 40
  1  2  3  4
  5  6  7  8
 14 10 12 15
  9 13    11
step 41
  1  2  3  4
  5  6  7  8
 14 10 12 15
  9 13 11   
step 42
  1  2  3  4
  5  6  7  8
 14 10 12   
  9 13 11 15
step 43
  1  2  3  4
  5  6  7  8
 14 10    12
  9 13 11 15
step 44
  1  2  3  4
  5  6  7  8
 14    10 12
  9 13 11 15
step 45
  1  2  3  4
  5  6  7  8
    14 10 12
  9 13 11 15
step 46
  1  2  3  4
  5  6  7  8
  9 14 10 12
    13 11 15
step 47
  1  2  3  4
  5  6  7  8
  9 14 10 12
 13    11 15
step 48
  1  2  3  4
  5  6  7  8
  9    10 12
 13 14 11 15
step 49
  1  2  3  4
  5  6  7  8
  9 10    12
 13 14 11 15
step 50
  1  2  3  4
  5  6  7  8
  9 10 11 12
 13 14    15
step 51
  1  2  3  4
  5  6  7  8
  9 10 11 12
 13 14 15   

Process returned 0 (0x0)   execution time : 16.759 s
Press ENTER to continue.

решение в 52 хода съело ~1GB...

Это сообщение отредактировал(а) Леопольд - 23.11.2010, 08:17

--------------------

вопросов больше чем ответов

Леопольд

Дата 22.11.2010, 23:32 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 943
Регистрация: 17.6.2009

Репутация: 10
Всего: 13

Цитата(Isaev @ 22.11.2010, 18:11

)

Леопольд, а как отвязать этот код от boost
при трансляции на другой язык очень мешает

В джаве есть сbорщик мусора, так что на всевозможные _ptr просто "заbить", это очистка памяти. Foreach, вроде, тоже есть в джаве...

Не уверен что стоит делать на джаве, она ведь гораздо дольше раbотает... Разве нельзя какой-ниbуть bиндер к С++ или С использовать?

Код

extern "C" void binderC()
{
    auto result = aStarSearch(Node(start), Node(goal));
    //transfer the result to the java code
}

Это сообщение отредактировал(а) Леопольд - 22.11.2010, 23:40

--------------------

вопросов больше чем ответов

1 Пользователей читают эту тему (1 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| C/C++: Общие вопросы \| Следующая тема »