Привет, Хабр!
Прошел ровно год с момента публикации разбора задачи про красные и синие точки, и вот я снова нашел время, разобрать ещё одну увлекательную задачу. Надеюсь, вам понравится!
Задача
Дан связный прямоугольный лабиринт клеток, одна из которых обозначена как выход. В произвольной клетке появляется черепаха, и она может перемещаться в четырех направлениях (вверх, вправо, вниз, влево).
Черепаха не мыслит логически, однако имеет безупречную память. Она может запомнить и выполнить любую конечную последовательность команд. Черепаха не может перемещаться сквозь стенки лабиринта, и поэтому просто игнорирует команду, если не может ее исполнить и переходит к следующей.
Как только черепаха оказывается в клетке "выход", она тут же выходит из лабиринта и больше не исполняет никакие команды.
Расположение стенок лабиринта и клетки "выход" известны заранее, а вот начальное расположение черепахи неизвестно.
Помогите черепахе выбраться из лабиринта. Напишите конечную последовательность команд (up, right, down, left), которая гарантирует ей выход независимо от ее начального местонахождения.
Например, для черепахи изображенной на рис. 1 подойдет последовательность: down, left, left, up, right, up, up, up, up, left, down, left, up. Однако, легко убедиться, что данная последовательность не подойдет, если начальное положение черепахи будет передвинуто, например, в нижний левый угол.
Вы не знаете начальное расположение черепахи. Ваша последовательность команд должна быть универсальной, то есть, выводить черепашку из лабиринта независимо от ее начальной позиции.
Вам на вход дается лабиринт с клеткой "выход". Гарантируется, что лабиринт связный: от любой клетки возможно дойти до любой другой.
Придумайте алгоритм, который по лабиринту строит универсальную последовательность команд для черепахи.
Решение
Первая попытка решить
Давайте для каждой клетки составим маршрут, приводящий черепаху к выходу. Поскольку клеток, в которых может находиться черепаха конечное число, а именно , то просто выпишем все такие маршруты и будем перебирать их в любом порядке.
Если черепаха прошла по маршруту и не нашла выход, то продолжим перебирать варианты, предварительно вернувшись на исходную позицию, отменив команды справа налево. Например, для маршрута right, up, left сначала отменим третье действие - выполним right, затем второе - выполним down, затем первое - выполним left. Таким образом получим новую последовательность right, down, left.
Все классно, да? Но есть одно но.
Рассмотрим черепашку на рис. 2. Пусть у нее была последовательность, состоящая из одной единственной команды right. В этом случае, черепашка упрется в стенку справа, поэтому ничего не сделает. Однако, если мы попытаемся отменить данную операцию, то мы должны будем попросить черепаху пойти влево (выполнить left), что приведет ее совсем не туда, откуда она начинала.
Таким образом, мы на самом деле не умеем отменять ходы и возвращать черепаху на исходную позицию, что ломает нам нашу первую попытку и мы терпим неудачу.
Работа над ошибками
В первой попытке мы все же поняли кое-что важное: для каждой клетки лабиринта можно выписать путь к выходу.
Давайте просто выберем одну произвольную клетку и напишем последовательность команд, выводящую черепашку к выходу из нее. Если черепашка в самом деле оказалась в данной клетке, то нам повезло и делать больше ничего не требуется. Кстати, даже если черепашка начинала из другой клетки, префикс нашей последовательности мог привести ее к выходу, что только лучше.
Однако, если чуда не случилось, то черепаха сейчас все еще находится где-то в лабиринте. Но, где именно она может находиться?
На самом деле вариантов не так много, как кажется на первый взгляд. Изначально черепаха находилась в одной из клеток, но проделав данный маршрут она могла перейти в одну из
клеток, если не вышла. Таким образом, количество вариантов нового расположения как минимум на 1 меньше, чем было изначально.
На рисунке 3 изображено, что примерно произошло в терминах теории множеств. Слева - множество клеток до выполнения набора команд, справа - после. Синими точками обозначены клетки, в которых теоретически может находиться черепаха. Как можно видеть, за счет того, что как минимум одна синяя точка (клетка) гарантированно переходит в клетку "выход", справа появится как минимум одна белая точка (клетка, в которую нас никогда не приведет данная последовательность команд).
На этом этапе вы, возможно, уже догадались, к чему я клоню :)
На следующем шаге мы выберем любую другую синюю точку (клетку с черепахой) и построим от нее маршрут до выхода. Пройдя по маршруту, количество возможных для черепахи клеток опять уменьшится хотя бы на одну. Будем продолжать в том же духе, пока синие клетки не закончатся совсем. Всего нам потребуется не более таких итераций, чтобы успешно завершить процесс и гарантированно вывести черепаху на свободу, пока та не померла с голоду.
Любопытный факт: черепахи могут голодать по несколько месяцев. Их организм приспособлен к таким условиям благодаря медленному метаболизму :)
Заключение
Спасибо, что дочитали до конца. Если вам понравилось, нажмите стрелочку вверх, это действительно мотивирует меня продолжать делиться с вами интересными задачами и их разборами.
Комментарии (201)
ParaMara
20.06.2024 04:14+1Ещё когда меня учили теории вероятности, услышал от препода «к сожалению, большинство интересных множеств не измеримы, а большинство измеримых - не интересны». Вот так, «к сожалению», но это нисколько не мешает продолжать развивать теорию в том же направлении.
Встречал выдающегося советского математика который перед окончательным включением человека в круг профессионального общения проводил собеседование и подробно выяснял всю историю жизни лет с 14. И мог отказать без объяснения причин. Ему, а так объяснял что вывел из опыта - если человек хотя бы однажды выполнял работу на которой видел конкретные результаты своего труда, то для математики он потерян, независимо от способностей к таковой.
Такие они, математики.
В данном случае решение задачи предполагает что у черепахи есть компас, что делает его «математическим», то есть практически бесполезным.
Зная математиков, замечу, что от не «популяризатора», в просторечии шарлатана, скорее всего услышал бы изложение того же самого на таком, обычно максимальном, уровне абстракции где нет ни лабиринта ни черепахи, но зато появляется возможность применения.
kipar
20.06.2024 04:14+2если компаса нет, то надо после решения для одной ориентации продолжать выполнять шаги еще для трех вариантов повернутого лабиринта.
serginho
20.06.2024 04:14Проделав один из маршрутов, черепаха может прийти в клетку, маршрут для которой вы уже проходили. Так что нет уверенности, что ваше решение рабочее
ruomserg
20.06.2024 04:14+2Поправьте меня - но я понял решение автора так:
Выбираем любую клетку в лабиринте (для определенности А1) и строим путь к выходу.
Если черепаху заспаунит в А1, то после выполнения этой программы она будет на свободе
Если после выполнения этой программы черепаха не на свободе, то она заспаунилась в какой-то другой клетке кроме A1.
Запускаем нашу программу написанную для A1 для всех других произвольных клеток лабиринта и отмечаем, куда мы попали. Автор утверждает что при этом образуется хотя бы одна клетка в лабиринте, в которую мы НЕ попадем ни из какой другой.
Таким образом, размер лабиринта (даже если мы из него не вышли чисто по прихоти теории вероятности) уменьшился на 1 клетку, и мы можем решить задачу заново, присоединив получившуюся программу к полученной в предыдущем шаге. Проделав это m*n-1 раз - мы получим программу, которая выводит черепаху из любой точки лабиринта.
Мое возражение сводится к тому, что никто не ограждает нам физическими стенками точку в которую мы не смогли попасть исполняя программу "A1" - и поэтому выкидывать ее из лабиринта неправильно. Если только черепаха не умеет понимать что она уже была в этой точке (и активировать программу ассоциированную с ней), то нет никакой гарантии, что более поздняя программа "Б2", будучи выполнена из неправильной локации - не приведет нас в "белую точку" А1, образовав цикл. Более того, на m*n-1 шаге алгоритма у нас есть ровно один шанс выйти из лабиринта, и все остальные шансы попасть в точку которую мы считаем "белой"... Нужна пояснительная бригада от автора.
kipar
20.06.2024 04:14+1Как я понял, на первом шаге будет как минимум одна белая клетка (та из которой начали). На втором шаге получится минимум две белые клетки, но они не будут совпадать с белой клеткой на предыдущем шаге, просто их всегда хотя бы на 1 меньше чем на предыдущем шаге. Ну и на последнем шаге у нас останется одна синяя клетка (которая вполне может скажем совпадать с той из которой мы начинали) и мы просто допишем последовательность для неё.
ruomserg
20.06.2024 04:14+2Ну да, в этом и суть. Автор считает что метод работает по-индукции, и на каждом шаге белых точек становится больше. Но поскольку см. выше - никто эти белые точки стенками не ограждает и они существуют только мысленно - не получится ли что на втором шаге алгоритма у нас вместо двух белых точек - только одна ?...
kipar
20.06.2024 04:14+1на втором шаге у нас было m*n-1 стартовых клеток, как минимум одна из них в итоге вышла из лабиринта. Так что m*n-1 синих получится никак не может.
ruomserg
20.06.2024 04:14Это нетривиальное утверждение - у меня пока не получается ни доказать его в общем случае, ни найти контр-пример. Доказательство автора из теории множеств пока не убеждает по причине см. выше: реальный лабиринт не уменьшается от того, что мы нашли точку в которую не смогли бы попасть из любой другой выполнив программу первого шага.
demitryy Автор
20.06.2024 04:14Можете представить, что у вас во всех синих клетках одновременно сидят черепахи и вы хотите выпустить их всех. Тогда изначально у вас n*m-1 черепах. После первой итерации как минимум одна черепаха выйдет как только встанет на клетку "выход", количество черепах в лабиринте гарантированно уменьшится.
ruomserg
20.06.2024 04:14+1Этот первый шаг сомнений не вызывает. Если мы выполнили программу "X" верную для клетки А1, но не вышли из лабиринта - то мы теперь точно не находимся в А1. Теперь мы предполагаем что оказались в клетке "Б2" и выполняем программу "Y" рассчитанную для выхода из этой точки. И вот дальше идет тонкое предположение - что в итоге мы окажемся и не в точке А1 (потому что на втором шаге мы рассматриваем лабиринт без А1) и не в Б2 - потому что мы выполнили программу верную для этой точки, но игра не кончилась. Однако, выполняя программу Y для Б2 - мы можем вновь оказаться в А1, и поэтому после очередного шага размерность лабиринта сохранится m*n-2, и уменьшаться уже не будет.
Однако и это утверждение "размерность сохранится" мне тоже не нравится - потому что это означает возможность бесконечного блуждания в полносвязном лабиринте при сколь угодно длинной и разнообразной программе. Что тоже контр-интуитивно (и скорее всего, неверно).
demitryy Автор
20.06.2024 04:14Этот первый шаг сомнений не вызывает. Если мы выполнили программу "X" верную для клетки А1, но не вышли из лабиринта - то мы теперь точно не находимся в А1.
Это утверждение не верно. Представьте лабиринт
, выход в крайней правой клетке. После выполнения right мы освободим черепаху из центра, но черепаха с крайней левой клетки перейдет в центр. Поэтому следующая команда будет снова right.ruomserg
20.06.2024 04:14Ну да, согласен - у автора хитрее. Выполнив программу из А1 и не попав к выходу - мы выполняем ту же самую программу "X" для всех остальных клеток лабиринта, и гарантированно находим хотя бы одну клетку "~A1", в которой мы не можем оказаться. Дальше мы выбираем клетку Б2, и повторяем процесс - получая после двух шагов множество (~A1,~Б2) из двух клеток в которых мы не можем оказаться. Но опять-таки второй переход - что множество будет состоять из двух клеток а не только из (~Б2) - мне кажется сомнительным.
demitryy Автор
20.06.2024 04:14+3В интерпретации, где вы управляете сразу n*m-1 черепахами у вас после каждой итерации будет исчезать (выходить из лабиринта) как минимум одна черепаха. Рано или поздно черепахи закончатся.
ruomserg
20.06.2024 04:14+1Не доказана эквивалентность задачи с одной черепахой задаче с многими черепахами...
demitryy Автор
20.06.2024 04:14Если вы придумали последовательность команд, которая будет освобождать n*m-1 черепах, занимающих все поле, то та же последовательность будет работать и для любой отдельной из черепах.
Batalmv
20.06.2024 04:14Так не работает
Метод мат индукции, который вы неявно применяете, как требует доказать, что переход N->N+1 возможен
А так ... вы просто постулируете, что он возможен и получаете "доказательство"
wataru
20.06.2024 04:14Индукция нужна, когда у вас бесконечная счетная последовательость. Если у вас конечное количество вариантов, то индукция не нужна.
Batalmv
20.06.2024 04:14Счетное - не значит что вы лично можете это подсчитать. Классика - на первую клетку одне зернышко, на вторую - да, и так до 64й
Суть в принципе, метод работает на бесконечной последовательности, значит и на конечной тоже
Но вот попытки постулировать верность N->N-1 просто так, а потом доказывать основное утверждение вызывают ... ну вы поняли
wataru
20.06.2024 04:14Очевидно же. Решение выводит черепаху с любой начальной точки - значит выводит всех черепах из лабиринта. Ведь можно просто проигнорировать всех черепах, кроме одной. Она выходит, потому что начинает в любой точке. И так для всех черепах. С другой стороны, алгоритм, который выведет всех черепах, выведет черепаху с любой начальной точки (опять же, игнорируем мысленно всех черепах, кроме одной. Она выходит, ведь она одна из всех)
Batalmv
20.06.2024 04:14После выполнения right мы освободим черепаху из центра, но черепаха с крайней левой клетки перейдет в центр. Поэтому следующая команда будет снова right.
Так у вас черепашка без памяти, с чего она знает это?
wataru
20.06.2024 04:14+1Память есть у составителя алгоритма же. Он записал в ответ путь для центральной черепахи. Посмотрел, где окажутся остальные после выполнения уже записанного алгоритма, приписал часть. чтобы следующую черепаху вывести, и так далее.
Batalmv
20.06.2024 04:14Вам на вход дается лабиринт с клеткой "выход". Гарантируется, что лабиринт связный: от любой клетки возможно дойти до любой другой.
Придумайте алгоритм, который по лабиринту строит универсальную последовательность команд для черепахи.
Читаем условие вместе. Это финальна постановка задачи. Надо АЛГОРИТМ, ОДНА ШТУКА
Доп. условия
Черепаха не может перемещаться сквозь стенки лабиринта, и поэтому просто игнорирует команду, если не может ее исполнить и переходит к следующей.
Т.е. обратной связи нет
Вы не знаете начальное расположение черепахи. Ваша последовательность команд должна быть универсальной, то есть, выводить черепашку из лабиринта независимо от ее начальной позиции
Вот место, где легко доказывается, что надо по сути просто обойти все клетки
Если вам не понравилось мое объяснение из другого комментария - вот еще одно. Если строить путь назад, то получается как раз и выбранной клетки в любые. Так как надо поддерживать ВСЕ стартовые позиции, значит их всех надо обойти
Надеюсь очевидно, что маршрут имеет обратную функцию?
Поэтому задача эквивалентна задаче обхода всех клеток. Без памяти, без обратной связи, с произвольной конфигурацией стенок.
--------------------------------
Он записал в ответ путь для центральной черепахи. Посмотрел, где окажутся остальные после выполнения уже записанного алгоритма, приписал часть. чтобы следующую черепаху вывести, и так далее.
Вы можете смореть на все что угодно, но если речь идет о данной задаче, то автор просит дать УНИВЕРСАЛЬНЫЙ алгоритм, имея на вход описание алгорима и координаты выхода
Поэтому смотреть будет не автор, а алгоритм :) А по условиям можно лишь двигать черепахой
-------------------------
Если уж совсем погружаться в теорию, от у нас имеет место быть классчическая машина Тьюрига, четыре возможных значения, и НЕТ СОСТОЯНИЯ
Точнее как раз не классическая, иначе б все было понятно, а обрезанная по возможностям
Моделировать ее аналог я в комменарии не буду, вы уж извините, так как без "состояния машины" и так понятно, что упражнение не имеет смысла.
Да и я уже не студент, программирование на такого рода моделях уже чуток в прошлом
Zara6502
20.06.2024 04:14Поэтому смотреть будет не автор, а алгоритм :) А по условиям можно лишь двигать черепахой
я так и понял эту задачу, но прочитав эту ветку обсуждения полез внимательно перечитывать статью и оказывается совсем не нужен универсальный алгоритм, вам, как наблюдателю дают лабиринт без черепахи и просят составить такой набор команд, который гарантированно выведет черепаху где бы она не появилась.
wataru
20.06.2024 04:14А универсальный точно также составляется. Надо только выписать все лабиринты (их конечное число). Потом берем любую клетку в любом лабиринте и выводим ее из него. При этом все клетки во всех лабиринтах сдвигаем согласно этому же алгоритму. Повторяем, пока все клетки не выведем.
Batalmv
20.06.2024 04:14Hу тогда ошибка еще более очевидна
Давайте просто выберем одну произвольную клетку и напишем последовательность команд, выводящую черепашку к выходу из нее. Если черепашка в самом деле оказалась в данной клетке, то нам повезло и делать больше ничего не требуется. Кстати, даже если черепашка начинала из другой клетки, префикс нашей последовательности мог привести ее к выходу, что только лучше.
Однако, если чуда не случилось, то черепаха сейчас все еще находится где-то в лабиринте. Но, где именно она может находиться?
На самом деле вариантов не так много, как кажется на первый взгляд. Изначально черепаха находилась в одной из
клеток, но проделав данный маршрут она могла перейти в одну из 
клеток, если не вышла. Простой пример. Я произвольно (я имею право) выбираю клетку под клеткой выход (на картинке). Теперь по предложенному способу наша послебовательность up. :)
А где оказалась наша черепашка? Ха-ха. Она там же где и стоит и из "из
к" мы не перешли никуда и остались там жеВсе, алгоритм опрвергнут
demitryy Автор
20.06.2024 04:14Простой пример. Я произвольно (я имею право) выбираю клетку под клеткой выход (на картинке). Теперь по предложенному способу наша послебовательность up. :)
Тогда прямо под клеткой выход появится пустая клетка (где точно не может быть черепахи). Более того, весь нижний ряд можно считать теперь пустыми клетками, если хотите. Число пустых клеток увеличилось. Теперь проделаем так с оставшимися непустыми клетками, при этом будем следить куда клетки переходят. Важно, что число пустых клеток будет строго монотонно расти от итерации к итерации.
Batalmv
20.06.2024 04:14Тогда прямо под клеткой выход появится пустая клетка (где точно не может быть черепахи).
Как это знание помогает создать алгоритм? Тем более черепашка может иметь любую стартовую позицию.
Я просто указал место в алгоритме, которое элеменарно опровергается, как минимум так, как оно написано
С чем спорим?
Выдаейте полный свой и поговорим
Zara6502
20.06.2024 04:14предлагаю посмотреть на моё решение, так как авторское для моего восприятия слишком "странное" и на мой взгляд усложнённое.
https://habr.com/ru/articles/823066/comments/#comment_26955316
Mingun
20.06.2024 04:14Алгоритм универсальный. Смотрите. У нас есть лабиринт, в нём
клеток, в которых может находиться черепаха, для удобства произвольным образом пронумеруем такие клетки от 
до 
. Теперь попытаемся построить алгоритм для вывода черепахи с клетки . Эта будет некоторая последовательность шагов, которая гарантированно существует, так как лабиринт полносвязный по условиям задачи.Применим эту последовательность шагов независимо ко всем
клеткам лабиринта и после окончания запомним, какие клетки остались заняты черепахами. По построению, черепаха с клетки из лабиринта выйдет. Черепахи с других клеток могут как выйти из лабиринта, так и остаться в нём. В любом случае, количество черепах, которых надо вывести, уменьшится, как минимум, на одну — а значит, и количество занятых клеток тоже.А теперь повторяем алгоритм для новых занятых клеток (на предыдущей итерации мы как раз составили такой список). Это в том числе может снова оказаться клетка
! Поскольку на каждой итерации количество занятых клеток уменьшается, в конечном итоге их не останется вовсе и алгоритм завершится.После каждой итерации мы приписываем полученную последовательность шагов для вывода черепахи с рассматриваемой на этой итерации клетки к общей последовательности шагов (которая изначально пуста). В конце алгоритма у нас будет последовательность шагов, которая гарантированно выведет черепашку с любой клетки лабиринта. Черепахе при этом не надо ни знать конфигурацию лабиринта, ни помнить, какие клетки она посещала, а какие нет, а просто выполнять шаги. Пройдя их все до конца, она окажется на свободе.
В вырожденном случае каждая итерация вывода черепашки с клетки
будет приводить в эту клетку другую черепашку, которую мы снова будем выводить из лабиринта (вновь и вновь применяя алгоритм для вывода черепашки из клетки ) и так до тех пор, пока не выведем их всех.Пример такого вырожденного случая — лабиринт из одной строки вида:
в . . . .(в— выход,.— возможное положение черепашки). Если мы пронумеруем клетки так:1 2 3 4 в . . . .и начнём выводить черепашку с клетки
, нам понадобится алгоритм из одной команды влево. При этом клетка снова окажется занята, но общее количество черепашек для вывода уменьшится с 4 до 3. Поэтому повторив итерации по выводу черепах 4 раза мы получим универсальный алгоритм вывода черепашек с любой клетки лабиринта: влево влево влево влево.
Mingun
20.06.2024 04:14Вот это утверждение неверно:
Однако, выполняя программу Y для Б2 - мы можем вновь оказаться в А1
поскольку программа Y специально составлена так, что бы привести черепашку из точки Б2 к выходу, а следовательно, при начале из Б2 в точке А1 оказаться нельзя.
Batalmv
20.06.2024 04:14Нашел это комменарий
Сморите, так как стартовая позиция произвольно, то вам надо вывести ВСЕХ черепашек :) Потому что если хоть одна останется - вот и есть стартовая позиция, где ваш алгоритм не сработает
И да, на первом шаге первая упала. Но на втором шаге этого уже может не произойти
-----------
Поэтому вам надо доказать, что в результате КАЖДОЙ итерации количество черепашек уменьшается
wataru
20.06.2024 04:14+1Это не важно. Важно, что множество возможных клеток, где черепаха может быть, уменьшается на один. Изначально это все клетки. Брем любую, переводим ее в выход из лабиринта. Все остальные клетки переедут куда-то. Но, этих концов будет не больше, чем всех остальных клеток. Вот у нас уже и остается nm-1 начальных вариантов. Может среди них есть та клетка, которую мы уже перевели в выход. Не страшно, повторим те же ходы, опять уменшив количество возможных положений черепахи.
Zara6502
20.06.2024 04:14не понял вашего решения, ведь у вас нет обратной связи, а значит нет возможности определить в какой точек вы находитесь, ну и заданный маршрут должен быть задан до старта, как вы собираетесь считывать синие точки и реагировать пост-фактум?
demitryy Автор
20.06.2024 04:14Как только черепаха наступит на клетку "выход", она обретет свободу, независимо от следующих команд. Поскольку структура лабиринта известна заранее, можно вычислить все маршруты и для каждой клетки S найти клетку T = route(S), в которую он ведет. Обратная связь от черепахи нигде не используется.
Zara6502
20.06.2024 04:14ну так и вопрос в том - как найти тот самый универсальный маршрут? Если вы просто будете наугад что-то выбирать вы легко можете попасть в петлю и черепаха будет бегать вечно, ну или до окончания списка команд, например
ССС.ССС С.....С СССССССС - стены, точка - пустая клетка.
Вы запросто будете ходить по второй полосе справа налево и обратно если у вас в командах нет "направо, направо, вверх" или "налево, налево, вверх" при соответствующем положении черепахи. Любые другие команды тут ничего делать не будут.
Mingun
20.06.2024 04:14Давайте пронумеруем ваш лабиринт от 0 до 6 слева-направо и от 0 до 2 сверху вниз:
(0,0) ... (6,0) (0,1) ... (6,1) (0,2) ... (6,2)Предположим, что выход в первой строке (похоже, вы на это намекаете), ее координата
(3,0). Тогда такой список команд выведет черепаху из любой точки:вверх (последняя команда для черепахи в
(3,1), т.е. сразу под выходом)направо (
->)вверх (последняя команда для черепахи в
(2,1), т.е. под выходом и на одну клетку левее. Первую команду "вверх" она проигнорирует, вторая ("направо") переведет ее в позицию первой черепахи, для которой мы уже знаем, как найти выход)направо (
->)вверх (последняя команда для черепахи в
(1,1))налево (
<-)налево (
<-)вверх (последняя команда для черепах справа от выхода. Ранее черепаха в
(5,1)игнорировала все команды вверх и направо, т.к. у нее там стенки, а черепаха в(4,1)сдвинулась один раз вправо и уперлась в стенку. В любом случае, первую команду "влево" обе черепахи встречают на позиции(5,1). Из этой позиции нужно дважды пойти влево и один раз вверх, чтобы выйти из лабиринта)
Вообще, возможно эту задачу будет проще решать, если представить себе, что черепаха стоит на месте, а движется сам лабиринт. Иногда черепаха остается на своей позиции, а иногда ее сдвигает стенкой. Цель -- надвинуть клетку выхода на черепаху
Zara6502
20.06.2024 04:14если что я не согласен с тезисом о том, что каждый новый маршрут уменьшает лабиринт на 1. Так как без обратной связи у вас нет гарантии что каждый последующий маршрут не приводит вас в предыдущую точку.
demitryy Автор
20.06.2024 04:14+1У нас уменьшается количество клеток, где может располагаться черепаха, а не сам лабиринт.
у вас нет гарантии что каждый последующий маршрут не приводит вас в предыдущую точку
Верно, но мы нигде это не используем
Zara6502
20.06.2024 04:14Так в чем решение? Как именно формировать универсальный маршрут? Вы построите nm-1 маршрутов и как вы предлагаете их объединить? Я лишь вижу описание способа уменьшения числа итераций за счёт исключения клеток, откуда маршрут уже был построен (то есть уменьшение лабиринта на 1, хотя вы так не считаете). Но это очевидная оптимизация, только у вас задача не решена.
wataru
20.06.2024 04:14Я в соседней ветке формализовал алгоритм. С формальным доказательством. https://habr.com/ru/articles/823066/comments/#comment_26955100
Zara6502
20.06.2024 04:14пардон, но я ничего не понял
wataru
20.06.2024 04:14Неужели, ни одно слово непонятно?
Соствляем шаги, чтобы первую клетку вывести из лабиринта (часть 1) Потом добавляем туда шаги (часть 2) так, чтобы вторая клетка вышла из лабиринта после преминения обеих частей. Потом добавляем третью часть алгоритма, так, чтобы третья клетка вышла из лабиринта после исполнения часть1+часть2+часть3. И т.д. Всего N-1 часть для всех N-1 клетки.
Zara6502
20.06.2024 04:14так алгоритм где? )
вот мое решение https://habr.com/ru/articles/823066/comments/#comment_26955316
wataru
20.06.2024 04:14Вон в той ветке формально Определен. G_{N-1}.
Zara6502
20.06.2024 04:14и как им пользоваться? что мне даст G_{N-1} ? куда координаты подставлять? я вас не понимаю.
wataru
20.06.2024 04:14G_{N-1} - это последовательность действий черепашки.
Если вам нужен "алгоритм", который по лабиринту выдает последовательность ходов, то он там расписан. В цикле строим эту последовательность из G, вернее дописываем к G новую часть. Надо только уметь строить последовательность ходов F_x для известного x - ну это каким-нибудь BFS из конечной точки постройте все кратчайшие пути до нее, а потом эти пути приписывайте к ответу. Еще надо уметь применять путь к заданной клетке.
Zara6502
20.06.2024 04:14пардон, но видимо не для моего ума, я понимаю только так как я сам написал ниже.
demitryy Автор
20.06.2024 04:14Я лишь вижу описание способа уменьшения числа итераций за счёт исключения клеток, откуда маршрут уже был построен
См. рис. 3.
На нем показано, что освободившаяся (белая) клетка не обязательно та, из которой маршрут был построен. Но одна клетка гарантированно станет белой, т.к. число стрелочек ведущих из левого кружочка в правый n*m - 2 (т.к. минимум одну стрелочку мы потратили на зеленый кружок).
Zara6502
20.06.2024 04:14я прекрасно понимаю что происходит, я не вижу вашего способа решения этой задачи. пусть за константу возьмём я что я туп, но решение же есть в тексте, процитируйте пожалуйста. то что одна клетка освободится это очевидно, но это же не решение.
demitryy Автор
20.06.2024 04:14то что одна клетка освободится это очевидно, но это же не решение
Минимум одна клетка освободится, и мы легко сможем все свободные (белые) клетки найти, выполнив набор команд для каждой занятой (синей) клетки. Каждый раз число свободных (белых) клеток увеличивается хотя бы на 1, за счет того, что мы будем выбирать новую синюю клетку и запускать программу на выход из нее.
Zara6502
20.06.2024 04:14я все равно вас не понимаю, вот что я написал https://habr.com/ru/articles/823066/comments/#comment_26955316
DGN
20.06.2024 04:14+2Это же просто. Пишем все маршруты выхода из всех клеток, исполняем циклически, по идее, рано или поздно клетка с черепахой и маршрут совпадут. Но нужен код, проверить эту теорию.
Если циклить нельзя, то делаем цепочку из всех вариантов по рандому, числом например в 10 в степени числа вариантов, это ведь всё еще будет конечная последовательность команд, а у черепахи феноменальная память.
Octabun
20.06.2024 04:14+1Циклить не работает, объяснено про возвращение в исходную точку. По рандому не работает в силу требования конечности. Смысл статьи как раз в том, что писать пути выхода нужно в определённой последовательности.
DGN
20.06.2024 04:14А нет цели вернуться в исходную точку. Мы просто исполняем весь набор программ, в надежде что он начнется с нужной точки, ну или команды приведут у выходу, пусть и неоптимально.
Zara6502
20.06.2024 04:14выше я нарисовал простой "карман" который может стать ловушкой, а представьте такие карманы более сложной формы, черепахе достаточно туда поспасть и любой набор команд может оказаться нерабочим.
Zara6502
20.06.2024 04:14или например у вас 1024 маршрута, вы их в цикле выполняете и на 65536-ой позиции, всё еще не выйдя из лабиринта вы опять оказываетесь в стартовой самой первой клетке и всё повторяется опять.
DGN
20.06.2024 04:14Но в другом порядке, потому что случайно перемешено.
Zara6502
20.06.2024 04:14в каком другом порядке если система вернулась в исходное состояние.
DGN
20.06.2024 04:14Возьмём к примеру классический лабиринт 8*8, что дает нам 63 стартовые позиции и 64 успешных маршрута. Мы их случайно перемешиваем и отправляем в черепаху, потом так делаем еще 10*63 степени раз. Это все еще конечная программа. Каждый ход приводит черепаху к выходу с вероятностью как минимум 1/63, а на самом деле гораздо выше, потому что и другие маршруты ведут к выходу. Если черепаха не вышла, она в исходной точке или в какой-то другой, и снова есть вероятность, дальше она будет немного падать, потому что правильного маршрута для этой точки может не быть, он уже был исполнен. Черепаха отрабатывает 64 маршоута и начинается новый блок случайных маршрутов. Печально, что не могу это закодить, как тот Василь Иваныч - на вопрос сколько будет 250*2 "чую что поллитра, а как сказать не знаю".
ruomserg
20.06.2024 04:14+1Напрашивается контр-пример примерно такого свойства: лабиринт состоит из трех областей (клеток). Программа X, будучи исполнена из начальной клетки "A" приводит к выходу. Она же из клетки "Б" - приводит в "A". Другая программа "Y", из клетки "Б" приводит к выходу, а из клетки "А" приводит в "Б". Очевидно, что программа "XY" при спауне в правильной локации (50% вероятности) - приводит нас к выходу после выполнения X, и приводит обратно в "А" при выполнении "XY" из неправильной локации. Причем сколько бы мы не циклили XY, при спауне в "Б" - мы будем бесконечно перемещаться между А и Б. Конкретно в этой ситуации, правильной программой будет XX или YY. Но для общего случая, такой переход надо доказывать...
DGN
20.06.2024 04:14Ок, для выхода из трёхклеточного лабиринта у нас есть две программы, а и б, для клеток 1 и 2, ну и третья клетка, сам выход. Генерируем 10 в 3 степени последовательностей из программ а и б в случайном порядке. Это конечная последовательность из 1000 программ каждая по 1 команде. аббабааб...
По мере усложнения лабиринта у нас растет и степень числа программ.
Mingun
20.06.2024 04:14Рандом не нужен, алгоритм полностью детерминирован и конечен. Смотреть мой комментарий.
Kerman
20.06.2024 04:14+2Я думаю, что решение в том, чтобы рассматривать M*N-1 черепах, одновременно работающих в SIMD. Алгоритм на каждом шаге должен выбирать тот путь, который максимально сокращает количество занятых клеток, помещая черепах в одну. И так, пока все не окажутся в одной. Далее задача сводится к доползанию до финиша толпы черепашек.
kipar
20.06.2024 04:14если лабиринт на торе, то вполне возможно что в одну черепашку их свести нельзя.
Zara6502
20.06.2024 04:14+1Вообще задачу интереснее усложнить до "найти самый короткий набор команд".
wataru
20.06.2024 04:14+1Вот это уже будет более сложная задача.
Можно построить граф, где вершины - все подмножества клеток. Начальное состояние - "все клетки". Сделав ход в какую-то сторону, каждая клетка туда смещаются, если там нет стены. Если стена есть, то клетка остается на месте. Конечная клетка не смещается никуда. Таким образом мы как бы отслеживаем все возможные положения черепахи после последовательности ходов. И вот в таком графе с 2^(n*m-1) вершин и 4*2^(n*m-1) ребер надо будет найти кратчайший путь в вершину {конечная клетка}.
Кажется, задача NP-полна. Какой-нибудь A* тут возможно отработает когда-нибудь, но для больших лабиринтов это будет все-равно медленно.
Zara6502
20.06.2024 04:14как я понимаю тут нужно как в шахматах или го смотреть на цену хода, но доказать я не смогу, не для моих мозгов.
то есть как в A* считаем цену каждого хода но для всех черепашек сразу, получается сумма, так как ходов только 4, то и суммы будет 4, ходим туда где сумма меньше. Так как критерием является уменьшение расстояния, то часть черепашек даже если временно будут идти на увеличение расстояния, то остальные на уменьшение. Хм, но не факт что лучший ход i даст лучший же ход i+1. В общем это вариант, то не факт что найдет оптимальное решение. Тогда только через граф и запускать Дейкстру, на небольших лабиринтах думаю будет работать нормально.
wataru
20.06.2024 04:14Цену хода сложно учитывать. Это какая-то жадность тогда получится. В A* надо снизу как-то оценивать количество оставшихся ходов, чтобы все клетки из заданного множества привести в конец. Можно, например, брать самую далекую клетку.
Zara6502
20.06.2024 04:14Допустим такую ловушку для черепахи
ССССССССССССС С...........С С.ССССССССС.С С.С.......С.С С.С.ССССС.С.С С.С.С...С.С.С С.С.ССС.С.С.С С.С.....С.С.С С.ССССССС.С.С С.........С.С СССССССССССхСздесь должен получиться очень строгий набор команд который в определенных клетках даёт положительный роут только в одну сторону, причем заранее не ясно где мы, а значит этот положительный роут в одном случае приведёт к выходу, а в другом - наоборот заведёт в тупик.
Получается что до запуска роута из центра до выхода, мы черепаху должны гарантированно в этот центр привести. Таким образом для каждого лабиринта есть точка гарантированного выхода и она может совпадать в самим выходом.
Например для спирали выше верным алгоритмом будет использование одних направлений только после других, у нас 11 шагов по горизонтали и 8 по вертикали - это максимумы. Соответственно чтобы гарантированной выйти, нужно выполнить такие команды:
11 вправо, 8 вниз - где бы мы не находились, мы окажемся в правом нижнем углу.
10 влево, 7 вверх - где мы не находились, мы сместимся в левый верхний угол.
Так как завитков у нас 3, то и повторить эти команды мы должны три раза.
Это частный случай, где придумать маршрут было не так и трудно, а вот как поступить в других ситуациях?
Mingun
20.06.2024 04:14Как один пример гарантированного алгоритма -- делать наоборот, но это явно будет не минимальный набор команд. В вашем примере можно сначала двинуться 9 раз вниз -- это очистит вертикаль сразу над выходом. Остальные черепашки либо сдвинуться на сколько-то шагов вниз, либо не изменят своего положения.
Далее нужно посмотреть на конфигурацию лабиринта (где так черепахи сидят) и выбрать команды, что бы какие-нибудь черепашки перешли в выход. Других черепашек это может загнать в тупики -- ну так и что, когда дойдет очередь вытаскивать их, мы их обратно целенаправленно из этих тупиков выведем.
Очевидно, что такая последовательность команд будет неоптимальной, но она гарантированно выведет черепаху из любого положения.
Batalmv
20.06.2024 04:14Я не очень понял один момент. У черепашки нет обратной связи, т.е. у нее есть память, но нет понимания, что произошло. Соответстенно, как верно указано, перебор маршрутов ничего не дает, так как черепашка не может пройти маршрут и потом снова оказаться в начальной точке, чтобы пройти следующий вариант маршрута
Но вот переход
На самом деле вариантов не так много, как кажется на первый взгляд. Изначально черепаха находилась в одной из
клеток, но проделав данный маршрут она могла перейти в одну из клеток, если не вышла. Таким образом, количество вариантов нового расположения как минимум на 1 меньше, чем было изначально. ничем не обоснован. Сорян. Черепашка без памяти и нет никаких гарантий, что через одну, две, три ... N команд она не окажется в своей начальной точке, где количество маршрутов все те же "
".Как по мне, в задачу надо что-то добавить, либо привести более строгое доказательство того, что количество вариантов после выполнения конечного числа шагов уменьшается
Мне кажется, что возникает вопрос - можно ли вообще гарантированно выйти из произвольного лабиринта без "памяти". К примеру, в вашей картинке, если я буду идти всегда держась правой стороны - я зациклюсь. То же самое, если я буду держаться левой стороны. Значит, чтобы сменить стратегию, мне надо знать, что я зациклился и в какой-то момент попробовать поменять стратегию на противоположную
Где-то так ...
wataru
20.06.2024 04:14+1Да нет, все строго. Если черепашка находилась в правильной клетке - она лабиринт прошла, для всех оставшихся n*m-2 варантов начальных клеток она где-то закончит свой маршрут (на самом деле, может быть даже меньше. Она может случайно по пути выйти из лабиринта).
Тут важное условие, что как только черепашка ступает на клетку-выход, она выиграла. Не надо составить алгоритм, который из любой точки закончит путь в данной. Достаточно чтобы, начиная из любой клетки, черепаха как-то где-то прошла через конечную клетку хотя бы раз. Именно поэтому одна клетка исключается. Составленный путь эту клетку переводит в конец. Значит, после выполнения этого пути можно забить на эту клетку совсем.
Zara6502
20.06.2024 04:14Не надо составить алгоритм, который из любой точки закончит путь в данной. Достаточно чтобы, начиная из любой клетки, черепаха как-то где-то прошла через конечную клетку хотя бы раз
Это как раз понятно, непонятно как вы распоряжаетесь этим.
Речь про ошибочность вот этого утверждения:
Однако, если чуда не случилось, то черепаха сейчас все еще находится где-то в лабиринте. Но, где именно она может находиться?
На самом деле вариантов не так много, как кажется на первый взгляд. Изначально черепаха находилась в одной из
клеток, но проделав данный маршрут она могла перейти в одну из клеток, если не вышла. Таким образом, количество вариантов нового расположения как минимум на 1 меньше, чем было изначально.Автор почему-то исключил тот вариант, что набор команд вернёт его в исходную точку, то есть количество клеток для исследования не изменилось и так и составляет
клеток, так как мы же можем легко сформулировать для лабиринта и такую задачу - как обойти весь лабиринт и вернуться в исходную точку, соответственно у нас как минимум маршрутов для возврата в исходную точку, что очевидно, ведь лабиринт связный.wataru
20.06.2024 04:14+3Автор почему-то исключил тот вариант, что набор команд вернёт его в исходную точку
Это исключено, потому что последовательность комманд переводит начальную точку в выход из лабиринта. Вот поэтому эта начальная клетка исключается. Все остальные куда-то там переводятся, но их количество nm-2.
Mingun
20.06.2024 04:14Автор почему-то исключил тот вариант, что набор команд вернёт его в исходную точку,
Но ведь набор команд не зациклен. Он любой. Предположим, что пока мы выводили других черепашек из лабиринта, одна из них описала в нем цикл и вернулась на свою исходную позицию. Ну так и что? Теперь мы будет строить маршрут специально для нее и выдадим такой набор команд, чтобы она попала к выходу. И так, повторяя это для каждой черепахи, выведем их всех.
При построении алгоритма нужно лишь отслеживать, какие клетки в лабиринте могут быть потенциально заняты черепахами. Например, в вашем примере со спиралью можно начать строить маршрут так, чтобы выгнать из тупика спирали засевшую там черепаху. Для этой спирали эти шаги также будут выгонять всех остальных черепах из этого тупика и вернуться они туда уже не смогут. Если помнить об этом, далее не нужно будет добавлять команды, чтобы пытаться выгнать черепах из этих пустующих клеток. Пока вы эти команды выполняете, часть других черепах уже может попасть к выходу (и в данном примере попадет!).
Zara6502
20.06.2024 04:14это я уже понял своим способом так как авторское описание происходящего я осилить так и не смог, читайте моё решение внизу обсуждений.
Batalmv
20.06.2024 04:14Да нет, все строго. Если черепашка находилась в правильной клетке - она лабиринт прошла, для всех оставшихся n*m-2 варантов начальных клеток она где-то закончит свой маршрут (на самом деле, может быть даже меньше.
Смотрите, вы по сути применяете как метод доказательства метод мат. индукции. Где доказываем верность для сосояния 0, и далее показываем, что переход из N в N+1 улучшает ситуацию
Но в свое посте вы самое важное как раз и подаете как нечто очевидное :)
С чего вы взяли, что следующий шаг улучшит ситуцию.
Простой наглядный пример. Черепашка начала возлде клетки "выход". У нее 4 команды.
Одна - успех, остальные три нет. При этом если одна из команд сменит клетку, ситуация УХУДШИЛАСЬ!!
Все, приехали, было условно 4 варианта, а стало 16
-------------------
Давайте четенько в математику, потому что так не работает
wataru
20.06.2024 04:14+3Нет тут индукции. Тут полу-инвариант скорее. Изначальну нас nm-1 возможных позиций для черепахи. После выполнения алгоритма у нас количество возможных позиций уменьшается на 1. Конечное число рано или поздно уменьшится до 0.
Простой наглядный пример. Черепашка начала возлде клетки "выход". У нее 4 команды.
Одна - успех, остальные три нет. При этом если одна из команд сменит клетку, ситуация УХУДШИЛАСЬ!!
Не ухудшилась! Какой бы мы ход не сделали, где бы черпашка не была, она не может раздвоиться. Будет ровно одна позиция, где она закончит путь. Так что эта соседняя клетка просто перейдет куда-то, но все так же даст +1 к количесвту возможных позиций.
Автор @demitryy шикарную аналогию придумал: представьте что у нас по черпахе в каждой клетке. После хода они все все где-то окажутся. Они могут объединится в одной клетке (если одна черепаха уперлась в стену, а другая со спины в ту же клетку пришла). Но они не могут одновременно пойти в 2 клетки.
Batalmv
20.06.2024 04:14Не ухудшилась! Какой бы мы ход не сделали, где бы черпашка не была, она не может раздвоиться. Будет ровно одна позиция, где она закончит путь
Утверждение что путь конечен требует доказательств. Вы сейчас принимаете это как исину, но это не так
представьте что у нас по черпахе в каждой клетке. После хода они все все где-то окажутся. Они могут объединится в одной клетке (если одна черепаха уперлась в стену, а другая со спины в ту же клетку пришла). Но они не могут одновременно пойти в 2 клетки.
Смотрите, есть строгое доказательство, или его нет. Аналогии не работают.. Ок, пусть мы посадили в каждую клетку черепашку и они все выполняют один маршрут. Ок. Но в реальности ничего не поменялось: алгоритм обхода будет выводить черепашку из лабиринта эквивалентно тому, что в аналогии ВСЕ черепашки буду выведены из лабиринта
Доказательство простое и тривиальное. Если хоя одна из черепашек не вышла, значит для ее стартовой позиции алгоритм не сработает.
Ну и наоборот. Не буду описывать.
---------------
Эта аналогия никак нас не приближает к решению задачи, а просот вводит другое эквивалентное условие. Но решения то нет
-------------------------------
Давайе по другому. По условиям задачи лабиринт связан. Значит если вы придумаете маршрут, который обойдет ВСЕ клетки, значит вы сможете выйти, так как непременно попадете на клетку exit. Ну и обратно тоже верно, так как клетка с выходом находится в произвольном месте
Ну вот и попробуйте без памяти обойти все клетки.
Либо надо дополнять условие задачи
wataru
20.06.2024 04:14+1Утверждение что путь конечен требует доказательств. Вы сейчас принимаете это как исину, но это не так
Вы же дали путь из одного хода в какую-то сторону. Конечен.
А так в доказательстве фигурирует максимум n*m-1конечных путей (переводящих какую-то клетку в конечную). Не надо же вам доказывать, что в лабиринте есть конечные кратчайшие пути из любой клетки в другую, покуда лабиринт, как дано, связный?
Давайе по другому. По условиям задачи лабиринт связан. Значит если вы придумаете маршрут, который обойдет ВСЕ клетки, значит вы сможете выйти, так как непременно попадете на клетку exit. Ну и обратно тоже верно, так как клетка с выходом находится в произвольном месте
Вот тут вы без доказательства приводите совсем не верное утверждение. Да, такой путь решит задачу. Нет, решение не обязано быть таким. Из того, что клетка с выходом находится в произвольном месте не следует, что путь должен обходить все клетки.
Batalmv
20.06.2024 04:14Вы же дали путь из одного хода в какую-то сторону. Конечен.
Надо доказать, что он достигнет результата. Иначе он будет "безконечным" и тоже без позитивного результата :)
А так в доказательстве фигурирует максимум n*m-1конечных путей (переводящих какую-то клетку в конечную).
Смотрите в чем проблема :) Я понял. Поясняю. Есть n*m-1 КЛЕТОК. Тут я не спорю. Это очевидно
Нет, не буду пояснять. Сначала спрошу. С чего вы взяли, что есть ровно по ОДНОМУ маршруту на каждую целевую клетку
Простой пример, чтобы попасть на клетку ниже есть опции:
down
up, down
right, down
left, down
....
При этом памяти нет, обратной связи нет
Вот тут вы без доказательства приводите совсем не верное утверждение
Я его как раз привел. Клетка exit может біть выбрана произвольно, поэтому чобы в нее попасть, надо уметь перебрать все клетки УНИВЕРСАЛЬНЫМ алгоримом. Напомнить условие?
wataru
20.06.2024 04:14+1Ладно, вот вам формальное доказательство.
Занумеруем все клетки лабиринта. Пусть их будет N. Конечная клетка N.
Обозначим за F_i путь из клетки i в N. Это последовательность действий, она же алгоритм. F_i(x) - результат действия алгоритма F_i на клетку x. Это - где черепаха окажется, если она начинала в клетке x и выполнет шаги из F_i (при этом, дойдя до клетки N черепаха остается там). Обозначим применение двух последовательностей пути A и B как A.B: A.B(x) = B(A(X))Построим N-1 алгоритмов:
G_1 = F_1
G_2 = G_1.F_{G_1(2)}
G_3 = G_2.F_{G_2(3)}
...
G_{N-1}=G_{N-2}.F(G_{N-2}(N-1)).Тут для каждого алгоритма смотрим, куда переедет клетка i-1 пока что. И приписываем к предыдущему алгоритму кусок, который переводит эту клетку в конец.
Докаем, что G_{N-1} переводит любую начальную позицию в N. Пусть эта позиция 1<= i < N.
Распишем G_{N-1} по определению, подставив все определения для G_j, j>=i:
G_{N-1}= G_{i-1}.F_(G_{i-1}(i)).F_{G_i(i+1)}...
Рассмотрим начало G_{i-1}.F_{G_{i-1}(i)}. Это начало переводит позицию i в N, ведь можно обозначить G_{i-1}(i) = k и тогда этот алгоритм это G_{i-1}.F_k. Если его применить к i? получитм F_k(G_{i-1}(i)) = F_k(k) = N (по определению F_k).
Поскольку, после достижения N дальнейшие шаги никуда черепаху не двигают, мы доказали что произвольное начало i переводится построенным алгоритмом в N. ЧТД.
Тут нет индукции. Это доказательство по построением.
Batalmv
20.06.2024 04:14Тут для каждого алгоритма смотрим, куда переедет клетка i-1 пока что
Вот тут проблема. Вы НЕ ЗНАЕТЕ, куда вы переехали, так как по условиям задачи
Напомню оригинальную постановку
Черепаха не может перемещаться сквозь стенки лабиринта, и поэтому просто игнорирует команду
команда в стену игнорируется
памяти нет
Чтобы алгоритм работал, надо добавить условие, к примеру "знание того, что клетка изменилась после команды". Тогда конечно, нет никакой проблемы. Черепашка без проблем нащупывет путь, определяя эмпирически где стена, а где ее нет
И напомню, требуется ОДИН универсальный алгоритм. Вы не можете решать задачу так.
черепашка в начальной позиции
применили последовательность команд
не вышла
ок. позвращаем все назад и даем другую
Команды "back to start" нет в списке, можно только давать команды по 4м направлениям. Поэтому и вышла машина Тьюринга, но без состояния :)
Давайте определимся, мы решаем задачу из статьи, либо какую-то другую.
---------------------
Я понял, вы просто считаете, что черепашка знает где она, хотя я в упор не вижу, где это ей разрешено по условиям задачи
wataru
20.06.2024 04:14+2Вот тут проблема. Вы НЕ ЗНАЕТЕ, куда вы переехали, так как по условиям задачи
Всмысле?! Мы не знаем, где черпаха находится, но мы знаем лабиринт. Мы можем взять вот эту вот i-1-ую клетку, применить к ней уже выписанную на бумаге последовательность ходов и узнать, где она окажется.
ок. позвращаем все назад и даем другую
Мы не возвращаем черепаху! Именно поэтому когда мы хотим вывести черепаху, если бы она была на второй клетке в самом начале, мы применяем не F_2, а F_{G(1)}. Мы предполагаем, что черпаха была на 2 позиции. Смотрим, а где бы она оказалась с текущим алгоритмом и дописываем его так, чтобы эта 2-ая клетка в итоге вышла из лабиринта. При этом мы не портим первую клетку, ведь мы только что-то дописываем к алгоритму.
Я понял, вы просто считаете, что черепашка знает где она,
Перечитайте определения в начале статьи. Там нигде не фигурирует "где черепаха находится". Там тупо лабиринт, конкретные в нем клетки и конкретные последовательности действий.
Еще раз, не формально, но может вам понятнее станет: алгоритм состоит из N-1 частей. Первая выводит черепаху, если бы она была в первой клетке. Вторая исправляет "ошибку" первой части, если бы черепаха была на второй клетке в самом начале. Третья часть исправляет ошибку первых двух, если бы черепаха начинала в третьей клетке и т.д. В итоге, черепаха начав в какой-то клетке i первыми i-1 частями алгоритма куда-то передет, то i-ая часть эту ошибку исправит и выведет черепаху из лабиринта. Что там дальше - уже не важно.
Вот пример: лабиринт из 4 клеток вряд ".E..". Выход во второй клете. Первая часть - "Вправо" выведет первую клетку. Если бы черепаха была на второй клетке, она окажется в третьей по итогу первой части. Поэтому вторая часть будет "Влево,Влево" (а не один шаг, нужный со второй клетки. Надо исправлять ошибку алгоритма при начале из второй клетки, а не просто выводить черепаху с этой клетки).Третья клетка по итогу окажется в выходе уже и ничего дописывать не надо. Итоговый алгоритм "right, left, left" выведет черепаху с любой клетки.
Zara6502
20.06.2024 04:14Вот пример: лабиринт из 4 клеток вряд ".E..". Выход во второй клете. Первая часть - "Вправо" выведет первую клетку. Если бы черепаха была на второй клетке, она окажется в третьей по итогу первой части. Поэтому вторая часть будет "Влево,Влево" (а не один шаг, нужный со второй клетки. Надо исправлять ошибку алгоритма при начале из второй клетки, а не просто выводить черепаху с этой клетки).Третья клетка по итогу окажется в выходе уже и ничего дописывать не надо. Итоговый алгоритм "right, left, left" выведет черепаху с любой клетки.
простите что лезу в разговор, но мне это понятно было изначально, просто я не вижу где это решение описывается в статье.
wataru
20.06.2024 04:14просто я не вижу где это решение описывается в статье.
Вот:
На следующем шаге мы выберем любую другую синюю точку (клетку с черепахой) и построим от нее маршрут до выхода
синяя точка - позиция какой-то другой изначальной, после применения текущего алгоритма.
Zara6502
20.06.2024 04:14+1простой пример, лезу я в Вики и читаю алгоритм Дейкстры, сажусь за C# и пишу код, есть описание алгоритма и есть его реализация на ЯП.
Что мне прочитать по аналогии в статье чтобы я мог переложить это в код, то есть практически реализовать алгоритм? То что написал я внизу - я могу запрограммировать, то что написано в статье - нет (так же как и то, что вы написали в виде доказательства).
Batalmv
20.06.2024 04:14Вот пример: лабиринт из 4 клеток вряд ".E..". Выход во второй клете. Первая часть - "Вправо" выведет первую клетку. Если бы черепаха была на второй клетке, она окажется в третьей по итогу первой части. Поэтому вторая часть будет "Влево,Влево" (а не один шаг, нужный со второй клетки. Надо исправлять ошибку алгоритма при начале из второй клетки, а не просто выводить черепаху с этой клетки)
Почему не будет цикла?
Вы рассматриваете вырожденный случай, когда есть только прямой путь, где условно только "вперед" или "назад". Т.е. по сути в вас не произвольный граф, а просто ряд. Но лабиринт это граф з вершинами, где может быть до 4 ребер
И тут легко получить циклы, и возможность их преодоления надо доказать
Вы же допускаете, что исправляя ошибку к примеру третьего шага, вы не "портите" результат второго.
Т.е. ОК
У вас есть множество F_i(x). Это да, для каждой клетки. Условно вы применили F1, к примеру выполнили команду up для клетки под выходом. Но теперь у вас еще M*N-2 вариантов переходов, которые в общем случае случились. И это зависит от конфигурации лабирина. И у вас уже есть множество вариантов всех клеток, кроме тех, у кого стенка внизу (так как в эти клетки нельзя перейти по команде up). Дальше что?
Если вы дадите другую команду, к примеру left, то окажется, что множество клеток, где есть черепашка - это все клетки из предыдущего множества, где стенка слева (т.е. мы остались на месте), либо другие клетки, если стенки не було.
И тут пичалька. Это могут быть клетки, которые к примеру, были откинуты на предыдущем шаге, ну или вообще любые.
Т.е. у вас по сути легко может быть возврат не клетки где вы были и почему в какой-то момент вы не словите цикл по которому вы будете ходить
----------------
Для "кишки" - конечно, все будет работать так как в какой-то момент вы начнете правильную последовательность. Но для графа это надо доказывать явно
wataru
20.06.2024 04:14У вас есть множество F_i(x)
Не множество, а последовательность ходов.
Дальше что?
Берем любую из возможных n*m-2 клеток (куда после применения up попала какая-то другая) и строим путь из нее в конец.
Если вы дадите другую команду, к примеру left
Если бы да кабы. Мы-то выбрали дать сначала команду up, потому что выбрали какую-то конкретную клетку, которую на первом шаге перевели в конец.
Т.е. у вас по сути легко может быть возврат не клетки где вы были и почему в какой-то момент вы не словите цикл по которому вы будете ходить
Ну и пусть какая-то клетка вернется туда, где начинала. Когда очередь дойдет до нее, мы построим путь из ее текущего положения в конец. Ну опять аналогия может вам помочь понять: изначально в каждой клетке есть черепаха. Со своим номером. Вот мы сначала первую черепаху переводим в конец. Потом вторую, с той позиции, где она оказалась и т.д. Вообще не важно, что какая-то черепаха вернется туда, где была раньше. Если мы какую-то черепаху из лабиринта вывели, она там опять не появится уже.
Batalmv
20.06.2024 04:14Да уже допер, спасибо
https://habr.com/ru/articles/823066/comments/#comment_26955548
Mingun
20.06.2024 04:14ок. позвращаем все назад и даем другую
Хитрость в том, что это вы придумали необходимость этого шага. А он не нужен. Вы просто фактически вернулись опять к началу задачи. Представьте, что до этого никаких команд не было, а черепаха изначально материализовалась в этой клетке. И повторите алгоритм поиска. Заметьте, что в алгоритме нигде нет никаких условных конструкций (ЕСЛИ что-то ТО ДЕЛАЙ то-то). Есть только действия (ДЕЛАЙ то-то).
А во время построения алгоритма вы вполне памятью можете пользоваться и помнить, в каких клетках могут быть черепахи, а в каких -- не могут. Можете даже подсчитывать их количество в каждой клетке после каждого шага, хотя для решения задачи это не нужно. Изначально в каждой клетке может быть 1 черепаха. После команды, скажем, "вправо" в каких-то клетках будет уже 0 черепах (т.к. они оттуда ушли вправо, а новая не пришла, т.к. слева была стенка), а в каких-то -- 2 (т.к. у этой клетки слева стенки не было), а в каких-то так и осталась одна (либо черепаха из нее не двинулась, т.к. справа стенка, либо она ушла вправо, а на ее место пришла другая из клетки слева).
Batalmv
20.06.2024 04:14Я понял только что, тут для себя выписал корткую версию: https://habr.com/ru/articles/823066/comments/#comment_26955548
Спасибо
Mingun
20.06.2024 04:14Лабиринт фиксирован и известен тому, кто ищет в нём путь. Запрета на использование памяти при построении маршрута в условиях задачи нет. Черепахе же ничего помнить не нужно, ей просто надо следовать по построенному маршруту.
wataru
20.06.2024 04:14+1Кажется, решается и более сложная задача, где черепаха должна оказаться в конечной клетке после всех ходов (при этом она может просто пройти через нее в процессе, но этого не достаточно).
Рассмотрим множество всех клеток, где черепаха может быть. Изначально это все клетки лабиринта. При выполнении хода все клетки в этом множестве смещаются в какую-то сторону, если там нет стены. Если там есть стена, то клетка остается на месте. При этом за счет стен можно "объединять" клетки, уменьшая мощность множества возможных клеток. Когда одна клетка наезжает на другую, они уже больше никогда не разделятся. Надо как-то объединить все клетки в одну, которую потом можно будет привести в конечную.
Возьмем 2 любые клетки в множестве, составим последовательность ходов, которая приведет их обе в одну и ту же клетку. После выполнения этой последовательности ходов, мощность множества уменьшится хотя бы на 1.
Теперь самое интересное: как объединить 2 произвольные клетки (назовем их А и Б). Пусть расстояние между клетками L. Возьмем кратчайший путь из А в Б и выполним эти шаги. Клетка А переместится в Б. Клетка Б тоже куда-то уедет. Если клетка Б по пути столкнулась хоть с одной стеной, то расстояние между клетками стало меньше L. Ведь, если повторить только те ходы, которые не бились об стенку, то мы повторим путь клетки Б и придем в ее новое положение. Если же клетка Б не столкнулась ни с одной стеной, то относительная разность координат клеток не изменилась. При этом путь из нового положения А в новое положение Б состоит из ровно тех же L шагов и не столкнется ни с одной стеной. Повторим их. Клетка А опять перейдет в положение клетки Б. Клетка Б опять или столкнется со стеной, или сместится на тот же вектор. Но, поле-то конченое. Клетка Б не сможет бесконечно перемещатся на этот же вектор ни разу не сталкиваясь со стеной. Через min(n/dx, m/dy) повторений клетка Б упрется в границу поля и не сможет переместится на тот же вектор ни разу не ударившись в стену. Поэтому, за конечное количество ходов мы уменьшим расстояние между клетками хотя бы на 1. А значит, за конечное количество ходов мы сможем уменьшить его до 0, объединив клетки.
Zara6502
20.06.2024 04:14Поскольку автор и пара других участников настаивают на том что в статье указано решение задачи, но я его не наблюдаю (и видимо не я один), то предлагаю своё решение:
наша задача - записывать ходы приводящие к выходу, а общий набор команд дополнять из этого списка.
исходим из концепции что все клетки заполнены черепашками и каждый ход или выводит одну черепашку из лабиринта или меняет их положение.
так же "фишки" черепашек склеиваются в одну когда например черепашка уперлась в стену, а другая пришла к ней же в клетку, формально это говорит о том, что с какой-то клетки выход неизбежно случается для нескольких черепашек.
отмечая точки, откуда мы выводим конкретную черепашку и записывая такой маршрут мы позже ведём в такие клетки ближайших черепашек, что позволяет нам в окончательный маршрут вставлять склейку из двух - маршрут до этой клетки и маршрут до выхода, который уже известен.
Применяя этот алгоритм вы гарантированно построите такой маршрут, который при сообщении черепахе в любой позиции гарантирует её успешное вызволение из лабиринта.
Собственно вот это и называется решением задачи. Уж простите если оно на палочках, а не через язык математики.
wataru
20.06.2024 04:14Вроде похоже, что вы такое же решение, как и у меня или у автора подразумеваете, но непонятно.
отмечая точки, откуда мы выводим конкретную черепашку и записывая такой маршрут мы позже ведём в такие клетки ближайших черепашек
Вот тут не понятно, что происходит. Что значит "мы ведем в такие клетки ближайших черепашек". Как именно ведем, какие такие клетки?
Можно пример? Вот лабиринт ".E.." - 4 клетки без стен, выход со второй.Zara6502
20.06.2024 04:14Что значит "мы ведем в такие клетки ближайших черепашек"
Ну если до позиции из которой вы уже записали маршрут например 1 клетка, а до выхода 20 клеток, то какой смысл вам в голове крутить опять все ходы, вы ведёте черепашку к уже известному маршруту эту самую одну клетку, а потом весь роут в 333 команды копируете в конечный маршрут. Это не более чем оптимизация, решение работает и без этого.
Можно пример? Вот лабиринт ".E.." - 4 клетки без стен, выход со второй.
пример плохой, лучше так
В.... ..... ....ч ....Чгде точка это пусто, В - выход, Ч - черепаха, ч - известная уже ранее позиция из которой мы знаем маршрут. Вот чтобы не строить маршрут Ч->В вы строите Ч->ч, а потом просто копируете ч->В.
demitryy Автор
20.06.2024 04:14+1Маршруты вида Ч -> Ч плохи тем, что одна черепаха может убегать от другой. Объяснить как строить такие склейки сложнее, чем просто вести черепашек в выходу :)
Zara6502
20.06.2024 04:14ну для меня склейка - это очевидная оптимизация, задача поиска кратчайшего роута же не стоит, а значит пусть все черепашки идут к ближайшим известным роутам.
а что такое "убегать от другой" и почему это плохо?
demitryy Автор
20.06.2024 04:14пусть все черепашки идут к ближайшим известным роутам
Это как?
Zara6502
20.06.2024 04:14Выше я показал как, путь ч->В мы уже знаем, смотрим расстояние Ч->ч и Ч->В, если первое меньше, то идем туда, получается набор команд, которые мы записываем в конечный маршрут, а после дописываем уже ранее известный ч->В.
Zara6502
20.06.2024 04:14для картинки выше маршрут ч->В это:
вверх, вверх, влево, влево, влево, влевоа для Ч->ч:
вверхрезультирующий маршрут будет
вверх + вверх, вверх, влево, влево, влево, влево
Batalmv
20.06.2024 04:14+1Все, дошло
Краткая версия:
Высыпали на все клетки черепашек
Каждую итерацию выводим из лабиринта одну черепашку и это маршрут дописываем в универсальный
Остальные черепашки куда-то попадают, но нам по фиг
Прикол был в том, надо надо было перестать думать ходами, а думать только маршрутами :)
Спасибо
Alexandroppolus
20.06.2024 04:14Авторское решение вызывает вопросы. Допустим, упрощенно, у нас в лабиринте только 3 клетки: А, В, С, причем С - выход.
1) Предполагаем, что черепашка в А, строим маршрут из неё. Но черепашка была в В и этим маршрутом пришла в А. Фиаско.
2) Теперь мы строим маршрут из В в С, но черепашка из А приходит в В.
Это упрощенный пример, но где гарантия, что в лабиринте подобного не случится?
Mingun
20.06.2024 04:14+1У вас логическая ошибка на втором шаге. Не нужно строить маршрут из B в C, вы же уже знаете, что в B никого нет, черепаха оттуда уже находится в A. Вот и стройте опять маршрут из A в C.
Alexandroppolus
20.06.2024 04:14Ага, понял, спасибо. После каждого шага у нас новый набор "синих" точек, где может быть черепаха, и неважно, что какие-то из них раньше были "белыми" или стартовыми. Я что-то с этим моментом затупил.
Phantovas
20.06.2024 04:14А если из клетки вы попали в клетку с тремя стенами, что дальше? Обратно вернуться на белую, то к числу итераций +1, а не вернуться, то черепаха не достигнет выхода.
MaximDoroshenko
20.06.2024 04:14Если у черепахи идеальная память, то почему бы не заставить ее запомнить условия нахождения в разных частях лабиринта и затем при помощи сортировки подбирать условия для выхода из оного?
Zara6502
20.06.2024 04:14Вчера еще мозговал над задачей, в основном в аспекте ваших утверждений, всё же я считаю что у вас есть ошибки:
Как можно видеть, за счет того, что как минимум одна синяя точка (клетка) гарантированно переходит в клетку "выход"
Это утверждение ложно, не на каждой итерации черепашка будет попадать на клетку "выход". Чем меньше у вас будет черепашек, тем больше будут интервалы между выходами.
справа появится как минимум одна белая точка (клетка, в которую нас никогда не приведет данная последовательность команд).
Не понятен смысл этого утверждения, для нас абсолютно не важно что где-то освободится клетка, мы же не в неё идём. На следующих итерациях она может заполниться, а другая освободиться. Что вам даст эта информация и как вы её хотите использовать? Если это говорится в контексте уменьшения числа итераций, то его тут нет, точнее в вашем повествовании он всегда -1, хотя, как видно ниже из моих рассуждений, можно сделать так, что число итераций всегда будет в диапазоне 1 <= X < nm-1, причем X будет стремиться к 1.
На следующем шаге мы выберем любую другую синюю точку (клетку с черепахой) и построим от нее маршрут до выхода. Пройдя по маршруту, количество возможных для черепахи клеток опять уменьшится хотя бы на одну
Тут вас спасло "хотя бы", так как в теории вы можете взять одну единственную черепаху и пока ведёте её к выходу у вас просто весь лабиринт опустеет (это если мы рассматриваем лабиринт как заполненный черепашками). Это верно для любого лабиринта без ответвлений, тогда маршрут для самой дальней клетки по пути выводит всех черепах.
---
Касательно оптимизации, один вариант я предложил уже ранее - это движение очередной черепашки к уже готовому маршруту, но вечером я придумал еще один вариант (который не является отдельным, а скорее взгляд на предыдущий под другим ракурсом) - нужно делать ходы, которые склеивают черепашек и чем больше за ход их склеивается, тем меньше шагов будет в результирующем маршруте (то есть разница только в том, что за ход мы соединяем как можно больше черепашек, так как каждая такая склейка уменьшает число итераций). Но не берусь сказать каким будет критерий окончания склеиваний, возможно склеивание нужно производить всегда, когда есть такая возможность, то есть пока существуют соседние черепашки одна из которых упрётся в стенку, а вторая встанет на её клетку. Формально это всё та же концепция использования известных маршрутов, только возведённая в некоторую степень.
Кстати нашёл физическую модель, схожую с задачей с кучей черепашек - это игра с шариком в лабиринте, где наклоны перемещают шарик. Правда шариков должно быть столько, сколько клеток в лабиринте и они должны превращаться в один при взаимном проникновении. Условность конечно, но возможно кому-то будет проще так всё представить.
demitryy Автор
20.06.2024 04:14+1Это утверждение ложно, не на каждой итерации черепашка будет попадать на клетку "выход". Чем меньше у вас будет черепашек, тем больше будут интервалы между выходами.
Итерация = следование по маршруту до выхода. После каждой итерации число синих клеток уменьшится хотя бы на 1.
Не понятен смысл этого утверждения, для нас абсолютно не важно что где-то освободится клетка, мы же не в неё идём.
Если число белых клеток увеличилось, значит число синих уменьшилось, т.к. в сумме их всегда n*m-1. Когда синие клетки закончатся, черепашка гарантированно выйдет.
Тут вас спасло "хотя бы", так как в теории вы можете взять одну единственную черепаху и пока ведёте её к выходу у вас просто весь лабиринт опустеет
Все рассуждения, очевидно, про верхнюю оценку числа ходов. Это называется аккуратно формулировать свои мысли :)
Zara6502
20.06.2024 04:14Нужно найти где я туплю. Давайте начнем отсюда:
На самом деле вариантов не так много, как кажется на первый взгляд. Изначально черепаха находилась в одной из
клеток, но проделав данный маршрут она могла перейти в одну из клеток, если не вышла. Таким образом, количество вариантов нового расположения как минимум на 1 меньше, чем было изначально. Для меня тут очевидно, что "проделав данный маршрут" черепаха могла вернуться в исходную точку, а значит состояние не изменилось, а значит она не перешла в другую клетку, а значит количество вариантов нового расположения осталось неизменным.
На рисунке 3 изображено, что примерно произошло в терминах теории множеств. Слева - множество клеток до выполнения набора команд, справа - после. Синими точками обозначены клетки, в которых теоретически может находиться черепаха. Как можно видеть, за счет того, что как минимум одна синяя точка (клетка) гарантированно переходит в клетку "выход", справа появится как минимум одна белая точка (клетка, в которую нас никогда не приведет данная последовательность команд).
Объясните другими словами, так как исходя из первого абзаца мы не можем исключить вероятность того, что множества вернулись в исходное состояние, а значит ничего никуда не перешло.
На следующем шаге мы выберем любую другую синюю точку (клетку с черепахой) и построим от нее маршрут до выхода. Пройдя по маршруту, количество возможных для черепахи клеток опять уменьшится хотя бы на одну.
А здесь я уже запутался. В первом абзаце вы пишете о теоретической возможности не попасть на выход, а в этом абзаце вы уже подразумеваете что строите гарантирующий выход маршрут.
И что конкретно значат синие и белые клетки? Как именно вы их определяете? По какому принципу вы их уменьшаете на 1 и какой критерий их выбора?
demitryy Автор
20.06.2024 04:14+1Для меня тут очевидно, что "проделав данный маршрут" черепаха могла вернуться в исходную точку, а значит состояние не изменилось, а значит она не перешла в другую клетку, а значит количество вариантов нового расположения осталось неизменным.
Это неверно. Из того, что черепаха могла вернуться в ту же точку не следует, что число вариантов не изменилось. У меня в статье на рис. 3 как раз изображены такие случаи, однако все равно появилась новая белая клетка.
Объясните другими словами, так как исходя из первого абзаца мы не можем исключить вероятность того, что множества вернулись в исходное состояние, а значит ничего никуда не перешло.
Множество не могли вернуться в исходное состояние, т.к. минимум одна синяя клетка перешла в зеленую (а зеленая умеет переходить только сама в себя, если хотите).
А здесь я уже запутался. В первом абзаце вы пишете о теоретической возможности не попасть на выход, а в этом абзаце вы уже подразумеваете что строите гарантирующий выход маршрут.
Не всякая синяя клетка попадет в зеленую. Но одна (та самая, выбранная нами) - обязательно попадает.
И что конкретно значат синие и белые клетки? Как именно вы их определяете?
Синяя клетка - это клетка, где может находиться черепаха. Например, вначале все кроме клетки "выход" - синие.
Белая клетка - это клетка, где гарантированно нет черепахи.
Зеленая клетка - клетка "выход".
По какому принципу вы их уменьшаете на 1 и какой критерий их выбора?
Выполняя итерацию за итерацией, число синих клеток уменьшается хотя бы на 1 естественным образом. Наша задача - отслеживать их. Для этого просто вручную посмотрим куда переходит каждая из них. Минимум одна синяя точно перейдет в зеленую (т.к. она была выбрана и для нее специально был построен туда маршрут), остальные - отследим и перейдем к следующей итерации =)
Zara6502
20.06.2024 04:14Это неверно. Из того, что черепаха могла вернуться в ту же точку не следует, что число вариантов не изменилось. У меня в статье на рис. 3 как раз изображены такие случаи, однако все равно появилась новая белая клетка.
Как-то не получается у вас объяснить.
Множество не могли вернуться в исходное состояние, т.к. минимум одна синяя клетка перешла в зеленую (а зеленая умеет переходить только сама в себя, если хотите).
Вы в статье ввели два состояния, одно допускает такие ситуации а другое - нет. Эта путаница создана вами, а я лишь пытаюсь понять как вы это всё воедино сводите.
Мне очевидно что если я веду черепаху на выход, то она выйдет, но зачем тогда вы описываете ситуацию когда этого не происходит?
Выполняя итерацию за итерацией, число синих клеток уменьшается хотя бы на 1 естественным образом. Наша задача - отслеживать их. Для этого просто вручную посмотрим куда переходит каждая из них. Минимум одна синяя точно перейдет в зеленую (т.к. она была выбрана и для нее специально был построен туда маршрут), остальные - отследим и перейдем к следующей итерации =)
Это как раз понятно, непонятно тогда зачем у вас в статье написано:
Однако, если чуда не случилось, то черепаха сейчас все еще находится где-то в лабиринте. Но, где именно она может находиться?
На самом деле вариантов не так много, как кажется на первый взгляд. Изначально черепаха находилась в одной из
клеток, но проделав данный маршрут она могла перейти в одну из клеток, если не вышлаВ моем решении такие ситуации могут быть и я объяснил почему, но у вас синее переходит в зеленое обязательно, зачем тогда этот абзац?
demitryy Автор
20.06.2024 04:14+1Мне очевидно что если я веду черепаху на выход, то она выйдет, но зачем тогда вы описываете ситуацию когда этого не происходит?
Этого может не произойти, если черепаха сидит не в выбранной вами клетке. Она может сидеть в любой синей, мы же не знаем в какой из них :)
В моем решении такие ситуации могут быть и я объяснил почему, но у вас синее переходит в зеленое обязательно, зачем тогда этот абзац?
Одна клетка обязательно перейдет в зеленую. Остальные - как повезет. Если ваша черепаха в той выбранной синей, то она точно выйдет.
Zara6502
20.06.2024 04:14Этого может не произойти, если черепаха сидит не в выбранной вами клетке
Зачем мне выбирать клетку без черепахи?
Она может сидеть в любой синей, мы же не знаем в какой из них :)
Мне кажется вы уже просто меня троллите.
Одна клетка обязательно перейдет в зеленую
Нет. Например справа от выхода стена, тогда команда "налево" не приведет к тому, что у вас кто-то достигнет финиша.
demitryy Автор
20.06.2024 04:14+2Зачем мне выбирать клетку без черепахи?
Затем, что вы не знаете, где черепаха. Все синие клетки для вас норм.
Мне кажется вы уже просто меня троллите.
Кто кого троллит)
Нет. Например справа от выхода стена, тогда команда "налево" не приведет к тому, что у вас кто-то достигнет финиша.
Одна итерация - это не одна команда, а последовательность команд, переводящая одну из синих клеток в зеленую.
wataru
20.06.2024 04:14Вы там ниже алгоритм запросили. Вот сделайте то же самое для своего решения.
Zara6502
20.06.2024 04:14сделать что? я весь алгоритм изложил сейчас пишу реализацию, оформлю в виде статьи, почитаете.
wataru
20.06.2024 04:14Алгоритм в виде псевдокода или блок схемки.
Zara6502
20.06.2024 04:14Создать список черепах расставив их на свободные клетки лабиринта
Цикл - пока список черепах не пуст
Рассчитать путь для первой черепахи до выхода
Записать в результирующий список команд
Передвинуть всех черепах из списка по маршруту из п.3 производя слияние элементов списка при совпадении клеток или удаляя из списка тех, что вышли из лабиринта
Вернуться в п.2
create List<Turtles> T commands result while (T not empty) Turtles t = GetFirst(T) commands C = FindPath(t, exit) foreach (T) move (C) exclude (t) groupby (cells) remove (T) exit result += C return print result
demitryy Автор
20.06.2024 04:14+2Браво! А теперь замените черепаху на синюю клетку и получится дословно алгоритм из статьи.
Создать список синих клеток (все свободные клетки лабиринта)
Цикл - пока список синих клеток не пуст
Рассчитать путь для синей клетки до выхода
Записать в результирующий список команд
Передвинуть все синие клетки из списка по маршруту из п.3 производя слияние элементов списка при совпадении клеток или удаляя из списка тех, что вышли из лабиринта
Вернуться в п.2
Zara6502
20.06.2024 04:14Браво мне, который это написал в одном из комментариев, в статье об этом нет ни слова. У вас скорее всего профдеформация и вы на какие-то вещи смотрите как на само собой разумеющиеся, но статью могут читать люди далекие как от математики, так и от программирования. Если в вашей статье и есть такая информация, то она или не указана вовсе или слишком завуалирована. Я статью перечитал в общей сложности около 15 раз, это ни капли не дало никакого понимания, но есть масса запутывающих мест, о которых я написал.
wataru
20.06.2024 04:14А теперь, вместо того, чтобы двигать всех черепах на C на каждой итерации, можно двигать их по одной сразу на все предыдущие С. Ну это просто перестановка действий.
Вот там где вы t берете - там же будет какая-то позиция, которая получается, если к какой-то изначальной клетке применить все C на всех предыдущих итерациях.
Тогда сначала код упрастится до:
create List<Turtles> T commands result while (T not empty) Turtles u = GetFirst(T) t = u move (result) commands C = FindPath(t, exit) remove T u result += C return print resultА дальше можно просто заменить while/GetFirst на простой цикл по T. И получится мое решение.
Zara6502
20.06.2024 04:14А теперь, вместо того, чтобы двигать всех черепах на C на каждой итерации, можно двигать их по одной сразу на все предыдущие С. Ну это просто перестановка действий.
не понял
Вот там где вы t берете - там же будет какая-то позиция, которая получается, если к какой-то изначальной клетке применить все C на всех предыдущих итерациях.
Ну так все Т на каждой итерации и смещаются по С, никаких предыдущих просто не будет, у вас лабиринт всегда в актуальном состоянии. Если вам хочется, вы можете все черепашки включая t двигать сразу, только это ничего не изменит.
А дальше можно просто заменить while/GetFirst на простой цикл по T. И получится мое решение.
объяснение непонятно.
вы сначала получаете список команд, потом двигаете черепашек, можете двигать одновременно, это не принципиально. У вас нет никакого прошлого списка команд, это вам просто не нужно, так как все черепашки смещаются онлайн без задержек.
wataru
20.06.2024 04:14Хорошо, вот у вас в коде есть
foreach (T) move (C) exclude (t) groupby (cells)Во-первых, вы согласны, что не объединяя по ячейкам, алгоритм все так же работает? Более того, он выдаст тот же результат, потому что, если 2 значения в мульти-множестве T когда-то совпадут и вы выведете одно из них из лабиринта, то второе тоже выйдет из лабиринта и окажется в выходе. Потом, на какой-то следующей итерации,
FindPath(t, exit)для того значения вернет пустой список.
Во-вторых, можно exit из множества T не удалять по той же причине. Ну возьмете вы его потом на следующей итерации в качестве t и исключите, приписав пустой список к командам.
Достаточно токльо удалять из T тот t, который вы из лабиринта выводите.Теперь у вас там в алгоритме:
foreach (T) move (C) exclude (t)Теперь, давайте вместо move сделаем "отложенное движение". Команда DelayedMove не будет двигать клетку сразу, а будет возвращать какой-то тип "фантом", где записана начальная клетка и последовательность действий. И будет команда actualize, которая, собственно, эти действия применит.
create List<Turtles> T commands result while (T not empty) Turtles t = GetFirst(T).actualize() commands C = FindPath(t, exit) T2 = {} foreach x in (T): if (x == t) continue Phantom u = DelayedMove(x.actualze(), C) T2 += u T = T2 result += C return print resultСогласны пока, что этот код полностью эквивалентен вашему (пока не думайте про скорость или память. Мы про абстрактный алгоритм говорим)? Ну, вычисляется значение t чуть позже. Аналогия: мы вместо int i=4 храним string s="2+2" и перед использованием значения в вычислениях вызваем eval().
Следующий шаг: мы не будем вычислять ячейку при DelayedMove в цикле. Вместо этого будем дополнять списко команд. Вместо
Phantom u = DelayedMove(x.actualze(), C)
сделаемPhantom u = AppendMoves(x, C)create List<Turtles> T commands result while (T not empty) Turtles t = GetFirst(T).actualize() commands C = FindPath(t, exit) T2 = {} foreach x in (T): if (x == t) continue u = AppendMoves(x, C) T2 += u T = T2 result += C return print resultПока все понятно?
А теперь главное: в моментt = GetFirst(T).actualize()вот это GetFirst(t) содержит ровно тот же список команд, как и result. Ведь мы же там на каждой итерации внешнего while приписываем к списку команд C. И этот же C приписываем к result. Поэтому нам не надо вычислять все эти команды в фантомах. Мы знаем, что команды будут result. Можно выкинуть циклforeach x in (T):и просто применять result к GetFirst(T):create List<Turtles> T commands result while (T not empty) Turtles t = DelayedMove(GetFirst(T), result).actualize() commands C = FindPath(t, exit) T = T - x result += C return print resultНу и, раз тут отложенные вычисления сразу же актуализируются, можно просто двигать сразу.
Потом у нас остался цикл while, где из множества берется первый элемент и удаляется. Заменяем просто на for. Вот и получился мой алгоритм.
Zara6502
20.06.2024 04:14спасибо за попытку объяснить, но я совсем не понял что вы проделали. попробую комментировать последовательно и разбираться.
вы согласны, что не объединяя по ячейкам, алгоритм все так же работает?
да, но это очевидное упрощение и нет причин его не использовать, например при дебаге вы не будете завалены лишними данными. привычка.
можно exit из множества T не удалять по той же причине
по тем же причинам освобождаем память, делаем данные компактнее и проще для отладки
Теперь, давайте вместо move сделаем "отложенное движение". Команда DelayedMove не будет двигать клетку сразу, а будет возвращать какой-то тип "фантом", где записана начальная клетка и последовательность действий
ну пока понятно что сделано, но непонятно зачем?
И будет команда actualize, которая, собственно, эти действия применит.
ну ок
Turtles t = GetFirst(T).actualize()и что вы тут применяете?
Согласны пока, что этот код полностью эквивалентен вашему
нет, потому что не понимаю изменений
Ну, вычисляется значение t чуть позже
в каком смыслу "чуть позже"? оно там же где и было, только добавили actualize которая что?
Следующий шаг: мы не будем вычислять ячейку при DelayedMove в цикле. Вместо этого будем дополнять списко команд. Вместо
Phantom u = DelayedMove(x.actualze(), C)Тут я уже окончательно потерялся, я не понимаю идею.
Пока все понятно?
Совсем непонятно.
А теперь главное: в момент
t = GetFirst(T).actualize()вот это GetFirst(t) содержит ровно тот же список команд, как и resultt - это черепашка из списка, там нет команд. А GetFirst() просто например делает t = T[0]
Ведь мы же там на каждой итерации внешнего while приписываем к списку команд C. И этот же C приписываем к result
Ну в result у нас набор команд, а С пока еще не определен.
Поэтому нам не надо вычислять все эти команды в фантомах
С фантомами я ничего не понял.
Мы знаем, что команды будут result
Тоже не ясно на чем основано утверждение.
Можно выкинуть цикл
foreach x in (T):и просто применять result к GetFirst(T)Возможно это какая-то оптимизация, но мне не ясна его логика. Зачем нам весь result применять к одному элементу списка черепашек?
Ну и, раз тут отложенные вычисления сразу же актуализируются, можно просто двигать сразу.
Я не знаю что происходило до этим слов, но я сказал уже что черепашек можно двигать вместе с Т, это ни на что не влияет, но это и не меняет сам код.
Заменяем просто на for
Я не знаю как в вашем ЯП, но в Си-ориентированных while и for это по сути одно и то же, поэтому сама необходимость замены непонятна.
while(T not empty)for(; T not empty;)вот варианты в C#, та же конструкция, просто for позволяет одной строкой оформлять инициализацию, условие и итераторы, чисто косметическое действие.
wataru
20.06.2024 04:14да, но это очевидное упрощение и нет причин его не использовать
по тем же причинам освобождаем память, делаем данные компактнее и проще для отладки
Это упрощает объяснение. Допустите это пока что.
Turtles t = GetFirst(T).actualize()и что вы тут применяете?
Во множестве Т у нас с прошлого шага же не координаты, а начальная точка + список команд. Мы же там не применяли комады Move, а делали DelayedMove, и в результате получили какой-то PhantomMove вместо координат черепашки. Их во множество T и сложили.
А вот в actualize() мы команды применяем и получаем координаты точки. Ну, только косяк с первой итерацией. Допустим, что у координаты тоже можно вызвать actualize, который ничего не делает.
Таким образом я переношу вычисления на следующие итерации.
Пока это кажется глупым и лишними действиями, но я хочу шаг за шагом перобразовать ваш код в мой. Он же сильно проще, правда? И при этом не требует памяти под множество T, а выдает те же самые команды. За счет лишь другого порядка вычисления координат черепах.
Этот момент теперь понятен?
Zara6502
20.06.2024 04:14Во множестве Т у нас с прошлого шага же не координаты, а начальная точка + список команд. Мы же там не применяли комады Move, а делали DelayedMove, и в результате получили какой-то PhantomMove вместо координат черепашки. Их во множество T и сложили.
проще понимать когда вы озвучиваете всю концепцию, а потом детализируете отдельные блоки. Зачем задерживать ходы мне непонятно, отсюда и непонятна вся движуха.
А вот в actualize() мы команды применяем и получаем координаты точки. Ну, только косяк с первой итерацией. Допустим, что у координаты тоже можно вызвать actualize, который ничего не делает.
и зачем?
Таким образом я переношу вычисления на следующие итерации.
Ну вот смотрите как я это вижу - у вас таймер, который раз в 10 секунд издаёт сигнал, по сигналу вы открываете дверь. Вы предлагаете не по сигналу дверь открывать, а через 2 секунды после него. Ну ок. Зачем? Обычно изложение алгоритма идет с постановки задачи. Я хочу сделать то-то и то-то, для этого я делаю то-то и то-то, что позволяет сделать так-то и так-то. А вы открыли черный ящик, показываете болтик и предлагаете его крутить, зачем-почему?
Пока это кажется глупым и лишними действиями, но я хочу шаг за шагом перобразовать ваш код в мой
Ну в моей голове это так не работает. Нужно объяснение действия, тогда и будет понимание. Дерганье за мочку уха когда гремит гром - это не из области рационального, это суеверие, а объяснение что мы так стимулируем внутреннее ухо, чтобы нивелировать действие ультразвука - это понятно.
Этот момент теперь понятен?
Нет ) Мне кажется куда проще просто объяснить свою реализацию чем придумывать лишние ступени которые только путают.
wataru
20.06.2024 04:14+1Ну вот реализация:
create List<Turtles> T commands result for t in T: // Вычисляем, где оказалась бы черепаха, если бы она начинала в клетке v. u = Apply(t, commands) // Приписываем команды, выводящие черепаху с позиции u к ответу. С = FindPath(t, exit) commands += С return commandsТут также ответ строится из кусков, которые выводят какую-то черепаху из лабиринта (C). Разница с вашей, что вы на очередной кусок двигаете всех черепах циклом на каждой итерации. А я беру одну конкретную черепаху и двигаю ее на все прошлые куски. Я пытался по шагам показать, почему этот алгоритм эквивалентен вашему, просто меняя код на эквивалентный, но вам, к сожалению, не зашло.
Вот аналогия - в статье есть картинка с синими точками и черными горизонтальными линиями между двумя "уровнями" лабиринта. Вот представьте у вас nm-1 уровней. Это, фактически, изображения вашего множества T на каждой итерации. Вы берете и на каждой итерации и продолжаете все черные линии (кроме той, что вышла) в следующий уровень. Я же беру первую точку в первом уровне и рисую из нее линию в первый уровень. На следующей итерации беру вторую точку из первого уровня и рисую из нее линию во второй уровень. На третьей итерации беру третью точку из первого уровня и рисую из нее линию до третьего уровня. И т. д. Точки те же, линии те же, но прорядок их прорисовки разный.
Zara6502
20.06.2024 04:14Я же беру первую точку в первом уровне и рисую из нее линию в первый уровень. На следующей итерации беру вторую точку из первого уровня и рисую из нее линию во второй уровень. На третьей итерации беру третью точку из первого уровня и рисую из нее линию до третьего уровня. И т. д. Точки те же, линии те же, но прорядок их прорисовки разный.
и каким образом вы получаете данные для других уровней если у вас еще эти команды неизвестны?
Разница с вашей, что вы на очередной кусок двигаете всех черепах циклом на каждой итерации
а как вы можете получить положение каждой черепахи и набор команд до того как вы передвинете черепах?
Вот вам простой лабиринт
... чE. Ч..мы выводим черепашку "ч" (2 строка) командой вправо, только применив эту команду к черепашке "Ч" (3 строка) мы сможем определить что она оказалась в позиции под "Е" и только после этого создать новый набор команд уже для неё. Пока вы не сделали команды для "ч" и не передвинули "Ч" вы не знаете в каком месте она окажется, а значит и не можете ничего сделать с этой черепашкой. То есть набор команд строго последовательный.
wataru
20.06.2024 04:14+2и каким образом вы получаете данные для других уровней если у вас еще эти команды неизвестны?
На i-ой итерации все данные извесны же! У нас уже есть спискок команд с предыдущих итераций (в commands).
а как вы можете получить положение каждой черепахи и набор команд до того как вы передвинете черепах?
Вот картинка. Слева ваш алгоритм. Справа мой. Каждый прямоугольник - это множество T. Черные линии показывают применение команд к элементам. Зеленый круг - выход. Синий - это ваше t и мое u. Красным показаны команды, которые переводят эту выбранную точку в конец.
Вот на первой итерации вы вычислили списко комманд C1. Мой алгоритм тоже. Вы переместили все точки, я лишь сложил C1 в commands. На следующей итерации вы получили синий круг как FindFirst, А я применил команды из commands. Получил тот же синий круг. Высчитал те же C2. Опять, вы все линии продлили, а я лишь дописал список комманд, который применю на следующей итерации.
Вы на каждой итерации продлеваете линии, а я на каждой итерации рисую одну линию.
Zara6502
20.06.2024 04:14На i-ой итерации все данные извесны же! У нас уже есть спискок команд с предыдущих итераций (в commands).
вы пишете о том, что вы не заканчиваете работу с первым уровнем и сразу идёте на второй, то есть вы говорите о том что на итерации i вы получаете данные итерации i+1
Вы на каждой итерации продлеваете линии, а я на каждой итерации рисую одну линию.
вы наивный вариант что ли используете?
wataru
20.06.2024 04:14+1вы пишете о том, что вы не заканчиваете работу с первым уровнем и сразу идёте на второй, то есть вы говорите о том что на итерации i вы получаете данные итерации i+1
Ну... да. Так и вы получаете команды на i-ой итерацци (в C) и используете их, чтобы получить координаты черепах для следующих итераций. Только вы в i-ой же итерации эти команды применяете. А я их применяю на следующих итерациях.
вы наивный вариант что ли используете?
Не знаю, какой из них наивный, но количество действий такое же. А код короче и проще. А требования по памяти даже меньше, ибо не надо хранить множество черепах.
Вы картинку посмотрели? Неужели даже с ней ничего не понятно?
Zara6502
20.06.2024 04:14Ну... да
Вот смотрите, вы тут говорите "ну да" для факта что вы используете данные итерации i+1 на этаме i, а дальше пишете
А я их применяю на следующих итерациях
то есть с точностью да наоборот по отношению к предыдущему тексту. Вот и как вас понимать?
Вы картинку посмотрели? Неужели даже с ней ничего не понятно?
Если вы не пользуетесь Т, то вам придется обходить все nm-1 клетки и применять команды, это наивный алгоритм. Ну это как пузырёк и quicksort.
Я понял что вы делаете. Это жутко ) Но да, это будет работать, как-то и на больших лабиринтах даже когда-то выполнится )
Я когда читал статью я и думал о чем-то оптимальном, но никак не о наивном решении.
wataru
20.06.2024 04:14+2Вот смотрите, вы тут говорите "ну да" для факта что вы используете данные итерации i+1 на этаме i, а дальше пишете
Нет. Я ответил на "на итерации i вы получаете данные итерации i+1". А где еще мы их можем получить, если не на итерации i? Мы их там вычисляем, чтобы на следующей итерации использовать.
то есть с точностью да наоборот по отношению к предыдущему тексту. Вот и как вас понимать?
Вы сказали "получаете" а не "используете".
вам придется обходить все nm-1 клетки и применять команды
Ура! Вы, наконец-то поняли этот алгоритм. Ведь поняли же?
Если вы не пользуетесь Т, то вам придется обходить все nm-1 клетки и применять команды, это наивный алгоритм. Ну это как пузырёк и quicksort.
Нет, оно имеет ровно ту же вычислительную сложность: O(n^2m^2). С одной стороны, ваш алгоритм может чуть быстрее выполнится на каких-то лабиринтах из-за того, что вы каких-то черепашек раньше вычеркиваете. С другой стороны, у вас там какие-то лишние вычисления, чтобы из множества повторяющиеся элементы удалять.
Zara6502
20.06.2024 04:14Ура! Вы, наконец-то поняли этот алгоритм. Ведь поняли же?
Ну он ужасен )
Кстати он у вас не будет работать по простой причине, пока вы например выполните nm/2 команд у вас черепаха может убежать в эту зону и вы просто никогда на неё не попадёте последующими командами. Так что без контроля за черепахами никак.
Касательно всё того же моего вопроса про попадание на ту же позицию, вот у вас набор команд применится к i+1 элементу и черепашка убежит на позицию i-1, с которой вы уже отработали, и всё.
оно имеет ровно ту же вычислительную сложность
худший вариант - да, но не средний.
ваш алгоритм может чуть быстрее выполнится на каких-то лабиринтах из-за того, что вы каких-то черепашек раньше вычеркиваете. С другой стороны, у вас там какие-то лишние вычисления, чтобы из множества повторяющиеся элементы удалять.
Ну возьмите лабиринт 10х10 без стен, выход в позиции нижнего правого угла, 9 команд вниз и 9 вправо и в моём случае лабиринт будет пуст, а ваш обработает только неполные две строки. Я понимаю что для BigO нотации это не имеет значения, но для практической реализации - имеет.
wataru
20.06.2024 04:14+2Кстати он у вас не будет работать по простой причине, пока вы например выполните nm/2 команд у вас черепаха может убежать в эту зону и вы просто никогда на неё не попадёте последующими командами. Так что без контроля за черепахами никак.
Ну бред же. В какую зону? Я там где алгоритм формально математически давал, даже доказал формально, что он работает. И уже десяток комментариев пытаюсь вам разъяснить, что алгоритм полностью эквивалентен вашему.
худший вариант - да, но не средний.
Вы игнорируете вычисления, которые тратите на фильтрацию множества.
Ну возьмите лабиринт 10х10 без стен
После 9 ходов вправо и 9 ходов вниз, мой алгоритм для каждой очередной черепахи вычислит, что она уже в выходе (максимум за 18 проверок) и ничего в ответ дописывать не будет. Ну, выполнит он 8*10*18/2 = 720 лишних проверок (18 - это максимальная длина пути, но не все черепахи проходят этот путь. Кто-то выйдет после всего нескольких шагов. В среднем как раз по 9 проверок на черепаху и будет).
С другой стороны, ваш алгоритм на первой итерации должен будет как-то удалить 10 черепах. Как? Если там хотя бы одна проверка в хешсете, что черепаха такая уже есть, то это 99 проверок только на первой итерации. На второй итерации еще 90. Потом 80.. Итого 550 проверок. Ну и 55 для оставшихся черепах, т.е. суммарно около 600. Уже разницы почти нет. 720 проверок у меня против 600 у вас. Но у вас там какой-то хешсет или какая-нибудь хитрая структура вроде массива поколений со списками понадобится, так что. можно смело умножать на 3. С другой стороны и у меня проверок будет 2 - что черепаха в конце и что есть ли стена дальше. В итоге даже в этом лучшем для вас случае по количеству вычислений наши алгоритмы получаются примерно равны.
Zara6502
20.06.2024 04:14Ну бред же
ну вы согласились что ваш алгоритм наивный, то есть обрабатывает nm-1 состояний, а значит когда вы прошли nm/2 состояний вы не сможете вернуться на предыдущие в любом случае, но нет никакой гарантии что в эти клетки не попадут черепашки по результатам работы nm/2 маршрутов.
Я там где алгоритм формально математически давал, даже доказал формально, что он работает
я не силён в математике, поэтому не могу судить.
И уже десяток комментариев пытаюсь вам разъяснить, что алгоритм полностью эквивалентен вашему.
Выше вы как раз подтвердили что он у вас наивный, то есть обрабатывает (пытается) все возможные состояния. Мой вариант этого не делает и это принципиальные отличия.
Вы игнорируете вычисления, которые тратите на фильтрацию множества.
ну даже если там будет O(nlogn) то это очень не близко к O(n^2m^2). Тем более это постоянно убывающая последовательность.
После 9 ходов вправо и 9 ходов вниз, мой алгоритм для каждой очередной черепахи вычислит, что она уже в выходе
Ну вот видите, у вас уже какой-то другой алгоритм снова. Тот, про который вы сознались в последнем случае будет, без вариантов, считать nm-1 состояний независимо от маршрутов, причем отталкиваясь не от положений черепашек, а от положения клеток (что для меня и странно и мне сдаётся, что всё же я вас не так понимаю, а вы не можете объяснить работу вашего алгоритма, потому что опять у нас расхождения в показаниях).
С другой стороны, ваш алгоритм на первой итерации должен будет как-то удалить 10 черепах. Как?
На самом деле можно вообще обойтись без хэшсета и процесса удаления как такового, можно ограничиться фиксированным массивом с доступом O(1) и индексатором размера. Тогда конечно потребуется nm-1 памяти, но зато работать будет быстро. Операция "удаления" будет просто копированием элемента массива с уменьшением индексатора.
Если там хотя бы одна проверка в хешсете, что черепаха такая уже есть, то это 99 проверок только на первой итерации
пока что мы опять запутались в вашем алгоритме, я уже не знаю от чего мне отталкиваться. если от наивного алгоритма, то у вас проверок на стены и финиш в принципе не должно быть, но вы о них пишете тут:
С другой стороны и у меня проверок будет 2 - что черепаха в конце и что есть ли стена дальше
получается вы тоже проверяете и на стены, что не согласуется с тем о чем писал я и на что вы согласились как на ваш алгоритм.
опять путаница.
В итоге даже в этом лучшем для вас случае по количеству вычислений наши алгоритмы получаются примерно равны.
Ну пока рано даже предположения делать.
wataru
20.06.2024 04:14ну вы согласились что ваш алгоритм наивный, то есть обрабатывает nm-1 состояний, а значит когда вы прошли nm/2 состояний вы не сможете вернуться на предыдущие в любом случае, но нет никакой гарантии что в эти клетки не попадут черепашки по результатам работы nm/2 маршрутов.
Еще раз посмотрите на алгоритм. Мы перебираем НАЧАЛЬНЫЕ точки черепах. Не те, куда они переместились, а те, где они могли быть только в самом начале.
Выше вы как раз подтвердили что он у вас наивный, то есть обрабатывает (пытается) все возможные состояния. Мой вариант этого не делает и это принципиальные отличия.
Да те же самые состояния мой обрабатывает. Только нет оптимизации "выкинуть слившихся черепах".
На самом деле можно вообще обойтись без хэшсета и процесса удаления как такового, можно ограничиться фиксированным массивом с доступом O(1) и индексатором размера.
Все равно несколько операций: взять черепаху из массива, посмотреть, есть ли пометка в массиве пометок, записать в новый массив.
то у вас проверок на стены и финиш в принципе не должно быть
Я же там двигаю черепаху на каждой итерации. И вот "лишние" операции происходят из-за того, что я двигаю черепаху, которая у вас бы раньше удалилась за счет слияния. И вот эти "лишние" движения - это прикладывание команд к черепахе - а там как раз проверка на стены и конец.
Ну пока рано даже предположения делать.
Давайте напишем наши алгоритмы и сравним вывод и скорость работы? Вам С++ знаком?
Zara6502
20.06.2024 04:14Еще раз посмотрите на алгоритм. Мы перебираем НАЧАЛЬНЫЕ точки черепах. Не те, куда они переместились, а те, где они могли быть только в самом начале.
это мне понятно, но непонятно почему гарантируется что например на последней итерации все черепашки выйдут из лабиринта. пока я склонен считать что пока вы последовательно идёте по клеткам у вас может появиться ситуация, когда одна (как минимум) черепашка окажется в некоем тупике, и последующие команды её оттуда не выведут.
Да те же самые состояния мой обрабатывает. Только нет оптимизации "выкинуть слившихся черепах".
опять 25, выше же вы написали что перебираете ВСЕ точки, мой алгоритм этого НЕ делает, в этом его смысл. И так как вы не следите за черепашками, а я слежу, то мне нет нужды строить маршруты от пустых клеток.
Все равно несколько операций: взять черепаху из массива, посмотреть, есть ли пометка в массиве пометок, записать в новый массив.
Ну не придумывайте, вы так же берёте черепах, только у вас это всегда nm-1 штук, а у меня с каждой итерацией их всё меньше и меньше, маршруты у меня короче, их тоже меньше, у вас результирующий маршрут в среднем будет длиной (n/2+m/2)*(nm/2), а у меня ниже этого значения.
Я же там двигаю черепаху на каждой итерации. И вот "лишние" операции происходят из-за того, что я двигаю черепаху, которая у вас бы раньше удалилась за счет слияния. И вот эти "лишние" движения - это прикладывание команд к черепахе - а там как раз проверка на стены и конец.
Зачем? В том понимании вашего алгоритма, которое сформировалось у меня у вас будет ровно nm-1 маршрутов, и они все ведут к выходу без столкновений со стенами.
Давайте напишем наши алгоритмы и сравним вывод и скорость работы?
В процессе, но я не могу гарантировать что это будет быстро, я не умею писать как робот, для меня это процесс сравнимый с написанием стихов - если нет вдохновения, то ничего не пишу.
Если бы полностью знал ваш алгоритм, я бы его реализовал у себя и можно было бы сравнить, ну или вы берите мой и пишите, но я чужой код плохо читаю, так что проверить не смогу.
Вам С++ знаком?
Поверхностно, я могу, если припёрло, конвертировать его в C# и то не всё. Но именно сам писать на нём не умею. Я пользуюсь C#.
wataru
20.06.2024 04:14но непонятно почему гарантируется что например на последней итерации все черепашки выйдут из лабиринта.
Ну так потому что каждая черепашка имеет одну конкретную клетку, где она начинает. На какой-то итерации эта клетка будет рассматриваться и путь дополнится так, что бы черепашка дошла до конца (с той позиции где она будет после выполнения текущего пути).
Поверхностно, я могу, если припёрло, конвертировать его в C# и то не всё. Но именно сам писать на нём не умею. Я пользуюсь C#.
Надеюсь, вам моя реализация вашего алгоритма будет понятна.
Вот код. Ваш алгоритм - Algo2(). Мой - Algo1(). До этого идет класс Maze, который логику в лабиринте реализует.
Кстати, там проверка работы алгоритмов есть, и оба алгоритма ее проходят.
Результат работы на абсолютно пустом лабиринте (kMaze3):
Clever algo took 64094ns Naive algo took 70064nsТ.е. в худшем случае "наивный" алгоритм оказался всего на 7% медленнее. Не в разы и не на порядки. И это я ваш быстрый алгоритм вылизал до предела, с использованием массива поколений. Никаких аллокаций памяти и хешей. Чуть-чуть где-то менее оптимально его напишите и будет он даже хуже "наивного". Соответственно, не такой уж он "наивный".
На лабиринте со стенами (kMaze2) результат:
Clever algo took 5005ns Naive algo took 4003nsТ.е. наивный алгоритм оказывается еще и быстрее ваших оптимизаций во многих тестах.
Можете сами скомпилировать, или переписать на C#, если не верите.
Zara6502
20.06.2024 04:14Ну так потому что каждая черепашка имеет одну конкретную клетку, где она начинает. На какой-то итерации эта клетка будет рассматриваться и путь дополнится так, что бы черепашка дошла до конца (с той позиции где она будет после выполнения текущего пути).
Вот и непонятно почему nm-2 действий не уведут черепашку в такие дали, откуда она уже не вернется.
Надеюсь, вам моя реализация вашего алгоритма будет понятна.
я плохо понимаю чужой код, во всяком случае то что написано внутри AlgoX соответствует тому о чем мы уже говорили, остальное нужно разбирать.
И это я ваш быстрый алгоритм вылизал до предела, с использованием массива поколений. Никаких аллокаций памяти и хешей. Чуть-чуть где-то менее оптимально его напишите и будет он даже хуже "наивного". Соответственно, не такой уж он "наивный".
Ну вот вижу уже ненужный блок:
for (int x = 0; x < m.Width(); ++x) {for (int y = 0; y < m.Height(); ++y) {if (m.IsWall(x, y)) continue;turtles.emplace_back(x, y);}}
Тут тоже неправильная реализация
m.ApplyCommands(turtles[i].first, turtles[i].second, c);Это не понял
if (!m.IsExit(turtles[i].first, turtles[i].second) && was[turtles[i].first][turtles[i].second] < stage) {was[turtles[i].first][turtles[i].second] = stage;turtles[last_pos++] = turtles[i];}
Эта операция лишняя
turtles.resize(last_pos);---
Т.е. наивный алгоритм оказывается еще и быстрее ваших оптимизаций во многих тестах.
ну пока у вас кривенькая реализация, поэтому рано говорить.
Можете сами скомпилировать, или переписать на C#, если не верите.
Не делайте из меня монстра, я не сомневаюсь в ваших словах и способностях. Чужое переписывать не стану, я это буду делать в 10 раз дольше и потом не буду понимать если будут ошибки - где их искать.
Предлагаю перейти в личные сообщения, а то у автора истерика началась.
wataru
20.06.2024 04:14+1Вот смотрите, вы тут говорите "ну да" для факта что вы используете данные итерации i+1 на этаме i, а дальше пишете
Нет. Я ответил на "на итерации i вы получаете данные итерации i+1". А где еще мы их можем получить, если не на итерации i? Мы их там вычисляем, чтобы на следующей итерации использовать.
то есть с точностью да наоборот по отношению к предыдущему тексту. Вот и как вас понимать?
Вы сказали "получаете" а не "используете".
вам придется обходить все nm-1 клетки и применять команды
Ура! Вы, наконец-то поняли этот алгоритм. Ведь поняли же?
Если вы не пользуетесь Т, то вам придется обходить все nm-1 клетки и применять команды, это наивный алгоритм. Ну это как пузырёк и quicksort.
Нет, оно имеет ровно ту же вычислительную сложность: O(n^2m^2). С одной стороны, ваш алгоритм может чуть быстрее выполнится на каких-то лабиринтах из-за того, что вы каких-то черепашек раньше вычеркиваете. С другой стороны, у вас там какие-то лишние вычисления, чтобы из множества повторяющиеся элементы удалять.
Zara6502
20.06.2024 04:14Нет. Я ответил на "на итерации i вы получаете данные итерации i+1". А где еще мы их можем получить, если не на итерации i? Мы их там вычисляем, чтобы на следующей итерации использовать.
я ошибся в оформлении текста, имеется в виду "использовать".
wataru
20.06.2024 04:14+1Ну вот, вы ошиблись в оформлении текста, а потом меня "Вот и как вас понимать?"
Я не использую на i-ой итерации данные для i+1. Я их там считаю.
Zara6502
20.06.2024 04:14Ну вот, вы ошиблись в оформлении текста, а потом меня "Вот и как вас понимать?"
пардон
Mingun
20.06.2024 04:14Для меня тут очевидно, что "проделав данный маршрут" черепаха могла вернуться в исходную точку, а значит состояние не изменилось, а значит она не перешла в другую клетку, а значит количество вариантов нового расположения осталось неизменным.
Для данной черепахи да, её состояние не изменилось, но для всего лабиринта — в нём стало на (как минимум) одну черепаху меньше.
Zara6502
20.06.2024 04:14И как вы это докажите? Я могу вам привести массу конфигураций лабиринтов и положений черепахи где это не будет работать.
Mingun
20.06.2024 04:14Докажу что? Что черепах в лабиринте стало меньше? Это доказывать не надо, это по построению алгоритма работает, так как каждая итерация указанного алгоритма выгоняет минимум одну черепаху из лабиринта (может больше, если другие черепахи оказались на пути выгоняемой).
Zara6502
20.06.2024 04:14Докажу что? Что черепах в лабиринте стало меньше? Это доказывать не надо, это по построению алгоритма работает
в моем алгоритме - да, потому что когда моя черепашка двигается к выходу - она из него гарантированно выходит. почему у вас черепашки могут перемещаться не на выход - ну это вопрос к вам, а не ко мне. потому что я продолжаю вашу логику - если черепашку отправили не на выход, то откуда появляется уверенность, что какая-то другая черепашка в этот момент вышла?
Mingun
20.06.2024 04:14Потому что за одну итерацию мы двигаем на выход одну черепаху из одной конкретной клетки. Вот она и выходит. Черепахи из других клеток могут как выйти, так и просто переместиться на новую позицию в лабиринте (в вырожденном случае новая позиция совпадает со старой). На следующей итерации мы рассматриваем уже оставшихся черепах на этих новых позициях. Всё точно так же, как и у вас.
Zara6502
20.06.2024 04:14Потому что за одну итерацию мы двигаем на выход одну черепаху из одной конкретной клетки
нет, я приводил уже цитаты где про выход вообще ни слова.
На следующей итерации мы рассматриваем уже оставшихся черепах на этих новых позициях. Всё точно так же, как и у вас.
Значит и описание алгоритма должно совпадать, чего мы не наблюдаем.
Mingun
20.06.2024 04:14+1Читайте статью внимательнее, всё там сказано (раздел Работа над ошибками):
Давайте просто выберем одну произвольную клетку и напишем последовательность команд, выводящую черепашку к выходу из нее. Если черепашка в самом деле оказалась в данной клетке, то нам повезло и делать больше ничего не требуется.
...
Однако, если чуда не случилось, то черепаха сейчас все еще находится где-то в лабиринте.Это одна итерация. Явно об этом не сказано, но по контексту понятно, что синие точки означают новые позиции оставшихся черепах после применения к ним маршрута для первой черепахи.
На следующем шаге мы выберем любую другую синюю точку (клетку с черепахой) и построим от нее маршрут до выхода. Пройдя по маршруту, количество возможных для черепахи клеток опять уменьшится хотя бы на одну. Будем продолжать в том же духе, пока синие клетки не закончатся совсем.
Это последующий цикл из итераций.
Zara6502
20.06.2024 04:14Однако, если чуда не случилось, то черепаха сейчас все еще находится где-то в лабиринте.
автор пишет что он применил путь, но черепаха не попала на выход. это странно.
Явно об этом не сказано, но по контексту понятно, что синие точки означают новые позиции оставшихся черепах после применения к ним маршрута для первой черепахи
Вы уверены что именно так оформляются алгоритмы?
Это последующий цикл из итераций.
Я об этом так же писал автору с вопросом, в предыдущем абзаце черепаха до выхода почему-то не дошла, а в этом он пишет о том, что она гарантированно вышла. Нестыковка.
Mingun
20.06.2024 04:14Вы путаете двух черепах. Одна — ту, которую мы вели — дошла. Вторая — любая другая — могла дойти, а могла и нет. Вы опять невнимательно прочитали, отсюда и непонятки.
Zara6502
20.06.2024 04:14Однако, если чуда не случилось, то черепаха сейчас все еще находится где-то в лабиринте.
Я понимаю эту фразу как - если она не попала на выход то где-то еще в лабиринте и находится, то что автор здесь понимает другую черепаху я не могу знать.
wataru
20.06.2024 04:14+1Что вы спорите, вы же выше уже этот же самый алгоритм привели в виде псевдокода?!
Для меня тут очевидно, что "проделав данный маршрут" черепаха могла вернуться в исходную точку,
Но окажется во множестве T на какой-то итерации та же клетка, что была во множестве на какой-то предыдущей итерации. В чем проблема? Может даже это одна и та же черепаха сама вернулась в свою прошлую точку. Но мощность множества T уменьшается же.
Zara6502
20.06.2024 04:14Что вы спорите, вы же выше уже этот же самый алгоритм привели в виде псевдокода?!
Я пишу о своем алгоритме, то о чем в статье пишет автор мне пока непонятно до сих пор.
Но окажется во множестве T на какой-то итерации та же клетка, что была во множестве на какой-то предыдущей итерации. В чем проблема? Может даже это одна и та же черепаха сама вернулась в свою прошлую точку. Но мощность множества T уменьшается же.
она уменьшается в моем алгоритме, потому что я там гарантирую выход одной черепашки всегда. что происходит в статье и какие там озвучены смыслы я пока не понял, а все рассуждения на тему только путают, не ясно до сих пор зачем вести черепаху НЕ к выходу.
wataru
20.06.2024 04:14+1Я пишу о своем алгоритме, то о чем в статье пишет автор мне пока непонятно до сих пор.
Уверяю вас, в статье описан ровно этот же самый алгоритм. Точь-в-точь. Да, автор не выписал псевдокод, и не был очень формален, но алгоритм именно этот. Допустите это. И попробуйте, исходя из этой предпосылки, снова взглянуть на статью - сразу найдете все ключевые идеи из вашего алгоритма там описанные.
Zara6502
20.06.2024 04:14это называется - натянуть сову на глобус, я в статье много чего нашел что автор даже прокомментировать не может.
wataru
20.06.2024 04:14+1Да все нормально автор комментирует. Я вот вообще не понимаю, на чем вас заклинило, что вы слова нескольких человек вообще не можете воспринять.
Zara6502
20.06.2024 04:14ну я всё понял, резюмирую:
В статье небрежное оформление текста вводящее в заблуждение.
Мой косяк с тем, что я ожидал увидеть у вас решение близкое к оптимальному, а не наивное.
Так же ваше несколько вольное обращение с изложением мыслей, масса допущений, которые вы воспринимаете как должное, а я просто без них не понимал о чем вы говорите (например с i -> i+1 мы до сих пор не разобрались в другом треде).
Собственно вот этот набор и привёл к тому что я не мог понять о чем вы говорите.
Alexandroppolus
20.06.2024 04:14+1Кстати, задачу можно решить, даже если мы не знаем сам лабиринт и клетку с выходом, а знаем лишь, что путь от черепахи до выхода точно есть. Просто перебираем все возможные лабиринты (без закрытых комнат), для каждого перебираем все возможные клетки выхода, и для каждой пары (лабиринт+выход) применяем вышеуказанный способ.
Zara6502
20.06.2024 04:14Решил реализовать свой вариант решения, сделал универсальный обход лабиринта, наверное по результату оформлю в виде статьи.
На анимации белые точки это построение маршрутов от выхода, а красные - максимально длинный путь, он просто как пример, выбирая любую точку можно дойти до выхода.
demitryy Автор
20.06.2024 04:14+2То, что выбрав любую точку можно дойти до выхода доказывать как раз не нужно, т.к. это следует из словосочетания "связный лабиринт" :)
Zara6502
20.06.2024 04:14я не об этом, я о том что мне не требуется Дейкстра чтобы найти выход, информация о том как именно выйти строится во время обхода.
demitryy Автор
20.06.2024 04:14+1мне не требуется Дейкстра чтобы найти выход, информация о том как именно выйти строится во время обхода.
Да нет никакой разницы как вы его найдете, хоть dfs запустите. Речь же не о том. Задача стояла "придумайте алгоритм, который выпишет конечную последовательность". Это теоретическая задача, а не контест. Здесь никаких ограничений по времени и памяти нет у вас нет.
Zara6502
20.06.2024 04:14а причем здесь задача? я пишу о реализации своего алгоритма на ЯП, вы за контекстом треда следите.
demitryy Автор
20.06.2024 04:14а причем здесь задача? я пишу о реализации своего алгоритма на ЯП, вы за контекстом треда следите.
Так если задача не причем, почему пишите об этом здесь?
Zara6502
20.06.2024 04:14я уведомил заинтересованных о том, что будет сделано, будет странно писать об этом нигде. Здесь - тема, родившая обсуждение. Но в моём треде идёт разговор о моем алгоритме и моей программе, правда странно обсуждать в таком треде саму статью?
Zara6502
20.06.2024 04:14жаль, но я в статье так и не вижу алгоритма, если он есть, приведите пример его реализации, можно в виде блок-схемы или на любом условном языке.
wataru
20.06.2024 04:14Дано:
L - лабиринт
MakePath(v, L) - выдает последовательность ходов, чтобы перейти к выходу из клетки v. Можно, например, BFS найти все кратчайшие пути из конечной точки и развернуть их.Apply(v, c, L) - вычисляет, где окажется черепашка, если она была в клетке v и выполнит команды c. Тупо применяем команды по одной и двигаем позицию, если стена не мешает.
commands = {} for v - клетка в L: // Вычисляем, где оказалась бы черепаха, если бы она начинала в клетке v. u = Apply(v, commands, L) // Приписываем команды, выводящие черепаху с позиции u к ответу. commands += MakePath(u, L) return commandsZara6502
20.06.2024 04:14Какая связь этого текста и статьи? Где синие, белые и зеленые клетки? Где некая оптимизация, отчего-то же автор даже статью написал, а ваше решение это просто констатация факта - есть задача и мы её решаем. Автор в статье пишет о двух взаимоисключающих вещах, с одной стороны о ходах не приводящих к выходу, с другой - только о ходах приводящих к выходу. Я в своем алгоритме это описываю, автор - нет. На вопросы о таких противоречиях пишутся какие-то странные ответы.
Это похоже на урок по рисованию совы - рисуем два овала, а потом дорисовываем сову.
У вас нет функции которая запоминает для каждой клетки смещение после применения маршрута, то есть после того как вы доведёте первую черепаху вы не будете знать откуда вести вторую.
// Вычисляем, где оказалась бы черепаха, если бы она начинала в клетке v. u = Apply(v, commands, L) - она окажется на выходе, зачем это вычислять?// Приписываем команды, выводящие черепаху с позиции u к ответу. - вы вывели одну черепаху, теперь у вас нет никакой информации о том что у вас в лабиринте и где, на выходе у вас только один маршрут для одной позиции.
demitryy Автор
20.06.2024 04:14+1Где некая оптимизация, отчего-то же автор даже статью написал
Оптимизация чего? Я как автор статьи не совсем понимаю, о чем вы :)
Zara6502
20.06.2024 04:14Ваша статья не должна быть перечислением очевидного, на очевидное должна быть какая-то хитрая оптимизация, которую я из зашёл прочитать, кроме противоречивого текста путающего нестыковками я не увидел никакого вау решения. Вы просто предлагаете вывести черепашек по одной даже не описывая как именно, ведь изюминка там и должна быть. Я написал как сам алгоритм, так и предложил две оптимизации оного - это и есть материал для статьи.
wataru
20.06.2024 04:14+2Где синие, белые и зеленые клетки
Чуть упращено тут, не нужны эти клетки. Считайте, что все клетки синие, в цикле мы берем одну из них, проводим линию, потом дописываем ответ так, чтобы эта точка стала зеленой.
У вас нет функции которая запоминает для каждой клетки смещение после применения маршрута, то есть после того как вы доведёте первую черепаху вы не будете знать откуда вести вторую.
Не надо ничего запомнинать. Если черепаха была на второй клетке, но на второй итерации цикла мы вычислим, где бы она оказалась и допишем в ответ путь, выводящий ее с этой новой клетки.
она окажется на выходе, зачем это вычислять?Нет! После первой итерации цикла на выходе окажется только первая клетка! Вторая клетка, следуюя пока накопленным интсрукциям в commands, переедет куда-то.
вы вывели одну черепаху, теперь у вас нет никакой информации о том что у вас в лабиринте и гдеНо мы можем эти команды из command мысленно применить к любой начальной точке и вычислить, где она окажется.
Zara6502
20.06.2024 04:14Но мы можем эти команды из command мысленно применить к любой начальной точке и вычислить, где она окажется
о том и речь, нет алгоритма и нет реализации, есть идея, причем очевидная, небрежно оформленная, вы даже псевдокод написали умолчав о половине действий. для меня это как-то странно. Как говорится - сказал А - говори Б, или молчи.
После первой итерации цикла на выходе окажется только первая клетка! Вторая клетка, следуюя пока накопленным интсрукциям в commands, переедет куда-то
Я и пишу об этом, она куда-то уехала, ваш псевдокод об этом не знает и ничего не учитывает.
Не надо ничего запомнинать
Ну как же не надо? У вас только и есть что ваша память. Вам нужно все позиции сдвинуть исходя из набора команд и получить для всех переехавших черепашек их новые позиции.
Чуть упращено тут
Да тут не то что упрощено, тут просто половины нет.
demitryy Автор
20.06.2024 04:14о том и речь, нет алгоритма и нет реализации, есть идея
Вполне корректный алгоритм.
небрежно оформленная, вы даже псевдокод написали умолчав о половине действий
А код на питоне вас устроит? :)
Zara6502
20.06.2024 04:14Вполне корректный алгоритм
Напомню: Алгоритм - Последовательность проведения вычислительных операций для определения искомого результата, искомой величины.
Идея - Мысль, замысел, намерение, план.
Какая идея заложена в статье? Что черепашек нужно доводить до финиша. Это очевидно по условию задачи. Что конкретно предлагает автор? Я не смог разглядеть (я не против что я не в состоянии это увидеть, но пока даже после обсуждения, другим языком, я ответа не получил).
В противовес я озвучил свою идею и привёл алгоритм, включая его реализацию на псевдоязыке.
Mingun
20.06.2024 04:14Я и пишу об этом, она куда-то уехала, ваш псевдокод об этом не знает и ничего не учитывает.
В смысле, не учитывает? Строчка
u = Apply(v, commands, L)применяет все команды (commands) к клеткеv, потому что строчка ниже (commands += MakePath(u, L)) гарантирует добавление в этот список всех команд от предыдущих клеток.Поэтому для первой клетки применяются только команды, сгенерированные для выхода черепашки с первой клетки, для второй клетки — команды, сгенерированные для выхода черепашки с первой клетки — переводят вторую клетку в некоторую позицию
x(которая в общем случае может и совпадать со старой позицией второй клетки или даже с позицией первой клетки) — плюс команды для вывода черепашки из позицииxи так далее для остальных клеток.Просто вы, очевидно, ожидали, что на каждой итерации по клеткам будет вычисляться путь из клетки и сразу применяться ко всем клеткам, а в данном псевдокоде он просто накапливается в массиве
commandsи применяется к клетке только когда мы доходим до поиска пути к выходу из неё.Zara6502
20.06.2024 04:14Просто вы, очевидно, ожидали, что на каждой итерации по клеткам будет вычисляться путь из клетки и сразу применяться ко всем клеткам, а в данном псевдокоде он просто накапливается в массиве
commandsи применяется к клетке только когда мы доходим до поиска пути к выходу из неё.так, вот это уже интереснее. кажется я зацепился за понимание, нужно это обмозговать, посмотрим что получится.
хм. то есть вы предлагаете тупо все-все-все клетки брать по одной, применять к каждой предыдущий набор команд, строить для неё маршрут к выходу, чтобы последующие клетки уже считать через накопительный эффект от этих команд? Если я правильно понял, то как вы докажите, что применение непонятного набора команд ДО появления нужного поставит черепашку в нужную позицию?
просто в алгоритме с кучей черепашек вы отслеживаете их положение по результату применения команд, это для вас даёт гарантию, что каждый последующий набор команд выводит одну черепашку из лабиринта и одновременно - меняет и учитывает новое положение других черепашек. То есть таким алгоритмом мы гарантируете связность действий.
если же вы перебором в цикле просто применяете ко всем клеткам наборы команд без учета положения черепашек вы можете их загнать в какой-то угол карты и они оттуда могут в принципе не выйти, например вы перегоните черепашку на координату клетки, которую уже прошли в вашем цикле, соответственно вы никогда не приведёте её к финишу.
ну или я не понял ваши слова.
Mingun
20.06.2024 04:14применение непонятного набора команд
Набор команд не непонятный, а ровно тот, который выведет черепах с предыдущих клеток лабиринта.
вы можете их загнать в какой-то угол карты и они оттуда могут в принципе не выйти
Такого быть не может, потому что если в результате применения предыдущих команд мы загнали черепаху в угол, мы построим команды для вывода её из этого угла, а не изначальной позиции черепахи!
вы перегоните черепашку на координату клетки, которую уже прошли в вашем цикле, соответственно вы никогда не приведёте её к финишу
С чего бы? Кто вам запрещает заново запустить алгоритм вывода черепахи из этой клетки, если уж она там снова оказалась? С точки зрения построенного маршрута у вас в нём просто будут одинаковые куски команд типа влево, вверх, вправо, вниз, ..., влево, вверх, вправо, вниз.
Zara6502
20.06.2024 04:14Такого быть не может
недостаточно просто об этом сказать, у вас должно быть в алгоритме это указано.
Кто вам запрещает заново запустить алгоритм вывода черепахи из этой клетки, если уж она там снова оказалась?
Это не соответствует условиям задачи.
Mingun
20.06.2024 04:14В алгоритме это указано, вам уже в разных ветках много раз показали, где и почему. По условиям: где в условиях сказано, что нельзя приходить в ту же самую клетку?
Напишите конечную последовательность команд (up, right, down, left), которая гарантирует ей выход независимо от ее начального местонахождения.
Ни слова про то, что черепаха не может проходить несколько раз одну и ту же клетку.
Zara6502
20.06.2024 04:14Ни слова про то, что черепаха не может проходить несколько раз одну и ту же клетку.
вы уже собственные слова не помните.
Кто вам запрещает заново запустить алгоритм вывода черепахи из этой клетки, если уж она там снова оказалась?
цитирую повторно. Запрещает условие задачи:
Вы не знаете начальное расположение черепахи. Ваша последовательность команд должна быть универсальной, то есть, выводить черепашку из лабиринта независимо от ее начальной позиции.
Вам на вход дается лабиринт с клеткой "выход". Гарантируется, что лабиринт связный: от любой клетки возможно дойти до любой другой.
Придумайте алгоритм, который по лабиринту строит универсальную последовательность команд для черепахи.
То есть вы сначала даёте список команд, потом появляется черепаха и его исполняет, давать команды смотря на поле - нельзя. То есть когда у вас черепаха вернется на свою старую позицию, потому что вы зачем-то её не отправили к выходу, то всё, ваше множество возвращается в исходное состояние и у вас не случилось -1.
Mingun
20.06.2024 04:14Нет, нет, и нет! Что значит «вернётся на старую позицию»? Если у вас черепаха не выходит из лабиринта по окончанию алгоритма, всего алгоритма, а не его части, которая обеспечивает вывод одной черепахи с одной конкретной клетки, то ваш алгоритм неправильный.
Ещё раз. У вас есть этап планирования, во время которого вы строите маршрут, который будет рабочим для любого положения черепахи в лабиринте. И есть этап исполнения этого маршрута черепахой. Если хотя бы одна черепаха по итогу не оказалась на выходе — значит, вы плохо сделали свою работу на этапе планирования и выдали неверный алгоритм.
вы уже собственные слова не помните
После одной итерации алгоритма какие-то черепахи могут вернуться на изначальную позицию (но не та, которую мы выводим на этой итерации). Когда мы обойдём итерациями все клетки, мы получим весь алгоритм, пригодный для вывода черепах с любой клетки.
Zara6502
20.06.2024 04:14Нет, нет, и нет! Что значит «вернётся на старую позицию»? Если у вас черепаха не выходит из лабиринта по окончанию алгоритма, всего алгоритма, а не его части, которая обеспечивает вывод одной черепахи с одной конкретной клетки, то ваш алгоритм неправильный.
Ну я и говорю о том, что вы что-то делаете неправильно, ну или пишете так, что вас неправильно понимают.
Ещё раз. У вас есть этап планирования, во время которого вы строите маршрут, который будет рабочим для любого положения черепахи в лабиринте. И есть этап исполнения этого маршрута черепахой. Если хотя бы одна черепаха по итогу не оказалась на выходе — значит, вы плохо сделали свою работу на этапе планирования и выдали неверный алгоритм.
Мне-то зачем это повторять, я эту задачу уже решил. Мы обсуждаем несуразность описания в статье и некоторые утверждения других участников. У меня всё давно работает, меня обсуждать не нужно.
После одной итерации алгоритма какие-то черепахи могут вернуться на изначальную позицию (но не та, которую мы выводим на этой итерации).
Да я уже нашел ошибку в статье, так что этот вопрос уже закрыт.
demitryy Автор
20.06.2024 04:14Да я уже нашел ошибку в статье, так что этот вопрос уже закрыт.
Благодарю вас за проделанную работу. Однако, ни на одну фактическую ошибку вы так и не указали, зато сообщили всем вокруг, что не смогли ничего понять.
Убедительно прошу прекратить вас спамить и замусоривать комментарии.
Спасибо!
Zara6502
20.06.2024 04:14зато сообщили всем вокруг, что не смогли ничего понять
из вашей статьи действительно ничего невозможно понять.
Убедительно прошу прекратить вас спамить и замусоривать комментарии
я отвечаю на комментарии в свой адрес, а не спамлю. я не нарушаю правил общения, это не ваша собственность и я не пишу вам, так что...
Deosis
Вот тут очень тонкий лед, так как не приведено никагого способа отличить синюю точку от белой.
А вообще в математике такая задача называется синхронизация конечного автомата.
demitryy Автор
Предполагается честно выполнить набор команд
от каждой синей клетки 
и "вручную" собрать множество новых синих клеток 