Комментарии 14
> для квадрата 6x6 таких циклов находится уже 19 724 (при этом направленных незамкнутых маршрутов из одного только угла у него обнаруживается 524 486, кто бы мог подумать!), но времени на подсчет уходит уже полдня.
Подтверждаю. Правда, моя программа находит сии числа за считанные секунды, но это уже детали.
Подтверждаю. Правда, моя программа находит сии числа за считанные секунды, но это уже детали.
Другие размеры не считали?
Остальное упомянутое — совпадает. 7*6 — 1067638 циклов. Только у меня она говорит число в два раза меньше, видимо оттого, что я учитывал и тот факт, что циклы в одну и другую сторону эквивалентны, так что можно изначально только один из двух ходов делать. Что сокращает время расчёта ещё в два раза.
7*7 падает через несколько часов отчего-то. 8*8 поставил считаться со времени предыдущей статьи — пока насчиталось несколько десятков миллиардов (незамкнутых) (сколько точно — не знаю, ибо слишком редко числа выводятся).
> В принципе, проверку связности можно свести к линейной сложности, если соседей находить за константное время. Для этого, правда, придется усложнить структуру данных, и, например, перейти к честному представлению графов в виде списка связностей. Но, во-первых, не хотелось бы залезать в дебри
А вот это вот и было бы самое интересное. Можно складывать числа последовательным прибавлением единицы, но никто так не делает. Зачем нужен хаскель, коли на нём нельзя (или очень сложно) сделать то, что на обычном языке программирования делается в одно действие?
7*7 падает через несколько часов отчего-то. 8*8 поставил считаться со времени предыдущей статьи — пока насчиталось несколько десятков миллиардов (незамкнутых) (сколько точно — не знаю, ибо слишком редко числа выводятся).
> В принципе, проверку связности можно свести к линейной сложности, если соседей находить за константное время. Для этого, правда, придется усложнить структуру данных, и, например, перейти к честному представлению графов в виде списка связностей. Но, во-первых, не хотелось бы залезать в дебри
А вот это вот и было бы самое интересное. Можно складывать числа последовательным прибавлением единицы, но никто так не делает. Зачем нужен хаскель, коли на нём нельзя (или очень сложно) сделать то, что на обычном языке программирования делается в одно действие?
Я тоже вначале думал делить пополам, но потом понял, что это не учитывает симметрию и количество геометрически различных циклов так не подсчитаешь. А Хаскель удобен для экспериментов. Из-за компактности кода идеи проверяются быстро. Да и в первой статье я писал, что плясал от языка, я его изучаю для общего развития, как, можно сказать, локомотива функциональной парадигмы.
Какой же это локомотив, когда он даже чемодан на колёсиках с трудом тянет? Это уже как-то смешно — в любом обычном языке заводим массив и вуаля, а в самом лучшем в мире хаскеле это настолько сложно, что даже подумать страшно. Получается, что либо хаскель не столь уж хорош, либо вы его недостаточно изучили. Так что ждём третью статью.
Хаскель я, безусловно, еще знаю плохо, да и лучшим в мире его не называл. У каждого языка свои достоинства и недостатки. Универсального языка не было, нет, да и не надо.
Но и Вы с функциональным подходом, смотрю, не очень знакомы. И раз уж Вы подталкиваете меня к дальнейшим экспериментам, я тоже попробую. Поизучайте. Только не спрашивайте зачем это все насочиняли. Как показывает практика, map и filter вовсю шагают по планете и внедряются уже в Яву. zip, reduce (он же fold), конструкторы списков и прочие генераторы корнями отсюда же. Ждем распространения монад.
Ну а на дальнейшие статьи планы есть. Буду ждать музу )
Прошу прощения, если предыдущий комментарий показался резким, но Вы таки взяли меня «на слабо». Разогнал чемодан и отчитался в последней статье )
Т.е у 7х6 всего в 4 раза больше циклов, чем у 6х6? Хм, что-то у меня уже пятый день лопатит и закончить не может. Да уж, нетороплив.
А для 8х8, если верить википедии, количество циклов составляет 13 триллионов, а незамкнутых маршрутов еще на три порядка больше. В лоб не подсчитаешь.
А для 8х8, если верить википедии, количество циклов составляет 13 триллионов, а незамкнутых маршрутов еще на три порядка больше. В лоб не подсчитаешь.
Но таки да, хотя бы в два раза вычисления можно сократить, тут я совсем поленился. Чтобы не рассматривать ветки, начинающиеся, скажем, ходом (1,1) -> (3,2), клетку (3,2) надо удалить из начальной области, а чтобы в ней заканчивать — сделать ее целевой.
Тогда ожидаемо находится в два раза меньше вариантов за вдвое меньшее время.
Тогда ожидаемо находится в два раза меньше вариантов за вдвое меньшее время.
В общем, после всех оптимизаций и заточки под конкретную задачу удалось ускориться на три с лишним порядка и циклы в квадрате 6х6 теперь считаются за 10 секунд, в прямоугольнике 6х7 — за 20 минут. И даже в 6х8 за полтора дня находится 55488142 цикла (половинка, по Вашему совету, от всех направленных). Думал, кстати, что будет больше. Но до миллиардов все равно далеко и обсчет 7х8 с моими скоростями, по прикидкам, займет полгода-год.
А Вам он может и поддастся, ориентировочно должно оказаться около 10^10 вариантов, если будет меньше, то под вопросом окажется и оценка из Википедии.
А Вам он может и поддастся, ориентировочно должно оказаться около 10^10 вариантов, если будет меньше, то под вопросом окажется и оценка из Википедии.
проблемы обнаруживаются у квадрата со стороной 32
Помнится, еще на курсах писал по Варнсдорфу, так как рекурсию на тот момент ниасилил. Долго пытался понять, почему на больших числах работает не всегда. Если честно, и сейчас понимаю слабо. Эвристика — она такая.
У Гика вроде написано, что и на 8×8 работает не всегда, можно зайти в тупик при неудачных выборах при равном числе соседей.
Для 8х8, читал, экспериментально доказали, что тупиковая ситуация существует для любой начальной клетки, если следовать правилу, но выбор при равных соседях делать неслучайно. Думаю, это верно и для других размеров.
В общем-то, действительно, удивительно, что правило так хорошо работает в большинстве случаев.
В общем-то, действительно, удивительно, что правило так хорошо работает в большинстве случаев.
Разбиение на 16 квадратов 13x13 циклически заполняется и вовсе за полтора десятка секунд. Так что для больших размеров такой метод заполнения мелкими областями все же может оказаться полезным.
Метод разделяй и властвуй во всей красе. Осталось пройти до конца и разбиение на меньшие области сделать рекурсивным. Так из решения 6 получить решения 12, 24,…
А из 50 получить 100 и 200.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Хаскель — ход конем II