Форум программистов, компьютерный форум 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) принадлежит закрашенной области , “Мимо” – в противном случае. подробнее

Показать сообщение отдельно
monolit
179 / 179 / 21
Регистрация: 24.03.2011
Сообщений: 641
Завершенные тесты: 1
16.12.2013, 22:37     Реализация алгоритма А* (поиск кратчайших расстояний на графе)
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 Посмотреть сообщение
как "собрать" именно оптимальный путь?
Храни родителей ячеек (из которой пришли), восстанавливается потом легко (в примере видно), начиная с конечной.
 
Текущее время: 15:02. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru