Версия для печати темы

Нажмите сюда для просмотра этой темы в обычном формате

Форум «Всё о Паскале» _ Алгоритмы _ поиск пути для кубика

Автор: Тёмный Эльф 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) *
Возможно как-нибудь обойтись, например, без рекурсии и сделать алгоритм более оптимальным?
Это можно почти всегда в простых случаях. Но почему ты отказываешься от рекурсии, даже не попробовав? Рекурсия обычно реализуется на порядок проще - так может, начать все же с нее?.. Если уж говорить об оптимальности, то не следует ли оптимизировать ВСЕ, в том числе и затраты собственного времени? smile.gif И вообще, об оптимизации можно говорить только тогда, когда уже что-то есть.

Цитата(Тёмный Эльф @ 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 лень дожидаться smile.gif

Автор: Тёмный Эльф 25.11.2007 23:21

Цитата(Lapp)
Тёмный Эльф, один вопрос мне неясен: можно ли наступать на уже пройденные клетки? Если можно, то способ отутюжить весь квадрать легко придумать и без всякого программирования. А если нельзя, то, думается мне, что задача при n>3 не имеет решения..

Не-е на клетку можно ступать только один раз. Ну а время в секундах измеряется.
С реализацией "в лоб" разобралась (спасибо xds)
Цитата(xds)
10x10 лень дожидаться

yes2.gif дольше чем полчаса.. (здесь то и встает вопрос, возможно ли оптимизировать на уровне алгоритма)
Цитата(Lapp)
Почему она оказалась в теории Паскаля? Здесь обсуждаются вопросы, касающиеся теории реализации программ на Паскале и специфики выполнения паскалевсикх программ!

промахнулась малость wink.gif
Цитата(Lapp)
И подозреваю, что скоро придется перенести в Задачи..

Да не, не придется: меня интересует алгоритм.

Автор: Lapp 26.11.2007 9:19

Цитата(Lapp @ 25.11.2007 13:49) *
думается мне, что задача при n>3 не имеет решения..
Да, поспешил я с выводами.. smile.gif Вчера сделал прогу (в три ночи), запустил для эн равных 4 и 5, увидел, что решения нет - да и обобщил недолго думая.. smile.gif)))

Цитата(xds @ 25.11.2007 17:41) *

Для 8x8 и 9x9 тоже. 10x10 лень дожидаться smile.gif
Да, n=9 считалось на моем ноуте (AMD Turion 64 X2 @1.8 GHz) полминуты.. 10х10 пока все считается, уже 30 мин. Да, вопрос оптимизации встает, что называется, в полный рост smile.gif. Я предлагаю всем, кому интересно, сделать следующее.
1. Опубликовать здесь время работы своей программы без оптимизации (с указанием процессора).
2. Включиться в соревнование по оптимизации smile.gif.

Автор: xds 26.11.2007 11:58

AMD Duron @ 800 MHz:
n = 8 - 1,43 с;
n = 9 - 18,84 с;
n = 10 - ? (точно больше 50 минут pardon.gif)

В первую очередь интересно, для каких ещё n нет решения smile.gif

Автор: 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 имею следующее:

Solution 1,  Time: 0h 0m 12s (1200 ms)
┌─┐┌┐┌──┐
│┌┘│││┌┐│
│└─┘└┘│└┘
│┌───┐└─┐
│└┐┌┐│┌─┘
│*││└┘└─┐
└┘││┌──┐│
┌┐││└┐┌┘│
*└┘└─┘└─┘

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

hardcase прав, очень похоже на фрактал. Но только я бы не стал искать сходства с каким-то конкретным фракталом. Если подумать, то так и должно быть (круто ляпнул, типа вумный.. smile.gif) - структура больших петель повторяет структуру малых. Вообще, забавно, что в таких простых условиях получается такой интересный результат.. smile.gif

