Форум программистов, компьютерный форум CyberForum.ru

Реализация алгоритма А* (поиск кратчайших расстояний на графе) - C++

Восстановить пароль Регистрация
 
hoob
19 / 11 / 1
Регистрация: 04.11.2012
Сообщений: 89
Записей в блоге: 1
16.12.2013, 21:40     Реализация алгоритма А* (поиск кратчайших расстояний на графе) #1
В общем, уже несколько дней бьюсь над небольшой проблемой:
написал поиск кратчайших путей на графе на основе алгоритма А*.
Пути находятся, все хорошо, но вот незадача: не могу восстановить оптимальный путь, т.е сам кратчайший путь с целью его отображения. Получается найти только путь "брожения" алгоритма в поисках пути.
Вот сам код:
C++ (Qt)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
bool Graph::findPath(Node* node_from, Node* node_to)
{
    QMap<double,aNode> open; // key - cost function f 
    QMap<quint64,aNode> closed; // key - Node id
    
    aNode sNode;
    sNode.it = nodes.find(node_from->id);
    sNode.g = 0;
    sNode.h = distance(node_from,node_to);
    sNode.f = sNode.g + sNode.h;
    sNode.comeFrom = 0;
 
    open.insert(sNode.f, sNode);
 
    while (!open.isEmpty())
    {
        aNode x = open.begin().value();
        if (x.it->id == node_to->id)
        {
            int comeFrom = x.comeFrom;
            while (comeFrom != 0)
            {
                route.push_back(comeFrom);
                comeFrom = closed.find(comeFrom)->comeFrom;
            }
            return true;
        }
        open.remove(x.f);
        closed.insert(x.it->id,x);
        for (int i = 0 ; i < x.it->adj.size() ; i++)
        {
            if (!edges.contains(QPair<quint64,quint64>(x.it->id,x.it->adj[i])))
                continue;
            if (closed.contains(x.it->adj[i]))
                continue;
            aNode y;
            y.it = nodes.find(x.it->adj[i]);
            y.g = x.g + edges.find(QPair<quint64,quint64>(x.it->id,x.it->adj[i]))->cost;
            y.h = distance(&(*y.it),node_to);
            y.f = y.g + y.h;
            y.comeFrom = x.it->id;
            if (open.key(y,-2) == -2)
                open.insert(y.f,y);
            else
                if (y.g < open.find(open.key(y))->g )
                    open.insert(y.f, y);
        }
    }
    return false;
}
Пишу на Qt. Реализация А* требует использования приоритетной очереди для открытого списка, вместо этого использую QMap с ключом в виде функции цены f, т.к Мар все равно сортируется по ключу по возрастанию, то свои задачи она выполняет (поправьте, если ошибаюсь).
На всякий случай aNode:
C++
1
2
3
4
5
6
7
8
9
10
11
class aNode
{
public:
    aNode();
    ~aNode();
    QHash<quint64,Node>::iterator it;
    quint64 comeFrom;
    double f;
    double g;
    double h;
};
Валидность данных и эвристическая оценка точно правильные.
Ощущение, что я как-то не так расставляю comeFrom в узлах очереди.

Вопрос в том, как "собрать" именно оптимальный путь?
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
16.12.2013, 21:40     Реализация алгоритма А* (поиск кратчайших расстояний на графе)
Посмотрите здесь:

C++ Поиск кратчайших путей из одного источника для неориентированного графа
C++ Эффективный алгоритм подсчета расстояний от произвольной вершины до всех стальных вершин в графе
C++ Поиск кратчайших путей между двумя вершинами графа методом Шимбела.
Поиск циклов в графе. Поиск центра взвешенного графа C++
C++ Прогрмма по поиску кратчайших путей в графе
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
monolit
179 / 179 / 21
Регистрация: 24.03.2011
Сообщений: 641
Завершенные тесты: 1
16.12.2013, 22:37     Реализация алгоритма А* (поиск кратчайших расстояний на графе) #2
QМар все равно сортируется по ключу по возрастанию, то свои задачи она выполняет (поправьте, если ошибаюсь).
Поправляю. Красно-черное дерево это.
Извини, в коде разбираться неохота, но вот довольно простой приме (сам писал), без особых изысков, зато коротко и быстро (не самый быстродейственный, конечно, но для обычных задач хватает, даже трудоемких)
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
    
