|
пятничная задачка (про) коня
|
|||
---|---|---|---|
#18+
тут на днях всплывала тема про домино и 8 ферзей на шахматной доске. ну вот и подумал - а не забацать ли на оракле решение классической шахматной задачи коня. думаю, всем она известна, но на всякий случай: есть пустая шахматная доска (обыкновенная, фиде-европейская, размера 8x8 ) задача 1) за 64 хода обойти конем все её клетки (что, естественно, означает не наступать ни на какое поле дважды) задача 2) то же самое, но с условием что с поля 64-го хода конь может допрыгнуть до начальной своей позиции (то есть зациклить всю траекторию) решений в природе много. имхо, достаточно получить ~одно я решал на 11g. без pl/sql обойтись не смог (ну и еще чутка с алгоритмом подшаманил, но, надеюсь, что таки в рамках спортивных приличий ) Код: plsql 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. 20. 21. 22. 23. 24. 25. 26. 27. 28. 29. 30. 31. 32. 33. 34. 35. 36. 37. 38. 39. 40.
удачи! ... |
|||
:
Нравится:
Не нравится:
|
|||
01.04.2012, 01:46 |
|
пятничная задачка (про) коня
|
|||
---|---|---|---|
#18+
orawish, Это неинтересно, вот если бы получить все решения. Но на 11.2 это невозможно :-( ... |
|||
:
Нравится:
Не нравится:
|
|||
01.04.2012, 11:41 |
|
пятничная задачка (про) коня
|
|||
---|---|---|---|
#18+
orawishзадача 1) за 64 хода обойти конем все её клетки (что, естественно, означает не наступать ни на какое поле дважды) задача 2) то же самое, но с условием что с поля 64-го хода конь может допрыгнуть до начальной своей позиции (то есть зациклить всю траекторию) ... я решал на 11g. без pl/sql обойтись не смог 1 или 2? ... |
|||
:
Нравится:
Не нравится:
|
|||
01.04.2012, 11:56 |
|
пятничная задачка (про) коня
|
|||
---|---|---|---|
#18+
andreymx, Код: plsql 1. 2.
но, навскидку, с 11.1 совместимо ... |
|||
:
Нравится:
Не нравится:
|
|||
01.04.2012, 14:40 |
|
пятничная задачка (про) коня
|
|||
---|---|---|---|
#18+
Bfinkorawish, Это неинтересно, вот если бы получить все решения. Но на 11.2 это невозможно :-( про неинтересно - не согласен. мне очень было интересно. кряхтел, потел, и очень доволен, что таки сделал. а вот про множественные решения могу сказать, что побочным продуктом процесса было строгое доказательство, что решений (задачи 2, даже без учета различий в начальном поле) много больше 1e6. на самом деле, очевидно что миллион это на много-много-много порядков грубая оценка того количества снизу (но, повторю, строгая = экспериментальная). ну, можно добавить: задача 3) - представить тех решений, допустим, 1001 задача 4) - оценить количество решений которое предлагаемый способ находит за одно исполнение (или какую-либо единицу времени) ... |
|||
:
Нравится:
Не нравится:
|
|||
01.04.2012, 14:58 |
|
пятничная задачка (про) коня
|
|||
---|---|---|---|
#18+
orawish, я могу сразу сказать, что когда-то хотел решить эту задачку, но не смог. Наверное, поэтому мне и неинтересно отдельное решение, хочется решить все, сразу и окончательно. ... |
|||
:
Нравится:
Не нравится:
|
|||
01.04.2012, 15:11 |
|
пятничная задачка (про) коня
|
|||
---|---|---|---|
#18+
Bfinkorawish, я могу сразу сказать, что когда-то хотел решить эту задачку, но не смог. Наверное, поэтому мне и неинтересно отдельное решение, хочется решить все, сразу и окончательно. а я вот сомневаюсь, что атомов во вселенной хватит, чтобы те все решения изобразить :) шейсятчетвертая - это очень большая степень (причем, и при среднем основании совсем не 2 ;) наивно пытаться окучить всю задачу бруттофорсом (имхо) - далеко не для нашего уровня развития технологий. да еще и симметрия (не только задачи, но и решения) чудовищная. так что - надо думать .. для затравки - в тех двух решениях, что я привел - есть очевидная подсказка ... |
|||
:
Нравится:
Не нравится:
|
|||
01.04.2012, 15:40 |
|
пятничная задачка (про) коня
|
|||
---|---|---|---|
#18+
orawish, я и говорю - 11.2 слабоват. Есть куда развиваться. А, допустим, квантовому компьютеру, хотя бы с 16ю кубитами уже легко получить все решения. ... |
|||
:
Нравится:
Не нравится:
|
|||
01.04.2012, 15:42 |
|
пятничная задачка (про) коня
|
|||
---|---|---|---|
#18+
Bfinkorawish, я и говорю - 11.2 слабоват. Есть куда развиваться. А, допустим, квантовому компьютеру, хотя бы с 16ю кубитами уже легко получить все решения. не верю (c) :) кстати - парой постов выше я говорил про миллион решений, влёгкую полученных алгоритмом, обыгравшем отдельный (очень) частный случай. ну так я наврал (у того частного алгоритма) решений не менее чем 1e9 ... |
|||
:
Нравится:
Не нравится:
|
|||
01.04.2012, 15:56 |
|
пятничная задачка (про) коня
|
|||
---|---|---|---|
#18+
orawishandreymx, Код: plsql 1. 2.
но, навскидку, с 11.1 совместимовообще-то я имел в виду - какую из задач ты решал? :) ... |
|||
:
Нравится:
Не нравится:
|
|||
01.04.2012, 17:24 |
|
пятничная задачка (про) коня
|
|||
---|---|---|---|
#18+
andreymxorawishandreymx, Код: plsql 1. 2.
но, навскидку, с 11.1 совместимовообще-то я имел в виду - какую из задач ты решал? :) а, ну это же очевидно из решения - начало с концом на дистанции как раз одного хода - сталбыть 2) ... |
|||
:
Нравится:
Не нравится:
|
|||
01.04.2012, 17:28 |
|
пятничная задачка (про) коня
|
|||
---|---|---|---|
#18+
andreymx, + то есть ответы тут для 2) , а алгоритму пофиг - находит и те, которые 1) ... |
|||
:
Нравится:
Не нравится:
|
|||
01.04.2012, 17:34 |
|
пятничная задачка (про) коня
|
|||
---|---|---|---|
#18+
Для этого алгоритма есть оптимизация для полей очень большого размера. Там где классический поиск заходит в слишком долгий спуск и проверки. Суть в том что конь идёт не по всему полю а по "коридорам". ... |
|||
:
Нравится:
Не нравится:
|
|||
01.04.2012, 19:35 |
|
пятничная задачка (про) коня
|
|||
---|---|---|---|
#18+
maytonДля этого алгоритма есть оптимизация для полей очень большого размера. Там где классический поиск заходит в слишком долгий спуск и проверки. Суть в том что конь идёт не по всему полю а по "коридорам". ну так за чем же дело стало? вперёд! ;) ... |
|||
:
Нравится:
Не нравится:
|
|||
01.04.2012, 19:43 |
|
пятничная задачка (про) коня
|
|||
---|---|---|---|
#18+
я намекал, что в решении из стартового поста есть подсказка. тот кто хотел её найти, наверное, уже нашел.. (на 32 ходу или около того ;) на картинке три позиции - после ходов 1, 8 и 32 черная лошадь обозначает стартовую и финишную позицию траектории коня к соответствующему ходу, белая - прочие пройденные поля. то обстоятельство, что между 8 и 32 ходом изменилась не только конечная, но и начальная точка траектории - это еще одна подсказка :) ... |
|||
:
Нравится:
Не нравится:
|
|||
02.04.2012, 00:53 |
|
пятничная задачка (про) коня
|
|||
---|---|---|---|
#18+
Мой метод Эйлера остановился на 52 ходу а дальше уже думать надо :) ... |
|||
:
Нравится:
Не нравится:
|
|||
02.04.2012, 09:16 |
|
пятничная задачка (про) коня
|
|||
---|---|---|---|
#18+
andreymxМой метод Эйлера остановился на 52 ходу а дальше уже думать надо :) 52 ход это же тринадцатый с конца, вот, наверное, и причина :) а если серьёзно - две вещи есть, над которыми стОит подумать 1) исключение из рассмотрения вариантов, которые при разнице в траектории к эн-ному ходу содержат одну и ту же картину на доске 2) исключение позиций, продолжение которых заведомо к решению не приведёт ... |
|||
:
Нравится:
Не нравится:
|
|||
02.04.2012, 11:23 |
|
пятничная задачка (про) коня
|
|||
---|---|---|---|
#18+
Мне кажется интереснее решать задачу обхода конём произвольных областей (сложной формы) лабиринтов и т.п. и (или) доказывать невозможность их обойти на ранних этапах. А теория обхода прямоугольных досок IMHO уже исследована. Три основных метода описаны тут . ... |
|||
:
Нравится:
Не нравится:
|
|||
02.04.2012, 12:01 |
|
пятничная задачка (про) коня
|
|||
---|---|---|---|
#18+
maytonМне кажется интереснее решать задачу обхода конём произвольных областей (сложной формы) лабиринтов и т.п. и (или) доказывать невозможность их обойти на ранних этапах. А теория обхода прямоугольных досок IMHO уже исследована. Три основных метода описаны тут . теория пусть себе развивается. развивать ли её или только использовать (или даже игнорировать ) - личный выбор каждого. форум то (вроде бы) про оракл. и тема (имхо) тоже про оракл. поговорить про алгоритмы на уровне абстрагированном от оракла пришлось - и это потому, что наиболее грубые подходы обречены в силу магии данных задачи. ну и (имхо) достаточно уже поговорили. пора бы и порешать ... |
|||
:
Нравится:
Не нравится:
|
|||
02.04.2012, 12:45 |
|
пятничная задачка (про) коня
|
|||
---|---|---|---|
#18+
orawishну и (имхо) достаточно уже поговорили. пора бы и порешать Скажем дружно "НЕТ" диктату на sql.ru! ... |
|||
:
Нравится:
Не нравится:
|
|||
02.04.2012, 14:23 |
|
пятничная задачка (про) коня
|
|||
---|---|---|---|
#18+
Bfinkorawish, я и говорю - 11.2 слабоват. Есть куда развиваться. А, допустим, квантовому компьютеру, хотя бы с 16ю кубитами уже легко получить все решения.По-моему квантовому компьютеру будет просто получить первое решение. Точно также, когда-то я изучал генетический алгоритм для расстановки ферзей на доске 300*300. Обычный метод на таких объемах загнется, а генетический алгоритм неплохо справляется с задачей поиска первого решения. Это, конечно, мало имеет общего с квантовыми вычислениями, но идея одна: максмиально бысто найти первое решение. Как бы там ни было с квантовым даже поэкспериментировать не удастся ибо эмулятор пока сделать невозможно. :) ... |
|||
:
Нравится:
Не нравится:
|
|||
02.04.2012, 14:45 |
|
пятничная задачка (про) коня
|
|||
---|---|---|---|
#18+
Sql-брутфорс. Сервер слабоват проверить :), по идее должно работать. with field as ( select 'a1' s_name from dual union all select 'a2' s_name from dual union all select 'a3' s_name from dual union all select 'a4' s_name from dual union all select 'a5' s_name from dual union all select 'a6' s_name from dual union all select 'a7' s_name from dual union all select 'a8' s_name from dual union all select 'b1' s_name from dual union all select 'b2' s_name from dual union all select 'b3' s_name from dual union all select 'b4' s_name from dual union all select 'b5' s_name from dual union all select 'b6' s_name from dual union all select 'b7' s_name from dual union all select 'b8' s_name from dual union all select 'c1' s_name from dual union all select 'c2' s_name from dual union all select 'c3' s_name from dual union all select 'c4' s_name from dual union all select 'c5' s_name from dual union all select 'c6' s_name from dual union all select 'c7' s_name from dual union all select 'c8' s_name from dual union all select 'd1' s_name from dual union all select 'd2' s_name from dual union all select 'd3' s_name from dual union all select 'd4' s_name from dual union all select 'd5' s_name from dual union all select 'd6' s_name from dual union all select 'd7' s_name from dual union all select 'd8' s_name from dual union all select 'e1' s_name from dual union all select 'e2' s_name from dual union all select 'e3' s_name from dual union all select 'e4' s_name from dual union all select 'e5' s_name from dual union all select 'e6' s_name from dual union all select 'e7' s_name from dual union all select 'e8' s_name from dual union all select 'f1' s_name from dual union all select 'f2' s_name from dual union all select 'f3' s_name from dual union all select 'f4' s_name from dual union all select 'f5' s_name from dual union all select 'f6' s_name from dual union all select 'f7' s_name from dual union all select 'f8' s_name from dual union all select 'g1' s_name from dual union all select 'g2' s_name from dual union all select 'g3' s_name from dual union all select 'g4' s_name from dual union all select 'g5' s_name from dual union all select 'g6' s_name from dual union all select 'g7' s_name from dual union all select 'g8' s_name from dual union all select 'h1' s_name from dual union all select 'h2' s_name from dual union all select 'h3' s_name from dual union all select 'h4' s_name from dual union all select 'h5' s_name from dual union all select 'h6' s_name from dual union all select 'h7' s_name from dual union all select 'h8' s_name from dual ) select /*+FIRST_ROWS */ steps from ( select t.*, level lvl, SYS_CONNECT_BY_PATH(s_name, '/') steps from ( select row_number() over(order by s_name) id, f.s_name, row_number() over(order by s_name) parent_id from field f ) t where level <= 64 connect by NOCYCLE ( ( (id = prior parent_id + 10 and mod(prior parent_id, 8) not in (0, 7)) or (id = prior parent_id - 6 and mod(prior parent_id, 8) not in (0, 7)) or (id = prior parent_id + 17 and mod(prior parent_id, 8) not in (0)) or (id = prior parent_id - 15 and mod(prior parent_id, 8) not in (0)) or (id = prior parent_id - 10 and mod(prior parent_id, 8) not in (1, 2))or (id = prior parent_id + 6 and mod(prior parent_id, 8) not in (1, 2)) or (id = prior parent_id - 17 and mod(prior parent_id, 8) not in (1)) or (id = prior parent_id + 15 and mod(prior parent_id, 8) not in (1)) ) ) start with s_name = 'c4' ) where lvl = 64 and rownum = 1; ... |
|||
:
Нравится:
Не нравится:
|
|||
02.04.2012, 15:15 |
|
пятничная задачка (про) коня
|
|||
---|---|---|---|
#18+
ukkuSql-брутфорс. Сервер слабоват проверить :), по идее должно работать.. о, дак это легко проверяется. запускаете потихоньку прибавляя уровни. начиная с десятого советую прибавлять строго по одному. ... |
|||
:
Нравится:
Не нравится:
|
|||
02.04.2012, 15:58 |
|
пятничная задачка (про) коня
|
|||
---|---|---|---|
#18+
orawishukkuSql-брутфорс. Сервер слабоват проверить :), по идее должно работать.. о, дак это легко проверяется. запускаете потихоньку прибавляя уровни. начиная с десятого советую прибавлять строго по одному.а где-то с четырнадцатого - по четверти :) ... |
|||
:
Нравится:
Не нравится:
|
|||
02.04.2012, 16:02 |
|
пятничная задачка (про) коня
|
|||
---|---|---|---|
#18+
orawish, по чуть-чуть нельзя( - это ж брутфорс. Первые 63 этапа могут быть логичные, а вот 64ий не сойдется. А никто не считал, сколько в теории верных результатов? А то у мя уже час считается, чую надо будет ждать маленькую вечность с тупым перебором. ... |
|||
:
Нравится:
Не нравится:
|
|||
02.04.2012, 16:06 |
|
пятничная задачка (про) коня
|
|||
---|---|---|---|
#18+
ukku, ваш алгоритм, похоже, скорее мёртв, чем жив. не позднее 19 хода он фатально ошибается и весело продолжает скакать по первому возможному варианту до 60-го на 60-м ходов не остается совсем и начинается вечный балет по перемалыванию заведомо неживого хвоста (из минимум ~сорока одного уровня) ... |
|||
:
Нравится:
Не нравится:
|
|||
02.04.2012, 16:32 |
|
пятничная задачка (про) коня
|
|||
---|---|---|---|
#18+
orawish Код: plsql 1. 2. 3. 4. 5. 6. 7. 8. 9. 10.
Тут можно расширить постановку и искать обходы не только конём но и королём, ферзём и произвольной фигурой которая ходит вовсе не по правилам шахмат. ... |
|||
:
Нравится:
Не нравится:
|
|||
02.04.2012, 16:34 |
|
пятничная задачка (про) коня
|
|||
---|---|---|---|
#18+
maytonи произвольной фигурой которая ходит вовсе не по правилам шахмат.и по площади занимает произвольные 8х8 клеток шахматной доски. ... |
|||
:
Нравится:
Не нравится:
|
|||
02.04.2012, 16:38 |
|
пятничная задачка (про) коня
|
|||
---|---|---|---|
#18+
Поэтому и назвал тупым перебором :) Кто дойдет до 64 только тот и будет верный. Ладно хватит работать сегодня, надо будет завтра подумать чтобы заведомо не верные отсекались. ... |
|||
:
Нравится:
Не нравится:
|
|||
02.04.2012, 16:38 |
|
пятничная задачка (про) коня
|
|||
---|---|---|---|
#18+
orawishну так за чем же дело стало? вперёд! ;)Первое, что приходит на ум - воспользоваться правилом Варнсдорфа. Если вдруг не сошлось - вернуться до того момента когда был выбор из нескольких и выбрать другое. Если опять не сошлось - опять вернуться и т. д. Если ~перебором - то решать задачу для половины доски как рекомендуют здесь , при этом так чтоб конь из конечного положения мог заскочить на другую половину. Потом подход повторить. Но слишком много рутины - это отталкивает от задачи. ... |
|||
:
Нравится:
Не нравится:
|
|||
02.04.2012, 23:12 |
|
пятничная задачка (про) коня
|
|||
---|---|---|---|
#18+
dbms_photoshoporawishну так за чем же дело стало? вперёд! ;)Первое, что приходит на ум - воспользоваться правилом Варнсдорфа. Если вдруг не сошлось - вернуться до того момента когда был выбор из нескольких и выбрать другое. Если опять не сошлось - опять вернуться и т. д. Если ~перебором - то решать задачу для половины доски как рекомендуют здесь , при этом так чтоб конь из конечного положения мог заскочить на другую половину. Потом подход повторить. Но слишком много рутины - это отталкивает от задачи. насколько я понимаю, решение от ukku и есть инкарнация алгоритма Варнсдорфа, по сути - тот же перебор. т.е. сам по себе, без дополнительных приседаний - абсолютно никаких шансов ... |
|||
:
Нравится:
Не нравится:
|
|||
03.04.2012, 00:18 |
|
пятничная задачка (про) коня
|
|||
---|---|---|---|
#18+
orawish, Абсолютно нет. Правило ВарнсдорфаПри обходе доски коня следует всякий раз ставить на поле, из которого он может сделать наименьшее число ходов на еще не пройденные поля; если таких полей несколько, то можно выбрать любое из них. ... |
|||
:
Нравится:
Не нравится:
|
|||
03.04.2012, 00:29 |
|
пятничная задачка (про) коня
|
|||
---|---|---|---|
#18+
dbms_photoshoporawish, Абсолютно нет. Правило ВарнсдорфаПри обходе доски коня следует всякий раз ставить на поле, из которого он может сделать наименьшее число ходов на еще не пройденные поля; если таких полей несколько, то можно выбрать любое из них. согласен. (посмотрел в код :) в части алгоритма выбора - принципиально разные подходы. ... |
|||
:
Нравится:
Не нравится:
|
|||
03.04.2012, 00:49 |
|
пятничная задачка (про) коня
|
|||
---|---|---|---|
#18+
Метод Варнсдорфа pl-sql-ный отрабатывает за 15 сотых секунд. Sql-ый вариант не справился за 990 минут :) Ни у кого идей нету, как на sql можно реализовать "память"? Чтобы запоминать, где конь уже был (кроме connect nocycle) ... |
|||
:
Нравится:
Не нравится:
|
|||
03.04.2012, 10:17 |
|
пятничная задачка (про) коня
|
|||
---|---|---|---|
#18+
ukkuМетод Варнсдорфа pl-sql-ный отрабатывает за 15 сотых секунд. Sql-ый вариант не справился за 990 минут :) Ни у кого идей нету, как на sql можно реализовать "память"? Чтобы запоминать, где конь уже был (кроме connect nocycle)Через recursive subquery factoring можно, но там куча ограничений на запрос. ... |
|||
:
Нравится:
Не нравится:
|
|||
03.04.2012, 10:25 |
|
пятничная задачка (про) коня
|
|||
---|---|---|---|
#18+
ukkuМетод Варнсдорфа pl-sql-ный отрабатывает за 15 сотых секунд. Sql-ый вариант не справился за 990 минут :) Ни у кого идей нету, как на sql можно реализовать "память"? Чтобы запоминать, где конь уже был (кроме connect nocycle) вы же траекторию рисуете - в ней всё есть ... |
|||
:
Нравится:
Не нравится:
|
|||
03.04.2012, 10:48 |
|
пятничная задачка (про) коня
|
|||
---|---|---|---|
#18+
ukkuМетод Варнсдорфа pl-sql-ный отрабатывает за 15 сотых секунд. Sql-ый вариант не справился за 990 минут :) Ни у кого идей нету, как на sql можно реализовать "память"? Чтобы запоминать, где конь уже был (кроме connect nocycle) В классике алгоритмизации это состояние хранит стек рекурсии. Попытка развернуть это в таблицу - конечно оригинально - но будет антипаттерном с точки зрения ресурсов IMHO. ... |
|||
:
Нравится:
Не нравится:
|
|||
03.04.2012, 12:05 |
|
пятничная задачка (про) коня
|
|||
---|---|---|---|
#18+
maytonПопытка развернуть это в таблицу - конечно оригинально - но будет антипаттерном с точки зрения ресурсов IMHO. Смысл извращения в самом извращение :) Надо было б написать по-человечески взяли бы плюсы или тому подобное. ... |
|||
:
Нравится:
Не нравится:
|
|||
03.04.2012, 12:14 |
|
пятничная задачка (про) коня
|
|||
---|---|---|---|
#18+
В прошлом году мы где-то доказывали полноту языка SQL по Тьюрингу. Если доказали то можно решить любую задачку. ... |
|||
:
Нравится:
Не нравится:
|
|||
03.04.2012, 12:28 |
|
пятничная задачка (про) коня
|
|||
---|---|---|---|
#18+
maytonВ прошлом году мы где-то доказывали полноту языка SQL по Тьюрингу. Если доказали то можно решить любую задачку.1-е апреля было позавчера. ... |
|||
:
Нравится:
Не нравится:
|
|||
03.04.2012, 12:54 |
|
пятничная задачка (про) коня
|
|||
---|---|---|---|
#18+
dbms_photoshopmaytonВ прошлом году мы где-то доказывали полноту языка SQL по Тьюрингу. Если доказали то можно решить любую задачку.1-е апреля было позавчера. Не важно. Жанр пятничных задачек мне интересен вне зависимости от праздников. Просто не понятна была глубина извращённости решения которую хотел получить автор. ... |
|||
:
Нравится:
Не нравится:
|
|||
03.04.2012, 12:58 |
|
пятничная задачка (про) коня
|
|||
---|---|---|---|
#18+
dbms_photoshopmaytonВ прошлом году мы где-то доказывали полноту языка SQL по Тьюрингу. Если доказали то можно решить любую задачку.1-е апреля было позавчера. offtop: кстати, про первое апреля (тема же как раз от этого числа) признаться, ждал, что первым решением будет селект из дуала заранее понятно какой строки. :) ... |
|||
:
Нравится:
Не нравится:
|
|||
03.04.2012, 13:30 |
|
пятничная задачка (про) коня
|
|||
---|---|---|---|
#18+
orawishdbms_photoshopпропущено... 1-е апреля было позавчера. offtop: кстати, про первое апреля (тема же как раз от этого числа) признаться, ждал, что первым решением будет селект из дуала заранее понятно какой строки. :) Была мысль стишок из вики распарсить ) ... |
|||
:
Нравится:
Не нравится:
|
|||
03.04.2012, 13:41 |
|
пятничная задачка (про) коня
|
|||
---|---|---|---|
#18+
orawish, Мне как-то сразу показалось, что на вход поступает начальная позиция, на выходе - маршрут. Если начальная позиция любая, то есс-но задача особого смысла не имеет. ... |
|||
:
Нравится:
Не нравится:
|
|||
03.04.2012, 14:12 |
|
пятничная задачка (про) коня
|
|||
---|---|---|---|
#18+
ukkuМетод Варнсдорфа pl-sql-ный отрабатывает за 15 сотых секунд. Sql-ый вариант не справился за 990 минут :) Ни у кого идей нету, как на sql можно реализовать "память"? Чтобы запоминать, где конь уже был (кроме connect nocycle) память реализуется записью в табличку у меня подобная задача считалась за ночь метод решения - построение дерева всех возможных ходов, с проверками на "такое уже было" ... |
|||
:
Нравится:
Не нравится:
|
|||
03.04.2012, 16:23 |
|
пятничная задачка (про) коня
|
|||
---|---|---|---|
#18+
dbms_photoshoporawish, Мне как-то сразу показалось, что на вход поступает начальная позиция, на выходе - маршрут. Если начальная позиция любая, то есс-но задача особого смысла не имеет. недопонял я, про что вы. если решение циклическое, то начальная позиция для него - любая. (т.е. если замкнёте , то решать можно, начиная с какой хотите позиции) ... |
|||
:
Нравится:
Не нравится:
|
|||
03.04.2012, 17:52 |
|
пятничная задачка (про) коня
|
|||
---|---|---|---|
#18+
orawishdbms_photoshoporawish, Мне как-то сразу показалось, что на вход поступает начальная позиция, на выходе - маршрут. Если начальная позиция любая, то есс-но задача особого смысла не имеет. недопонял я, про что вы. если решение циклическое, то начальная позиция для него - любая. (т.е. если замкнёте , то решать можно, начиная с какой хотите позиции)Начиная с произвольной - неинтересно. В этом решении можно увидеть определенные закономерности и заставить двигаться коня согласно их: То же самое касательно закономерностей здесь: А вот если на входе может быть любое поле, а не a1 это уже интересней. ... |
|||
:
Нравится:
Не нравится:
|
|||
03.04.2012, 18:30 |
|
пятничная задачка (про) коня
|
|||
---|---|---|---|
#18+
Я и предлагал рассмотреть самый общий случай. И поле - произвольной области. Не прямогуольное. Или объединение множества прямогольников. Или лабиринт. ... |
|||
:
Нравится:
Не нравится:
|
|||
03.04.2012, 18:33 |
|
пятничная задачка (про) коня
|
|||
---|---|---|---|
#18+
maytonЯ и предлагал рассмотреть самый общий случай. И поле - произвольной области. Не прямогуольное. Или объединение множества прямогольников. Или лабиринт. а кто против? во всяком случае - я не против. рассматривайте ... |
|||
:
Нравится:
Не нравится:
|
|||
03.04.2012, 19:06 |
|
пятничная задачка (про) коня
|
|||
---|---|---|---|
#18+
dbms_photoshop.. А вот если на входе может быть любое поле, а не a1 это уже интересней. и всё же - вашу мысль я не догоняю.. пусть на входе будет любое поле (b8, например). есть возможность на него плюнуть, решить задачу начиная с любого другого поля (a1, например) и если решение циклическое, то для представления решения с началом в b8 достаточно тупо перетащить substr_от_instr_b8 из морды в хвост ... |
|||
:
Нравится:
Не нравится:
|
|||
03.04.2012, 19:24 |
|
пятничная задачка (про) коня
|
|||
---|---|---|---|
#18+
orawishdbms_photoshop.. А вот если на входе может быть любое поле, а не a1 это уже интересней. и всё же - вашу мысль я не догоняю.. пусть на входе будет любое поле (b8, например). есть возможность на него плюнуть, решить задачу начиная с любого другого поля (a1, например) и если решение циклическое, то для представления решения с началом в b8 достаточно тупо перетащить substr_от_instr_b8 из морды в хвостОк, тогда я не догоняю в чем вообще сложность. Чисто от лени я решал без создания дополнительных объектов, кроме того у меня в коде можно видеть "не очень хорошие" названия переменных и прочие антипаттерны. В общем цель была как можно быстрее написать эту рутину. Красным выделено ноу-хау решения. Уже озвученный правило Варнсдорфа Код: plsql 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. 20. 21. 22. 23. 24. 25. 26. 27. 28. 29. 30. 31. 32. 33. 34. 35. 36. 37. 38. 39. 40. 41. 42. 43. 44. 45. 46. 47. 48. 49. 50. 51. 52. 53. 54. 55. 56. 57. 58. 59. 60. 61. 62. 63. 64. 65. 66. 67. 68. 69. 70. 71. 72. 73. 74. 75. 76. 77. 78. 79. 80. 81. 82. 83. 84. 85. 86. 87. 88. 89. 90. 91. 92. 93. 94. 95. 96. 97. 98. 99. 100. 101. 102. 103. 104. 105. 106. 107. 108. 109. 110. 111. 112. 113.
Код: plsql 1. 2. 3. 4. 5. 6. 7. 8. 9. 10.
Процесс поиска замкнутого я уже не автоматизировал, легче было поклацать. ... |
|||
:
Нравится:
Не нравится:
|
|||
04.04.2012, 01:25 |
|
пятничная задачка (про) коня
|
|||
---|---|---|---|
#18+
попробовал sql-ем таблички Код: plsql 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. 20. 21. 22. 23. 24. 25. 26. 27. 28. 29. 30. 31. 32. 33. 34. 35. 36. 37. 38. 39. 40. 41. 42. 43.
запрос Код: plsql 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. 20. 21. 22. 23. 24. 25. 26. 27. 28. 29. 30. 31. 32. 33. 34. 35. 36. 37. 38. 39. 40. 41. 42. 43. 44. 45. 46. 47. 48. 49. 50. 51. 52. 53. 54. 55. 56. 57. 58. 59. 60. 61. 62. 63. 64. 65. 66. 67. 68. 69. 70. 71. 72. 73. 74. 75. 76. 77. 78. 79. 80. 81. 82. 83. 84. 85. 86. 87. 88. 89. 90. 91. 92. 93. 94. 95. 96. 97. 98. 99. 100. 101. 102. 103. 104. 105. 106. 107. 108. 109. 110. 111. 112. 113. 114. 115. 116. 117. 118. 119. 120. 121. 122. 123. 124. 125. 126. 127. 128. 129. 130. 131. 132. 133. 134. 135. 136. 137. 138. 139. 140. 141. 142. 143. 144. 145. 146. 147. 148. 149. 150. 151. 152. 153. 154. 155. 156. 157. 158. 159. 160. 161. 162. 163. 164. 165. 166. 167. 168. 169. 170. 171. 172. 173. 174. 175. 176. 177. 178. 179. 180. 181. 182. 183. 184. 185. 186. 187. 188. 189. 190. 191. 192. 193. 194. 195. 196. 197. 198. 199. 200. 201. 202. 203. 204. 205. 206. 207. 208. 209. 210. 211. 212. 213. 214. 215. 216. 217. 218. 219. 220. 221. 222. 223. 224. 225. 226. 227. 228. 229. 230. 231. 232. 233. 234. 235. 236. 237. 238. 239. 240. 241. 242. 243. 244. 245. 246. 247. 248. 249. 250. 251. 252. 253. 254. 255. 256. 257. 258. 259. 260. 261. 262. 263. 264. 265. 266. 267. 268. 269. 270. 271. 272. 273. 274. 275. 276. 277. 278. 279. 280. 281. 282. 283. 284. 285. 286. 287. 288. 289. 290. 291. 292. 293. 294. 295. 296. 297. 298. 299. 300. 301. 302. 303. 304. 305. 306. 307. 308. 309. 310. 311. 312. 313. 314. 315. 316. 317. 318. 319. 320. 321. 322. 323. 324. 325. 326. 327. 328. 329. 330. 331. 332. 333. 334. 335. 336. 337. 338. 339. 340. 341. 342. 343. 344. 345. 346. 347. 348. 349. 350. 351. 352. 353. 354. 355. 356. 357. 358. 359. 360. 361. 362. 363. 364. 365. 366. 367. 368. 369.
на 28 ходу план запроса строится 5 минут :)) оракл, 9-ка по крайней мере, не хочет материализовать запрос из материализованного подзапроса ... |
|||
:
Нравится:
Не нравится:
|
|||
04.04.2012, 07:19 |
|
пятничная задачка (про) коня
|
|||
---|---|---|---|
#18+
dbms_photoshoporawishпропущено... и всё же - вашу мысль я не догоняю.. пусть на входе будет любое поле (b8, например). есть возможность на него плюнуть, решить задачу начиная с любого другого поля (a1, например) и если решение циклическое, то для представления решения с началом в b8 достаточно тупо перетащить substr_от_instr_b8 из морды в хвостОк, тогда я не догоняю в чем вообще сложность. Чисто от лени я решал без создания дополнительных объектов, кроме того у меня в коде можно видеть "не очень хорошие" названия переменных и прочие антипаттерны. В общем цель была как можно быстрее написать эту рутину. Красным выделено ноу-хау решения. .. Процесс поиска замкнутого я уже не автоматизировал, легче было поклацать. а я считаю, что зря вы скромничаете - в том смысле, что очень хорошее решение нарисовали. для задачи 1) оно просто вне конкуренции процесс поклацать до циклического (т.е. решение задачи 2 ) тут Код: plsql 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. 20. 21. 22. 23. 24. 25. 26. 27. 28. 29. 30. 31. 32. 33. 34. 35. 36. 37. 38. 39. 40. 41. 42. 43. 44. 45. 46. 47. 48. 49. 50. 51. 52. 53. 54. 55. 56. 57. 58. 59. 60. 61. 62. 63. 64. 65. 66. 67. 68. 69. 70. 71. 72. 73. 74. 75. 76. 77. 78. 79. 80. 81. 82. 83. 84. 85. 86. 87. 88. 89. 90. 91. 92. 93. 94. 95. 96. 97. 98. 99. 100. 101. 102. 103. 104. 105. 106. 107. 108. 109. 110. 111. 112. 113. 114. 115. 116. 117. 118. 119. 120. 121. 122. 123. 124. 125. 126. 127. 128. 129. 130. 131. 132. 133. 134. 135. 136. 137. 138. 139. 140. 141.
из чего видно, что и задача 2 таким способом решается (по крайней мере) на порядок быстрее, чем моим алгоритмом (сейчас опубликую). но остаются еще: задача 3) - 1001 решение найти и задача 4) таки попробовать оценить их (решений) количество :) ... |
|||
:
Нравится:
Не нравится:
|
|||
04.04.2012, 13:37 |
|
пятничная задачка (про) коня
|
|||
---|---|---|---|
#18+
dbms_photoshop, класс) orawish задача 4 решается у dbms_photoshop примерно, если посчитать произведение всех order by substr(column_value, 1, 2) на каждом шаге. конечно не все из них ведут к правильному решению но ошибку будет на 1-2 порядка) а вот третья задачка интересная, но думаю тоже можно оттолкнутся от той же строки сортировки что и в предыдушем случае только не сортировать по , dbms_random.value а ввести еще какой нибудь дополнительный массив где отмечать пройденные \ не пройденные маршруты. то есть достигнув решения. возвращаемся на n шагов назад. где substr(column_value, 1, 2)>1 и идем в другую сторону. ... |
|||
:
Нравится:
Не нравится:
|
|||
04.04.2012, 14:13 |
|
пятничная задачка (про) коня
|
|||
---|---|---|---|
#18+
Vintdbms_photoshop, класс) orawish задача 4 решается у dbms_photoshop примерно, если посчитать произведение всех order by substr(column_value, 1, 2) на каждом шаге. конечно не все из них ведут к правильному решению но ошибку будет на 1-2 порядка) а вот третья задачка интересная, но думаю тоже можно оттолкнутся от той же строки сортировки что и в предыдушем случае только не сортировать по , dbms_random.value а ввести еще какой нибудь дополнительный массив где отмечать пройденные \ не пройденные маршруты. то есть достигнув решения. возвращаемся на n шагов назад. где substr(column_value, 1, 2)>1 и идем в другую сторону. рассуждения хорошо бы подкреплять вычислениями (многократно ужЕ проверено, что умозрительные оценки в данной задаче совершенно не оправдываются :) ... |
|||
:
Нравится:
Не нравится:
|
|||
04.04.2012, 14:21 |
|
пятничная задачка (про) коня
|
|||
---|---|---|---|
#18+
мой способ - тут Код: plsql 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. 20. 21. 22. 23. 24. 25. 26. 27. 28. 29. 30. 31. 32. 33. 34. 35. 36. 37. 38. 39. 40. 41. 42. 43. 44. 45. 46. 47. 48. 49. 50. 51. 52. 53. 54. 55. 56. 57. 58. 59. 60. 61. 62. 63. 64. 65. 66. 67. 68. 69. 70. 71. 72. 73. 74. 75. 76. 77. 78. 79. 80. 81. 82. 83. 84. 85. 86. 87. 88. 89. 90. 91. 92. 93. 94. 95. 96. 97. 98. 99. 100. 101. 102. 103. 104. 105. 106. 107. 108. 109. 110. 111. 112. 113. 114. 115. 116. 117. 118. 119. 120. 121. 122. 123. 124. 125. 126. 127. 128. 129. 130. 131. 132. 133. 134. 135. 136. 137. 138. 139. 140. 141. 142. 143. 144. 145. 146. 147. 148. 149. 150. 151. 152. 153. 154. 155. 156. 157. 158. 159. 160. 161. 162. 163. 164. 165. 166. 167. 168. 169. 170. 171. 172. 173. 174. 175. 176. 177. 178. 179. 180. 181. 182. 183. 184. 185. 186. 187. 188. 189. 190. 191. 192. 193. 194. 195. 196. 197. 198. 199. 200. 201. 202.
т.е. таки брутфорс, но не задачи целиком, а задачи, разделённой на три фазы (по брутфорсу на фазу) на самом деле - на картинках, что я рисовал выше, сказано буквально всё 1) фаза - 8 ходов, на протяжении которых конь не должен выходить из своего квадранта доски (4x4), и не должен допускать, чтобы вся траектория имела два соседних поля по вертикали. а также требуется, чтобы на 8 ходу конь пришел к полю, соседнему (по горизонтали) с полем старта. 2) фаза - ходы с 9 по 32. здесь в движение приходит и голова и хвост траектории одновременно. то есть скачут как бы два, коня, но одной дивизией - т.е. как бы строй держат ) на каждом ходу. вариантов не много - перебор их проходит быстро. 3) свободной остается половина доски. вторая половина доски здОрово ограничивает количество вариантов. можно, вроде бы и попробовать перебрать их все. однако - увы и ах.. вариантов всё равно слишком, слишком много. тут приходится подключать pl/sql - первым делом , для того, чтобы отсекать ходы после которых гарантированно решение не может быть получено. и вторым делом - для исключения дубликатов позиции (разумеется, это = пройденные поля+позиция коня ). Все. теперь про результаты. если на каждом ходу исключать (из дальнейшего рассмотрения ) дубликаты позиций, то, глядя на позицию после 32 хода, очевидно что решений уникальных не может быть больше двух - ведь подходов к финальной точке лишь два. что, собственно и имеем в результате нашего запроса. Если дубликаты позиций не исключать (комментируем в пакете) Код: plsql 1. 2. 3.
, то решение всё равно будет получено (за в 5-7 раз бОльшее время = 135 секунд у меня получилось ) и решений этих будет числом 21390. пора сделать первый вывод. поскольку на 32 ходу позиция на доске симметричная, то для первых 32 ходов (если мы не будем заставлять коня держать строй ) имеем столько же (ровно 21390) вариантов траектории. умножаем.. :) ... |
|||
:
Нравится:
Не нравится:
|
|||
04.04.2012, 15:07 |
|
пятничная задачка (про) коня
|
|||
---|---|---|---|
#18+
orawish, надеюсь за плагиат не побьют)) Код: plsql 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. 20. 21. 22. 23. 24. 25. 26. 27. 28. 29. 30. 31. 32. 33. 34. 35. 36. 37. 38. 39. 40. 41. 42. 43. 44. 45. 46. 47. 48. 49. 50. 51. 52. 53. 54. 55. 56. 57. 58. 59. 60. 61. 62. 63. 64. 65. 66. 67. 68. 69. 70. 71. 72. 73. 74. 75. 76. 77. 78. 79. 80. 81. 82. 83. 84. 85. 86. 87. 88. 89. 90. 91. 92. 93. 94. 95. 96. 97. 98. 99. 100. 101. 102. 103. 104. 105. 106. 107. 108. 109. 110. 111. 112. 113. 114. 115. 116. 117.
в зависимости от количества ветвлений сильно различается количество вариантов... но свои 2 порядка я получил)) от 10т до 1м ... |
|||
:
Нравится:
Не нравится:
|
|||
04.04.2012, 15:12 |
|
пятничная задачка (про) коня
|
|||
---|---|---|---|
#18+
dbms_photoshop, это попытка таки понакликать (тупым упорством) 1001 различное решение задачи 2) Код: plsql 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. 20. 21. 22. 23. 24. 25. 26. 27. 28. 29. 30. 31. 32. 33. 34. 35. 36. 37. 38. 39. 40. 41. 42. 43. 44. 45. 46. 47. 48. 49. 50. 51. 52. 53. 54. 55. 56. 57. 58. 59. 60. 61. 62. 63. 64. 65. 66. 67. 68. 69. 70. 71. 72. 73. 74. 75. 76. 77. 78. 79. 80. 81. 82. 83. 84. 85. 86. 87. 88. 89. 90. 91. 92. 93. 94. 95. 96. 97. 98. 99. 100. 101. 102. 103. 104. 105. 106. 107. 108. 109. 110. 111. 112. 113. 114. 115. 116. 117. 118. 119. 120. 121. 122. 123. 124. 125. 126. 127. 128. 129. 130. 131.
результат Код: plsql 1. 2. 3. 4. 5.
то есть удалось это за 48 минут, в результате 146611 повторений вашей процедуры (т.е. столько решений задачи 1 было достигнуто), чтобы получить 1001+1870 решений задачи 2, из которых 1001 уникальны ... |
|||
:
Нравится:
Не нравится:
|
|||
04.04.2012, 15:22 |
|
пятничная задачка (про) коня
|
|||
---|---|---|---|
#18+
Vint, однако, не верю. :) по той простой причине, что мои прикидки дают совсем-совсем другой по порядку величины диапазон значений, где может быть результат. вот смотрИте (вспомним комбинаторику) Код: plsql 1. 2. 3. 4. 5. 6. 7. 8.
это количество вариантов позиции, которая могла бы возникнуть на 32 ходу, в случае если бы конь умел летать , но на каждом ходу таки менял цвет поля приземления. реальных позиций, разумеется меньше. но намного ли? на порядок? на два? на три? да хотя бы и так - тут этих порядков 18. ну а количество вариантов траектории для достижения каждой позиции - см. выше результат брутфорса. так что, навскидку, я сказал бы - 1е20..1e25 дополнительные вычисления, разумеется, помогут это уточнить ( / или опровергнуть :) на досуге покручу ... |
|||
:
Нравится:
Не нравится:
|
|||
04.04.2012, 16:18 |
|
пятничная задачка (про) коня
|
|||
---|---|---|---|
#18+
orawish, в том то и дело... конь летать не умеет.. он из каждой позиции может сдвинутся всего на n позиций сумма которых и дает в моем примере ветвления. и каждый ход их максимум 8,а минимум 2, чем и пользуется правило варнсдорфа. произведение всех ветвлений(а не факториал как у Вас) дает количество вариантов, которое было бы, если бы у нас была начальная позиция. но примерно... так как ветвлений может быть от ~75 до ~90, потому как зависит от слепого рандома... и поэтоу как раз получаются числа от нескольких тысяч до нескольких сотен тысяч вариантов на каждый маршрут... я очень смутно помню что в теории игр было чтото похожее и даже методы оценки таких маршрутов... но это было так давно, что успело очень прочно забыться) итого, надо ограничить как то условия. например тем, что позиция известна. иначе вариантов будет в 64 раза больше)) ... |
|||
:
Нравится:
Не нравится:
|
|||
04.04.2012, 16:31 |
|
пятничная задачка (про) коня
|
|||
---|---|---|---|
#18+
Vintorawish, в том то и дело... конь летать не умеет.. он из каждой позиции может сдвинутся всего на n позиций сумма которых и дает в моем примере ветвления. и каждый ход их максимум 8,а минимум 2, чем и пользуется правило варнсдорфа. произведение всех ветвлений(а не факториал как у Вас) дает количество вариантов, которое было бы, если бы у нас была начальная позиция. но примерно... так как ветвлений может быть от ~75 до ~90, потому как зависит от слепого рандома... и поэтоу как раз получаются числа от нескольких тысяч до нескольких сотен тысяч вариантов на каждый маршрут... я очень смутно помню что в теории игр было чтото похожее и даже методы оценки таких маршрутов... но это было так давно, что успело очень прочно забыться) итого, надо ограничить как то условия. например тем, что позиция известна. иначе вариантов будет в 64 раза больше)) как быть с тем, что Код: plsql 1. 2.
? и это только варианты, которые обязаны на 32 ходу соответствовать одной позиции, а их, (позиций) 10 в степени до-фи-га ... |
|||
:
Нравится:
Не нравится:
|
|||
04.04.2012, 16:44 |
|
пятничная задачка (про) коня
|
|||
---|---|---|---|
#18+
orawish, если допустить, что мы начинаем из угла, на первом ходу 2 варианта, на втором 10, на третьем около 80, на четвертом меньше тысячи.. это все можно подсчитать... но потом количество вариантов не продолжает расти экспоненциально, так как начинают попадаться уже пройденные клетки... количество стабилизируется, кстати хорошая задача найти ход с которого количество вариантов не растёт, и к концу ходов начинает спадать. в зависимости от конечных условий всё быстрее(например если из начальной позиции надо прыгнуть до конечной). опять же всё из теории игр. сейчас появилось немного времени попытаюсь найти. где то я точно читал про подобную задачу. ... |
|||
:
Нравится:
Не нравится:
|
|||
04.04.2012, 17:07 |
|
пятничная задачка (про) коня
|
|||
---|---|---|---|
#18+
Vintorawish, если допустить, что мы начинаем из угла, на первом ходу 2 варианта, на втором 10, на третьем около 80, на четвертом меньше тысячи.. это все можно подсчитать... но потом количество вариантов не продолжает расти экспоненциально, так как начинают попадаться уже пройденные клетки... количество стабилизируется, кстати хорошая задача найти ход с которого количество вариантов не растёт, и к концу ходов начинает спадать. в зависимости от конечных условий всё быстрее(например если из начальной позиции надо прыгнуть до конечной). опять же всё из теории игр. сейчас появилось немного времени попытаюсь найти. где то я точно читал про подобную задачу. ну, поскольку я (в основном) долбил задачу от середины, то уверенно могу сказать - и после 32 хода количество вариантов на каждом последующем ходу продолжает будь-здоров как расти (настолько, что перебор без дополнительных мер не имеет шансов). и еще - можете посмотреть на каком (начиная от первого) ходу накрываются тазом брутфорсы и сколько (+ какой прирост на уровень) вариантов уникальных позиций имеют они тогда. ... |
|||
:
Нравится:
Не нравится:
|
|||
04.04.2012, 17:26 |
|
пятничная задачка (про) коня
|
|||
---|---|---|---|
#18+
Vintorawish, если допустить, что мы начинаем из угла, на первом ходу 2 варианта, на втором 10, на третьем около 80, на четвертом меньше тысячи.. это все можно подсчитать... но потом количество вариантов не продолжает расти экспоненциально, так как начинают попадаться уже пройденные клетки... количество стабилизируется, кстати хорошая задача найти ход с которого количество вариантов не растёт, и к концу ходов начинает спадать. в зависимости от конечных условий всё быстрее(например если из начальной позиции надо прыгнуть до конечной). опять же всё из теории игр. сейчас появилось немного времени попытаюсь найти. где то я точно читал про подобную задачу. кстати - про можно посчитать. вот это и есть решение (в смысле - было бы). попробуйте. Эйлер таки не смог (ну, правда, и оракла у него не было ;) ... |
|||
:
Нравится:
Не нравится:
|
|||
04.04.2012, 17:30 |
|
пятничная задачка (про) коня
|
|||
---|---|---|---|
#18+
orawishпроцесс поклацать до циклического (т.е. решение задачи 2 ) тутПросто у меня при тестировании с третьей попытки получился замкнутый маршрут и я решил не париться. :) orawish задача 3) - 1001 решение найтиЕсли начинать не из угла доски, то, думаю, время нахождения 1001 решения сократится в разы. orawish задача 4) таки попробовать оценить их (решений) количествоВот это самое интересное. Как написано по ссылке, которую я уже приводил: http://golovolomka.hobby.ru/books/gik/02.shtml Значительно труднее проблема, состоящая не в отыскании определенного маршрута коня по доске, а в нахождении всех маршрутов и подсчете их числа. Увы, эта задача не решена до сих пор, и шансов на успех немного. Известно, правда, что число решений не превосходит C63168 (число сочетаний из 168 элементов по 63, оно состоит из ста цифр), но больше 30 миллионов. Математик Ф. Миндинг, подошедший к проблеме с алгебраической точки зрения, предложил метод, позволяющий вывести формулу для числа всех решений, однако вычисления, которые следует при этом провести, практически неосуществимы.Интересно что за метод, вычисления для которого практически не осуществимы, при этом для половины доски уже найдено точное число решений. Как бы там ни было, делать свои брутфорсы без изучения работ по тематике из сабжа бессмысленно. ... |
|||
:
Нравится:
Не нравится:
|
|||
04.04.2012, 17:32 |
|
пятничная задачка (про) коня
|
|||
---|---|---|---|
#18+
orawishкстати - про можно посчитать. вот это и есть решение (в смысле - было бы). попробуйте. Эйлер таки не смог (ну, правда, и оракла у него не было ;)Три минуты гугления привели к: 33,439,123,484,294 . ... |
|||
:
Нравится:
Не нравится:
|
|||
04.04.2012, 17:36 |
|
пятничная задачка (про) коня
|
|||
---|---|---|---|
#18+
dbms_photoshop, хм.. а мне казалось что всё проще)))..... ... |
|||
:
Нравится:
Не нравится:
|
|||
04.04.2012, 17:37 |
|
пятничная задачка (про) коня
|
|||
---|---|---|---|
#18+
Созрел быстрый и универсальный алгоритм для обхода произвольных областей клеток. 1) Прозвольная область заполняется заполняющей кривой Гильберта или кривой Пеано с шириной в 4 клетки. Границы кривой обозначаются как стенки которые конь не пересекает. 2) Конь обходит область придерживаясь этого коридора. Поскольку движение коня в коридоре - быстро и детерминировано то в целом конь очень быстро обходит произвольные и сложные области. Кривую Гилберта я взял просто без оснований. Интуитивно. Хотя по ней можно спорить. Возможно есть варианты обхода "змейкой", "спиралью", Z-порядком e.t.c. ... |
|||
:
Нравится:
Не нравится:
|
|||
04.04.2012, 17:40 |
|
пятничная задачка (про) коня
|
|||
---|---|---|---|
#18+
dbms_photoshoporawishкстати - про можно посчитать. вот это и есть решение (в смысле - было бы). попробуйте. Эйлер таки не смог (ну, правда, и оракла у него не было ;)Три минуты гугления привели к: 33,439,123,484,294 . отлично! ответ известен. осталось получить его от оракла :) ... |
|||
:
Нравится:
Не нравится:
|
|||
04.04.2012, 18:01 |
|
пятничная задачка (про) коня
|
|||
---|---|---|---|
#18+
mayton, Уже потихоньку начинает напрягать желание местных обитателей пытаться изобретать велосипед. По ссылке, что я приводил есть абзац: "При каких значениях m и n существует маршрут коня по всем полям доски m*n (с посещением каждого из них по одному разу)?" ... |
|||
:
Нравится:
Не нравится:
|
|||
04.04.2012, 18:15 |
|
пятничная задачка (про) коня
|
|||
---|---|---|---|
#18+
orawishdbms_photoshopпропущено... Три минуты гугления привели к: 33,439,123,484,294 . отлично! ответ известен. осталось получить его от оракла :)Ок, я почитаю в свободное от работы время теорему из приведенного документа на предмет выводы формулы. ... |
|||
:
Нравится:
Не нравится:
|
|||
04.04.2012, 18:16 |
|
пятничная задачка (про) коня
|
|||
---|---|---|---|
#18+
dbms_photoshop, чел, я говорю не о прямоугольных досках. ... |
|||
:
Нравится:
Не нравится:
|
|||
04.04.2012, 18:17 |
|
пятничная задачка (про) коня
|
|||
---|---|---|---|
#18+
dbms_photoshoporawishпропущено... отлично! ответ известен. осталось получить его от оракла :)Ок, я почитаю в свободное от работы время теорему из приведенного документа на предмет выводы формулы. ну а я попробую усовершенствовать силовой вариант. ~2e9 решений полузадачи это не так уж и много. опять же - одно дело посчитать сколько их, а другое - отрисовать их всех ... |
|||
:
Нравится:
Не нравится:
|
|||
04.04.2012, 18:21 |
|
пятничная задачка (про) коня
|
|||
---|---|---|---|
#18+
mayton, Ок, надеюсь не надо доказывать, что, к примеру, для доски с шириной 2 и любой длиной задача неразрешима? Если подумать далее, то можно прийти к заключению, что область можно разбить на некоторые разрешимые подобласти. Обход делается опять же по правилу Варнсдорфа. К чему здесь блистать своими анти познаниями по кривым? ... |
|||
:
Нравится:
Не нравится:
|
|||
04.04.2012, 18:22 |
|
пятничная задачка (про) коня
|
|||
---|---|---|---|
#18+
orawish~2e9 решений полузадачиНе понял при чем здесь два миллиарда. ... |
|||
:
Нравится:
Не нравится:
|
|||
04.04.2012, 18:28 |
|
пятничная задачка (про) коня
|
|||
---|---|---|---|
#18+
dbms_photoshop, я же и говорю о ширине коридора. ... |
|||
:
Нравится:
Не нравится:
|
|||
04.04.2012, 18:36 |
|
пятничная задачка (про) коня
|
|||
---|---|---|---|
#18+
dbms_photoshoporawish~2e9 решений полузадачиНе понял при чем здесь два миллиарда. это бред (). очередное доказательство, что нефиг трендеть на основе домыслов, а надо запросы писать. ... |
|||
:
Нравится:
Не нравится:
|
|||
04.04.2012, 21:32 |
|
пятничная задачка (про) коня
|
|||
---|---|---|---|
#18+
обычным SQL за 0.2 сек на Оракл 9.2? это реально :-) таблицы Код: plsql 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. 20. 21. 22. 23. 24. 25. 26. 27. 28. 29. 30. 31. 32. 33. 34. 35. 36. 37. 38. 39. 40. 41. 42. 43. 44. 45. 46. 47.
запрос Код: plsql 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. 20. 21. 22. 23. 24. 25. 26. 27. 28. 29. 30. 31. 32. 33. 34. 35. 36. 37. 38. 39. 40. 41. 42. 43. 44. 45. 46. 47. 48. 49. 50. 51. 52. 53. 54. 55. 56. 57. 58. 59. 60. 61. 62. 63. 64. 65. 66. 67. 68. 69. 70. 71. 72. 73. 74. 75. 76. 77. 78. 79. 80. 81. 82. 83. 84. 85. 86. 87. 88. 89. 90. 91. 92. 93. 94. 95. 96. 97. 98. 99. 100. 101. 102. 103. 104. 105. 106. 107. 108. 109. 110. 111. 112. 113. 114. 115. 116. 117. 118. 119. 120. 121. 122. 123. 124. 125. 126. 127. 128. 129. 130. 131. 132. 133. 134. 135. 136. 137. 138. 139. 140. 141. 142. 143. 144. 145. 146. 147. 148. 149. 150. 151. 152. 153. 154. 155. 156. 157. 158. 159. 160. 161. 162. 163. 164. 165. 166. 167. 168. 169. 170. 171. 172. 173. 174. 175. 176. 177. 178. 179. 180. 181. 182. 183. 184. 185. 186. 187. 188. 189. 190. 191. 192. 193. 194. 195. 196. 197. 198. 199. 200. 201. 202. 203. 204. 205. 206. 207. 208. 209. 210. 211. 212. 213. 214. 215. 216. 217. 218. 219. 220. 221. 222. 223. 224. 225. 226. 227. 228. 229. 230. 231. 232. 233. 234. 235. 236. 237. 238. 239. 240. 241. 242. 243. 244. 245. 246. 247. 248. 249. 250. 251. 252. 253. 254. 255. 256. 257. 258. 259. 260. 261. 262. 263. 264. 265. 266. 267. 268. 269. 270. 271. 272. 273. 274. 275. 276. 277. 278. 279. 280. 281. 282. 283. 284. 285. 286. 287. 288. 289. 290. 291. 292. 293. 294. 295. 296. 297. 298. 299. 300. 301. 302. 303. 304. 305. 306. 307. 308. 309. 310. 311. 312. 313. 314. 315. 316. 317. 318. 319. 320. 321. 322. 323. 324. 325. 326. 327. 328. 329. 330. 331. 332. 333. 334. 335. 336. 337. 338. 339. 340. 341. 342. 343. 344. 345. 346. 347. 348. 349. 350. 351. 352. 353. 354. 355. 356. 357. 358. 359. 360. 361. 362. 363. 364. 365. 366. 367. 368. 369. 370. 371. 372. 373. 374. 375. 376. 377. 378. 379. 380. 381. 382. 383. 384. 385. 386. 387. 388. 389. 390. 391. 392. 393. 394. 395. 396. 397. 398. 399. 400. 401. 402. 403. 404. 405. 406. 407. 408. 409. 410. 411. 412. 413. 414. 415. 416. 417. 418. 419. 420. 421. 422. 423. 424. 425. 426. 427. 428. 429. 430. 431. 432. 433. 434. 435. 436. 437. 438. 439. 440. 441. 442. 443. 444. 445. 446. 447. 448. 449. 450. 451. 452. 453. 454. 455. 456. 457. 458. 459. 460. 461. 462. 463. 464. 465. 466. 467. 468. 469. 470. 471. 472. 473. 474. 475. 476. 477. 478. 479. 480. 481. 482. 483. 484. 485. 486. 487. 488. 489. 490. 491. 492. 493. 494. 495. 496. 497. 498. 499. 500. 501. 502. 503. 504. 505. 506. 507. 508. 509. 510. 511. 512. 513. 514. 515. 516. 517. 518. 519. 520. 521. 522. 523. 524. 525. 526. 527. 528. 529. 530. 531. 532. 533. 534. 535. 536. 537. 538. 539. 540. 541. 542. 543. 544. 545. 546. 547. 548. 549. 550. 551. 552. 553. 554. 555. 556. 557. 558. 559. 560. 561. 562. 563. 564. 565. 566. 567. 568. 569. 570. 571. 572. 573. 574. 575. 576. 577. 578. 579. 580. 581. 582. 583. 584. 585. 586. 587. 588. 589. 590. 591. 592. 593. 594. 595. 596. 597. 598. 599. 600. 601. 602. 603. 604. 605. 606. 607. 608. 609. 610. 611. 612. 613. 614. 615. 616. 617. 618. 619. 620. 621. 622. 623. 624. 625. 626. 627. 628. 629. 630. 631. 632. 633. 634. 635. 636. 637. 638. 639. 640. 641. 642. 643. 644. 645. 646. 647. 648. 649. 650. 651. 652. 653. 654. 655. 656. 657. 658. 659. 660. 661. 662. 663. 664. 665. 666. 667. 668. 669. 670. 671. 672. 673. 674. 675. 676. 677. 678. 679. 680. 681. 682. 683. 684. 685. 686. 687. 688. 689. 690. 691. 692. 693. 694. 695.
результат: ,1,18,33,50,60,54,64,47,62,56,39,24,7,13,3,9,26,41,58,52,35,25,10,4,19,2,17,11,5,20,14,8,23,40,55,61,51,57,42,59,49,34,44,29,46,63,48,31,16,6,12,27,37,43,53,36,30,45,28,22,32,38,21,15, 11-ки у меня еще нету... возможно, её WITH бы помог обойтись меньшим количеством кода? ... |
|||
:
Нравится:
Не нравится:
|
|||
05.04.2012, 22:53 |
|
пятничная задачка (про) коня
|
|||
---|---|---|---|
#18+
на всякий - я этот запрос вручную не набирал :) Код: plsql 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14.
... |
|||
:
Нравится:
Не нравится:
|
|||
05.04.2012, 23:03 |
|
пятничная задачка (про) коня
|
|||
---|---|---|---|
#18+
оказывается, 11g не любит GROUP BY и аналитику в RECURSIVE WITH с UNION ALL вываливается ORA-32486 а так бы всё красиво :) Код: plsql 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. 20. 21. 22. 23. 24. 25. 26. 27. 28. 29. 30. 31. 32. 33. 34. 35. 36. 37. 38. 39. 40. 41. 42. 43. 44. 45. 46. 47. 48. 49. 50. 51. 52. 53. 54. 55. 56. 57. 58. 59.
... |
|||
:
Нравится:
Не нравится:
|
|||
06.04.2012, 00:51 |
|
пятничная задачка (про) коня
|
|||
---|---|---|---|
#18+
Добил-таки одним запросом :) Код: plsql 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. 20. 21. 22. 23. 24. 25. 26. 27. 28. 29. 30. 31. 32. 33. 34. 35. 36. 37. 38. 39. 40. 41. 42. 43. 44. 45. 46. 47. 48. 49. 50. 51. 52. 53. 54. 55. 56.
для ОРакл 11XE ... |
|||
:
Нравится:
Не нравится:
|
|||
06.04.2012, 01:18 |
|
пятничная задачка (про) коня
|
|||
---|---|---|---|
#18+
Ну ты и демон. Ладно завтра проверю. ... |
|||
:
Нравится:
Не нравится:
|
|||
06.04.2012, 01:37 |
|
пятничная задачка (про) коня
|
|||
---|---|---|---|
#18+
andreymxДобил-таки одним запросом :) .. для ОРакл 11XE а на результат с какой стороны смотреть? Код: plsql 1. 2. 3. 4. 5. 6. 7. 8.
... |
|||
:
Нравится:
Не нравится:
|
|||
06.04.2012, 12:30 |
|
пятничная задачка (про) коня
|
|||
---|---|---|---|
#18+
orawish, номера полей при обходе12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364 ... |
|||
:
Нравится:
Не нравится:
|
|||
06.04.2012, 12:33 |
|
пятничная задачка (про) коня
|
|||
---|---|---|---|
#18+
andreymxorawish, номера полей при обходе1t2t3t4t5t6t7t89t10t11t12t13t14t15t1617t18t19t20t21t22t23t2425t26t27t28t29t30t31t3233t34t35t36t37t38t39t4041t42t43t44t45t46t47t4849t50t51t52t53t54t55t5657t58t59t60t61t62t63t64 ага! теперь понятно :) ... |
|||
:
Нравится:
Не нравится:
|
|||
06.04.2012, 12:38 |
|
пятничная задачка (про) коня
|
|||
---|---|---|---|
#18+
andreymx, чесслово - я не нарочно. это цитирование обалдело :) ... |
|||
:
Нравится:
Не нравится:
|
|||
06.04.2012, 12:43 |
|
пятничная задачка (про) коня
|
|||
---|---|---|---|
#18+
orawishandreymx, чесслово - я не нарочно. это цитирование обалдело :)та мы сами такие :) ... |
|||
:
Нравится:
Не нравится:
|
|||
06.04.2012, 12:44 |
|
пятничная задачка (про) коня
|
|||
---|---|---|---|
#18+
как оказалось, 11g вполне достаточно, чтобы таки решить задачу про все решения тупым перебором. как то грустно даже ... |
|||
:
Нравится:
Не нравится:
|
|||
11.04.2012, 19:05 |
|
пятничная задачка (про) коня
|
|||
---|---|---|---|
#18+
orawish, Аудитория замерла в ожидании. ... |
|||
:
Нравится:
Не нравится:
|
|||
11.04.2012, 19:06 |
|
пятничная задачка (про) коня
|
|||
---|---|---|---|
#18+
dbms_photoshoporawish, Аудитория замерла в ожидании. после 25-го хода количество вариантов позиции начинает уверенно падать. пока - это всё, что могу сказать. а полный расклад обязательно будет, но чуть позже. :) ... |
|||
:
Нравится:
Не нравится:
|
|||
11.04.2012, 19:11 |
|
пятничная задачка (про) коня
|
|||
---|---|---|---|
#18+
Эээ ... пора звать автора "Стебелька". Уж у него-то есть быстрое решение по этой задаче. ... |
|||
:
Нравится:
Не нравится:
|
|||
11.04.2012, 19:25 |
|
пятничная задачка (про) коня
|
|||
---|---|---|---|
#18+
maytonЭээ ... пора звать автора "Стебелька". Уж у него-то есть быстрое решение по этой задаче. не силён я в фольклоре. о чем вы? ... |
|||
:
Нравится:
Не нравится:
|
|||
11.04.2012, 19:33 |
|
пятничная задачка (про) коня
|
|||
---|---|---|---|
#18+
orawishmaytonЭээ ... пора звать автора "Стебелька". Уж у него-то есть быстрое решение по этой задаче. не силён я в фольклоре. о чем вы? А забудь, проехали. ... |
|||
:
Нравится:
Не нравится:
|
|||
11.04.2012, 23:02 |
|
пятничная задачка (про) коня
|
|||
---|---|---|---|
#18+
быстро сказка сказывается, но как всегда дело делается дотолкал я таки в гору этот паровоз. и .. получил, таки от оракла значение, которое и так знал - http://ru.wikipedia.org/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D1%85%D0%BE%D0%B4%D0%B5_%D0%BA%D0%BE%D0%BD%D1%8F Количество всех замкнутых маршрутов коня (гамильтоновых циклов) без учёта направления обхода равно 13 267 364 410 532 (спасибочки предыдущим сетевым и прочим исследователям, а также википедии) четыре картинки (маслом) чего это стоило на (сугубо одной ноде от x2:2 1/4) 1) спейса - чтобы хранить все результаты (причем с учетом, что использовалась compress for query high) надо ~4.9 Tb. но, поскольку всё хранить не надо, а достаточно хранить лишь два шага (из энного считается еэплюспервый), то ,в пике (35 ход) это "всего" 825 Gb ... |
|||
:
Нравится:
Не нравится:
|
|||
18.10.2012, 16:24 |
|
пятничная задачка (про) коня
|
|||
---|---|---|---|
#18+
2) времени (тут мы понимаем, что один шаг состоит из 64/2 = 32 полей) ... |
|||
:
Нравится:
Не нравится:
|
|||
18.10.2012, 16:26 |
|
пятничная задачка (про) коня
|
|||
---|---|---|---|
#18+
4) ну и, собственно, результат ... |
|||
:
Нравится:
Не нравится:
|
|||
18.10.2012, 16:29 |
|
пятничная задачка (про) коня
|
|||
---|---|---|---|
#18+
orawish http://ru.wikipedia.org/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D1%85%D0%BE%D0%B4%D0%B5_%D0%BA%D0%BE%D0%BD%D1%8F Количество всех замкнутых маршрутов коня (гамильтоновых циклов) без учёта направления обхода равно 13 267 364 410 532dbms_photoshopТри минуты гугления привели к: 33,439,123,484,294 .Как же все-таки банально описание того, что процитированная мной цифра неправильная. http://en.wikipedia.org/wiki/Talk%3AKnight%27s_tour Yes, that's the entry, and I agree it's not completely clear. It claims "Loebbing and Wegener give 33,439,123,484,294 for the 8 X 8 board. The value given here is due to B. McKay and agrees with that given by Wegener in his book.". Reading Loebbing and Wegener gives the figure 33,439,123,484,294 (closed, undirected), but it also claims that it's wrong, because 33,439,123,484,294 is not divisible by 4 . It seems to me that the Sloane page is saying that 13,267,364,410,532 is the corrected figure for 33,439,123,484,294, and is therefore the correct number of closed, undirected 8x8 knight's tours. Wolfram's Mathworld agrees with the 13,267,364,410,532 figure, and they cite [Wegener, I. Branching Programs and Binary Decision Diagrams. Philadelphia, PA: SIAM, 2000] which is a book [ISBN 0-898-71458-3]. I don't have the book, but at this point I think we've got enough verifiability, so I'm going ahead. Until a wiki-author reads that book, I think we don't know the number of non-closed tours. Mathworld simply quotes the figure from the paper which gives the wrong figure for the number of closed tours, which must be highly suspect. Adam1729 07:23, 12 April 2007 (UTC) 13,267,364,410,532 ... |
|||
:
Нравится:
Не нравится:
|
|||
19.10.2012, 02:14 |
|
пятничная задачка (про) коня
|
|||
---|---|---|---|
#18+
dbms_photoshop, да, симметрия - существенна для этой задачи. так, очевидно, что решение для количества всех нециклических траекторий может быть получено как сумма 10 расчетов - (например) с начальных полей a1,b1,b2,c1-c3,d1-d4, разумеется, с учетом соответствующего симметрии каждого поля веса. также, для полей большой диагонали (a1,b2,c3,d4) симметрия позволяет вдвое (т.е. диагонально) ограничить и позиции второго хода. ... |
|||
:
Нравится:
Не нравится:
|
|||
19.10.2012, 03:23 |
|
пятничная задачка (про) коня
|
|||
---|---|---|---|
#18+
Код: plsql 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. 20. 21. 22. 23. 24. 25. 26. 27. 28.
Написал тупо в лоб минут за 15. ОКончания работы пока не дождался. Тему не читал :) ... |
|||
:
Нравится:
Не нравится:
|
|||
19.10.2012, 18:11 |
|
пятничная задачка (про) коня
|
|||
---|---|---|---|
#18+
collow.. Написал тупо в лоб минут за 15. ОКончания работы пока не дождался. Тему не читал :) (имхо) ну и напрасно . совершенно не обязательно прыгать на грабли, которые уже известны всем. (и особенно больно, если прыгать с 64-го этажа) ... |
|||
:
Нравится:
Не нравится:
|
|||
19.10.2012, 18:34 |
|
пятничная задачка (про) коня
|
|||
---|---|---|---|
#18+
Ну я как бы ни на что и не претендую. ... |
|||
:
Нравится:
Не нравится:
|
|||
19.10.2012, 19:09 |
|
пятничная задачка (про) коня
|
|||
---|---|---|---|
#18+
collow, Просто решил продемонстрировать свою туполобость? ... |
|||
:
Нравится:
Не нравится:
|
|||
19.10.2012, 19:19 |
|
пятничная задачка (про) коня
|
|||
---|---|---|---|
#18+
Да не, просто зацепил начальный пост о невозможности сделать это на чистом скл и тем более полный перебор. В этом плане да, решил немного выпендриться. Бывает. На самом деле если бы я сразу обратил внимание на дату начального поста, не стал бы вообще заморачиваться. Ну а теперь можно и развитие сюжета почитать. ... |
|||
:
Нравится:
Не нравится:
|
|||
19.10.2012, 19:33 |
|
пятничная задачка (про) коня
|
|||
---|---|---|---|
#18+
Решал относительно недавно эту задачу на MSSQL с помощью рекурсивного CTE (решение очень похоже на это пятничная задачка (про) коня ) сейчас для закрепления материала начал решать ее под оракл тем же методом. каково же было мое удивление, когда я понял, что нельзя использовать конструкции такого вида : Код: plsql 1. 2. 3. 4. 5. 6. 7. 8. 9. 10.
если бы не трюк с MAX(Ss.Id_to1) KEEP (DENSE_RANK FIRST ORDER BY COUNT(*)) , подсмотренный у andreymx , наверно не обошелся бы без Pl\sql. ... |
|||
:
Нравится:
Не нравится:
|
|||
21.02.2013, 23:37 |
|
пятничная задачка (про) коня
|
|||
---|---|---|---|
#18+
init.oraкаково же было мое удивлениеRSFC (recursive subquery factoring clause) вообще сильно отстает от CTE: 11020487 . ... |
|||
:
Нравится:
Не нравится:
|
|||
22.02.2013, 01:43 |
|
пятничная задачка (про) коня
|
|||
---|---|---|---|
#18+
dbms_photoshopinit.oraкаково же было мое удивлениеRSFC (recursive subquery factoring clause) вообще сильно отстает от CTE: 11020487 . Зато в RSFC можно писать в рекурсивной части Код: plsql 1. 2. 3. 4. 5. 6.
что довольно неплохо. ... |
|||
:
Нравится:
Не нравится:
|
|||
22.02.2013, 11:59 |
|
пятничная задачка (про) коня
|
|||
---|---|---|---|
#18+
init.oraРешал относительно недавно эту задачу на MSSQL с помощью рекурсивного CTE (решение очень похоже на это пятничная задачка (про) коня ) сейчас для закрепления материала начал решать ее под оракл тем же методом. каково же было мое удивление, когда я понял, что нельзя использовать конструкции такого вида : Код: plsql 1. 2. 3. 4. 5. 6. 7. 8. 9. 10.
если бы не трюк с MAX(Ss.Id_to1) KEEP (DENSE_RANK FIRST ORDER BY COUNT(*)) , подсмотренный у andreymx , наверно не обошелся бы без Pl\sql. пример (как мне видится) сути вашей проблемы не отображает, ибо, чтобы заработал, достаточно выполнить то, что говорит вам ORA-32042: рекурсивная фраза WITH должна напрямую ссылаться на себя в одной из ветвей UNION ALL Код: plsql 1. 2. 3. 4. 5. 6. 7. 8. 9. 10.
... |
|||
:
Нравится:
Не нравится:
|
|||
22.02.2013, 12:44 |
|
пятничная задачка (про) коня
|
|||
---|---|---|---|
#18+
orawishinit.oraРешал относительно недавно эту задачу на MSSQL с помощью рекурсивного CTE (решение очень похоже на это пятничная задачка (про) коня ) сейчас для закрепления материала начал решать ее под оракл тем же методом. каково же было мое удивление, когда я понял, что нельзя использовать конструкции такого вида : Код: plsql 1. 2. 3. 4. 5. 6. 7. 8. 9. 10.
если бы не трюк с MAX(Ss.Id_to1) KEEP (DENSE_RANK FIRST ORDER BY COUNT(*)) , подсмотренный у andreymx , наверно не обошелся бы без Pl\sql. пример (как мне видится) сути вашей проблемы не отображает, ибо, чтобы заработал, достаточно выполнить то, что говорит вам ORA-32042: рекурсивная фраза WITH должна напрямую ссылаться на себя в одной из ветвей UNION ALL Код: plsql 1. 2. 3. 4. 5. 6. 7. 8. 9. 10.
Понятное дело! пример, который я привел сильно упрощен, чтобы показать суть проблемы с которой я столкнулся. В подзапросе хотел использовать Row_number(), вот так: Код: plsql 1. 2. 3. 4. 5. 6. 7.
... |
|||
:
Нравится:
Не нравится:
|
|||
22.02.2013, 13:14 |
|
пятничная задачка (про) коня
|
|||
---|---|---|---|
#18+
init.oraВ подзапросе хотел использовать Row_number(), вот таккак ты себе представляешь рекрсию по условию над результатами рекурсии. Если предполагаешь сначала сформировать набор, потом фильтровать, так и делай. ... |
|||
:
Нравится:
Не нравится:
|
|||
22.02.2013, 13:18 |
|
пятничная задачка (про) коня
|
|||
---|---|---|---|
#18+
-2-init.oraВ подзапросе хотел использовать Row_number(), вот таккак ты себе представляешь рекрсию по условию над результатами рекурсии. Если предполагаешь сначала сформировать набор, потом фильтровать, так и делай. нет, нет.. никакой рекурсии над рекурсией. хотелось бы сначала отфильтровать записи в зависимости от рекурсивного члена, затем применить ROW_NUMBER, затем отфильтровать по нему. в частности решение andreymx (точнее, последнюю его часть) Код: plsql 1. 2. 3. 4. 5. 6.
я хотел (точнее не хотел, а не знал что можно так использовать MAX(Ss.Id_to1) KEEP (DENSE_RANK FIRST ORDER BY COUNT(*)) ) бы переписать таким образом( в MSSQL это возможно) Код: plsql 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11.
... |
|||
:
Нравится:
Не нравится:
|
|||
22.02.2013, 14:28 |
|
пятничная задачка (про) коня
|
|||
---|---|---|---|
#18+
andreymxобычным SQL за 0.2 сек на Оракл 9.2? это реально :-)А можно два слова о подходе? И что означают колонки и цифры в таблице ss? ... |
|||
:
Нравится:
Не нравится:
|
|||
05.03.2013, 01:31 |
|
пятничная задачка (про) коня
|
|||
---|---|---|---|
#18+
Благодарный читательandreymxобычным SQL за 0.2 сек на Оракл 9.2? это реально :-)А можно два слова о подходе? И что означают колонки и цифры в таблице ss?да там вроде всё понятно - что за подход ... |
|||
:
Нравится:
Не нравится:
|
|||
05.03.2013, 10:02 |
|
пятничная задачка (про) коня
|
|||
---|---|---|---|
#18+
andreymxБлагодарный читательпропущено... А можно два слова о подходе? И что означают колонки и цифры в таблице ss?да там вроде всё понятно - что за подход Он оказался слишком гениален для меня. Так же как и число строк - 2008 в ss. В чем идея? ... |
|||
:
Нравится:
Не нравится:
|
|||
05.03.2013, 11:50 |
|
пятничная задачка (про) коня
|
|||
---|---|---|---|
#18+
dbms_photoshop, Здравствуйте, а вы можете объяснить решение, пожалуйтста. Например, комментариями, не совсем понимаю, что происходит в каждой строке. ... |
|||
:
Нравится:
Не нравится:
|
|||
29.03.2020, 22:18 |
|
пятничная задачка (про) коня
|
|||
---|---|---|---|
#18+
Jack963 dbms_photoshop, Здравствуйте, а вы можете объяснить решение, пожалуйтста. Например, комментариями, не совсем понимаю, что происходит в каждой строке. Смирись. Если ты не в состоянии понять что-либо работающее, ты, тем более, не сможешь создать что-нибудь близкое по сложности сам. Ищи другую нишу для трудоустройства. ... |
|||
:
Нравится:
Не нравится:
|
|||
30.03.2020, 07:56 |
|
пятничная задачка (про) коня
|
|||
---|---|---|---|
#18+
Jack963 dbms_photoshop, Здравствуйте, а вы можете объяснить решение, пожалуйтста. Например, комментариями, не совсем понимаю, что происходит в каждой строке. Вместо того, чтоб почитать про метод ты решило избавиться от процедур и функций и сделать решение более сложным для понимания. Это персональный выбор каждого - включить мозг или заниматься вредительством. ... |
|||
:
Нравится:
Не нравится:
|
|||
30.03.2020, 13:18 |
|
|
start [/forum/topic.php?all=1&fid=52&tid=1881402]: |
0ms |
get settings: |
8ms |
get forum list: |
12ms |
check forum access: |
3ms |
check topic access: |
3ms |
track hit: |
36ms |
get topic data: |
9ms |
get forum data: |
3ms |
get page messages: |
106ms |
get tp. blocked users: |
1ms |
others: | 278ms |
total: | 459ms |
0 / 0 |