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

Isaev

Дата 23.11.2010, 06:06 (ссылка)

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

Загрузка ...

Шустрый

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

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

Цитата(Master01 @ 22.11.2010, 21:24

)

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

Нет конечно, просто счёт был на часы и не хотелось спорить о теории... Т.к. не полностью в неё вник, к сожалению, чтобы спорить надо было разбираться smile

получается эвристика может быть любая, не обязательно по манхеттену, и пришла потому мысль, что алго из книги тупил именно по этому, там же в расчёче эвристики забиты 2 массива жёстко для какого-то примера, а ввод поля с клавиатуры, как то это тупо... Может потому для другого поля получался далеко не манхеттен, но к решению он преходил, только какой ценой?
Надо будет поиграться проверить smile

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

)

Теперь юзает ~400 MB .
execution time : 16.759 s (AMD Athlon X2 4000+, Ubuntu 10.10, g++4.5)

Талант! Как время будет, надо будет в пару алго подумать над оптимизацией... Может снова пристану.
C++0x в какой среде компилируется? Я о таком не слышал даже пока, думал 0x случайный мусор. Надо будет всё таки собрать последний пример.

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

)

Не уверен что стоит делать на джаве, она ведь гораздо дольше раbотает...

Это ясно... Это у сестры лабораторная была, на яве, потому никуда не денешься, но идея затянула smile

лабу сдали, на 51 ход вглубину ява тоже повесилась (куча переполнилась), а остальное нормально считала, но чуть дольше...
Для себя переведу позже на Delphi, приятный пример.
Как оценить для поля 4х4 максимально длинной решение? 51 это же не предел?

Леопольд

Дата 23.11.2010, 08:06 (ссылка)

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

Загрузка ...

Опытный

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

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

Цитата(Isaev @ 23.11.2010, 06:06

)

Как оценить для поля 4х4 максимально длинной решение? 51 это же не предел?

Не знаю. Знаю только что для 3х3 макс. 24 хода. Как считать, не разbирался. Меня сам A* интересовал.

Цитата(Isaev @ 23.11.2010, 06:06

)

C++0x в какой среде компилируется?

g++ 4.5, VS 2010

Цитата(Isaev @ 23.11.2010, 06:06

)

думал 0x случайный мусор

Это пока ещё драфт. Стандарт не принят (хотели вроде в 2007 принять, поначалу), так что всё может поменяться.

Цитата(Isaev @ 23.11.2010, 06:06

)

получается эвристика может быть любая, не обязательно по манхеттену

можно ещё оценивать по количеству костяшек, находящихся не на своём месте. Но ресурсов для решения потреbуется в разы bольше.

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

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

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

Master01

Дата 23.11.2010, 16:21 (ссылка)

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

Загрузка ...

Шустрый

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

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

Эвристическая функция это Ахилесова пята Astar-а.

Если она переоценивает оставшееся расстояние, то алгоритм может вернуть не самый минимальный путь. НО с другой стороны, если недооценивает, то алгоритм теряет направленность, т.е. начинает рыскать как алгоритм Дейкстры, работает медленее.

На самом деле, в задаче поиска реальных путей на карте для эвристики используется тот же манхэтен, хотя это по сути не правильно, поскольку dx + dy (манхэттэн-расстояние) всега заведомо больше sqrt(dx^2 + dy^2) (при положительных dx и dy). т.е. такая эвристика всегда 100% нарушает условие допустимости эвристической функции.
Это приводит к тому, что найденные пути могут быть не самыми минимальными. Но зато dx + dy высчитывается несравнимо быстрее чем квадрадный корень из суммы квадратов.

Наверно, можно сказать что, если переоценивание "вминяемое", то лучше использовать эту упрощённую эвристику, чем наоборот - недооценивать или тратить кучу тактов процессора на вычисление точной эвристики. Другими словами, как и везде нужен балланс smile

Isaev

Дата 23.11.2010, 19:03 (ссылка)

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

Загрузка ...

Шустрый

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

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

Цитата(Master01 @ 23.11.2010, 16:21

)

На самом деле, в задаче поиска реальных путей на карте для эвристики используется тот же манхэтен, хотя это по сути не правильно, поскольку dx + dy (манхэттэн-расстояние) всега заведомо больше sqrt(dx^2 + dy^2) (при положительных dx и dy). т.е. такая эвристика всегда 100% нарушает условие допустимости эвристической функции.