/**
pair<int, int> first  - откуда, last - куда.
mPassable - матрица проходимости (тебе может не нужна, но это из одного проекта моего....)
labeled - помеченные ячейки (уже просмотренные)
auxPrice и прочие ***price - стоимость прохождения(повторюсь - код из левого проекта, там было так нужно)
*/
if (first == last || !mPassable(last)) return vector<ipair>();
    int dx[] = {-1,  0,  1, 1, 1, 0, -1, -1};
    int dy[] = {-1, -1, -1, 0, 1, 1,  1,  0};
 
    list<ipair> open(1, first);
    map<ipair, ipair> parents;
 
        labeled = 0; //тут было другое, это не важно
    label(first) = ++labeled;
    
    list<ipair>::iterator minInd;
    ipair cur, tempCur;
    for(double minVal;;) {
        minVal = DBL_MAX;
        if (open.size()==0) return vector<ipair>();
/*тут ищем с наименьшей стоимость в открытом списке*/
        for(auto it = open.begin(); it!=open.end(); ++it) {
            if (minVal > auxPrice(*it)) {
                minVal = auxPrice(*it);
                minInd = it;
            }
        }
        cur = *minInd;
        if (cur==last) break;
        open.erase(minInd);
/*обсчет соседних не проверенных и занес. их в открытый*/
        for(int i = 0; i<8; ++i) {
            tempCur = make_pair(cur.first+dx[i], cur.second+dy[i]);
            if (label.isCorrect(tempCur) && mPassable(tempCur) && label(tempCur)!=labeled) {
                price(tempCur) = mCost(tempCur) + price(cur) + gm::evr_dist(tempCur, cur);
                auxPrice(tempCur) = price(tempCur) + gm::evr_dist(tempCur, last);
                label(tempCur) = labeled;
                open.push_back(tempCur);
                parents[tempCur] = cur;
            }
        }
    }
    /*обратная трассировка*/
    vector<ipair> closed;
    cur = parents[last];
    closed.push_back(last);
    while(cur != first) {
        closed.push_back(cur);
        cur = parents[cur];
    };
    
    return closed;
Добавлено через 2 минуты
Цитата Сообщение от hoob Посмотреть сообщение
А* требует использования приоритетной очереди
Она просто советует, а не требует. Мне вот к примеру такой вариант не подошел бы (или свою очередь писать бы пришлось), поэтому воспользовался обычным списком, а цены брал непосредственно из матрицы.

Добавлено через 1 минуту
И последнее:
Цитата Сообщение от hoob Посмотреть сообщение
как "собрать" именно оптимальный путь?
Храни родителей ячеек (из которой пришли), восстанавливается потом легко (в примере видно), начиная с конечной.
hoob
19 / 11 / 1
Регистрация: 04.11.2012
Сообщений: 89
Записей в блоге: 1
16.12.2013, 22:46  [ТС]     Реализация алгоритма А* (поиск кратчайших расстояний на графе) #3
Цитата Сообщение от monolit Посмотреть сообщение

Добавлено через 1 минуту
И последнее:

Храни родителей ячеек (из которой пришли), восстанавливается потом легко (в примере видно), начиная с конечной.
Я так и делаю см. строчки 18 - 26. Просто, может быть я не так как-то родителей назначаю?
monolit
179 / 179 / 21
Регистрация: 24.03.2011
Сообщений: 641
Завершенные тесты: 1
16.12.2013, 23:18     Реализация алгоритма А* (поиск кратчайших расстояний на графе) #4
А ты пробовал на простейшем примере, к примеру, где длина пути 2-3-4? Проверил бы и увидел, где косяк... Хотя может ты и проверил, не исключаю, но вроде у тебя схема похожая на правильную - если на первый взгляд.
hoob
19 / 11 / 1
Регистрация: 04.11.2012
Сообщений: 89
Записей в блоге: 1
18.12.2013, 14:48  [ТС]     Реализация алгоритма А* (поиск кратчайших расстояний на графе) #5
Тему можно закрывать: проблема была в другом месте. Поиск работает правильно.
Yandex
Объявления
18.12.2013, 14:48     Реализация алгоритма А* (поиск кратчайших расстояний на графе)
Ответ Создать тему
Опции темы

Текущее время: 01:09. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru