Здравствуйте, Кодт, Вы писали:
К>http://i.imgur.com/dAtcCfH.gif[/img]
К>Ну и этюд для программистов: придумать алгоритм управления змейкой.
Не, это тривиально -- уменьшать заметаемую площадь. А вот задача покруче -- найти минимальную длину змейки, ее конфигурацию (не считаем, что управление было оптимальным) и положение яйца, которая на заданном поле уже не сможет съесть его.
Здравствуйте, denisko, Вы писали:
К>>Ну и этюд для программистов: придумать алгоритм управления змейкой. D>Не, это тривиально -- уменьшать заметаемую площадь. А вот задача покруче -- найти минимальную длину змейки, ее конфигурацию (не считаем, что управление было оптимальным) и положение яйца, которая на заданном поле уже не сможет съесть его.
На самом деле, не совсем тривиально.
Одно из возможных решений — построить гамильтонов цикл и всегда бегать по нему.
Проблема здесь лишь в том, что время достижения яйца не условно-линейное (по кратчайшему пути), а условно-квадратичное (через все свободные ячейки).
В реальных змейках у яиц был таймаут, после которого они исчезали и перебазировались в новом месте.
А задача про минимальный геймовер — ну, например, такой ответ
Змейка, чья голова 1, хвост 8
345
216
87
яйцо — в любой другой точке. Управление было жесточайше неоптимальным.
Предшествующий скриншот выглядит так
234
1@5
76
поворачиваем за яйцом, съедаем его и геймовер.
Почти очевидно, что змейка или попадает в заранее подготовленный (предыдущим неоптимальным управлением) тупик и вскоре погибает, или (начав оптимально управляться с данного момента) способна добраться до любой точки игрового поля.
Минимальный тупик я показал.
Здравствуйте, Кодт, Вы писали:
К>Здравствуйте, denisko, Вы писали:
К>>>Ну и этюд для программистов: придумать алгоритм управления змейкой. D>>Не, это тривиально -- уменьшать заметаемую площадь. А вот задача покруче -- найти минимальную длину змейки, ее конфигурацию (не считаем, что управление было оптимальным) и положение яйца, которая на заданном поле уже не сможет съесть его.
К>На самом деле, не совсем тривиально.
К>Одно из возможных решений — построить гамильтонов цикл и всегда бегать по нему.
Ну или по-просту максимально длинный путь без самопересечений. К>Проблема здесь лишь в том, что время достижения яйца не условно-линейное (по кратчайшему пути), а условно-квадратичное (через все свободные ячейки). К>В реальных змейках у яиц был таймаут, после которого они исчезали и перебазировались в новом месте.
Все равно, если бегаешь так, то умрешь последним (но, может быть, голодным). А вообще отсюда много довольно интересных задач вытекает, даже не связанных непосредственно с управлением. Типа существования хоть какой-то стратегии, когда время появления и исчезновения яиц сравнимо или много меньше длины питончика (скорость всегда 1).
Здравствуйте, fin_81, Вы писали:
_>На сколько я помню для квадратной решетки нечетного размера нельзя построить гамильтонов путь.
Ну и нестрашно. Для такой решётки без одной клетки можно построить путь.
Прокладываем два пути, отличающихся в одной клетке — например, без 1,1 и без 2,2. Дальше, по-моему, очевидно.
Здравствуйте, Кодт, Вы писали:
К>Здравствуйте, fin_81, Вы писали:
_>>На сколько я помню для квадратной решетки нечетного размера нельзя построить гамильтонов путь.
К>Ну и нестрашно. Для такой решётки без одной клетки можно построить путь. К>Прокладываем два пути, отличающихся в одной клетке — например, без 1,1 и без 2,2. Дальше, по-моему, очевидно.
А можно ли переключится на другой путь когда змейка полная?
Здравствуйте, fin_81, Вы писали:
_>А можно ли переключится на другой путь когда змейка полная?
Дык, разумеется.
Вот у нас ситуация: n-1 точка содержит змейку, последняя n'ная точка — яйцо.
Добегаем до точки ветвления (1,2) и съедаем яйцо. При этом гамильтонов цикл размыкается, а змейке больше некуда расти. Мультик!
Вот, к примеру, поле 3*3.
цикл цикл змейка добежала и съела!
через через до яйца
1,1 2,2
+-+-+ + +-+ @ #-# @ #-# H #-#
| | | | | | | | | | |
+ + + +-+ + #-# H H t # # t #
| | | | | | | | |
+-+-+ +-+-+ #-#-t #-#-# #-#-#
Здравствуйте, Кодт, Вы писали:
_>>А можно ли переключится на другой путь когда змейка полная?
К>Дык, разумеется. К>... К>Вот, к примеру, поле 3*3. К>...
Это еще не доказательство для всех размеров полей и почти полных змеек длиной n-k (k>=1).
Решение не знаю.
Здравствуйте, denisko, Вы писали:
К>>Одно из возможных решений — построить гамильтонов цикл и всегда бегать по нему. D>Ну или по-просту максимально длинный путь без самопересечений.
Путь (должен) быть замкнутым. Иначе мы рискуем пробежать до конца этого пути и упереться.
Либо это должен быть максимально длинный путь в пространстве-времени (с учётом того, что освобождается место от хвоста), — но это "по определению" и неконструктивно.
Можно поискать середину между достаточным условием (цикл) и необходимым, но неконструктивным. Какой-то класс путей...
К>>В реальных змейках у яиц был таймаут, после которого они исчезали и перебазировались в новом месте. D>Все равно, если бегаешь так, то умрешь последним (но, может быть, голодным). А вообще отсюда много довольно интересных задач вытекает, даже не связанных непосредственно с управлением. Типа существования хоть какой-то стратегии, когда время появления и исчезновения яиц сравнимо или много меньше длины питончика (скорость всегда 1).
Если таймаут яйца больше, чем количество свободных клеток (делённое на скорость змейки), то, как бы яйцо ни перебазировалось, рано или поздно гамильтонова змейка до него добежит. Либо сдохнет с голоду, конечно...
Здравствуйте, fin_81, Вы писали:
_>Это еще не доказательство для всех размеров полей и почти полных змеек длиной n-k (k>=1). _>Решение не знаю.
Для поля 2n*2n есть цикл.
Для поля 2n*(2n-1) есть цикл.
Для поля (2n-1)*(2n-1) с выколотой точкой (2,2) есть цикл? Если да, то и с выколотой точкой (1,1) есть, и именно такой, какой нам нужен.
Завтра придумаю, как он выглядит.
Здравствуйте, Кодт, Вы писали:
К>Здравствуйте, fin_81, Вы писали:
_>>Это еще не доказательство для всех размеров полей и почти полных змеек длиной n-k (k>=1). _>>Решение не знаю.
К>Для поля 2n*2n есть цикл. К>Для поля 2n*(2n-1) есть цикл. К>Для поля (2n-1)*(2n-1) с выколотой точкой (2,2) есть цикл? Если да, то и с выколотой точкой (1,1) есть, и именно такой, какой нам нужен. К>Завтра придумаю, как он выглядит.
Здравствуйте, AlexRK, Вы писали:
ARK>Здравствуйте, Кодт, Вы писали:
К>>Ну и этюд для программистов: придумать алгоритм управления змейкой.
ARK>Круто! ARK>Я даже до половины никогда не доходил.
так здесь компьютерное управление, не ручное, с клавиатуры.
Здравствуйте, dimgel, Вы писали:
D>Здравствуйте, clickfraudprotection, Вы писали:
C>>так здесь компьютерное управление, не ручное, с клавиатуры.
D>Слишком витиеватая траектория местами для компьютерного управления.
поскольку скорость большая то вручную с клавиатуры маловероятно. а вот заранее расчитать траекторию возможно.
Здравствуйте, clickfraudprotection, Вы писали:
К>>Для поля (2n-1)*(2n-1) с выколотой точкой (2,2) есть цикл? Если да, то и с выколотой точкой (1,1) есть, и именно такой, какой нам нужен. К>>Завтра придумаю, как он выглядит.
C>http://en.wikipedia.org/wiki/De_Bruijn_sequence C>так. "змея" максимум семимерная.
Перекуём баги на фичи!
