Ключевое слово
11 | 07 | 2020
Новости Библиотеки
Шахматы Онлайн
Welcome, Guest
Username: Password: Remember me

TOPIC: алгоритмические задачки

алгоритмические задачки 10 Март 2020 18:23 #181

  • Sam Sebe
  • Sam Sebe's Avatar
  • OFFLINE
  • Боярин
  • Posts: 1309
  • Thank you received: 27
  • Karma: 3
Придумал, как выиграть время. Будем подсчитывать не все расстановки кораблей, помещающиеся в змейку, а только те, где корабли идут упорядоченным строем: линкор, за ним 2 крейсера, за ними 3 эсминца и 4 катера в конце, причем порядок допускается как в одну сторону змейки, так и в другую. Если отбраковку кораблей на нужный порядок делать не в самом конце, а в процессе расстановки, то за те же менее чем 5 минут можно рассмотреть змейки длиной уже не 40, а 45 клеток. Последним, 10-м номером попалась змейка, в которую не помещается ни один упорядоченный строй кораблей.

l45_order.png


Но до змеек длиной 63 клетки все равно далеко. ((
Сам себе доктор наук
Last Edit: 10 Март 2020 18:26 by Sam Sebe.

алгоритмические задачки 11 Март 2020 10:59 #182

  • Sam Sebe
  • Sam Sebe's Avatar
  • OFFLINE
  • Боярин
  • Posts: 1309
  • Thank you received: 27
  • Karma: 3
Очередная идея, с виду неплохая. Если подсчитывать одни лишь упорядоченные расстановки кораблей, как в предыдущем посте, то змейку можно было бы разбить на две переменные части и помещать в одну часть, например, линкор с крейсерами, а в другую - эсминцы с катерами, чтобы подсчитывать расстановки кораблей в этих частях раздельно, а затем просто взять и перемножить сделанные подсчеты. Выигрыш получился бы колоссальный. Но тут возникает серьезное осложнение: эти две части будут или могут, во-первых, стыковаться и, во-вторых, касаться друг друга уголками клеток, тогда как корабли не должны ни стыковаться, ни касаться друг друга. Поэтому обе части расстановок придется хранить, причем раздельно, чтобы потом их все можно было перебрать и отбраковать некоторые их пары. Впрочем, не исключено, что различным разбиениям змейки на части будут соответствовать одинаковые расстановки кораблей и поэтому без хранения расстановок для их сравнения не обойтись все равно. Так что априори непонятно, получится выигрыш или нет.
Сам себе доктор наук
Last Edit: 12 Март 2020 05:47 by Sam Sebe.

алгоритмические задачки 14 Март 2020 06:25 #183

  • Sam Sebe
  • Sam Sebe's Avatar
  • OFFLINE
  • Боярин
  • Posts: 1309
  • Thank you received: 27
  • Karma: 3
Идея оказалась очень хорошей. Правда, поначалу я думал резать змейку на части переменной длины, но потом сообразил, что достаточно брать просто максимальные части, одну и другую независимо, и даже не части змейки, а два ее экземпляра. В один экземпляр я помещал большие корабли, а в другой - катера (потом наоборот). Затем расстановки кораблей, найденные в экземплярах, перемножались и в целом невозможные отбраковывались. И за те же менее чем 5 минут удалось рассмотреть 10 змеек длиной уже не 45, а 50 клеток. Последней, 10-й попалась змейка примерно средней емкости.

l50_ordered.png


Но до змеек длиной 63 клетки все равно далеко. ((

Теперь по идее надо попробовать взять не 2, а 3 экземпляра змейки, чтобы в один поместить линкор и крейсера, в другой - эсминцы, а в третий - катера.
Сам себе доктор наук
Last Edit: 14 Март 2020 07:35 by Sam Sebe.

алгоритмические задачки 14 Март 2020 06:49 #184

  • Sam Sebe
  • Sam Sebe's Avatar
  • OFFLINE
  • Боярин
  • Posts: 1309
  • Thank you received: 27
  • Karma: 3
Заметил ошибочку: перепутаны обозначения старта и финиша змейки, надо будет исправить...
Сам себе доктор наук

алгоритмические задачки 14 Март 2020 07:43 #185

  • Sam Sebe
  • Sam Sebe's Avatar
  • OFFLINE
  • Боярин
  • Posts: 1309
  • Thank you received: 27
  • Karma: 3
Исправил.

Фактически программа считает дважды. Сначала корабли упорядочиваются в одну сторону, а затем - вместо того чтобы менять программу - змейка реверсируется и программа считает снова. Змейку-то я реверсировал, а поменять обозначения старта и финиша на печати забыл. Поскольку змейка в данном случае не максимальна, то разница такая, что змейка продолжима (должна быть) со стороны старта, но не продолжима со стороны финиша - что хорошо видно на последнем изображении.
Сам себе доктор наук
Last Edit: 14 Март 2020 08:38 by Sam Sebe.

алгоритмические задачки 15 Март 2020 05:54 #186

  • Sam Sebe
  • Sam Sebe's Avatar
  • OFFLINE
  • Боярин
  • Posts: 1309
  • Thank you received: 27
  • Karma: 3
Sam Sebe wrote:
Теперь по идее надо попробовать взять не 2, а 3 экземпляра змейки, чтобы в один поместить линкор и крейсера, в другой - эсминцы, а в третий - катера.

Удивительно, но получилось много хуже. Для длины змеек в 40 клеток результат воспроизвелся, для 45 клеток я не дождался конца, а для 50 даже и пробовать не стал.
Сам себе доктор наук
Last Edit: 15 Март 2020 05:54 by Sam Sebe.

алгоритмические задачки 15 Март 2020 07:30 #187

  • Sam Sebe
  • Sam Sebe's Avatar
  • OFFLINE
  • Боярин
  • Posts: 1309
  • Thank you received: 27
  • Karma: 3
Sam Sebe wrote:
Sam Sebe wrote:
Теперь по идее надо попробовать взять не 2, а 3 экземпляра змейки, чтобы в один поместить линкор и крейсера, в другой - эсминцы, а в третий - катера.

Удивительно, но получилось много хуже. Для длины змеек в 40 клеток результат воспроизвелся, для 45 клеток я не дождался конца, а для 50 даже и пробовать не стал.

Поскольку экземпляров змейки теперь 3, то при отбраковке невозможных расстановок использовался тройной цикл. Пришлось разбить его на два двойных цикла. Стало лучше, но не намного, если сравнивать, когда экземпляров змейки бралось 2. Результат для 50 клеток воспроизвелся вполне.
Сам себе доктор наук
Last Edit: 15 Март 2020 07:34 by Sam Sebe.

алгоритмические задачки 15 Март 2020 08:10 #188

  • Sam Sebe
  • Sam Sebe's Avatar
  • OFFLINE
  • Боярин
  • Posts: 1309
  • Thank you received: 27
  • Karma: 3
Тоже вот что интересно. В одну сторону змейки (от ее старта к ее финишу) можно поместить одно количество упорядоченных расстановок кораблей, а в другую (от финиша к старту) - другое количество. Относительную разность этих количеств можно считать величиной необратимости рассматриваемой змейки (правда, для слишком коротких змеек, в которые не помещается ни одна упорядоченная расстановка, эта величена не определена). Для рассмотренных змеек длиной, например, 50 клеток она в среднем составляет 70%.
Сам себе доктор наук
Last Edit: 15 Март 2020 08:14 by Sam Sebe.

алгоритмические задачки 15 Март 2020 17:55 #189

  • Sam Sebe
  • Sam Sebe's Avatar
  • OFFLINE
  • Боярин
  • Posts: 1309
  • Thank you received: 27
  • Karma: 3
У нас есть начальные части змеек, срединные и конечные. Их нужно соединить, состыковать в целые змейки. Для этого концы начальных частей должны предшествовать началам срединных частей, а концы срединных частей должны предшествовать началам конечных частей. В общем случае придется перебрать все три совокупности целиком. Если, однако, совокупность срединных частей упорядочить по их началам и конечных частей также, то их целиком уже можно будет не перебирать: как только условие стыковки нарушится, оставшиеся змейки перебирать уже бесполезно. В результате время наших подсчетов сократится в 1.5-2 раза.
Сам себе доктор наук
Last Edit: 15 Март 2020 18:36 by Sam Sebe.

алгоритмические задачки 16 Март 2020 13:40 #190

  • Sam Sebe
  • Sam Sebe's Avatar
  • OFFLINE
  • Боярин
  • Posts: 1309
  • Thank you received: 27
  • Karma: 3
Sam Sebe wrote:
У нас есть начальные части змеек, срединные и конечные. Их нужно соединить, состыковать в целые змейки. Для этого концы начальных частей должны предшествовать началам срединных частей, а концы срединных частей должны предшествовать началам конечных частей. В общем случае придется перебрать все три совокупности целиком. Если, однако, совокупность срединных частей упорядочить по их началам и конечных частей также, то их целиком уже можно будет не перебирать: как только условие стыковки нарушится, оставшиеся змейки перебирать уже бесполезно. В результате время наших подсчетов сократится в 1.5-2 раза.

Эту идею можно немного расширить, упорядочив (отсортировав) не только совокупности срединных и конечных частей змейки, но и совокупность ее начальных частей, и тем самым уменьшить время подсчетов еще на 20%. Уточню, что под частями змейки здесь имеются в виду не столько они сами, сколько размещенные в них корабли.

Однако более существенный выигрыш времени можно получить следующим образом. При стыковке частей змейки друг с другом необходимо проверять, не касаются ли друг друга размещенные в них корабли. Чаще всего это происходит непосредственно на стыках - значит, со стыков и надо начинать проверку. Время подсчетов сокращается примерно вдвое, и обсчитываются змейки длиной уже не 50, а 55 клеток. Правда, не за 5, а за 15 минут машинного времени.

l55_order.png


Впереди маячит длина 60 клеток и... рекордная далее. Но ради них нужно повысить быстродействие программы еще раз в 10, если не в 100. Как это сделать, идей у меня пока нет. Очень возможно, что рекордно длинные змейки будут вмещать уже не десятки и даже не сотни миллионов упорядоченных расстановок кораблей, но миллиарды.
Сам себе доктор наук
Last Edit: 16 Март 2020 13:52 by Sam Sebe.

алгоритмические задачки 19 Март 2020 15:13 #191

  • Sam Sebe
  • Sam Sebe's Avatar
  • OFFLINE
  • Боярин
  • Posts: 1309
  • Thank you received: 27
  • Karma: 3
Sam Sebe wrote:
Правда, не за 5, а за 15 минут машинного времени.
Ускорил программу еще в 5 раз :) и рассмотрел 10 змеек длиной уже не 55, а 60 клеток - за 9 минут машинного времени, причем полторы минуты ушло на (случайный) отлов самих змеек.

l60_order.png


Теперь можно было бы рассмотреть и змейки рекордной длины, но отловить их все или хотя бы 10 штук, если столько вообще существует, - та еще проблема. Например, на отлов 10 змеек длиной 62 клетки программе потребовалось почти полчаса. Надо бы что-то такое придумать ускоряющее...
Сам себе доктор наук

алгоритмические задачки 22 Март 2020 14:00 #192

  • Sam Sebe
  • Sam Sebe's Avatar
  • OFFLINE
  • Боярин
  • Posts: 1309
  • Thank you received: 27
  • Karma: 3
Ускорил программу еще втрое. Теперь можно обсчитывать и максимально длинные змейки. Проблема только найти их побольше: редко очень они попадаются, долго ждать. Т.е. задача вернулась на круги своя, доска лишь увеличилась с 8х8 до 10х10.

quantoforum.ru/mathematics/679-algoritmi...chki?start=90#484174
Сам себе доктор наук
Last Edit: 22 Март 2020 14:05 by Sam Sebe.

алгоритмические задачки 23 Март 2020 07:24 #193

  • Sam Sebe
  • Sam Sebe's Avatar
  • OFFLINE
  • Боярин
  • Posts: 1309
  • Thank you received: 27
  • Karma: 3
Что меня привлекает в этой задаче - так это ее небанальная художественная составляющая, открытия которой не приходится ожидать от собственно художников. Посмотрите хотя бы на ту насыщенность, с которой змейка максимальной (!) длины заполняет доску-полотно. (Пусть я еще не доказал, что 63 клетки - это максимум длины.)

222x222.png


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

алгоритмические задачки 24 Март 2020 07:15 #194

  • Sam Sebe
  • Sam Sebe's Avatar
  • OFFLINE
  • Боярин
  • Posts: 1309
  • Thank you received: 27
  • Karma: 3
Прочитал сейчас о возможно искусственном происхождении коронавируса SARS-CoV-2,
что S-белок дикого коронавируса был искусственно модифицирован.
lenta.ru/news/2020/03/24/2019ncov/

Я вот тоже пытаюсь "модифицировать" алгоритм получения змеек нужной (в идеале максимальной) длины, но плохо получается. Сейчас получение чисто случайное. Фиксируется множество стартовых клеток змейки, желательно наиболее продуктивных, которые последовательно перебираются. Змейка стартует и удлиняется, удлиняется, удлиняется... случайным образом, блуждая, пока не финиширует, поскольку удлиняться дальше некуда. Если змейка выходит нужной длины, она учитывается. И так последовательно перебирается все множество стартовых клеток много-много раз, пока не наберется требуемое число змеек нужной длины.

Но можно было бы делать и по-другому: стартовать не из фиксированных точек, а каждый раз из финишной точки только что полученной змейки - раз за разом. Так вот, первой способ по факту заметно продуктивнее этого, быстрее.
Сам себе доктор наук
Last Edit: 24 Март 2020 07:20 by Sam Sebe.

алгоритмические задачки 25 Март 2020 18:20 #195

  • Sam Sebe
  • Sam Sebe's Avatar
  • OFFLINE
  • Боярин
  • Posts: 1309
  • Thank you received: 27
  • Karma: 3
До этого змейка блуждала по доске совершенно случайно (насколько это возможно с генератором псевдослучайных чисел). Теперь же возникла новая идея. Пусть змейка блуждает случайно, но имеет тенденцию прижиматься к ближайшему краю доски. Это нетрудно реализовать, приписав вес каждому направлению движения в каждой точке доски статически или динамически. Какой вес? Я взял веса, пропорциональные числам Фибоначчи, причем сделал это динамически (надо будет попробовать и статически тоже). Результат не заставил себя ждать: за полчаса удалось поймать 10 змеек длиной 63 клетки и подсчитать количество помещающихся в них расстановок кораблей. Проследите на изображении, как змейка прижимается к ближайшему краю.

l63_order.png


А главное - обнаружились змейки длиной 64 клетки, т.е. предположение о максимальности змеек длиной 63 клетки оказалось ошибочным. Уверен, 64 клетки - максимум уж точно. Задача теперь - побольше наловить змеек этой длины.
Сам себе доктор наук
Last Edit: 25 Март 2020 18:48 by Sam Sebe.

алгоритмические задачки 26 Март 2020 18:48 #196

  • Sam Sebe
  • Sam Sebe's Avatar
  • OFFLINE
  • Боярин
  • Posts: 1309
  • Thank you received: 27
  • Karma: 3
Ну вот, за час поймал 10 змеек максимальной длины и за три минуты их обработал. Поймал с помощью простого приема: если из некоторой клетки стартовала змейка длиной 63 или 64 клетки, то эта клетка с каждым разом испытывалась все чаще. Из 10 змеек 8 штук стартовали из одной и той же клетки, поэтому они друг на друга похожи. Всего ради этих 10 пришлось рассмотреть 31 091 587 змеек, стартовавших из 15 клеток (что это за клетки, догадаться нетрудно).

l64_order.png


Змейки самые длинные, но не самые емкие, выходит. Обратите внимание: из изображенной змейки легко получить еще несколько, просто выправив ей "коленки", какие можно.
Сам себе доктор наук
Last Edit: 26 Март 2020 18:50 by Sam Sebe.

алгоритмические задачки 27 Март 2020 08:06 #197

  • Sam Sebe
  • Sam Sebe's Avatar
  • OFFLINE
  • Боярин
  • Posts: 1309
  • Thank you received: 27
  • Karma: 3
До сих пор я рассматривал по 10 змеек каждой длины. Но почему, собственно, 10? Разделим доску привычным образом на четыре квадранта. В каждом их них змейка занимает некоторое число клеток. Например, в случае змейки длиной 63 клетки по факту встречались лишь числа 14, 15, 16 и 17, всего из которых можно составить 40 комбинаций (различных) с суммой 63. Поэтому я попробовал рассмотреть не 10, а 40 змеек длиной 63 клетки. Получилось не 40, а только 10 комбинаций. Отчасти это связано с тем, что клетки ("норы"), из которых стартовали такие змейки, имели приоритет. Так, из 40 змеек 39 штук стартовали из одной и той же клетки (а финишировали в 15 клетках). Не теория, конечно, но хоть какая-то оценка минимально необходимого для рассмотрения числа змеек.

Попутно попалась очень емкая змейка, из числа 39.

rec173479575.png
Сам себе доктор наук
Last Edit: 27 Март 2020 15:36 by Sam Sebe.

алгоритмические задачки 28 Март 2020 08:13 #198

  • Sam Sebe
  • Sam Sebe's Avatar
  • OFFLINE
  • Боярин
  • Posts: 1309
  • Thank you received: 27
  • Karma: 3
Это я про 63 клетки сказал. А что получилось в случае змеек длиной 64 клетки? Там из 10 змеек, напомню, 8 стартовали из одной и той же клетки 2-го квадранта доски (той, из которой выползали и 39 змеек длиной 63), а 2 - из других. И все змейки, за исключением одной, нарушающей идеальную картину, занимали в каждом из 4 квадрантов одинаковое число клеток - по 16, т.е. 16 + 16 + 16 + 16 = 64. И только у одной змейки - из упомянутых 8 - было иначе: 16 + 15 + 17 + 16 = 64.
Сам себе доктор наук
Last Edit: 28 Март 2020 08:17 by Sam Sebe.

алгоритмические задачки 31 Март 2020 06:48 #199

  • Sam Sebe
  • Sam Sebe's Avatar
  • OFFLINE
  • Боярин
  • Posts: 1309
  • Thank you received: 27
  • Karma: 3
Решил испытать идею в духе марковских процессов. Пусть змейка на каждом очередном шаге старается сохранить направление предыдущего шага, т.е. если на предыдущем шаге она двигалась по горизонтали, то и на следующем шаге она с большей вероятностью будет двигаться по горизонтали, а если по вертикали, то по вертикали. И что же? Эффект практически никакой, если не отрицательный. Попробовал и наоборот: с большей вероятностью не сохранять, а изменять направление движения. Все равно не лучше, если не хуже.

Но сама идея марковости привлекательная. Что присоветуете?
Сам себе доктор наук

алгоритмические задачки 31 Март 2020 06:53 #200

  • Vladimirovich
  • Vladimirovich's Avatar
  • OFFLINE
  • Инквизитор
  • Posts: 86024
  • Thank you received: 1294
  • Karma: 78
Марковский процесс это наоборот, полная независимость от истории
Каждому - своё.

алгоритмические задачки 31 Март 2020 07:05 #201

  • Sam Sebe
  • Sam Sebe's Avatar
  • OFFLINE
  • Боярин
  • Posts: 1309
  • Thank you received: 27
  • Karma: 3
Да, он не зависит от истории, но зависит от настоящего.

Если текущая клетка помечена как i, то следующая с фиксированной вероятностью тоже будет помечена как i, а если текущая была помечена как j, то с той же вероятностью следующая клетка тоже станет j (независимо от всех предыдущих пометок), иначе же - наоборот. Начальная клетка пусть равновероятно помечается i или j. Так вот я делал.

Разумеется, если соответствующий шаг по горизонтали или вертикали реализуется. Поскольку доска ограничена, змейка рано или поздно упрется в край или в саму себя и в этом смысле марковость нарушится, это да.
Сам себе доктор наук
Last Edit: 31 Март 2020 07:27 by Sam Sebe.

алгоритмические задачки 31 Март 2020 12:16 #202

  • Sam Sebe
  • Sam Sebe's Avatar
  • OFFLINE
  • Боярин
  • Posts: 1309
  • Thank you received: 27
  • Karma: 3
Владимирович, что скажете?
Сам себе доктор наук

алгоритмические задачки 31 Март 2020 15:02 #203

  • Vladimirovich
  • Vladimirovich's Avatar
  • OFFLINE
  • Инквизитор
  • Posts: 86024
  • Thank you received: 1294
  • Karma: 78
Ну мне сложно сказать что-то о результате численного эксперимента...
Каждому - своё.

алгоритмические задачки 31 Март 2020 15:24 #204

  • Sam Sebe
  • Sam Sebe's Avatar
  • OFFLINE
  • Боярин
  • Posts: 1309
  • Thank you received: 27
  • Karma: 3
Владимирович, прошу прощения, я в последнем сообщении чего-то наврал, поэтому я его пока уничтожил, буду разбираться.
Сам себе доктор наук

алгоритмические задачки 01 Апр 2020 09:12 #205

  • Sam Sebe
  • Sam Sebe's Avatar
  • OFFLINE
  • Боярин
  • Posts: 1309
  • Thank you received: 27
  • Karma: 3
Sam Sebe wrote:
Владимирович, прошу прощения, я в последнем сообщении чего-то наврал, поэтому я его пока уничтожил, буду разбираться.

Разобрался. То не ошибка была, а скорее недоразумение. Восстанавливать целиком сообщение я не буду, скажу только, что эффект от преимущественного сохранения направления движения змейки все-таки есть, если сравнивать с чисто случайным блужданием, но по сравнению с оказавшимся действительно эффективным прижатием змейки к ближайшему краю доски этот эффект отрицателен. Это можно объяснить тем, что эффективное движение, судя по двузначному числу его изломов и однозначному числу изломов при упомянутом сохранении, сохраниться не стремится.
Сам себе доктор наук
Last Edit: 01 Апр 2020 09:12 by Sam Sebe.

алгоритмические задачки 02 Апр 2020 07:20 #206

  • Sam Sebe
  • Sam Sebe's Avatar
  • OFFLINE
  • Боярин
  • Posts: 1309
  • Thank you received: 27
  • Karma: 3
Змейку на доске можно считать матрицей из нулей и единиц: 1 там, где змейка есть, и 0, где ее нет. И для этой матрицы можно что-нибудь посчитать, линейно-алгебраическое. Что именно? Ну, детерминант и собственные значения и вектора вряд ли здесь уместны, не знаю. А вот перманент этой матрицы, возможно, имеет смысл. Перманент отличается от детерминанта тем, что его члены складываются сами по себе, без коэффициента (символа Леви-Чивиты у членов детерминанта). Правда, вычисление перманента считается трудоемким.

Вики wrote:
В отличие от детерминанта, который может быть легко вычислен, например методом Гаусса, вычисление перманента является очень трудоёмкой вычислительной задачей, относящейся к классу сложности #P-полных задач. Она остаётся #P-полной даже для матриц, состоящих лишь из нулей и единиц.

В настоящее время неизвестен алгоритм решения таких задач за полиномиальное от размера матрицы время. Существование подобного полиномиального алгоритма было бы даже более сильным утверждением, чем знаменитое P=NP.

В декабре 2012 четыре независимые группы исследователей предложили прототип квантового фотонного устройства, вычисляющего перманент матрицы.

Однако в нашем случае я бы этого не сказал. Сделаем прямо в лоб. Возьмем 10 вложенных циклов и в самом внутреннем цикле заведем множество из номеров столбцов. И как только в этом множестве наберется ровно 10 элементов, добавим к перманенту единицу. Казалось бы, придется рассмотреть 1010 комбинаций номеров - десять миллиардов! Но нет, поставим в начале каждого цикла проверку того, является ли соответствующий элемент матрицы нулевым, и если он нулевой, то дальше по циклам ходить незачем. Тогда по факту перманент вычисляется довольно быстро, за минуту-полторы. Я посчитал перманент для змеек длиной 63 клетки, он оказался пятизначным числом, 23-38 тысяч. Теперь надо бы осмыслить, что все это значит.
Сам себе доктор наук

алгоритмические задачки 02 Апр 2020 08:02 #207

  • Vladimirovich
  • Vladimirovich's Avatar
  • OFFLINE
  • Инквизитор
  • Posts: 86024
  • Thank you received: 1294
  • Karma: 78
Sam Sebe wrote:
Теперь надо бы осмыслить, что все это значит.
Вообще, мне казалось, что лучше наоборот... Сначала осмыслить, а потом считать :)
Каждому - своё.

алгоритмические задачки 02 Апр 2020 08:08 #208

  • Sam Sebe
  • Sam Sebe's Avatar
  • OFFLINE
  • Боярин
  • Posts: 1309
  • Thank you received: 27
  • Karma: 3
Не, это как с теоремой существования. Сначала надо посмотреть, не о пустом ли мы говорим. Представьте себе, что перманент пришлось бы считать 4 часа. В любом случае, хотелось бы, чтобы критика была конструктивной.
Сам себе доктор наук

алгоритмические задачки 02 Апр 2020 08:16 #209

  • Vladimirovich
  • Vladimirovich's Avatar
  • OFFLINE
  • Инквизитор
  • Posts: 86024
  • Thank you received: 1294
  • Karma: 78
Sam Sebe wrote:
В любом случае, хотелось бы, чтобы критика была конструктивной.
Куда уж конструктивнее... Совершенно незачем считать то, что никто практически не использует (грета тунберг будет недовольна :))
Каждому - своё.

алгоритмические задачки 02 Апр 2020 09:07 #210

  • Sam Sebe
  • Sam Sebe's Avatar
  • OFFLINE
  • Боярин
  • Posts: 1309
  • Thank you received: 27
  • Karma: 3
Vladimirovich wrote:
Совершенно незачем считать то, что никто практически не использует
Если это относится не к змейкам, а к перманенту, то интуитивно я чувствую, что в данном случае это важная их характеристика.

Sam Sebe wrote:
Я посчитал перманент для змеек длиной 63 клетки, он оказался пятизначным числом, 23-38 тысяч.
Посчитал перманент и для змеек длиной - это ее максимум - 64 клетки, тоже для 10 штук. Добавилась всего одна единичка в матрице, а перманент вырос до 32-48 тысяч.
Сам себе доктор наук
Last Edit: 02 Апр 2020 09:08 by Sam Sebe.
Moderators: Grigoriy
Рейтинг@Mail.ru

Научно-шахматный клуб КвантоФорум