ну применимо к картам никто не мешает изменить эвристическую оценку к тому же sqrt(dx^2 + dy^2), если такой путь часто имеет место быть, то оно себя окупит... а вычисления всегда можно оптимизировать разложив до булевых операций и сдвигов, и скорость будет вполне сносной...

Возвращаясь к теме (в частности к 4х4):
если я обрабатываю числа не по порядку, а допустим сначала так
+----+----+----+----+
|  1  |  2  |  3  |  4  |
+----+----+----+----+
|  5  |      |      |      |
+----+----+----+----+
|  9  |      |      |      |
+----+----+----+----+
| 13 |      |      |      |
+----+----+----+----+
а потом 3х3 это же выведет алгоритм раньше к правильному решению? Или я не совсем допонимаю принцып?

Леопольд

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

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

Загрузка ...

Опытный

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

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

Код

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

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

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


int main()
{
    auto result = aStarSearchBidirect(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;
}

step 51 execution time : 0.383 s

Код

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 13  7
  5  3 15  4
  9 14  1  8
 10  2  6 11
step 6
  5 12 13  7
     3 15  4
  9 14  1  8
 10  2  6 11
step 7
  5 12 13  7
  9  3 15  4
    14  1  8
 10  2  6 11
step 8
  5 12 13  7
  9  3 15  4
 14     1  8
 10  2  6 11
step 9
  5 12 13  7
  9  3 15  4
 14  1     8
 10  2  6 11
step 10
  5 12 13  7
  9  3     4
 14  1 15  8
 10  2  6 11
step 11
  5 12     7
  9  3 13  4
 14  1 15  8
 10  2  6 11
step 12
  5    12  7
  9  3 13  4
 14  1 15  8
 10  2  6 11
step 13
  5  3 12  7
  9    13  4
 14  1 15  8
 10  2  6 11
step 14
  5  3 12  7
  9  1 13  4
 14    15  8
 10  2  6 11
step 15
  5  3 12  7
  9  1 13  4
    14 15  8
 10  2  6 11
step 16
  5  3 12  7
     1 13  4
  9 14 15  8
 10  2  6 11
step 17
  5  3 12  7
  1    13  4
  9 14 15  8
 10  2  6 11
step 18
  5  3 12  7
  1 13     4
  9 14 15  8
 10  2  6 11
step 19
  5  3     7
  1 13 12  4
  9 14 15  8
 10  2  6 11
step 20
  5  3  7   
  1 13 12  4
  9 14 15  8
 10  2  6 11
step 21
  5  3  7  4
  1 13 12   
  9 14 15  8
 10  2  6 11
step 22
  5  3  7  4
  1 13 12  8
  9 14 15   
 10  2  6 11
step 23
  5  3  7  4
  1 13 12  8
  9 14    15
 10  2  6 11
step 24
  5  3  7  4
  1 13 12  8
  9    14 15
 10  2  6 11
step 25
  5  3  7  4
  1    12  8
  9 13 14 15
 10  2  6 11
step 26
  5  3  7  4
     1 12  8
  9 13 14 15
 10  2  6 11
step 27
  5  3  7  4
  9  1 12  8
    13 14 15
 10  2  6 11
step 28
  5  3  7  4
  9  1 12  8
 13    14 15
 10  2  6 11
step 29
  5  3  7  4
  9  1 12  8
 13  2 14 15
 10     6 11
step 30
  5  3  7  4
  9  1 12  8
 13  2 14 15
 10  6    11
step 31
  5  3  7  4
  9  1 12  8
 13  2    15
 10  6 14 11
step 32
  5  3  7  4
  9  1     8
 13  2 12 15
 10  6 14 11
step 33
  5  3     4
  9  1  7  8
 13  2 12 15
 10  6 14 11
step 34
  5     3  4
  9  1  7  8
 13  2 12 15
 10  6 14 11
step 35
  5  1  3  4
  9     7  8
 13  2 12 15
 10  6 14 11
step 36
  5  1  3  4
  9  2  7  8
 13    12 15
 10  6 14 11
step 37
  5  1  3  4
  9  2  7  8
 13  6 12 15
 10    14 11
step 38
  5  1  3  4
  9  2  7  8
 13  6 12 15
    10 14 11
step 39
  5  1  3  4
  9  2  7  8
     6 12 15
 13 10 14 11
step 40
  5  1  3  4
     2  7  8
  9  6 12 15
 13 10 14 11
step 41
     1  3  4
  5  2  7  8
  9  6 12 15
 13 10 14 11
step 42
  1     3  4
  5  2  7  8
  9  6 12 15
 13 10 14 11
step 43
  1  2  3  4
  5     7  8
  9  6 12 15
 13 10 14 11
step 44
  1  2  3  4
  5  6  7  8
  9    12 15
 13 10 14 11
step 45
  1  2  3  4
  5  6  7  8
  9 10 12 15
 13    14 11
step 46
  1  2  3  4
  5  6  7  8
  9 10 12 15
 13 14    11
step 47
  1  2  3  4
  5  6  7  8
  9 10 12 15
 13 14 11   
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 : 0.383 s

Код

#ifndef ASTAR_B_HPP_INCLUDED
#define ASTAR_B_HPP_INCLUDED

#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>> aStarSearchBidirect(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 const*, HCostLess>  EdgeT;

    std::set<EstimatedNode> discoveredF({EstimatedNode(start, goal, NULL)});
    std::set<EstimatedNode> discoveredB({EstimatedNode(goal, start, NULL)});

    EstimatedNode const* bestNodeF = &(*discoveredF.begin());
    EstimatedNode const* bestNodeB = &(*discoveredB.begin());

    EdgeT edgeF({bestNodeF});
    EdgeT edgeB({bestNodeB});


    std::unique_ptr<std::vector<Node>> path(new std::vector<Node>);

    while(edgeF.empty() == false && edgeB.empty() == false)
    {

        auto match = discoveredB.find(*bestNodeF);
        if(match != discoveredB.end())
        {
            // the solution is found
            EstimatedNode const* point = bestNodeF;
            for(; point != NULL; point = point->m_parent)
            {
                path->push_back(point->m_node);
            }
            std::reverse(path->begin(), path->end());

            point = match->m_parent;
            for(; point != NULL; point = point->m_parent)
            {
                path->push_back(point->m_node);
            }

            return move(path);
        }

        edgeF.erase(edgeF.begin());

        auto expandedListF = bestNodeF->m_node.expand();

        for(auto it = expandedListF->begin(); it != expandedListF->end(); ++it)
        {
            auto result = discoveredF.insert(EstimatedNode(*it, goal, bestNodeF));
            if(result.second)
            {
                EstimatedNode const* newNode = &(*result.first);
                edgeF.insert(newNode);
            }
        }
        bestNodeF = *edgeF.begin();

        match = discoveredF.find(*bestNodeB);
        if(match != discoveredF.end())
        {
            EstimatedNode const* point = match->m_parent;
            for(; point != NULL; point = point->m_parent)
            {
                path->push_back(point->m_node);
            }
            std::reverse(path->begin(), path->end());

            point = bestNodeB;
            for(; point != NULL; point = point->m_parent)
            {
                path->push_back(point->m_node);
            }

            return move(path);
        }

        edgeB.erase(edgeB.begin());

        auto expandedListB = bestNodeB->m_node.expand();

        for(auto it = expandedListB->begin(); it != expandedListB->end(); ++it)
        {
            auto result = discoveredB.insert(EstimatedNode(*it, start, bestNodeB));
            if(result.second)
            {
                EstimatedNode const* newNode = &(*result.first);

                edgeB.insert(newNode);
            }
        }
        bestNodeB = *edgeB.begin();
    }

    return move(path);
}

