Придумал, как выиграть время. Будем подсчитывать не все расстановки кораблей, помещающиеся в змейку, а только те, где корабли идут упорядоченным строем: линкор, за ним 2 крейсера, за ними 3 эсминца и 4 катера в конце, причем порядок допускается как в одну сторону змейки, так и в другую. Если отбраковку кораблей на нужный порядок делать не в самом конце, а в процессе расстановки, то за те же менее чем 5 минут можно рассмотреть змейки длиной уже не 40, а 45 клеток. Последним, 10-м номером попалась змейка, в которую не помещается ни один упорядоченный строй кораблей.
Очередная идея, с виду неплохая. Если подсчитывать одни лишь упорядоченные расстановки кораблей, как в предыдущем посте, то змейку можно было бы разбить на две переменные части и помещать в одну часть, например, линкор с крейсерами, а в другую - эсминцы с катерами, чтобы подсчитывать расстановки кораблей в этих частях раздельно, а затем просто взять и перемножить сделанные подсчеты. Выигрыш получился бы колоссальный. Но тут возникает серьезное осложнение: эти две части будут или могут, во-первых, стыковаться и, во-вторых, касаться друг друга уголками клеток, тогда как корабли не должны ни стыковаться, ни касаться друг друга. Поэтому обе части расстановок придется хранить, причем раздельно, чтобы потом их все можно было перебрать и отбраковать некоторые их пары. Впрочем, не исключено, что различным разбиениям змейки на части будут соответствовать одинаковые расстановки кораблей и поэтому без хранения расстановок для их сравнения не обойтись все равно. Так что априори непонятно, получится выигрыш или нет.
Идея оказалась очень хорошей. Правда, поначалу я думал резать змейку на части переменной длины, но потом сообразил, что достаточно брать просто максимальные части, одну и другую независимо, и даже не части змейки, а два ее экземпляра. В один экземпляр я помещал большие корабли, а в другой - катера (потом наоборот). Затем расстановки кораблей, найденные в экземплярах, перемножались и в целом невозможные отбраковывались. И за те же менее чем 5 минут удалось рассмотреть 10 змеек длиной уже не 45, а 50 клеток. Последней, 10-й попалась змейка примерно средней емкости.
Но до змеек длиной 63 клетки все равно далеко. ((
Теперь по идее надо попробовать взять не 2, а 3 экземпляра змейки, чтобы в один поместить линкор и крейсера, в другой - эсминцы, а в третий - катера.
Фактически программа считает дважды. Сначала корабли упорядочиваются в одну сторону, а затем - вместо того чтобы менять программу - змейка реверсируется и программа считает снова. Змейку-то я реверсировал, а поменять обозначения старта и финиша на печати забыл. Поскольку змейка в данном случае не максимальна, то разница такая, что змейка продолжима (должна быть) со стороны старта, но не продолжима со стороны финиша - что хорошо видно на последнем изображении.
Теперь по идее надо попробовать взять не 2, а 3 экземпляра змейки, чтобы в один поместить линкор и крейсера, в другой - эсминцы, а в третий - катера.
Удивительно, но получилось много хуже. Для длины змеек в 40 клеток результат воспроизвелся, для 45 клеток я не дождался конца, а для 50 даже и пробовать не стал.
Теперь по идее надо попробовать взять не 2, а 3 экземпляра змейки, чтобы в один поместить линкор и крейсера, в другой - эсминцы, а в третий - катера.
Удивительно, но получилось много хуже. Для длины змеек в 40 клеток результат воспроизвелся, для 45 клеток я не дождался конца, а для 50 даже и пробовать не стал.
Поскольку экземпляров змейки теперь 3, то при отбраковке невозможных расстановок использовался тройной цикл. Пришлось разбить его на два двойных цикла. Стало лучше, но не намного, если сравнивать, когда экземпляров змейки бралось 2. Результат для 50 клеток воспроизвелся вполне.
Тоже вот что интересно. В одну сторону змейки (от ее старта к ее финишу) можно поместить одно количество упорядоченных расстановок кораблей, а в другую (от финиша к старту) - другое количество. Относительную разность этих количеств можно считать величиной необратимости рассматриваемой змейки (правда, для слишком коротких змеек, в которые не помещается ни одна упорядоченная расстановка, эта величена не определена). Для рассмотренных змеек длиной, например, 50 клеток она в среднем составляет 70%.
У нас есть начальные части змеек, срединные и конечные. Их нужно соединить, состыковать в целые змейки. Для этого концы начальных частей должны предшествовать началам срединных частей, а концы срединных частей должны предшествовать началам конечных частей. В общем случае придется перебрать все три совокупности целиком. Если, однако, совокупность срединных частей упорядочить по их началам и конечных частей также, то их целиком уже можно будет не перебирать: как только условие стыковки нарушится, оставшиеся змейки перебирать уже бесполезно. В результате время наших подсчетов сократится в 1.5-2 раза.
У нас есть начальные части змеек, срединные и конечные. Их нужно соединить, состыковать в целые змейки. Для этого концы начальных частей должны предшествовать началам срединных частей, а концы срединных частей должны предшествовать началам конечных частей. В общем случае придется перебрать все три совокупности целиком. Если, однако, совокупность срединных частей упорядочить по их началам и конечных частей также, то их целиком уже можно будет не перебирать: как только условие стыковки нарушится, оставшиеся змейки перебирать уже бесполезно. В результате время наших подсчетов сократится в 1.5-2 раза.
Эту идею можно немного расширить, упорядочив (отсортировав) не только совокупности срединных и конечных частей змейки, но и совокупность ее начальных частей, и тем самым уменьшить время подсчетов еще на 20%. Уточню, что под частями змейки здесь имеются в виду не столько они сами, сколько размещенные в них корабли.
Однако более существенный выигрыш времени можно получить следующим образом. При стыковке частей змейки друг с другом необходимо проверять, не касаются ли друг друга размещенные в них корабли. Чаще всего это происходит непосредственно на стыках - значит, со стыков и надо начинать проверку. Время подсчетов сокращается примерно вдвое, и обсчитываются змейки длиной уже не 50, а 55 клеток. Правда, не за 5, а за 15 минут машинного времени.
Впереди маячит длина 60 клеток и... рекордная далее. Но ради них нужно повысить быстродействие программы еще раз в 10, если не в 100. Как это сделать, идей у меня пока нет. Очень возможно, что рекордно длинные змейки будут вмещать уже не десятки и даже не сотни миллионов упорядоченных расстановок кораблей, но миллиарды.
Ускорил программу еще в 5 раз и рассмотрел 10 змеек длиной уже не 55, а 60 клеток - за 9 минут машинного времени, причем полторы минуты ушло на (случайный) отлов самих змеек.
Теперь можно было бы рассмотреть и змейки рекордной длины, но отловить их все или хотя бы 10 штук, если столько вообще существует, - та еще проблема. Например, на отлов 10 змеек длиной 62 клетки программе потребовалось почти полчаса. Надо бы что-то такое придумать ускоряющее...
Ускорил программу еще втрое. Теперь можно обсчитывать и максимально длинные змейки. Проблема только найти их побольше: редко очень они попадаются, долго ждать. Т.е. задача вернулась на круги своя, доска лишь увеличилась с 8х8 до 10х10.
Что меня привлекает в этой задаче - так это ее небанальная художественная составляющая, открытия которой не приходится ожидать от собственно художников. Посмотрите хотя бы на ту насыщенность, с которой змейка максимальной (!) длины заполняет доску-полотно. (Пусть я еще не доказал, что 63 клетки - это максимум длины.)
По-моему, математикам глупо соревноваться с гуманитариями в понимании и оценке гуманитарных, в т.ч. художественных артефактов, в чем гуманитарии заведомо компетентнее. Умнее будет попытаться сказать о художественном такое слово, на какое гуманитарии попросту не способны, а математики способны.
Прочитал сейчас о возможно искусственном происхождении коронавируса SARS-CoV-2,
что S-белок дикого коронавируса был искусственно модифицирован. lenta.ru/news/2020/03/24/2019ncov/
Я вот тоже пытаюсь "модифицировать" алгоритм получения змеек нужной (в идеале максимальной) длины, но плохо получается. Сейчас получение чисто случайное. Фиксируется множество стартовых клеток змейки, желательно наиболее продуктивных, которые последовательно перебираются. Змейка стартует и удлиняется, удлиняется, удлиняется... случайным образом, блуждая, пока не финиширует, поскольку удлиняться дальше некуда. Если змейка выходит нужной длины, она учитывается. И так последовательно перебирается все множество стартовых клеток много-много раз, пока не наберется требуемое число змеек нужной длины.
Но можно было бы делать и по-другому: стартовать не из фиксированных точек, а каждый раз из финишной точки только что полученной змейки - раз за разом. Так вот, первой способ по факту заметно продуктивнее этого, быстрее.
До этого змейка блуждала по доске совершенно случайно (насколько это возможно с генератором псевдослучайных чисел). Теперь же возникла новая идея. Пусть змейка блуждает случайно, но имеет тенденцию прижиматься к ближайшему краю доски. Это нетрудно реализовать, приписав вес каждому направлению движения в каждой точке доски статически или динамически. Какой вес? Я взял веса, пропорциональные числам Фибоначчи, причем сделал это динамически (надо будет попробовать и статически тоже). Результат не заставил себя ждать: за полчаса удалось поймать 10 змеек длиной 63 клетки и подсчитать количество помещающихся в них расстановок кораблей. Проследите на изображении, как змейка прижимается к ближайшему краю.
А главное - обнаружились змейки длиной 64 клетки, т.е. предположение о максимальности змеек длиной 63 клетки оказалось ошибочным. Уверен, 64 клетки - максимум уж точно. Задача теперь - побольше наловить змеек этой длины.
Ну вот, за час поймал 10 змеек максимальной длины и за три минуты их обработал. Поймал с помощью простого приема: если из некоторой клетки стартовала змейка длиной 63 или 64 клетки, то эта клетка с каждым разом испытывалась все чаще. Из 10 змеек 8 штук стартовали из одной и той же клетки, поэтому они друг на друга похожи. Всего ради этих 10 пришлось рассмотреть 31 091 587 змеек, стартовавших из 15 клеток (что это за клетки, догадаться нетрудно).
Змейки самые длинные, но не самые емкие, выходит. Обратите внимание: из изображенной змейки легко получить еще несколько, просто выправив ей "коленки", какие можно.
До сих пор я рассматривал по 10 змеек каждой длины. Но почему, собственно, 10? Разделим доску привычным образом на четыре квадранта. В каждом их них змейка занимает некоторое число клеток. Например, в случае змейки длиной 63 клетки по факту встречались лишь числа 14, 15, 16 и 17, всего из которых можно составить 40 комбинаций (различных) с суммой 63. Поэтому я попробовал рассмотреть не 10, а 40 змеек длиной 63 клетки. Получилось не 40, а только 10 комбинаций. Отчасти это связано с тем, что клетки ("норы"), из которых стартовали такие змейки, имели приоритет. Так, из 40 змеек 39 штук стартовали из одной и той же клетки (а финишировали в 15 клетках). Не теория, конечно, но хоть какая-то оценка минимально необходимого для рассмотрения числа змеек.
Это я про 63 клетки сказал. А что получилось в случае змеек длиной 64 клетки? Там из 10 змеек, напомню, 8 стартовали из одной и той же клетки 2-го квадранта доски (той, из которой выползали и 39 змеек длиной 63), а 2 - из других. И все змейки, за исключением одной, нарушающей идеальную картину, занимали в каждом из 4 квадрантов одинаковое число клеток - по 16, т.е. 16 + 16 + 16 + 16 = 64. И только у одной змейки - из упомянутых 8 - было иначе: 16 + 15 + 17 + 16 = 64.
Решил испытать идею в духе марковских процессов. Пусть змейка на каждом очередном шаге старается сохранить направление предыдущего шага, т.е. если на предыдущем шаге она двигалась по горизонтали, то и на следующем шаге она с большей вероятностью будет двигаться по горизонтали, а если по вертикали, то по вертикали. И что же? Эффект практически никакой, если не отрицательный. Попробовал и наоборот: с большей вероятностью не сохранять, а изменять направление движения. Все равно не лучше, если не хуже.
Но сама идея марковости привлекательная. Что присоветуете?
Да, он не зависит от истории, но зависит от настоящего.
Если текущая клетка помечена как i, то следующая с фиксированной вероятностью тоже будет помечена как i, а если текущая была помечена как j, то с той же вероятностью следующая клетка тоже станет j (независимо от всех предыдущих пометок), иначе же - наоборот. Начальная клетка пусть равновероятно помечается i или j. Так вот я делал.
Разумеется, если соответствующий шаг по горизонтали или вертикали реализуется. Поскольку доска ограничена, змейка рано или поздно упрется в край или в саму себя и в этом смысле марковость нарушится, это да.
Владимирович, прошу прощения, я в последнем сообщении чего-то наврал, поэтому я его пока уничтожил, буду разбираться.
Разобрался. То не ошибка была, а скорее недоразумение. Восстанавливать целиком сообщение я не буду, скажу только, что эффект от преимущественного сохранения направления движения змейки все-таки есть, если сравнивать с чисто случайным блужданием, но по сравнению с оказавшимся действительно эффективным прижатием змейки к ближайшему краю доски этот эффект отрицателен. Это можно объяснить тем, что эффективное движение, судя по двузначному числу его изломов и однозначному числу изломов при упомянутом сохранении, сохраниться не стремится.
Змейку на доске можно считать матрицей из нулей и единиц: 1 там, где змейка есть, и 0, где ее нет. И для этой матрицы можно что-нибудь посчитать, линейно-алгебраическое. Что именно? Ну, детерминант и собственные значения и вектора вряд ли здесь уместны, не знаю. А вот перманент этой матрицы, возможно, имеет смысл. Перманент отличается от детерминанта тем, что его члены складываются сами по себе, без коэффициента (символа Леви-Чивиты у членов детерминанта). Правда, вычисление перманента считается трудоемким.
Вики wrote:
В отличие от детерминанта, который может быть легко вычислен, например методом Гаусса, вычисление перманента является очень трудоёмкой вычислительной задачей, относящейся к классу сложности #P-полных задач. Она остаётся #P-полной даже для матриц, состоящих лишь из нулей и единиц.
В настоящее время неизвестен алгоритм решения таких задач за полиномиальное от размера матрицы время. Существование подобного полиномиального алгоритма было бы даже более сильным утверждением, чем знаменитое P=NP.
В декабре 2012 четыре независимые группы исследователей предложили прототип квантового фотонного устройства, вычисляющего перманент матрицы.
Однако в нашем случае я бы этого не сказал. Сделаем прямо в лоб. Возьмем 10 вложенных циклов и в самом внутреннем цикле заведем множество из номеров столбцов. И как только в этом множестве наберется ровно 10 элементов, добавим к перманенту единицу. Казалось бы, придется рассмотреть 1010 комбинаций номеров - десять миллиардов! Но нет, поставим в начале каждого цикла проверку того, является ли соответствующий элемент матрицы нулевым, и если он нулевой, то дальше по циклам ходить незачем. Тогда по факту перманент вычисляется довольно быстро, за минуту-полторы. Я посчитал перманент для змеек длиной 63 клетки, он оказался пятизначным числом, 23-38 тысяч. Теперь надо бы осмыслить, что все это значит.
Не, это как с теоремой существования. Сначала надо посмотреть, не о пустом ли мы говорим. Представьте себе, что перманент пришлось бы считать 4 часа. В любом случае, хотелось бы, чтобы критика была конструктивной.
Совершенно незачем считать то, что никто практически не использует
Если это относится не к змейкам, а к перманенту, то интуитивно я чувствую, что в данном случае это важная их характеристика.
Sam Sebe wrote:
Я посчитал перманент для змеек длиной 63 клетки, он оказался пятизначным числом, 23-38 тысяч.
Посчитал перманент и для змеек длиной - это ее максимум - 64 клетки, тоже для 10 штук. Добавилась всего одна единичка в матрице, а перманент вырос до 32-48 тысяч.
и рассмотрел 10 змеек длиной уже не 55, а 60 клеток - за 9 минут машинного времени, причем полторы минуты ушло на (случайный) отлов самих змеек.
