Форум программистов, компьютерный форум, киберфорум
Наши страницы
Алгоритмы
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.83/6: Рейтинг темы: голосов - 6, средняя оценка - 4.83
wingblack
281 / 255 / 45
Регистрация: 09.04.2013
Сообщений: 956
1

Змея кусает свой хвост

05.04.2015, 23:22. Просмотров 1059. Ответов 9
Метки нет (Все метки)

В двумерной матрице NxN живет змея длинной K=2i.
Требуется находить положения змеи в матрице, при которых голова и хвост находятся в соседних (крест-накрест) ячейках. Соседние части змеи располагаются крест-накрест, проходить сквозь себя (несколько частей в одной ячейке) не умеет.

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

Есть ли оптимальные алгоритмы для решения подобных задач?
Из альтернатив перебору пока на ум приходит только рандом, или попытаться реализовать генетический алгоритм поверх рандома(в теории знаю как, но ранее реализовавыть не приходилось).
0
QA
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
05.04.2015, 23:22
Ответы с готовыми решениями:

Игра змейка С++ . Хвост. как создать хвост змейки
День добрый помогите, не знаю как сделать хвост. Код был взят с форума и переделан. Но с хвостом не...

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

Битва Змея-Горыныча и Ивана-царевича
Битва Ивана-царевича и Змея-Горыныча У Змея - 3 головы и 3 хвоста. Условия битвы: - если отрубит...

Битва Ивана царевича и змея горыныча
У змея - 3 головы и 3 хвоста. Условия битвы: - если отрубить 1 голову - вырастает новая...

Определить, сколько голов через T часов останется у змея Горыныча
Илья Муромец, собрался биться со змеем Горынычем. До начала боя у Горыныча было G голов. Илья...

9
wingblack
281 / 255 / 45
Регистрация: 09.04.2013
Сообщений: 956
07.04.2015, 10:57  [ТС] 2
Лучший ответ Сообщение было отмечено tezaurismosis как решение

Решение

В ЛС мне прислали предложение, которое я обобщу к следующему.
Сначала строим любое подходящее решение, затем из него получаем все остальные вот таким образом.
Пусть у нас есть угол
Код
****
*
*
*
мы его загибаем
Код
 ***
**
*
*
Получается, это достаточно не затратный и простой способ порождать новые решения из старых посредством внесения изменений.
Обозначим змею как массив инструкций о том, куда нужно сворачивать змее в текущей клетке на каждом шаге построения чтобы мы получили текущее решение (положение тела змеи до начала построений считаем несущественным). Пусть инструкции это числа от 0 до 2, где 0=прямо, 1=влево, 2=вправо.
Найдем признак угла. Рассмотрим 3 соседних значения A, B и C. Посредством перебора всех вариантов выяснилось, что признаком угла (который можно "загнуть") в клетке B являетcя условие
B != 0, B != A, B != C
При этом операция "заворачивания" сводится к прибавлению числа B ко всем 3-м числам и взятию остатка от деления на 3. Т.е. операция сложения проводится на пространстве чисел {0,1,2} с циклическим переполнением.
Конечно, сначала требуется проверить свободна ли та ячейка, в которую заворачиваем угол.

Остается придумать как правильно организовать перебор на таком методе.
0
Mikl___
Автор FAQ
14553 / 6697 / 704
Регистрация: 11.11.2010
Сообщений: 12,034
07.04.2015, 11:11 3
Я думаю нужно начинать с простых вариантов, при длине змеи допустим в 6, змея кусает свой хвост только в трех вариантах симметричные варианты не учитываем
Код
**
**
**
или
Код
 **
*  *
 **
или
Код
 **
* *
**
0
wingblack
281 / 255 / 45
Регистрация: 09.04.2013
Сообщений: 956
07.04.2015, 14:50  [ТС] 4
Прошу учитывать, что ходить можно только крест-накрест, в текущей поставке задачи диагональ использовать нельзя.

Нашел контр-пример для "заворачивания углов" при длине 8
Из такого положения
Код
***
* *
***
никак не получить
Код
****
****
Так что данный метод оставлю на потом.
0
07.04.2015, 14:50
Mysterious Light
Эксперт по математике/физике
4098 / 2006 / 411
Регистрация: 19.07.2009
Сообщений: 3,027
Записей в блоге: 22
07.04.2015, 16:20 5
Лучший ответ Сообщение было отмечено tezaurismosis как решение

Решение

Идея моя, но она быстро натыкается на проблему квадрата:
Код
12
43
цифрами указано направление обхода

Ниже прикрепляю картинку со всеми возможными конфигурациями 16-звениевой кольцевой змейки, полученными путём изгиба уголка от квадрата.

