Форум программистов, компьютерный форум, киберфорум
Наши страницы

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
hoob
20 / 12 / 1
Регистрация: 04.11.2012
Сообщений: 89
Записей в блоге: 1
#1

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

16.12.2013, 21:40. Просмотров 582. Ответов 4
Метки нет (Все метки)

В общем, уже несколько дней бьюсь над небольшой проблемой:
написал поиск кратчайших путей на графе на основе алгоритма А*.
Пути находятся, все хорошо, но вот незадача: не могу восстановить оптимальный путь, т.е сам кратчайший путь с целью его отображения. Получается найти только путь "брожения" алгоритма в поисках пути.
Вот сам код:
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 в узлах очереди.

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

Поиск кратчайших путей в графе - C++
Владислав Исенбаев — двукратный чемпион Урала по программированию, вице-чемпион TopCoder Open 2009, абсолютный чемпион ACM ICPC 2009. За то...

Прогрмма по поиску кратчайших путей в графе - C++
Всю голову поломал,но вот что-то толком не получается(((Нужна программа по поиску кратчайших путей в графе на основе теории нечетких...

Реализация матрицы смежности и инцидентности, поиск циклов в графе - C++
Здравствуйте. Есть программа, выводящая матрицу смежности и инцидентности. Прошу помощи в реализации добавления и удаления вершин и рёбер...

Найти диаметр графа, то есть, максимальное значение среди всех кратчайших расстояний между каждой парой вершин - C++
Найти диаметр графа, то есть максимальное значение среди всех кратчайших расстояний между каждой парой вершин. Ответ: номера двух вершин...

Эффективный алгоритм подсчета расстояний от произвольной вершины до всех стальных вершин в графе - C++
Реализовать в виде программы и исследовать эффективный алгоритм подсчета расстояний от произвольной вершины до всех стальных вершин в...

Поиск кратчайших путей из одного источника для неориентированного графа - C++
Дорогие программисты! Прошу вас помочь мне в очень срочном деле! Очень нужен код программы, которая в заголовке на С++. Нашла целую...

4
monolit
186 / 185 / 22
Регистрация: 24.03.2011
Сообщений: 669
Завершенные тесты: 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 Посмотреть сообщение
как "собрать" именно оптимальный путь?
Храни родителей ячеек (из которой пришли), восстанавливается потом легко (в примере видно), начиная с конечной.
1
hoob
20 / 12 / 1
Регистрация: 04.11.2012
Сообщений: 89
Записей в блоге: 1
16.12.2013, 22:46  [ТС] #3
Цитата Сообщение от monolit Посмотреть сообщение

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

Храни родителей ячеек (из которой пришли), восстанавливается потом легко (в примере видно), начиная с конечной.
Я так и делаю см. строчки 18 - 26. Просто, может быть я не так как-то родителей назначаю?
0
monolit
186 / 185 / 22
Регистрация: 24.03.2011
Сообщений: 669
Завершенные тесты: 1
16.12.2013, 23:18 #4
А ты пробовал на простейшем примере, к примеру, где длина пути 2-3-4? Проверил бы и увидел, где косяк... Хотя может ты и проверил, не исключаю, но вроде у тебя схема похожая на правильную - если на первый взгляд.
1
hoob
20 / 12 / 1
Регистрация: 04.11.2012
Сообщений: 89
Записей в блоге: 1
18.12.2013, 14:48  [ТС] #5
Тему можно закрывать: проблема была в другом месте. Поиск работает правильно.
0
18.12.2013, 14:48
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
18.12.2013, 14:48
Привет! Вот еще темы с ответами:

Поиск кратчайших путей между двумя вершинами графа методом Шимбела. - C++
Доброго всем время суток!! В универе задали на РГР написать программу в С++, которая находит кратчайший путь между двумя вершинами графа,...

Реализация поиска мостов на графе - C++
Подскажите, в чем проблема. Вроде весь код написан верно, но ничего не считает в итоге. У меня есть неориентированный граф, который я задаю...

Поиск циклов в графе. Поиск центра взвешенного графа - C++
В интернете, к сожалению, по этим вопросам не так уж много нашел. Можете посоветовать статью/пособие, где было бы подробно об этом написано?

АТД Графы. Поиск суммы расстояний между городами. - C++
Здравствуйте! Нужна помощь! Всем известная задача и в сети конечно много разнообразных тем! но не одна из них не доведена до...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
5
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru