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

Поиск кратчайшего пути на клетчатом поле. - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 16, средняя оценка - 4.69
nixe
Сообщений: n/a
17.03.2011, 21:10     Поиск кратчайшего пути на клетчатом поле. #1
Дано клетчатое поле (допустим n x n). На некоторые клетки наступать нельзя. Дана начальная клетка, дана конечная клетка. Надо найти кратчайший путь из начальной клетки в конечную.

Просьба: подтолкните меня, пожалуйста, к оптимальному решению! Пожалуйста, не решайте за меня, я сама. И, по возможности, не говорите прямым текстом, задавайте лучше наводящие вопросы, чтобы я сама додумалась, как лучше.

Имеющиеся на данный момент идеи:
  • поле имплементовать двухразмерным массивом, где клетки, куда можно наступать будут 0, клетки куда нельзя (камни, лес, что угодно, если предполагать, что у нас какая-нибудь карта ^^) - 1. Или наоборот, не принципиально пока.
  • каждую клетку воспринять как вершину графа. Таким образом, вершины, находящиеся в клетках, куда нельзя наступать, будут оторваны от графа, а вершины, соответствующие "обычным" клеткам, будут соответственно иметь от 1 до 4 граней.
  • таким образом, вся задача конвертируется на задачу поиска кратчайшего пути в графе => да поможет мне Дийкстра.

Что смущает в собственой идее - с ростом размера поля размер матрицы, описывающей граф, будет расти до неописуемых размеров, ибо уже для поля 8х8 (64 вершины), надо массив 64х64 для описания графа. Я первокурсник, опыта с графами, кроме теоретического, - нет, поэтому такие цифры кажутся неоправданно большими.

Критикуйте, стебите, буду только рада. Ещё раз, пожалуйста, прошу, подсказывайте аккуратно! Выводы хочу сделать сама!
И заранее спасибо, тем, кто-таки возьмётся.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
17.03.2011, 21:10     Поиск кратчайшего пути на клетчатом поле.
Посмотрите здесь:

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

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Ma3a
Эксперт C++
612 / 456 / 31
Регистрация: 28.01.2011
Сообщений: 605
17.03.2011, 21:17     Поиск кратчайшего пути на клетчатом поле. #2
Я за вариант с графом, а насчет представления, для больших размеров, задавать граф матрицей - довольно дорого, при увеличении размеров будет оптимальнее перейти на представление графа в виде списка ребер или списков смежности, так расходы памяти будут меньше, да и обход графа поудобнее реализовывать.
Yandex
Объявления
17.03.2011, 21:17     Поиск кратчайшего пути на клетчатом поле.
Ответ Создать тему
Опции темы

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