Есть мысль относительно проблемы квадрата: добавить правило, согласно которому можно «втягивать» такой квадрат в змейку, вытягивая аналогичный по размером на каком-либо прямолинейном из 2-x блоков участке:
Код
12       1.
43       2.
---  =>  ---
6.       67
7.       98
точка — свободная клетка.
2
Миниатюры
Змея кусает свой хвост  
wingblack
281 / 255 / 45
Регистрация: 09.04.2013
Сообщений: 956
08.04.2015, 10:58  [ТС] 6
Цитата Сообщение от Mysterious Light Посмотреть сообщение
Ниже прикрепляю картинку со всеми возможными конфигурациями 16-звениевой кольцевой змейки, полученными путём изгиба уголка от квадрата.
Далеко не все. Например, ни одна конфигурация не использует первичный изгиб всех 4-х углов в исходном квадрате, и не имеет загнутый левый-верхний угол.
Идея с переносом квадрата из тех, что "почему я сам не додумался", спасибо. Но тут тоже вопросы всплывают, например, проблема выбора куда перенести эти два элемента, довольно вероятны ситуации что получим конфигурацию достижимую изгибанием.
Как вы описали обход дерева конфигураций (плюс фильтрация симметричных) ? Меня этот вопрос больше всего беспокоит. Хранить всю родословную (дерево) для текущей конфигурации при значительной длине змеи будет проблематично.
0
Shamil1
Модератор
2444 / 1655 / 368
Регистрация: 26.03.2015
Сообщений: 6,052
08.04.2015, 11:27 7
А нельзя, глядя на картинку, определить, является ли она змеёй?
Каков предполагается порядок N и K?
0
wingblack
281 / 255 / 45
Регистрация: 09.04.2013
Сообщений: 956
08.04.2015, 12:38  [ТС] 8
Цитата Сообщение от Shamil1 Посмотреть сообщение
А нельзя, глядя на картинку, определить, является ли она змеёй?
Змея полностью описывается одномерной матрицей поворотов. Двумерная матрица ячеек типа занято/незанято может соответствовать нескольким конфигурациям. Если использовать аналогию с рисунком, то каждая ячейка сетки должна состоять из девяти пикселей(хотя достаточно 4-х, но будет менее наглядно) чтобы можно было однозначно определить вход и выход при проходе через эту ячейку)
Цитата Сообщение от Shamil1 Посмотреть сообщение
Каков предполагается порядок N и K?
Мне ставили как частный пример K = 100..1000, более общая задача требует от тысячи
N оценивается как сторона квадрата с вписанным кругом, площадь круга не намного более чем http://www.cyberforum.ru/cgi-bin/latex.cgi?\sqrt{K}. Как сильно "намного более" не уточняется. Верхняя граница - N не больше половины K
0
Shamil1
Модератор
2444 / 1655 / 368
Регистрация: 26.03.2015
Сообщений: 6,052
08.04.2015, 15:17 9
Генерировать картинки было бы гораздо проще, чем змей. Но сколько времени займёт проверка, является ли картинка змеёй?
Точно так же можно генерировать одномерные матрицы поворотов. Но сколько времени займёт проверка, является ли матрица поворотов змеёй?
0
wingblack
281 / 255 / 45
Регистрация: 09.04.2013
Сообщений: 956
08.04.2015, 15:59  [ТС] 10
Цитата Сообщение от Shamil1 Посмотреть сообщение
Но сколько времени займёт проверка, является ли картинка змеёй?
Для самого простого метода проверки около N*N*K для произвольной картинки, возможно можно к N*N приблизить.
Если генерировать произвольные картинки сетки с выходами, то есть порядка 4N*N картинок, и редко кто из них будет змеёй. Если матрица поворотов, то имеем 3K, поменьше, но тоже очень много для перебора.
У меня уже реализован черновик алгоритма простого перебора с возвратом в матрице поворотов. И он работает очень долго, запускал для K=256, за 3 часа перебор соответствовал K<64, точно сказать сейчас не могу.
0
08.04.2015, 15:59
Answers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
08.04.2015, 15:59

Напишите программу, которая определяет, сможет ли Илья Муромец одолеть Змея Горыныча
Илья Муромец идет на битву со Змеем Горынычем. У Змея Горыныча М голов, Илья Муромец за один удар...

Определить, сможет ли Илья Муромец одолеть Змея Горыныча и, если да, то сколько ударов для этого потребуется
Илья Муромец идет на битву со Змеем Горынычем. У Змея Горыныча М голов, Илья Муромец за один удар...

Илья Муромец собрался биться со змеем Горынычем. В течение какого часа единоборства у змея Горыныча не останется голов
Илья Муромец собрался биться со змеем Горынычем. До начала боя у Горыныча было G голов. Илья...


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

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

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