Прохождение лабиринта
 |
Наши проекты:
Журнал · Discuz!ML · Wiki · DRKB · Помощь проекту |
|
| ПРАВИЛА | FAQ | Помощь | Поиск | Участники | Календарь | Избранное | RSS |
| [3.138.200.66] |
|
|
правила раздела Алгоритмы
1. Помните, что название темы должно хоть как-то отражать ее содержимое (не создавайте темы с заголовком ПОМОГИТЕ, HELP и т.д.). Злоупотребление заглавными буквами в заголовках тем ЗАПРЕЩЕНО.
2. При создании темы постарайтесь, как можно более точно описать проблему, а не ограничиваться общими понятиями и определениями.
3. Приводимые фрагменты исходного кода старайтесь выделять тегами code.../code
4. Помните, чем подробнее Вы опишете свою проблему, тем быстрее получите вразумительный совет
5. Запрещено поднимать неактуальные темы (ПРИМЕР: запрещено отвечать на вопрос из серии "срочно надо", заданный в 2003 году)
6. И не забывайте о кнопочках TRANSLIT и РУССКАЯ КЛАВИАТУРА, если не можете писать в русской раскладке
2. При создании темы постарайтесь, как можно более точно описать проблему, а не ограничиваться общими понятиями и определениями.
3. Приводимые фрагменты исходного кода старайтесь выделять тегами code.../code
4. Помните, чем подробнее Вы опишете свою проблему, тем быстрее получите вразумительный совет
5. Запрещено поднимать неактуальные темы (ПРИМЕР: запрещено отвечать на вопрос из серии "срочно надо", заданный в 2003 году)
6. И не забывайте о кнопочках TRANSLIT и РУССКАЯ КЛАВИАТУРА, если не можете писать в русской раскладке
Модераторы: Akina, shadeofgray
Прохождение лабиринта
|
Сообщ.
#1
,
|
|
|
|
Помогите, плз, решить задачу. Есть лабиринт - набор клеток-комнат, в каждой из которых есть до четырех выходов в соседние (на север, юг, запад и восток). Требуется написать алгоритм прохождения лабиринта, который обойдет лабиринт, побывав в каждой клетке, за наименьшее число ходов и запоминая как можно меньше информации о каждой клетке лабиринта.
|
|
Сообщ.
#2
,
|
|
 |
Волновой алгоритм
|
|
Сообщ.
#3
,
|
|
|
|
http://algolist.manual.ru/games/wavealg.php
Вот пример реализации Прикреплённый файл  1995z2.rar (3.67 Кбайт, скачиваний: 193)
|
|
Сообщ.
#4
,
|
|
 |
Задача не корректно поставлена не возможно ОДНОВРЕМЕННО оптимизировать по двум параметрам.
Уточните, что Вам надо и Вам помогут |
|
Сообщ.
#5
,
|
|
 |
The-Boss
По-моему The great BAX Vano хочет передвигаться между соседними клетками. The great BAX Vano Вариант Для каждой клетки требует запоминания откуда приходил и в каких направлениях ты ходил. Придя в клетку первый раз продолжаешь движение в любом неотмеченном направлении. Попав повторно, если пришел с направления куда уходил идешь опять в неотмеченном. Если пришел с другого направления разворачиваешься и уходишь. Если неотмеченных нет возвращаешься по тому напралению откуда первый раз пришёл. Правда результат немного другой. Пройдешь по каждому ребру два раза. |
|
Сообщ.
#6
,
|
|
|
|
Это тривиальнейшая задача и всю жизнь для неё использовался волновой алгоритм. Обычно его оптимизируют, сохраняя как можно больше информации о маршруте. Но раз тут уж такая пьянка пошла, то используй как есть без оптимизации. 100% короткий маршрут. Вот описание и статейка. Реализации на Паскаль и С++. Держи!
Прикреплённый файл  _________________.zip (23.19 Кбайт, скачиваний: 451)
|
|
Сообщ.
#7
,
|
|
|
|
Это тривиальнейшая задача и всю жизнь для неё использовался волновой алгоритм. Обычно его оптимизируют, сохраняя как можно больше информации о маршруте. Но раз тут уж такая пьянка пошла, то используй как есть без оптимизации. 100% короткий маршрут. Вот описание и статейка. Реализации на Паскаль и С++. Держи!
Прикреплённый файл _________________.zip (23.19 Кбайт, скачиваний: 227)
|
|
Сообщ.
#8
,
|
|
|
|
Цитата Tosha @ Это тривиальнейшая задача и всю жизнь для неё использовался волновой алгоритм. Обычно его оптимизируют, сохраняя как можно больше информации о маршруте. Но раз тут уж такая пьянка пошла, то используй как есть без оптимизации. 100% короткий маршрут. Вот описание и статейка. Реализации на Паскаль и С++. Держи! Товарищи давайте читать вопрос. Требуется написать алгоритм прохождения лабиринта, который обойдет лабиринт, побывав в каждой клетке, за наименьшее число ходов и запоминая как можно меньше информации о каждой клетке лабиринта. [COLOR=red] Ваше "Это тривиальнейшая задача и всю жизнь для неё использовался волновой алгоритм. Обычно его оптимизируют, сохраняя как можно больше информации о маршруте. Но раз тут уж такая пьянка пошла, то используй как есть без оптимизации. 100% короткий маршрут. Вот описание и статейка. Реализации на Паскаль и С++. Держи! " Это - "Зaдaчa нaхождения сaмого короткого пути между некими точкaми A и В " - не отвечает поставленным автором темы требованиям. |
|
Сообщ.
#9
,
|
|
|
|
Да, давайте прочтем задачу
Цитата Помогите, плз, решить задачу. Есть лабиринт - набор клеток-комнат, в каждой из которых есть до четырех выходов в соседние (на север, юг, запад и восток). Требуется написать алгоритм прохождения лабиринта, который обойдет лабиринт, побывав в каждой клетке, за наименьшее число ходов и запоминая как можно меньше информации о каждой клетке лабиринта. Это задача не решается волновым алгоритмом, это задача на поиск гамильтонова цикла в графе. Решается она только перебором. Если я в чем-то не прав - исправьте ЗЫ Задача задана не очень корректно... |
|
Сообщ.
#10
,
|
|
|
|
Сорри, не правильно прочитал, потому погнал немного (много:)). Тут кстати может рулить алгоритм перебора с возвратом, как визвестной задаче о 8 ферзях.
borisvolfson прав:) Видимо гамильтонов цикл - примерно тоже самое. |
|
Сообщ.
#11
,
|
|
|
|
Да, это похоже на Гамильтонов цикл, за исключением того, что одну вершину графа можно посещать более одного раза и не обязательно возвращаться в исходную точку (если я правильно понял).
|
0 пользователей читают эту тему (0 гостей и 0 скрытых пользователей)
0 пользователей:
[ Script execution time: 0,0268 ] [ 15 queries used ] [ Generated: 20.04.24, 14:26 GMT ]