Как найти длинный путь между двумя точками?

Question

[aygumov]

Как искать самый длинный путь между ее головой и красной точкой?

Comments

[Алан Гибизов]

Ну и зачем ты спамишь в тэг python?

[Akina]

Например, поиском в ширину...

[Wataru]

Алан Гибизов, потому что автор, видимо, хочет в ответ готовый код на питоне.

[Алан Гибизов]

Wataru, ну ладно, пусть хочет. Если бы автор хотя бы предложил свою попытку в виде кода, пусть неудачную - тэг можно было бы оставить. А так... отправил жалобу "Это задание, а не вопрос".

[Василий Банников]

Думаю, можно взять любой алгоритм поиска кратчайшего пути, но поменять условие в коде, чтобы путь с каждым разом удлинялся

[Евгений Шатунов]

Алан Гибизов, автор очень торопится чтобы пытаться самостоятельно решить свой вопрос :)
Но, в целом, это задание и есть.

[Wataru]

Василий Банников, Нет, это так не работает. Некоторые алгоритмы, измененные таким образом - просто повиснут навсегда. Другие могут найти какой-то случайный путь, или вообще обломаться после первой же итерации и не найти ничего.

[aygumov]

Алан Гибизов, примет того что у меня получилось вы видите на экране , змейка работает по двум алгоритмам поиск кратчайшего пути и сохранять в своем распоряжении 80% от всей игровой области.

[aygumov]

Евгений Шатунов, нет , именно над этим проектом работаю уже месяц

[aygumov]

а так как гиены накидываться смысла нету , если не предлогаете идеи по алгоритму - вообще не комментируйте.

[Алан Гибизов]

aygumov, вы не поняли. Надо привести не картинку, а свой код или псевдокод, который отразит тот алгоритм, который вы выработали. Тогда будет тема для обсуждения. Сейчас это просто задача, а не вопрос.

[mayton2019]

В задаче не хватает мотивации. Или дополнения. Типа там - найти самый длинный путь для того чтобы змейка долго ползла. Это один кейс. Или найти самый длинный путь с максимальным числом поворотов. Это другой кейс. Больше клавиатурных нажатий.

Или если поле - бесконечное (завернутое в Тор) как часто бывает в играх - то будет что-то третье. А если можно повторно посещать ячейки где уже хвост удалился - то тогда будет сразу бесконечный путь.

Вобщем автор явно торопился. А спешка .. она здесь вредна. Мешает понять реальную задачу.

[Евгений Шатунов]

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

Answer 1

[Wataru]

Зачем вам самый длинный путь? Вообще, эта задача очень сложная. Кратчайший путь можно найти обходом в щирину или глубину, быстро и просто. Самый длинный - только полным перебором. Возможно, его можно как-то соптимизировать используя особенности вашей конкретной задачи (вроде заполнения прямоугольника змейкой и конструтирование маршрута из таких шаблонов), но это тоже очень сложно.

Comments

[Jacen11]

есть вот такой видос, https://www.youtube.com/watch?v=IDjFu7uxkVI, там автор видео ищет способ сделать змейку, а автор вопроса видимо решил повторить

Зачем вам самый длинный путь?

фишка в том, что когда змейка очень длинная, нужно чтобы оставалось место куда поползти потом, если сделать по кратчайшему расстоянию то змейка обрубает путь до точки и ломается

[Wataru]

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

Это очень хитрая задача, скорее всего на паттерны. Тривиальное решение - гонять змейку по кольцевому маршруту вдоль всего поля. Так, змейка будет обходить все клектки поля по одному разу за круг. Рано или поздно она съест яблоко и сможет двигаться так пока не заполнит все поле.

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

[aygumov]

Wataru, нет ,смотри , спиралью она точно не попадет в тупик потому что паралельно с каждым ходом проверяется что бы 80% от всего поля было доступно змейке

[aygumov]

Jacen11, да , я действую по его видео и дошел до этого алгоритма , где нужно искать длинный путь , но так и не понял как это реализовать

Answer 2

[maaGames]

Самый длинный путь - эта задача нерешаема, т.к. в самом начале игры змейка будет просто кругами бегать ВЕЧНО, ведь нет запрета на посещение одной и той же клетки.
Но вы решаете совсем другую задачу.
У вас задача съесть точку и удлинить змею, но не уткнуться в себя самого.
Для этого задаёте список правил, которые, с большой долей вероятности, позволят эту точку избегать:
2. двигаться вдоль границ игрового поля
1. двигаться вдоль тела змейки
3. ВАЖНО! не создавать петли. т.е. приближаясь к хвосту/стенке нежелательно оставлять незаполненные области
4. избегать движения к точке
5... ещё что-нибудь, что сразу в голову не приходит
X. делать пункты 1-4 на несколько ходов вперёд. Допустим, на 50 щагов вперёд можно без проблем просчитываь. Если на 47 шаге скушали точку, при этом оставались пустые клетки, то отматываете назад и пробуете двигаться в другие стороны.

Answer 3

[Некит Медведев]

Просто поворачивай дважды в крайних положениях и дойдёшь до конца(разворот на 180 на краю)

Answer 4

[Руслан .]

В конкретно в этой задаче кажется, что самое длинное расстояние, это количество ячеек игрового поля в области, которая содержит красную точку. Т.е. это можно попробовать решить каким либо алгоритмом заливки области цветом.