Форум «Всё о Паскале» _ Алгоритмы _ поиск пути для кубика
Автор: Тёмный Эльф 24.11.2007 21:45
Привет! Подскажите пожалуйста с алгоритмом. Есть матрица n на n. Имеется трехмерный кубик, который в начале пути находится в ячейке A[1,1], а в конце пути должен попасть в ячейку A[1,n]. При этом он должен пройти все ячейки матрицы, да еще плюс к этому не должен вставать на новую позицию своей запрещенной стороной (проще говоря, перваливаясь с одной своей стороны на другую, он не должен прикасаться к полу запрещенной стороной). В самом начале пути эта запрещенная сторона находится сверху.
Для матриц 2x2 и 3x3 этот путь легко найти. В первом случае кубик проходит путь 1342 (если элементы матрицы пронумерованы по порядку), а во втором 125478963. Но как быть с матрицами 4x4 и большего размера я уже не знаю!
Может, существует общий алгоритм нахождения этого пути?
Автор: xds 24.11.2007 22:33
Решение "в лоб" - катать по всякому кубик рекурсивной процедурой, исключая поворот на запрещенную сторону, попутно считая количество посещенных клеток (для определения в клетке (1, n) найдено решение или нет).
Автор: Тёмный Эльф 24.11.2007 22:41
Цитата(xds @ 24.11.2007 18:33)
Решение "в лоб" - катать по всякому кубик рекурсивной процедурой
Да, я думала над этим. Но, по-моему, это будет выполняться долго. Возможно как-нибудь обойтись, например, без рекурсии и сделать алгоритм более оптимальным? И еще: если, например, кубик может походить на две или более ячеек, то какому ходу отдать предпочтение?
Автор: Lapp 25.11.2007 17:49
Цитата(Тёмный Эльф @ 24.11.2007 18:41)
Да, я думала над этим. Но, по-моему, это будет выполняться долго.
А что означает "долго" в этом контексте?.. Минуты, часы, дни, годы?..
Цитата(Тёмный Эльф @ 24.11.2007 18:41)
Возможно как-нибудь обойтись, например, без рекурсии и сделать алгоритм более оптимальным?
Это можно почти всегда в простых случаях. Но почему ты отказываешься от рекурсии, даже не попробовав? Рекурсия обычно реализуется на порядок проще - так может, начать все же с нее?.. Если уж говорить об оптимальности, то не следует ли оптимизировать ВСЕ, в том числе и затраты собственного времени? И вообще, об оптимизации можно говорить только тогда, когда уже что-то есть.
Цитата(Тёмный Эльф @ 24.11.2007 18:41)
И еще: если, например, кубик может походить на две или более ячеек, то какому ходу отдать предпочтение?
Никакому, надо исследовать оба. В этом и есть смысл полного перебора (в виде рекурсии или нет).
Тёмный Эльф, один вопрос мне неясен: можно ли наступать на уже пройденные клетки? Если можно, то способ отутюжить весь квадрать легко придумать и без всякого программирования. А если нельзя, то, думается мне, что задача при n>3 не имеет решения..
Автор: Lapp 25.11.2007 18:23
Только сейчас обратил внимание, что тема абсолютно не на месте..
Цитата(Тёмный Эльф @ 24.11.2007 17:45)
Привет! Подскажите пожалуйста с алгоритмом.
Почему она оказалась в теории Паскаля? Здесь обсуждаются вопросы, касающиеся теории реализации программ на Паскале и специфики выполнения паскалевсикх программ!
М
Переношу в Алгоритмы. И подозреваю, что скоро придется перенести в Задачи..
Автор: hardcase 25.11.2007 18:35
Цитата(xds @ 24.11.2007 18:33)
Решение "в лоб" - катать по всякому кубик рекурсивной процедурой
Вполне согласен. Задача аналогична обходу шахматного поля конем. Как известно решение очень быстро находится.
Автор: xds 25.11.2007 19:21
Для n > 9 уже довольно долго.
Добавлено через 17 мин. Кроме того, на время выполнения влияет порядок перебора - оно меньше, если в первую очередь делается попытка хода с поворотом плоскости "запрещенной" грани.
Автор: hardcase 25.11.2007 21:09
Написал программу. Правда, на С# (паскаля нету на машине, но код неотличим от C-шного). Для размера поля 3х3 решение существует, для 6х6, для 7х7. Для размеров выше - не знаю.
З.Ы. багу исправлял =)) - вот и правил мессагу.
З.З.Ы. в аттаче пример обхода квадрата 6х6, который предложила программа - это известный фрактал, (не помню как называется) сразу наталкивает на мысли о множестве матриц, для которых существует решение.
Эскизы прикрепленных изображений
Автор: xds 25.11.2007 21:41
Для 8x8 и 9x9 тоже. 10x10 лень дожидаться
Автор: Тёмный Эльф 25.11.2007 23:21
Цитата(Lapp)
Тёмный Эльф, один вопрос мне неясен: можно ли наступать на уже пройденные клетки? Если можно, то способ отутюжить весь квадрать легко придумать и без всякого программирования. А если нельзя, то, думается мне, что задача при n>3 не имеет решения..
Не-е на клетку можно ступать только один раз. Ну а время в секундах измеряется. С реализацией "в лоб" разобралась (спасибо xds)
Цитата(xds)
10x10 лень дожидаться
дольше чем полчаса.. (здесь то и встает вопрос, возможно ли оптимизировать на уровне алгоритма)
Цитата(Lapp)
Почему она оказалась в теории Паскаля? Здесь обсуждаются вопросы, касающиеся теории реализации программ на Паскале и специфики выполнения паскалевсикх программ!
промахнулась малость
Цитата(Lapp)
И подозреваю, что скоро придется перенести в Задачи..
Да не, не придется: меня интересует алгоритм.
Автор: Lapp 26.11.2007 9:19
Цитата(Lapp @ 25.11.2007 13:49)
думается мне, что задача при n>3 не имеет решения..
Да, поспешил я с выводами.. Вчера сделал прогу (в три ночи), запустил для эн равных 4 и 5, увидел, что решения нет - да и обобщил недолго думая.. )))
Цитата(xds @ 25.11.2007 17:41)
Для 8x8 и 9x9 тоже. 10x10 лень дожидаться
Да, n=9 считалось на моем ноуте (AMD Turion 64 X2 @1.8 GHz) полминуты.. 10х10 пока все считается, уже 30 мин. Да, вопрос оптимизации встает, что называется, в полный рост . Я предлагаю всем, кому интересно, сделать следующее. 1. Опубликовать здесь время работы своей программы без оптимизации (с указанием процессора). 2. Включиться в соревнование по оптимизации .
Автор: xds 26.11.2007 11:58
AMD Duron @ 800 MHz: n = 8 - 1,43 с; n = 9 - 18,84 с; n = 10 - ? (точно больше 50 минут )
В первую очередь интересно, для каких ещё n нет решения
Автор: hardcase 26.11.2007 17:25
Ставлю свою софтину (C# .NET 2.0, без распараллеливания) на задачу с n=10 процессор Pentium D 925 (3GHz). Надеюсь, к вечеру закончит.
Автор: Lapp 26.11.2007 19:50
После чистки очевидных несуразностей на компе Athlon 64 X2, 2GHz для случая n=9 имею следующее:
Кстати, найденные первыми решения могут различаться в разных прогах - зависит от последовательности обхода клеток.
hardcase прав, очень похоже на фрактал. Но только я бы не стал искать сходства с каким-то конкретным фракталом. Если подумать, то так и должно быть (круто ляпнул, типа вумный.. ) - структура больших петель повторяет структуру малых. Вообще, забавно, что в таких простых условиях получается такой интересный результат..
2 xds: думаю, решения при n<>2,3 есть всегда. Я сейчас вывожу все решения, и их число растет с ростом n. Четверке и пятерке просто не повезло..
Сейчас тоже запущу свою прогу на n=10 и пойду спать
Автор: feniks25 26.11.2007 20:17
А можно исходники посмотреть. Уж больно интересно-мудрёная задачка. Если есть, то на делфи, а нет, то в чём будет другие языки тоже нужно изучать.
Автор: xds 26.11.2007 21:01
Цитата(Lapp @ 26.11.2007 22:50)
После чистки очевидных несуразностей на компе Athlon 64 X2, 2GHz для случая n=9 имею следующее:
1. По условию конец пути фиксирован - противоположная сторона первой строки (столбца). 2. И шо ж вы все транспонируете
Автор: hardcase 26.11.2007 23:09
Цитата(feniks25 @ 26.11.2007 16:17)
А можно исходники посмотреть. Уж больно интересно-мудрёная задачка. Если есть, то на делфи, а нет, то в чём будет другие языки тоже нужно изучать.
Для того, кто знает С, перевести будет не проблема. Единственный момент, у меня катается кубик с запрещенной гранью, остальные грани не нумерованы, результат она выдает в виде команд кубику (распечатываются они в обратном порядке при выходе из рекурсии).
З.Ы. Комп до сих пор считает - вот уже на протяжении 5 ч 30 м.
Как то даже незаметно закончился расчет "в лоб" для решения задачи с n=10. Времени ушло 7ч 25м. Вот результирующий файл. Еще раз замечу, что читать решение нужно задом-наперед (т.е. снизу - вверх).
Вот это да-а-а З.Ы Напишу средние значения для n=8 и n=9 (измеряла по 10 раз, потом считала среднее значение) n=8 : 0.9 сек n=9 : 8,2 сек (Процессор Intel Pentium 4 CPU 2.80GHz)
Автор: hardcase 27.11.2007 1:47
Судя по ответам xds'а, его программа справится с задачей часа за 3.
Автор: Тёмный Эльф 27.11.2007 2:39
Программа, откомпилированная на Microsoft Visual Studio. NET (без оптимизации) вычислила путь для n = 10 за ВНИМАНИЕ 1450 секунды (Процессор Intel Pentium 4 CPU 2.80GHz)
Автор: hardcase 27.11.2007 3:11
Цитата(Тёмный Эльф @ 26.11.2007 22:39)
Программа, откомпилированная на Microsoft Visual Studio. NET (без оптимизации) вычислила путь для n = 10 за ВНИМАНИЕ 1450 секунды (Процессор Intel Pentium 4 CPU 2.80GHz)
Это какая такая программа??
Автор: Тёмный Эльф 27.11.2007 3:35
Цитата(hardcase @ 26.11.2007 23:11)
Это какая такая программа??
Это программа xds. В прикрепленных файлах она. Но вообще странно, теперь я откомпилировала ее с оптимизацией по скорости, а результат получился хуже (на 100 секунд больше). Возможно, это потому, что у меня много программ работало одновременно?
Вот мой оригинальный вариант (BP 7.0), только добавлено измерение времени: CUBE.PAS ( 1.48 килобайт )
Кол-во скачиваний: 657
Автор: spill 14.03.2008 17:44
Есть поиск в ширину: 1. Первую клетку пометить числом 1. 2. Поместить в очередь координаты первой клетки 3. Пока очередь не пуста нелать: 3.1. Извлечь из очереди координаты очередной клетки 3.2. Всех непомеченных и соседей (с учетом границ и "темной" грани) этой клетки пометить числом, на 1 большим, чем число, которым помечена эта клетка. 3.3. Добавить в очередь координаты этих соседних клеток.
По окончании работы нужно построить оптимальный путь. Первой будет финишная клетка. Второй - соседняя с ней клетка, помеченная наименьшим числом. Третья - наименьшая из соседей второй ит.д.