|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Andrey Dashkovsky 2:5002/46.4 17 Aug 2001 16:25:33
To : Kostya Sudilovsky
Subject : Re: Sokoban (логическая игра)
--------------------------------------------------------------------------------
10 Авг 01 23:01, you wrote to me:
VG>>> Существует ли алгоритм прохождения лабиринтов игры Sokoban?
AD>> Для 1 ящика и поля nxn делали виртуальным графом,
KS> Ого! Это что за алгоритм? Чем делали?! Дейкстрой, очередью?
Обычно это Дейкстра, но в ряде случаев достаточно волнового алгоритма
AD>> получается ящик может находиться в одном из n^2 положения+сам
AD>> двигающий в одном из n^2 положений,
KS> А вот и нет!!! Для человека достаточно m*4 положений, где m - кол-во
KS> ящиков, и то, это - максимум. Hапример:
KS> ШШШШШШШШШ ШШ - стена, ЯЯ - ящик, 1,2,3 - положения бедного роботяги
KS> ШШШ 2ШШШШ положение 4 здесь никогда не достигается, а 1=3
KS> Ш 1ЯЯ3 ШШ
KS> Ш ШШ ШШ
KS> Ш ШШ
KS> ШШШШШШШШШ
Красиво.
AD>> Другого алгоритма для этой задачи наша бригада в своё
AD>> время не придумала, да я сомневаюсь есть ли он.
KS> Плохо думали! Здесь еще кучу всякого можно придумать - например все
KS> тупики залить стенками, чтобы туда ящики не затаскивать.
Логично, только я привык делать на общий случай. Предлагаемый вариант будет
зависить от тестов, причём надо ещё проверить будет ли выигрышь по времени?
AD>> Разве что можно сюда приплести динамическое программирование.
KS> Так это же оно, по-сути, и есть!
Hо почти, я имел ввиду какойнь-дь переборчик типа твоего заливания тупиков, тут
разбег большой.
Andrey
... ... Крокодил летает, но низэнько низэнько (c) Дейнес А.В....
--- GoldED+/386 1.1.4.7
* Origin: Всёфигня кроме пчёл,хотя пчёлы,еслиподумать,тоже фигня (2:5002/46.4)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