2 xds: думаю, решения при n<>2,3 есть всегда. Я сейчас вывожу все решения, и их число растет с ростом n. Четверке и пятерке просто не повезло.. smile.gif

Сейчас тоже запущу свою прогу на n=10 и пойду спать smile.gif

Автор: feniks25 26.11.2007 20:17

А можно исходники посмотреть. Уж больно интересно-мудрёная задачка.
Если есть, то на делфи, а нет, то в чём будет другие языки тоже нужно изучать.

Автор: xds 26.11.2007 21:01

Цитата(Lapp @ 26.11.2007 22:50) *

После чистки очевидных несуразностей на компе Athlon 64 X2, 2GHz для случая n=9 имею следующее:
Solution 1,  Time: 0h 0m 12s (1200 ms)
┌─┐┌┐┌──┐
│┌┘│││┌┐│
│└─┘└┘│└┘
│┌───┐└─┐
│└┐┌┐│┌─┘
│*││└┘└─┐
└┘││┌──┐│
┌┐││└┐┌┘│
*└┘└─┘└─┘


1. По условию конец пути фиксирован - противоположная сторона первой строки (столбца).
2. И шо ж вы все транспонируете smile.gif

Автор: hardcase 26.11.2007 23:09

Цитата(feniks25 @ 26.11.2007 16:17) *
А можно исходники посмотреть. Уж больно интересно-мудрёная задачка.
Если есть, то на делфи, а нет, то в чём будет другие языки тоже нужно изучать.

Для того, кто знает С, перевести будет не проблема. Единственный момент, у меня катается кубик с запрещенной гранью, остальные грани не нумерованы, результат она выдает в виде команд кубику (распечатываются они в обратном порядке при выходе из рекурсии).

З.Ы. Комп до сих пор считает - вот уже на протяжении 5 ч 30 м.


Прикрепленные файлы
Прикрепленный файл  Program.txt ( 5.77 килобайт ) Кол-во скачиваний: 410

Автор: hardcase 27.11.2007 1:18

Как то даже незаметно закончился расчет "в лоб" для решения задачи с n=10. Времени ушло 7ч 25м.
Вот результирующий файл. Еще раз замечу, что читать решение нужно задом-наперед (т.е. снизу - вверх).



Прикрепленные файлы
Прикрепленный файл  sol.txt ( 788 байт ) Кол-во скачиваний: 354

Автор: Тёмный Эльф 27.11.2007 1:29

Цитата(hardcase)
Времени ушло 7ч 25м.

Вот это да-а-а mega_chok.gif
З.Ы Напишу средние значения для 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 секунды blink.gif
(Процессор Intel Pentium 4 CPU 2.80GHz)

Автор: hardcase 27.11.2007 3:11

Цитата(Тёмный Эльф @ 26.11.2007 22:39) *
Программа, откомпилированная на Microsoft Visual Studio. NET (без оптимизации) вычислила путь для n = 10 за ВНИМАНИЕ 1450 секунды blink.gif
(Процессор Intel Pentium 4 CPU 2.80GHz)
Это какая такая программа??

Автор: Тёмный Эльф 27.11.2007 3:35

Цитата(hardcase @ 26.11.2007 23:11) *

Это какая такая программа??

Это программа xds. В прикрепленных файлах она.
Но вообще странно, теперь я откомпилировала ее с оптимизацией по скорости, а результат получился хуже (на 100 секунд больше). Возможно, это потому, что у меня много программ работало одновременно?


Прикрепленные файлы
Прикрепленный файл  3112007.cpp ( 2.16 килобайт ) Кол-во скачиваний: 358

Автор: xds 27.11.2007 11:00

Вот мой оригинальный вариант (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. Добавить в очередь координаты этих соседних клеток.

По окончании работы нужно построить оптимальный путь. Первой будет финишная клетка. Второй - соседняя с ней клетка, помеченная наименьшим числом. Третья - наименьшая из соседей второй ит.д.