Форум программистов, компьютерный форум, киберфорум
Алгоритмы
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск  
 
 
Рейтинг 4.75/16: Рейтинг темы: голосов - 16, средняя оценка - 4.75
 Аватар для Taras_Z
102 / 86 / 5
Регистрация: 27.10.2010
Сообщений: 534
Записей в блоге: 2

Найти выход из лабиринта

25.03.2014, 17:01. Показов 4307. Ответов 41
Метки нет (Все метки)

Студворк — интернет-сервис помощи студентам
Как можно искать выход из лабиринта, который задается отрезками. То есть надо найти даже не выход, а можно ли добраться до выхода. Точка старта и финиша задаются координатами, также задаются координаты отрезков (стен) - начало и конец. Так как размеры могут быть достаточно велики, то рисовать попиксельно и искать путь не получится. Так как нужно ответить ли добраться до выхода, как это можно сделать?
Миниатюры
Найти выход из лабиринта  
0
Programming
Эксперт
39485 / 9562 / 3019
Регистрация: 12.04.2006
Сообщений: 41,671
Блог
25.03.2014, 17:01
Ответы с готовыми решениями:

Угадай, где выход! (Поиск листа бинарного дерева, содержащего выход из лабиринта)
Никогда раньше не решал задачи на деревья, но вот решил начать. Самая большая проблема в том, что я никак не могу понять примеры тестов...

Помогите с выбором алгоритма(найти все ходы на карте лабиринта)
Дана карта вида(задаётся любая в файле) S ***| нужно найти все всевозможные проходы **F | от старта(S) до финиша(F) и выдать * ...

