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

Поиск оптимального пути в трехмерной карте - C++

Восстановить пароль Регистрация
 
GMS
0 / 0 / 0
Регистрация: 31.10.2010
Сообщений: 3
28.11.2013, 23:10     Поиск оптимального пути в трехмерной карте #1
Доброго времени суток.

Не получается решить задачу:
Существует 3-х мерная карта ячеек произвольной известной заранее размерности, каждая ячейка имеет свой "вес", известны координаты начальной и конечной ячейки соответственно. Необходимо найти оптимальный путь при котором сумма "весов" пройденных ячеек от начальной до конечной будет минимальна, двигаться можно только через грани, то есть 6 сторон, не выходя разумеется за границы.



Для визуализации карты в LabVIEW на основе OpenGLподобного интерфейса разработано приложение которое считывает из файла траекторию и подсвечивает ее на карте, но к сожалению или к счастью сам алгоритм нужно реализовать в c++ и тут возникли собственно трудности.

Поиск оптимального пути в трехмерной карте

Поиск оптимального пути в трехмерной карте

Что я пытался делать:
1) Про google, а в точности про алгоритм Дейкстры, А* и аналогичные, призванные решать такие задачи, в курсе, но к сожалению не смог применить, так как получающийся граф имеет в узлах по два "ребра" связи с разными длинами между соседними ячейками, сильно связанный. Все примеры и описания не предполагают такого графа.
2) Пытался решить задачу в лоб, рассчитывая на каждом шаге положительные направления движения (чтобы ни по какой из осей не удаляться от целевой точки) и выбирал тот шаг, который имеет наименьший вес. Начав реализовывать понял, что это ошибочно.

Подскажите как можно это реализовать в с++?
Карта в программе является трехмерным массивом типа integer, "веса" ячеек только положительные.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
28.11.2013, 23:10     Поиск оптимального пути в трехмерной карте
Посмотрите здесь:

C++ Поиск пути
C++ Поиск пути в лабиринте
C++ Поиск пути
C++ Поиск оптимального пути в графе
Поиск пути C++
C++ поиск длины пути
C++ Поиск пути
C++ Задача на поиск алгоритма оптимального разбития набора фильмов с учетом оценок этих фильмов

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Qwertiy
817 / 625 / 75
Регистрация: 20.08.2013
Сообщений: 2,525
06.12.2013, 18:29     Поиск оптимального пути в трехмерной карте #2
Цитата Сообщение от GMS Посмотреть сообщение
алгоритм Дейкстры
Он применим для ориентированных графов - не вижу проблем.
В качестве состояния (точнее вершины) надо брать 3 координаты.
Хотя вообще-то ассимптотика подозрительная O(n^6), где n - сторона куба.

Попробуй лучше использовать bfs с сетом пар (стоимость и вершина) вместо очередиди. Потому что рёбер мало.
Yandex
Объявления
06.12.2013, 18:29     Поиск оптимального пути в трехмерной карте
Ответ Создать тему
Опции темы

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