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

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

Войти
Регистрация
Восстановить пароль
 
GMS
0 / 0 / 0
Регистрация: 31.10.2010
Сообщений: 3
#1

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

28.11.2013, 23:10. Просмотров 382. Ответов 1
Метки нет (Все метки)

Доброго времени суток.

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



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

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

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

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

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

Поиск оптимального пути в графе - C++
Здравствуйте. Помогите, пожалуйста, написать код задачи по С++. необходимо найти минимальный путь в ориентированном графе, используя...

Задача на поиск алгоритма оптимального разбития набора фильмов с учетом оценок этих фильмов - C++
К дедушке приехали внуки: Екатерина и Дмитрий. Дедушка подготовил им подарок - коробку с видеофильмами, но сказал, что в коробке четное...

Поиск пути - C++
Люди добрые,помогите пожалуста с задачкой: Дан двумерный массив А состоящий из нулей и единиц, с клавиатуры вводятся координаты двух...

Поиск пути - C++
Здравствуйте, посмотрите пожалуйста код и прокомментируйте на сколько рационально я использую память и вычислительную мощность?:-#include...

Поиск пути - C++
есть таблица в которой некоторые клетки заняты и некоторые свободны. нужен алгоритм нахождения пути из точку а(х1,у1) в точку б(х2,у2). ...

Поиск пути - C++
Дан лабиринт из n комнат и матрица, в которой содержится информация о наличии прохода между любыми двумя комнатами, независимо от их...

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

Попробуй лучше использовать bfs с сетом пар (стоимость и вершина) вместо очередиди. Потому что рёбер мало.
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
06.12.2013, 18:29
Привет! Вот еще темы с ответами:

поиск длины пути - C++
Всем доброго утра Ребята подскажите пожалуйста алгоритм дана матрица расстояний n*n, в ячейках расположены расстояний между i и j...

Поиск пути в лабиринте - C++
Доброго времени суток! есть задача пройти лабиринт {1 1 1 1 1 0 1 0 0 0 0 0 0 0 1 1 1 1 0 1 1 1 0 0 0 0 1 1 1 0 1 0 0 0 1 1...

Поиск пути в лабиринте - C++
Есть двухмерный массив : 1 - препятствие, 0 - проход. Нужно найти кратчайший путь от одной точки до другой. У меня есть волновой...

Поиск пути на поле из шестиугольников - C++
Всем привет)) Нужна ваша помощь. В одной веб-игре нужно написать бота, игра в жанре ммо рпг (пошаговая). Я столкнулся с проблемой...


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

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

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