Найти выход из лабиринта
Пожалуйста помогите решить. Перевод. Вопрос задачи: наити выход роботу из лабиринта. Робот проходит только через (.), а это (#)...

41
 Аватар для Taras_Z
102 / 86 / 5
Регистрация: 27.10.2010
Сообщений: 534
Записей в блоге: 2
26.03.2014, 16:25  [ТС]
Студворк — интернет-сервис помощи студентам
wingblack,
Цитата Сообщение от Taras_Z Посмотреть сообщение
Попробовал сначала сделать так, но возникла одна проблема:
Со старта мы добавим синюю точку в очередь, так как она является видимой. Когда дойдет очередь до ее рассмотрения, с этой точки, финиш будет видим, но мы не можем дойти к старту до финиша.
Извините, забыл приложить рисунок.
Миниатюры
Найти выход из лабиринта  
0
1980 / 836 / 115
Регистрация: 01.10.2012
Сообщений: 5,253
Записей в блоге: 2
26.03.2014, 17:08
Цитата Сообщение от wingblack Посмотреть сообщение
Метод правой руки не является универсальным. Про это много и везде говорили уже.
Вот вам лабиринт, пробуйте с помощью него пройти его.
Так надо было с этого рисунка и начинать Хорошо, пусть есть разорванные отрезки и.т.п. Тогда каждая точка отрезка/пересечения - вершина графа. Строим ребра как говорилось выше. Задача свелась к хорошо известной.
0
 Аватар для Taras_Z
102 / 86 / 5
Регистрация: 27.10.2010
Сообщений: 534
Записей в блоге: 2
26.03.2014, 17:34  [ТС]
Цитата Сообщение от Igor3D Посмотреть сообщение
Тогда каждая точка отрезка/пересечения - вершина графа. Строим ребра как говорилось выше.
Можно подробнее?
0
1980 / 836 / 115
Регистрация: 01.10.2012
Сообщений: 5,253
Записей в блоге: 2
26.03.2014, 18:30
Цитата Сообщение от Taras_Z Посмотреть сообщение
Можно подробнее?
Отрезок - 2 точки, каждая из них - вершина графа. Если отрезки пересекаются - разбиваем их в точках пересечения, они тоже становятся вершинами. Плюс начальная и конечная вершины. Начинаем с начальной, пытаемся создать ребра со всеми остальными. Если ребро пересекает хоть один отрезок - оно недопустимо. Или если пересекает контур - тоже недопустимо. В конце-концов получается обычный граф
0
 Аватар для Taras_Z
102 / 86 / 5
Регистрация: 27.10.2010
Сообщений: 534
Записей в блоге: 2
26.03.2014, 18:38  [ТС]
Цитата Сообщение от Igor3D Посмотреть сообщение
Или если пересекает контур - тоже недопустимо
Что есть "контур"?
Сработает ли оно на таком примере?
Изображения
 
0
294 / 265 / 48
Регистрация: 09.04.2013
Сообщений: 1,038
26.03.2014, 19:25
Цитата Сообщение от Taras_Z Посмотреть сообщение
Что есть "контур"?
Сработает ли оно на таком примере?
Да, этот момент не слишком ясен.
Из одной точки может исходить несколько отрезков. Возможно нужно знать взаимное расположение отрезков ("по кругу"). Видимость точки из исходной можно задать как угол между двумя отрезками, образующими сектор видимости (в котором мы пришли в исходную точку) и отрезком образованным исходной и рассматриваемой точкой, т.е. входит ли точка в такой сектор (например через скалярное произведение векторов).
0
 Аватар для Taras_Z
102 / 86 / 5
Регистрация: 27.10.2010
Сообщений: 534
Записей в блоге: 2
26.03.2014, 19:42  [ТС]
Цитата Сообщение от wingblack Посмотреть сообщение
Да, этот момент не слишком ясен.
Из одной точки может исходить несколько отрезков. Возможно нужно знать взаимное расположение отрезков ("по кругу"). Видимость точки из исходной можно задать как угол между двумя отрезками, образующими сектор видимости (в котором мы пришли в исходную точку) и отрезком образованным исходной и рассматриваемой точкой, т.е. входит ли точка в такой сектор (например через скалярное произведение векторов).
Можно подробнее на примере?
0
294 / 265 / 48
Регистрация: 09.04.2013
Сообщений: 1,038
27.03.2014, 00:22
Пусть мы пришли из точки S в точку D и из которой потом пойдем в точку F
Сначала нужно определить какие отрезки DC и DB ограничивают сектор обзора точки D. Если мы знаем очередность отрезков выходящих через точку (например, по часовой стрелке), то нужно найти такой отрезок DB у которого минимальный угол с DF, следующий отрезок DC выбирается из соображения что угол CDB должен быть больше чем угол CDF, а DC и DB являются соседними.
угол CDB задает сектор обзора точки D.
Видимость точки F аналогично определяется как углы CDF и BDF которые должны быть не больше чем угол CDB. Естественно, также должно выполняться условие что отрезки FD и SD не должны пересекаться с стенами.

Отдельный случай когда точка принадлежит только одному отрезку - тогда никаких этих проверок делать не надо (кроме пересечения с границей), ибо у неё обзор 360о
Миниатюры
Найти выход из лабиринта  
1
294 / 265 / 48
Регистрация: 09.04.2013
Сообщений: 1,038
27.03.2014, 00:25
Скалярное произведение векторов
https://www.cyberforum.ru/cgi-bin/latex.cgi?(a,b)=\left|a \right|\left|b \right|cos\alpha
(a,b)=x1x2 + y1y2

чем дальше тем триангуляция выглядит более элегантным решением.
0
1980 / 836 / 115
Регистрация: 01.10.2012
Сообщений: 5,253
Записей в блоге: 2
27.03.2014, 14:36
Цитата Сообщение от Taras_Z Посмотреть сообщение
Что есть "контур"?
Сработает ли оно на таком примере?
Да, потому что известно "откуда пришли". Если точка "висит в воздухе" (отрезок не соединен), то можно идти куда угодно. Иначе проверяемся по углам образованным вектором пути и прилегающими к точке отрезками. Модуль углов находите скалярным произведением, знак - векторным.

Цитата Сообщение от wingblack Посмотреть сообщение
чем дальше тем триангуляция выглядит более элегантным решением.
Триангуляция всегда большой геморрой. Да и не вижу что она здесь дает
0
294 / 265 / 48
Регистрация: 09.04.2013
Сообщений: 1,038
27.03.2014, 15:16
Цитата Сообщение от Igor3D Посмотреть сообщение
Триангуляция всегда большой геморрой. Да и не вижу что она здесь дает
Возможно и сложнее, но не надо ничего выдумывать. А дает это то что от треугольников проще перейти к графу, а уж по нему найти путь проще.
0
1980 / 836 / 115
Регистрация: 01.10.2012
Сообщений: 5,253
Записей в блоге: 2
27.03.2014, 17:45
Цитата Сообщение от wingblack Посмотреть сообщение
А дает это то что от треугольников проще перейти к графу
Как бы не наоборот, ведь после триангуляции сторона треугольника еще не есть ребро графа.
0
 Аватар для Taras_Z
102 / 86 / 5
Регистрация: 27.10.2010
Сообщений: 534
Записей в блоге: 2
27.03.2014, 17:51  [ТС]
Я здесь придумал другой алгоритм:
1. Ищем любую точку, чтобы отрезок, соединяющий начальную и конечную точки не пересекался с другими.
2. С той точки обходим многоугольник по правилу правой руки.
3. Когда обошли полностью, то смотрим: Если точка старта или точка финиша не лежат в нем, то стираем все стороны многоугольника, не принадлежащих другим многоугольникам.
4. пока есть точки см. пункт 1
0
294 / 265 / 48
Регистрация: 09.04.2013
Сообщений: 1,038
27.03.2014, 23:38
Цитата Сообщение от Taras_Z Посмотреть сообщение
Я здесь придумал другой алгоритм:
1. Ищем любую точку, чтобы отрезок, соединяющий начальную и конечную точки не пересекался с другими.
2. С той точки обходим многоугольник по правилу правой руки.
3. Когда обошли полностью, то смотрим: Если точка старта или точка финиша не лежат в нем, то стираем все стороны многоугольника, не принадлежащих другим многоугольникам.
4. пока есть точки см. пункт 1
глобально убирать границы не надо, а то ложные проходы будут.
в таком алгоритме предварительно нужно соединить финиш и старт отрезками с одной из видимых точек

Добавлено через 19 минут
и не понятно как мы выбираем точки в (1)
хотелось бы более конкретные формулировки
0
 Аватар для Taras_Z
102 / 86 / 5
Регистрация: 27.10.2010
Сообщений: 534
Записей в блоге: 2
28.03.2014, 12:16  [ТС]
В (1) выбираем любую видимую точку с начальной вершины.

Добавлено через 2 часа 1 минуту
Цитата Сообщение от wingblack Посмотреть сообщение
убирать границы не надо, а то ложные проходы будут
Надо
0
294 / 265 / 48
Регистрация: 09.04.2013
Сообщений: 1,038
28.03.2014, 13:11
Цитата Сообщение от Taras_Z Посмотреть сообщение
Надо
Вот ваше же сообщение с картинкой Найти выход из лабиринта

Один раз прошли по многоугольнику и убрали его, теперь между стартом и финишем есть проход, которого быть не должно.
0
 Аватар для Taras_Z
102 / 86 / 5
Регистрация: 27.10.2010
Сообщений: 534
Записей в блоге: 2
28.03.2014, 13:35  [ТС]
wingblack,
Цитата Сообщение от Taras_Z Посмотреть сообщение
то стираем все стороны многоугольника, не принадлежащих другим многоугольникам.
Стираем только те стороны, которые не принадлежат другим многоугольникам.
0
294 / 265 / 48
Регистрация: 09.04.2013
Сообщений: 1,038
28.03.2014, 14:19
Тут я нашел упоминание алгоритма, который сначала ищет все тупики и убирает их из рассмотрения (страницу уже закрыл, а название не запомнил) Возможно его сюда тоже можно внести.

Если придумать как отойти от привязки к координатам, то можно удалить все лишние отрезки а то и многоугольники.

Если предположить что финиши и старт находятся внутри многоугольника, то первым делом можно безболезненно рекурсивно удалить все точки принадлежащие только одному отрезку (вместе с отрезком)
0
 Аватар для Taras_Z
102 / 86 / 5
Регистрация: 27.10.2010
Сообщений: 534
Записей в блоге: 2
28.03.2014, 14:36  [ТС]
Цитата Сообщение от wingblack Посмотреть сообщение
Тут я нашел упоминание алгоритма, который сначала ищет все тупики и убирает их из рассмотрения (страницу уже закрыл, а название не запомнил) Возможно его сюда тоже можно внести.
В историю браузера загляни.
Мой алгоритм правильный?
0
1980 / 836 / 115
Регистрация: 01.10.2012
Сообщений: 5,253
Записей в блоге: 2
28.03.2014, 15:35
Цитата Сообщение от Taras_Z Посмотреть сообщение
Я здесь придумал другой алгоритм:
1. Ищем любую точку, чтобы отрезок, соединяющий начальную и конечную точки не пересекался с другими.
2. С той точки обходим многоугольник по правилу правой руки.
3. Когда обошли полностью, то смотрим: Если точка старта или точка финиша не лежат в нем, то стираем все стороны многоугольника, не принадлежащих другим многоугольникам.
4. пока есть точки см. пункт 1
Отрезок пересекает квадрат ABCD на 2 сторонах ВC и CD. Точка А удовлетворяет условию "1". Обошли ABCD, точки в нем не лежат, удаляем и.. ничего не осталось
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
inter-admin
Эксперт
29715 / 6470 / 2152
Регистрация: 06.03.2009
Сообщений: 28,500
Блог
28.03.2014, 15:35

Найти выход из лабиринта, прочертив весь путь
Здравствуйте.Идея такая.Есть dmp рисунок.на нем нарисован лабиринт(ну как в журналах детские странички) как програмно просчитывая пиксели...

Составить программу, которая позволяет игроку найти выход из лабиринта
Составить программу, которая позволяет игроку найти выход из лабиринта. Условия: 1) пусть прямоугольное клеточное поле (размером NxN,...

Выход из лабиринта
Дан лабиринт M: array of boolean; (true - стена false - свободно) Начало в верхнем левом угле Конец в нижнем правом угле ...

Выход из лабиринта
Всем привет, возник вопрос по поводу лабиринта. Посмотрев форум не нашел такого же задания. Суть - написать программу, с помощью которой...

Выход из лабиринта
Помогите допилить.Нужен алгоритм нахождения выхода и лабиринта.За ранее спасибо! Вот сам лабиринт: uses GraphABC; const ...


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

Или воспользуйтесь поиском по форуму:
40
Ответ Создать тему
Новые блоги и статьи
Транслитерация текста с кириллицы на латиницу (вариант №5)
Maks 17.11.2026
Дабы оставить позади все споры о том, какая буква каким образом должна транслитерироваться на латиницу - решил таки доработать данное решение и довести его до мало-мальски логического завершения. . . .
Просмотровщик HLP и конвертер в CHM
Argus19 16.11.2026
Просмотровщик HLP и конвертер в CHM Давно хотел переделать справку Microsoft® Win32® Programmer's Reference, чтобы иметь её под рукой. Но использовать несколько программ не удобно. Искал другие. . .
BitTorrent (версия 7.11 English) и Меню Настройки
russiannick 15.11.2026
Пункты, отвечающие за отключение обновлений в BitTorrent версии 7. 11 (английской) Options Preferences General Language
Транслитерация текста с кириллицы на латиницу (вариант №4)
Maks 15.11.2026
Что-то я перемудрил с предыдущими версиями, в этот раз сделал всё проще, обратившись к функции "СтрокаЛатиницей" из типового общего модуля "СтроковыеФункцииКлиент". В данной функции нет апострофов,. . .
BitTorrent (версия 4.3.9) и Меню Настройки
russiannick 15.11.2026
В меню Настройки можно отключить автоматическое обновление программы. Карта этого меню приложена ниже. Нужный пункт выделен красным. Сервис Настройки Поведение
Транслитерация текста с кириллицы на латиницу (вариант №3)
Maks 15.11.2026
Обновленная версия предыдущей обработки. Изменения коснулись букв: Ъ, Ы, Ь, Э, отображения которых зависят от положения реквизита "Транслитерация имён". Изменено отображение буквы Й. Добавлена. . .
Транслитерация текста с кириллицы на латиницу (вариант №2)
Maks 13.11.2026
Обновленная версия ранее созданной обработки. Добавлено: - Проверка исходного текста на кириллицу, через обращение к стандартной функции "ТолькоКириллицаВСтроке" из общего модуля. . .
Часы с термометром и праздничным календарем
yariko 12.11.2026
Сегодня мы рассмотрим как можно сделать отличные многофункциональные часы. Итак, поставим конкретную задачу: разработать часы с календарем, двумя термодатчиками, выводом поздравительных сообщений. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru