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

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

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 16, средняя оценка - 4.69
nixe
Сообщений: n/a
#1

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

17.03.2011, 21:10. Просмотров 2251. Ответов 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++
Выдает ошибку Error 1 error C4996: 'itoa': The POSIX name for this item is deprecated. Instead, use the ISO C++ conformant name: _itoa. See...

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

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

Поиск кратчайшего пути (рекурсия) - C++
Помогите пожалуйста. Пусть имеется n городов. Некоторые из них соединены дорогами известной длины. С помощью рекурсии найти Кратчайшие...

Нахождение кратчайшего пути, поиск с возвратом - C++
Описание проблемы: Есть матрица MxN, на матрицы есть дом школьника и школа. Школьник может двигаться в 4 направления. На прохождения 1ой...

Поиск кратчайшего пути в матрице через рекурсию - C++
Есть задача: найти кратчайший путь в матрице,представляющий из себя сумму значений ее элементов. Матрица размера 10х10. Я реализовал сам...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Ma3a
Эксперт C++
617 / 461 / 31
Регистрация: 28.01.2011
Сообщений: 605
17.03.2011, 21:17 #2
Я за вариант с графом, а насчет представления, для больших размеров, задавать граф матрицей - довольно дорого, при увеличении размеров будет оптимальнее перейти на представление графа в виде списка ребер или списков смежности, так расходы памяти будут меньше, да и обход графа поудобнее реализовывать.
1
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
17.03.2011, 21:17
Привет! Вот еще темы с ответами:

Алгоритм Дейкстра. Поиск кратчайшего пути с запоминанием маршрута - C++
Всем привет, есть алгоритм Дейкстра, который находит минимальный маршрут из главной вершины во все остальные. Как сделать, чтобы помимо...

Поиск кратчайшего пути между вершинами на основе очереди - C++
Задан ориентированный граф вида матрицы смежности. Нужно определить кратчайшее расстояние от одной вершины к другой. Вход: 4 1 2 -...

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

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


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

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

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