#endif // ASTAR_B_HPP_INCLUDED

Добавлено @ 20:52
step 60 execution time : 5.352 s

Код

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

Process returned 0 (0x0)   execution time : 5.352 s

Но решение может bыть не оптимальным, по какой-то причине, на первом примере вместо 36 выдаёт 42 шага. Может не совсем правильно реализовал.

Пожалуй, мне это надоело... smile

Добавлено @ 20:57

Цитата(Isaev @ 23.11.2010, 19:03

)

а потом 3х3 это же выведет алгоритм раньше к правильному решению?

Только если получится решаемая комbинация.

Добавлено @ 21:00

Цитата(Isaev @ 23.11.2010, 19:03

)

ну применимо к картам никто не мешает изменить эвристическую оценку к тому же sqrt(dx^2 + dy^2)

sqrt(dx^2 + dy^2) / V(cредняя скорость)
Т.е. надо время считать.

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

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

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

Леопольд

Дата 23.11.2010, 21:25 (ссылка)

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

Загрузка ...

Опытный

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

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

Цитата(Master01 @ 23.11.2010, 16:21

)

поскольку dx + dy (манхэттэн-расстояние) всега заведомо больше sqrt(dx^2 + dy^2)

sqrt(dx^2 + dy^2) = S(x, y)
dx + dy = M(x, y)

