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

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

Восстановить пароль Регистрация
Другие темы раздела
C++ Написать программу, которая выводит координаты мыши при перемещении её над окном http://www.cyberforum.ru/cpp-beginners/thread1044523.html
Написать программу, которая выводит координаты мыши при перемещении её над окном. За ранее Благодарен!
C++ Добавить Удаление В программу Хелп Плиз!! не знаю как сделать удаление как не пытался не получается(( очень надо Я его сделал но он удаляет все ConsoleApplication12.cpp: определяет точку входа для консольного приложения. // #include "stdafx.h" #include "stdlib.h" #include "iostream" #include "windows.h" #include "iomanip" http://www.cyberforum.ru/cpp-beginners/thread1044510.html
не могу разобраться в несложной задаче C++
Задание: Даны целые числа a, b, c. Если числа не равны, то заменить каждое из них одним и тем же числом, равным большему из исходных, а если равны, то заменить числа нулями использовать как можно меньше строк и действий Проблема: недопустимый else без парного if #include <iostream> using namespace std; int main() {
Начал учить файлы =С C++
Не понимаю почему програма закрываеться самостоятельно! #define n 5 #include <stdio.h> #include <iostream> #include <locale.h> #include <iomanip> using namespace std; struct data
C++ Работа с классами http://www.cyberforum.ru/cpp-beginners/thread1044486.html
Здравствуйте! Вот у меня есть класс Team team.h#pragma once #include <string> using namespace std; class Team{ public: Team();
C++ вычисление произведения двух чисел и попадание точки в закрашенную область 1)Вычислить произведение двух чисел. Первое число - сумма третьей и четвертой цифр четырехзначного числа, второе - частное от деления первой цифры четырехзначного числа на вторую цифру числа. 2)Составить программу, которая выведет на экран “Попала”,если точка с введенными ко-ординатами (X,Y) принадлежит закрашенной области , “Мимо” – в противном случае. подробнее

Показать сообщение отдельно
hoob
19 / 11 / 1
Регистрация: 04.11.2012
Сообщений: 89
Записей в блоге: 1
16.12.2013, 21:40     Реализация алгоритма А* (поиск кратчайших расстояний на графе)
В общем, уже несколько дней бьюсь над небольшой проблемой:
написал поиск кратчайших путей на графе на основе алгоритма А*.
Пути находятся, все хорошо, но вот незадача: не могу восстановить оптимальный путь, т.е сам кратчайший путь с целью его отображения. Получается найти только путь "брожения" алгоритма в поисках пути.
Вот сам код:
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 в узлах очереди.

Вопрос в том, как "собрать" именно оптимальный путь?
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
 
Текущее время: 22:29. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru