поиск пути для кубика, в матрице nxn |
поиск пути для кубика, в матрице nxn |
Тёмный Эльф |
24.11.2007 17:45
Сообщение
#1
|
Влюблённый псих Группа: Пользователи Сообщений: 185 Пол: Женский Реальное имя: Лейла Репутация: 1 |
Привет! Подскажите пожалуйста с алгоритмом.
Есть матрица n на n. Имеется трехмерный кубик, который в начале пути находится в ячейке A[1,1], а в конце пути должен попасть в ячейку A[1,n]. При этом он должен пройти все ячейки матрицы, да еще плюс к этому не должен вставать на новую позицию своей запрещенной стороной (проще говоря, перваливаясь с одной своей стороны на другую, он не должен прикасаться к полу запрещенной стороной). В самом начале пути эта запрещенная сторона находится сверху. Для матриц 2x2 и 3x3 этот путь легко найти. В первом случае кубик проходит путь 1342 (если элементы матрицы пронумерованы по порядку), а во втором 125478963. Но как быть с матрицами 4x4 и большего размера я уже не знаю! Может, существует общий алгоритм нахождения этого пути? |
xds |
24.11.2007 18:33
Сообщение
#2
|
N337 Группа: Пользователи Сообщений: 737 Пол: Мужской Репутация: 26 |
Решение "в лоб" - катать по всякому кубик рекурсивной процедурой, исключая поворот на запрещенную сторону, попутно считая количество посещенных клеток (для определения в клетке (1, n) найдено решение или нет).
-------------------- The idiots are winning.
|
Тёмный Эльф |
24.11.2007 18:41
Сообщение
#3
|
Влюблённый псих Группа: Пользователи Сообщений: 185 Пол: Женский Реальное имя: Лейла Репутация: 1 |
Решение "в лоб" - катать по всякому кубик рекурсивной процедурой Да, я думала над этим. Но, по-моему, это будет выполняться долго. Возможно как-нибудь обойтись, например, без рекурсии и сделать алгоритм более оптимальным? И еще: если, например, кубик может походить на две или более ячеек, то какому ходу отдать предпочтение? Сообщение отредактировано: Тёмный Эльф - 24.11.2007 18:55 |
Lapp |
25.11.2007 13:49
Сообщение
#4
|
Уникум Группа: Модераторы Сообщений: 6 823 Пол: Мужской Реальное имя: Лопáрь (Андрей) Репутация: 159 |
Да, я думала над этим. Но, по-моему, это будет выполняться долго. А что означает "долго" в этом контексте?.. Минуты, часы, дни, годы?..Возможно как-нибудь обойтись, например, без рекурсии и сделать алгоритм более оптимальным? Это можно почти всегда в простых случаях. Но почему ты отказываешься от рекурсии, даже не попробовав? Рекурсия обычно реализуется на порядок проще - так может, начать все же с нее?.. Если уж говорить об оптимальности, то не следует ли оптимизировать ВСЕ, в том числе и затраты собственного времени? И вообще, об оптимизации можно говорить только тогда, когда уже что-то есть.И еще: если, например, кубик может походить на две или более ячеек, то какому ходу отдать предпочтение? Никакому, надо исследовать оба. В этом и есть смысл полного перебора (в виде рекурсии или нет).Тёмный Эльф, один вопрос мне неясен: можно ли наступать на уже пройденные клетки? Если можно, то способ отутюжить весь квадрать легко придумать и без всякого программирования. А если нельзя, то, думается мне, что задача при n>3 не имеет решения.. -------------------- я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой |
Lapp |
25.11.2007 14:23
Сообщение
#5
|
|||
Уникум Группа: Модераторы Сообщений: 6 823 Пол: Мужской Реальное имя: Лопáрь (Андрей) Репутация: 159 |
Только сейчас обратил внимание, что тема абсолютно не на месте..
Привет! Подскажите пожалуйста с алгоритмом. Почему она оказалась в теории Паскаля? Здесь обсуждаются вопросы, касающиеся теории реализации программ на Паскале и специфики выполнения паскалевсикх программ!
-------------------- я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой |
|||
hardcase |
25.11.2007 14:35
Сообщение
#6
|
code warrior Группа: Пользователи Сообщений: 484 Пол: Мужской Реальное имя: Славен Репутация: 8 |
Решение "в лоб" - катать по всякому кубик рекурсивной процедурой Вполне согласен. Задача аналогична обходу шахматного поля конем. Как известно решение очень быстро находится.-------------------- ИзВ ин ИтЕ зА нЕ рОв НЫй П оч ЕРк
|
xds |
25.11.2007 15:21
Сообщение
#7
|
N337 Группа: Пользователи Сообщений: 737 Пол: Мужской Репутация: 26 |
Для n > 9 уже довольно долго.
Добавлено через 17 мин. Кроме того, на время выполнения влияет порядок перебора - оно меньше, если в первую очередь делается попытка хода с поворотом плоскости "запрещенной" грани. -------------------- The idiots are winning.
|
hardcase |
25.11.2007 17:09
Сообщение
#8
|
code warrior Группа: Пользователи Сообщений: 484 Пол: Мужской Реальное имя: Славен Репутация: 8 |
Написал программу. Правда, на С# (паскаля нету на машине, но код неотличим от C-шного). Для размера поля 3х3 решение существует, для 6х6, для 7х7. Для размеров выше - не знаю.
З.Ы. багу исправлял =)) - вот и правил мессагу. З.З.Ы. в аттаче пример обхода квадрата 6х6, который предложила программа - это известный фрактал, (не помню как называется) сразу наталкивает на мысли о множестве матриц, для которых существует решение. Сообщение отредактировано: hardcase - 25.11.2007 17:42 Эскизы прикрепленных изображений -------------------- ИзВ ин ИтЕ зА нЕ рОв НЫй П оч ЕРк
|
xds |
25.11.2007 17:41
Сообщение
#9
|
N337 Группа: Пользователи Сообщений: 737 Пол: Мужской Репутация: 26 |
Для 8x8 и 9x9 тоже. 10x10 лень дожидаться
-------------------- The idiots are winning.
|
Тёмный Эльф |
25.11.2007 19:21
Сообщение
#10
|
Влюблённый псих Группа: Пользователи Сообщений: 185 Пол: Женский Реальное имя: Лейла Репутация: 1 |
Цитата(Lapp) Тёмный Эльф, один вопрос мне неясен: можно ли наступать на уже пройденные клетки? Если можно, то способ отутюжить весь квадрать легко придумать и без всякого программирования. А если нельзя, то, думается мне, что задача при n>3 не имеет решения.. Не-е на клетку можно ступать только один раз. Ну а время в секундах измеряется. С реализацией "в лоб" разобралась (спасибо xds) Цитата(xds) 10x10 лень дожидаться дольше чем полчаса.. (здесь то и встает вопрос, возможно ли оптимизировать на уровне алгоритма) Цитата(Lapp) Почему она оказалась в теории Паскаля? Здесь обсуждаются вопросы, касающиеся теории реализации программ на Паскале и специфики выполнения паскалевсикх программ! промахнулась малость Цитата(Lapp) И подозреваю, что скоро придется перенести в Задачи.. Да не, не придется: меня интересует алгоритм. |
Lapp |
26.11.2007 5:19
Сообщение
#11
|
Уникум Группа: Модераторы Сообщений: 6 823 Пол: Мужской Реальное имя: Лопáрь (Андрей) Репутация: 159 |
думается мне, что задача при n>3 не имеет решения.. Да, поспешил я с выводами.. Вчера сделал прогу (в три ночи), запустил для эн равных 4 и 5, увидел, что решения нет - да и обобщил недолго думая.. )))Для 8x8 и 9x9 тоже. 10x10 лень дожидаться 1. Опубликовать здесь время работы своей программы без оптимизации (с указанием процессора). 2. Включиться в соревнование по оптимизации . -------------------- я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой |
xds |
26.11.2007 7:58
Сообщение
#12
|
N337 Группа: Пользователи Сообщений: 737 Пол: Мужской Репутация: 26 |
AMD Duron @ 800 MHz:
n = 8 - 1,43 с; n = 9 - 18,84 с; n = 10 - ? (точно больше 50 минут ) В первую очередь интересно, для каких ещё n нет решения -------------------- The idiots are winning.
|
hardcase |
26.11.2007 13:25
Сообщение
#13
|
code warrior Группа: Пользователи Сообщений: 484 Пол: Мужской Реальное имя: Славен Репутация: 8 |
Ставлю свою софтину (C# .NET 2.0, без распараллеливания) на задачу с n=10 процессор Pentium D 925 (3GHz). Надеюсь, к вечеру закончит.
Сообщение отредактировано: hardcase - 26.11.2007 13:25 -------------------- ИзВ ин ИтЕ зА нЕ рОв НЫй П оч ЕРк
|
Lapp |
26.11.2007 15:50
Сообщение
#14
|
Уникум Группа: Модераторы Сообщений: 6 823 Пол: Мужской Реальное имя: Лопáрь (Андрей) Репутация: 159 |
После чистки очевидных несуразностей на компе Athlon 64 X2, 2GHz для случая n=9 имею следующее:
Solution 1, Time: 0h 0m 12s (1200 ms) Кстати, найденные первыми решения могут различаться в разных прогах - зависит от последовательности обхода клеток. hardcase прав, очень похоже на фрактал. Но только я бы не стал искать сходства с каким-то конкретным фракталом. Если подумать, то так и должно быть (круто ляпнул, типа вумный.. ) - структура больших петель повторяет структуру малых. Вообще, забавно, что в таких простых условиях получается такой интересный результат.. 2 xds: думаю, решения при n<>2,3 есть всегда. Я сейчас вывожу все решения, и их число растет с ростом n. Четверке и пятерке просто не повезло.. Сейчас тоже запущу свою прогу на n=10 и пойду спать -------------------- я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой |
Rian |
26.11.2007 16:17
Сообщение
#15
|
Знаток Группа: Пользователи Сообщений: 394 Пол: Мужской Репутация: 9 |
А можно исходники посмотреть. Уж больно интересно-мудрёная задачка.
Если есть, то на делфи, а нет, то в чём будет другие языки тоже нужно изучать. -------------------- Objective-C, Unity3d
|
xds |
26.11.2007 17:01
Сообщение
#16
|
N337 Группа: Пользователи Сообщений: 737 Пол: Мужской Репутация: 26 |
После чистки очевидных несуразностей на компе Athlon 64 X2, 2GHz для случая n=9 имею следующее: Solution 1, Time: 0h 0m 12s (1200 ms) 1. По условию конец пути фиксирован - противоположная сторона первой строки (столбца). 2. И шо ж вы все транспонируете -------------------- The idiots are winning.
|
hardcase |
26.11.2007 19:09
Сообщение
#17
|
code warrior Группа: Пользователи Сообщений: 484 Пол: Мужской Реальное имя: Славен Репутация: 8 |
А можно исходники посмотреть. Уж больно интересно-мудрёная задачка. Если есть, то на делфи, а нет, то в чём будет другие языки тоже нужно изучать. Для того, кто знает С, перевести будет не проблема. Единственный момент, у меня катается кубик с запрещенной гранью, остальные грани не нумерованы, результат она выдает в виде команд кубику (распечатываются они в обратном порядке при выходе из рекурсии). З.Ы. Комп до сих пор считает - вот уже на протяжении 5 ч 30 м. Сообщение отредактировано: hardcase - 26.11.2007 19:10 Прикрепленные файлы Program.txt ( 5.77 килобайт ) Кол-во скачиваний: 280 -------------------- ИзВ ин ИтЕ зА нЕ рОв НЫй П оч ЕРк
|
hardcase |
26.11.2007 21:18
Сообщение
#18
|
code warrior Группа: Пользователи Сообщений: 484 Пол: Мужской Реальное имя: Славен Репутация: 8 |
Как то даже незаметно закончился расчет "в лоб" для решения задачи с n=10. Времени ушло 7ч 25м.
Вот результирующий файл. Еще раз замечу, что читать решение нужно задом-наперед (т.е. снизу - вверх). Прикрепленные файлы sol.txt ( 788 байт ) Кол-во скачиваний: 252 -------------------- ИзВ ин ИтЕ зА нЕ рОв НЫй П оч ЕРк
|
Тёмный Эльф |
26.11.2007 21:29
Сообщение
#19
|
Влюблённый псих Группа: Пользователи Сообщений: 185 Пол: Женский Реальное имя: Лейла Репутация: 1 |
Цитата(hardcase) Времени ушло 7ч 25м. Вот это да-а-а З.Ы Напишу средние значения для n=8 и n=9 (измеряла по 10 раз, потом считала среднее значение) n=8 : 0.9 сек n=9 : 8,2 сек (Процессор Intel Pentium 4 CPU 2.80GHz) Сообщение отредактировано: Тёмный Эльф - 26.11.2007 22:45 |
hardcase |
26.11.2007 21:47
Сообщение
#20
|
code warrior Группа: Пользователи Сообщений: 484 Пол: Мужской Реальное имя: Славен Репутация: 8 |
Судя по ответам xds'а, его программа справится с задачей часа за 3.
-------------------- ИзВ ин ИтЕ зА нЕ рОв НЫй П оч ЕРк
|
Текстовая версия | 30.09.2024 0:45 |