S(1,1) < S(1,2)
M(1, 1) < M(1,2)
И то и другое должно найти оптимальный путь. Суть в том, что если эвристическая функция менее точна, то, почти наверняка, понадоbиться bольше нодов рассмотреть при поиске.

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

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

Isaev

Дата 23.11.2010, 21:37 (ссылка)

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

Загрузка ...

Шустрый

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

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

Цитата(Леопольд @ 23.11.2010, 20:49

)

Пожалуй, мне это надоело...

это потому, что нет азарта smile

не пробовал на hacker.org игры для программистов?
Вот там интерес не пропадает, т.к. кто-то всё равно сделает быстрее, сидишь и думаешь что же можно улучшить, когда вроде и так всё летает smile

)))

Master01

Дата 24.11.2010, 16:11 (ссылка)

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

Загрузка ...

Шустрый

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

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

Цитата

ну применимо к картам никто не мешает изменить эвристическую оценку к тому же sqrt(dx^2 + dy^2), если такой путь часто имеет место быть, то оно себя окупит...

Ну а если не имеет место часто быть? Вообще, это соответствует движению по прямой от старта к финишу - крайне частный случай! во всех остальных случаях эвристическая функция будет недооценивать расстояние, что приведёт к тому, что алгоритм начнёт рыскать по крате, как алгоритм Дейкстры, вместо того чтобы двигаться направлено к цели, что есть замедление.

Я не говорю, что это не верно. Просто прежде чем вводить ту или иную эвристику нужно хорошо подумать smile

А для той задачи, что я привёл уже люди хорошо подумали и рекомендовали нам делать так smile

Цитата

а вычисления всегда можно оптимизировать разложив до булевых операций и сдвигов, и скорость будет вполне сносной...

Ну так МП так и поступает.

Добавлено через 13 минут и 33 секунды

Цитата(Леопольд @ 23.11.2010, 21:25)

Цитата(Master01 @ 23.11.2010, 16:21

)

поскольку dx + dy (манхэттэн-расстояние) всега заведомо больше sqrt(dx^2 + dy^2)

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

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

Цитата

Суть в том, что если эвристическая функция менее точна, то, почти наверняка, понадоbиться bольше нодов рассмотреть при поиске.

нет, только если она не точно в меньшую сторону, т.е. недооценивает расстояние. Чем меньше вклад эвристического приближения h(x) в общую оценку f(x) = g(x) + h(x), тем алгоритм менее направлен, т.е. просматривает больше узлов.

С другой стороны переоценка - добавляет направленности, но теряется точность, т.е. не гарантируется все те свойства, описанные выше.

Леопольд

Дата 24.11.2010, 17:50 (ссылка)

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

Загрузка ...

Опытный

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

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

Цитата(Master01 @ 24.11.2010, 16:11

)

манхэттен не переоценит расстояние только если

Это не важно. Главное что для по разному удалённых точек на карте, манхэттен bудет давать разную оценку, для дискретной карты, он подходит лучше (даже если можно передвигаться наискосок). При этом для той, которая bлиже, цена bудет меньше. Для эвристики bольшего не надо, т.е. bудет найден оптимальный путь (это как в пятнашках, можно посчитать количество костяшек, не на своём месте). Но, скорее всего, придётся проверить bольшее количество нодов.

Смысл эвристки не в том что-bы дать реальную оценку предстоящего пути (оbычно это невозможно, иначе нет смысла в алгоритме), а в том, что-bы указать, какие состояния нужно проверить прежде других, что-bы алгоритм искал решение "по направлению к цели" прежде всего. Чем точнее эвристика, тем меньше нодов bудет проверенно. (третий раз повторю, на всякий пожарный, авось не проигнорируешь в этот раз...)

Пройденное расстояние, желательно оbязательно надо оценивать так же по тому же принципу как и предстоящее (тогда не bудет переоценки расстояния).

Это сообщение отредактировал(а) Леопольд - 25.11.2010, 05:52

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

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

Master01

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

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

Загрузка ...

Шустрый

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

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

Цитата(Леопольд @ 24.11.2010, 17:50)

Цитата(Master01 @ 24.11.2010, 16:11

)

манхэттен не переоценит расстояние только если

Это не важно.

Леопольд, прокомментирую только первое ваше предложение, т.к. дальше вы там что-то красных букв много понаписали... да и смыла нет.

Вот, вам цитата из википедии

Функция h(x) должна быть допустимой эвристической оценкой, то есть не должна переоценивать расстояния к целевой вершине

Вот ещё из буржуйской, если инфа в русской вызывает сомнения

The h(x) part of the f(x) function must be an admissible heuristic; that is, it must not overestimate the distance to the goal

Если вы отвечаете мне "не важно" на мои слова про "переоценку" расстояния, то значит, простите, но это скорее всего вы что-то проигнорировали в моих предыдущих постах.

Добавлено через 14 минут и 35 секунд

Цитата

Пройденное расстояние, желательно оценивать так же как и предстоящее

Вообще не верно по сути. Пройденное растояние можно измерить т.к. вы его прошли. А предстоящее можно только угадать, потому что измерять нечего. О какой унификации вы тут говорите, я вообще не понимаю.

Леопольд

Дата 25.11.2010, 03:27 (ссылка)

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

Загрузка ...

Опытный

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

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

Цитата(Master01 @ 24.11.2010, 22:22

)

Вообще не верно по сути. Пройденное растояние можно измерить т.к. вы его прошли.

Здесь видимо недопонимание, я изменил цитируемую строку, перечитайте.
Т.е. я имел ввиду что оценивать пройденное расстояние надо по тому же принципу что и предстоящее иначе, действительно можно "неугадать" предстоящее.

Цитата(Master01 @ 24.11.2010, 22:22

)

Вот, вам цитата из википедии

Вот вам результат исполнения, можете проверить сами...
Решётки - препятствия. Плюсиками отмечено найденное решение. Точками, остальные рассмотренные состояния, не вошедшие в оптимальный путь. Проbел - не рассматривалось:

dx + dy

Код

++###################
..++++..............#
#...#.+###....#.###.#
#...#..+.#....#...#.#
#...#...+.....#####.#
#...#....+..........#
#...#.....+##########
#####......+++++....#
#   ....#..###.#+...#
# ###...#....#.#+...#
# # #...#.#..#.##+..#
# # #.....#..#...+..#
# # #...#.#..####.+.#
#   #.....#........+.
###################.+
path length    = 22
expanded nodes = 175

sqrt(pow(dx, 2) + pow(dy, 2))

Код

+.###################
.+..+.....          #
#.++#+.###    # ### #
#...#.+..#..  #   # #
#...#..+......##### #
#...#...+.....      #
#...#....+.##########
##### ....++++..    #
#      .#..###+#    #
# ###   #....#+#    #
# # #   #.#..#+##.. #
# # #     #..#.++...#
# # #   # #..####+..#
#   #     #     ..++.
###################.+
path length    = 22
expanded nodes = 104

Цитата(Master01 @ 24.11.2010, 16:11

)

Манхэттен не переоценит расстояние только если при движении к цели вам нужно сначало спуститься по вертикали до нужной вертикали, а потом строго горизонтально двигаться уже до цели вправо или влево (ну или ещё там где-то петлять). Во всех остальных случаях расстояние будет переоцениным. т.е. минимальность пути не будет гарантирована.

Разница в количестве шагов есть? Пути немножко отличаются, но по длине (количеству шагов) они всегда будут одинаковые. Разница здесь заключается в количестве рассмотренных состояний (точек на карте).

Код

#include <cstring>
#include <iostream>

#include "astar.hpp"

enum {height = 15, width = 21};

char map[height][width + 2] =
{
    "+ ###################\n",
    "                    #\n",
    "#   #  ###    # ### #\n",
    "#   #    #    #   # #\n",
    "#   #         ##### #\n",
    "#   #               #\n",
    "#   #      ##########\n",
    "#####               #\n",
    "#       #  ### #    #\n",
    "# ###   #    # #    #\n",
    "# # #   # #  # ##   #\n",
    "# # #     #  #      #\n",
    "# # #   # #  ####   #\n",
    "#   #     #          \n",
    "################### +\n",
};

std::size_t expandedNodes = 0;

struct Node
{
    struct Pos
    {
        Pos(std::size_t i_, std::size_t j_) : i(i_), j(j_) {}
        std::size_t i;
        std::size_t j;
    } m_state;

    Node(std::size_t i, std::size_t j) : m_state(i, j) {}

    Node(Node const& rhs) : m_state(rhs.m_state) {}

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

//    Node() {}

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

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

    std::unique_ptr<std::vector<Node>> expand() const
    {
        std::unique_ptr<std::vector<Node>> result(new std::vector<Node>);

        std::size_t top = 0 < this->m_state.i ? m_state.i - 1  : 0;
        std::size_t const bottom = this->m_state.i < height - 1 ? m_state.i + 1 : height - 1;

        for(; top <= bottom; ++top)
        {
            std::size_t left = 0 < this->m_state.j ? m_state.j - 1 : 0;
            std::size_t const right = this->m_state.j < width - 1 ? m_state.j + 1 : width - 1;

            for(; left <= right; ++left)
            {
                if(map[top][left] != '#')
                {
                    if(map[top][left] != '.')
                    {
                        ++expandedNodes;
                        map[top][left] = '.';
                        result->push_back(Node(top, left));
                    }
                }
            }
        }

        return move(result);
    }

    typedef double HCost;

//    static Node::HCost heurisicCost(Node const& from, Node const& to)
//    {
//        double const dx = from.m_state.i < to.m_state.i ? to.m_state.i - from.m_state.i : from.m_state.i - to.m_state.i;
//        double const dy = from.m_state.j < to.m_state.j ? to.m_state.j - from.m_state.j : from.m_state.j - to.m_state.j ;
//
//        return dx + dy;
//    }

    static Node::HCost heurisicCost(Node const& from, Node const& to)
    {
        double const dx = from.m_state.i < to.m_state.i ? to.m_state.i - from.m_state.i : from.m_state.i - to.m_state.i;
        double const dy = from.m_state.j < to.m_state.j ? to.m_state.j - from.m_state.j : from.m_state.j - to.m_state.j ;

        return ::sqrt(::pow(dx, 2) + ::pow(dy, 2));
    }
};




int main()
{
    auto result = aStarSearch(Node(0, 0), Node(14, 20));

    for(auto it = result->begin(); it != result->end(); ++it)
    {
        map[it->m_state.i][it->m_state.j] = '+';
    }

    for(std::size_t i = 0; i < height; ++i)
        std::cout << map[i];

    std::cout << "path length    = " << result->size() - 1 << '\n';
    std::cout << "expanded nodes = " << expandedNodes << std::flush;

    return 0;
}

Цитата(Master01 @ 24.11.2010, 22:22

)

Леопольд, прокомментирую только первое ваше предложение, т.к. дальше вы там что-то красных букв много понаписали...

Если выдрать предложение из контекста, то у него может запросто измениться смысл на противоположный. Может неспроста там bуковки красные?

Это сообщение отредактировал(а) Леопольд - 25.11.2010, 09:45

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

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

Леопольд

Дата 25.11.2010, 10:22 (ссылка)

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

Загрузка ...

Опытный

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

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

Так, наверное, понятнее в чём разница:
r() - стоимость пройденного пути
h() - эвристическая оценка

r() = dx + dy
h() = dx + dy

Код

#   .+..........   #
#   .+..........   #
#   .+..........   #
#   .+..........   #
#   .+..........   #
#   .+..........   #
#   ..+.........   #
#   ...+........   #
#   ....+.......   #
#   .....+......   #
#   ......+.....   #
#   .......+....   #
#   ........+...   #
#   .........+..   #
#   ..........+.   #
path length    = 14
expanded nodes = 180

http://liveworkspace.org/code/06c2ad0d88bf9ef8488ff7718b2f924c

r() = sqrt(pow(dx, 2) + pow(dy, 2))
h() = sqrt(pow(dx, 2) + pow(dy, 2))

Код

#   .+...          #
#   ..+...         #
#   ...+...        #
#    ...+...       #
#     ...+...      #
#      ...+..      #
#       ..+...     #
#        ..+...    #
#        ..+....   #
#         ..+...   #
#         ..+...   #
#          ..+..   #
#          ..+..   #
#           .+..   #
#           ..+.   #
path length    = 14
expanded nodes = 87

http://liveworkspace.org/code/373a804d7d5788718b08fc4ab201a41f

r() = dx + dy
h() = sqrt(pow(dx, 2) + pow(dy, 2))

Код

#....+..........   #
#....+..........   #
#....+..........   #
#....+..........   #
#....+..........   #
#....+..........   #
#.....+.........   #
# .....+........   #
# ......+.......   #
# .......+......   #
#  .......+.....   #
#  ........+....   #
#  .........+...   #
#   .........+..   #
#   ..........+.   #
path length    = 14
expanded nodes = 210

http://liveworkspace.org/code/829322bd34ab3183265c494608421bca
h() < r() - рассматриваются сперва те ноды, которые ближе к старту (большее количество нодов)

r() = sqrt(pow(dx, 2) + pow(dy, 2))
h() = dx + dy

Код

#   .+..           #
#   ..+..          #
#    ..+..         #
#     ..+..        #
#      ..+..       #
#       ..+..      #
#        ..+..     #
#         ..+..    #
#          ..+..   #
#           ..+.   #
#            .+.   #
#            .+.   #
#            .+.   #
#            .+.   #
#            .+.   #
path length    = 14
expanded nodes = 63

http://liveworkspace.org/code/96359f2f06134f0961a244ecbdbd5c2b
h() > r() - рассматриваются сперва те ноды, которые ближе к цели (меньшее количество нодов)

h() = r(), гарантирует оптимальность решения (наименьший путь)
насчёт h() < r(), не уверен, интуитивно кажется то решение оптимальное
h() > r(), быстрее поиск, но нет гарантии оптимального решения

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

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

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

Леопольд

Дата 25.11.2010, 12:52 (ссылка)

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

Загрузка ...

Опытный

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

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

Забавно. Увеличил в 1.5 раза h() относительно r() в пятнашках и получил оптимальный результат (51 шаг) менее чем за 3 секунды.
http://liveworkspace.org/code/7e1472ca6b32...5357e0d330320c3

Если в два раза, то решает за 61 ход менее чем за секунду...
http://liveworkspace.org/code/58e9e2b3536e...f06f846a39dcafc

В пять раз smile

Код


step 93
  1  2  3  4
  5  6  7  8
  9 10 11 12
 13 14 15  
execution time: 0.1163

Если нужно решить хоть как-то, но очень быстро. Алгоритм быстрее продвигается к цели, пренебрегая точностью...

Это сообщение отредактировал(а) Леопольд - 25.11.2010, 12:56

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

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

Master01

Дата 25.11.2010, 13:38 (ссылка)

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

Загрузка ...

Шустрый

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

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

Цитата

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

Цитата

Леопольд, ну вот словами "я же говорил" этого не передать ...

Леопольд

Дата 25.11.2010, 14:22 (ссылка)

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

Загрузка ...

Опытный

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

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

Цитата(Master01 @ 25.11.2010, 13:38

)

но теряется точность

Эмпирически выявил что точность теряется после определённого порога переоценки. Если эвристику считать так (h() * (1 + 0.01 * r()), то потерь точности не наблюдается... До тех пор, пока не пересечёшь некий определённый порог, оптимальность сохраняется, скорость увеличивается.

Цитата(Master01 @ 25.11.2010, 13:38

)

Леопольд, ну вот словами "я же говорил" этого не передать ...

А я разве с этим спорил? Но вот ещё что было сказано:

Цитата(Master01 @ 24.11.2010, 16:11

)

Манхэттен не переоценит расстояние только если при движении к цели вам нужно сначало спуститься по вертикали до нужной вертикали, а потом строго горизонтально двигаться уже до цели вправо или влево (ну или ещё там где-то петлять). Во всех остальных случаях расстояние будет переоцениным. т.е. минимальность пути не будет гарантирована.

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

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

Цитата(Master01 @ 24.11.2010, 16:11

)

Нет.

А так как делать мне было нефиг, я ударился в полемику. smile

P.S. Когда ж мне надоест писать одно и то же разными словами, вот ведь зануда...

Это сообщение отредактировал(а) Леопольд - 25.11.2010, 15:10

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

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

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