Тогда по факту перманент вычисляется довольно быстро, за минуту-полторы.
Точнее, за 53-75 секунд для тех 10 змеек длиной 63 клетки, что я нашел. Это если считать в лоб, т.е. по определению перманента. Для сравнения пришлось написать рекурсивную процедуру его вычисления, т.е. обращающуюся к себе самой, поскольку перманент, подобно детерминанту, можно разложить по строке или столбцу. В руководстве по программированию сказано, что рекурсивные алгоритмы обычно выглядят изящнее, чем нерекурсивные, но имеют два существенных недостатка... В связи с этим рекомендуется по возможности использовать нерекурсивные ("плоские") алгоритмы. В нашем случае, как оказалось, никаких недостатков нет и те же самые перманенты вычисляются за 3.1-3.2 секунды, т.е. в 20 раз быстрее. ))
Ускорил процедуру вычисления перманента еще в 3 с лишним раза, просто не доводя рекурсию до матриц размером 1х1, а останавливаясь на матрицах 3х3. Теперь, когда у нас есть процедура вычисления перманента менее чем за 1 секунду, можно рассматривать какие-то связанные с ним задачки. Владимирович, предложите чего-нибудь. Включите фантазию на трезвую свежую голову! Я уже включил.
Смотрите, какие ассоциации. Андралексу, думаю, понравится, поскольку фантазия у него работает, в отличие от некоторых.
Вот как можно расшифровать слово "уж", змея, змейка: уязвимость vs живучесть, vulnerability VS survivability.
Линкор (в морском бою, не забыли?) и лейнер. Знаете, что такое лейнер? Это такой сменный вкладыш в артиллерийский ствол для повышения его живучести.
"Износ стволов значительно возрастает с увеличением калибра и длины ствола — на линкорах последних серий, имевших пушки калибром 14—16" и длину ствола 45—50 калибров, рассеивание снарядов значительно возрастало уже через несколько десятков (до ста) выстрелов", - сказано в Википедии. И еще: "Живучесть ствола (лейнера) орудия определяется как количество выстрелов, которые может произвести орудие до выхода из строя или снижения кучности выстрелов до неприемлемого уровня".
Будем говорить, что змейка живая, когда ее перманент положителен, и мертвая, когда он нулевой. Мало того, будем последовательно удалять из змейки ее клетки до тех пор, пока она не умрет: удалили n клеток, змейка еще живая, а удалили (n + 1)-ю клетку, она умерла, ее перманент обнулился. Если исходная длина змейки составляла l (эль) клеток, величину s = n/l назовем живучестью змейки, а сопряженную величину s* назовем уязвимостью змейки. Как определить сопряженность? Можно так:
s* = 1 - s, и тогда s + s* = 1 (единица),
но я склонен так:
s* = (1 - s)/(1 + s), и тогда s + s* + ss* = 1.
При этом удалять клетки можно по-разному, тем самым живучесть (уязвимость) бывает разная:
(1) головная, если клетки удаляются с начала змейки;
(2) хвостовая, если клетки удаляются с конца змейки;
(3) смешанная, если клетки равновероятно удаляются с начала и с конца;
(4) общая, если клетки равновероятно удаляются по всей длине;
(5) еще отдельно можно рассматривать тело змейки, но мы не будем.
Предварительные результаты следующие. Я взял 50 случайных змеек длиной l = 50 клеток каждая (одна змейка попалась мертвой, и в сумме их не 50, а 49). Головная и хвостовая живучести в среднем получились одинаковые, по 16% (n = 8 в среднем), но смешанная живучесть оказалась равной 22% (n = 11). Общая же живучесть вышла самой большой, 38% (n = 19), т.е. змейку можно всю изрешетить, а она все равно живая. Вот, например, распределение f числа n.
Последняя, 50-я змейка как раз среднестатистическая.
Если честно, то мне энтот перманент ни разу не понадобился
Поэтому, как его лучше считать, мне лень думать
Хорошо, давайте возьмем детерминант вместо перманента, наверняка хоть раз понадобившийся. Чем здесь он хуже перманента?
Во-первых, кроме неотрицательных он принимает и отрицательные значения, что нужно как-то интерпретировать.
Во-вторых, в процессе уменьшения змейки отрицательные значения детерминанта могут перемежаться с положительными и могут как убывать, так и возрастать (и по модулю тоже), что опять же нужно интерпретировать.
Для эксперимента я взял предыдущие 50 змеек длиной 50 клеток и сделал те же самые вычисления, но уже с детерминантом, - последовательно удаляя из змейки клетки, пока он не обнулится (в неудаленной клетке змейки в матрице стоит 1, а в удаленной - 0).
При этом у 27 змеек из 50 детерминант оказался нулевым изначально, до удалений, как у 50-й змейки, и у 5 змеек он обнулился при первом же удалении.
Вот, я как раз и объяснил, чем детерминант хуже перманента в данном случае.
Перманент здесь легко интерпретируется, а детерминант никак не интерпретируется.
Хайдук, ну ты даешь. Здесь вот уже сколько постов подряд я обсуждаю размещение кораблей в игре Морской бой, додумавшись размещать их змейков некоего замечательного вида (сами змейки возникли из предыдущей задачи этой ветки). В связи с этими змейками и размещениями дело дошло до того, что были введены такие важные понятия, как непрерывность, необратимость, живучесть и уязвимость (змеек и, по логике, флотилий). И идеи вроде как еще не закончились...
Я тут поразмыслил и понял, что определять живучесть и уязвимость змеек через перманент это нелогично. Логичнее будет определить их через количество расстановок кораблей в змейках - так же, как определялась необратимость змейки. И как только это количество уменьшится до нуля с убыванием числа клеток змейки, она умрет.
Я тут поразмыслил и понял, что определять живучесть и уязвимость змеек через перманент это нелогично. Логичнее будет определить их через количество расстановок кораблей в змейках - так же, как определялась необратимость змейки. И как только это количество уменьшится до нуля с убыванием числа клеток змейки, она умрет.
Короче, живучесть и уязвимость змейки определяются так же, как в посте #490931, только n определяется по-другому: удалили n клеток - количество расстановок кораблей, потенциально помещающихся в змейку, еще положительно, а удалили (n + 1)-ю клетку, оно обнулилось. Для эксперимента я взял те же самые 50 змеек длиной 50 клеток. В случае головной, хвостовой и смешанной живучестей получилось, что n = 12, а в случае общей живучести вышло n = 8.
Андралексу, думаю, понравится, поскольку фантазия у него работает, в отличие от некоторых.
Спасибо за комплимент! Полагаю, у других фантазия так же замечательно работает.
Догадались теперь, к чему я клоню?
Что можно сказать насчёт лейнеров на флоте? Это такие же сменные блоки, как картриджи для принтеров.
Почему ствол после выстрелов приходит в негодность?
Дело в этой формуле. Снаряд при выстреле никогда не начинает движение идеально строго по прямой траектории, параллельной стволу. По закону Паскаля, хотя векторы сил выталкивания газов на снаряд параллельны, всегда найдутся микродеформации, или другие погрешности снаряда (лейнера), которые изменят направление при ускорении снаряда.
Ствол служит направляющим элементом орудия Чем массивнее снаряд, тем тяжелее приходится стволу корректировать такие ушатывания снаряда.
Перманентность в змейках?
Могу только предположить степени живучести кораблей в игре "Морской Бой".
◘ - однопалубный. Располагается в самых неожиданных местах. При обнаружении шансы у противника на победу возрастают на 9%. Шанс = 3(N+2), где N - количество палуб: одна клетка и восемь прилегающих.
Имеет риск быть легко "вычисленным" в окончании игры.
◘◘ - двухпалубный. Крепче, так как при попадании у противника имеется вероятность промаха 75% на следкющем ходу. При уничтожении, шансы на победу противника возрастают на 12%.
◘◘◘ - трёхпалубный. Чуть крепче, так как 75% ещё умножается на 50% при третьем, окончательном попадании.
Шансы противника 15%.
◘◘◘◘ - четырёхпалубный. Легче всего "вычислить" в начале игры, несмотря на умножения вероятности при попадании 75% 50% 50%. Шансы противника 18%.
Дело в этой формуле. Снаряд при выстреле никогда не начинает движение идеально строго по прямой траектории, параллельной стволу. По закону Паскаля, хотя векторы сил выталкивания газов на снаряд параллельны, всегда найдутся микродеформации, или другие погрешности снаряда (лейнера), которые изменят направление при ускорении снаряда.
Ствол служит направляющим элементом орудия Чем массивнее снаряд, тем тяжелее приходится стволу корректировать такие ушатывания снаряда.
Поэтому артиллерия и перешла на нарезные орудия. Ось вращения обеспечивает гироскопическую стабилизацию
Я пока живучесть отдельных кораблей не подсчитал, а подсчитал только живучесть змейки - как бы контейнера, их всех содержащего. Но одна идея у меня есть.
Я пока живучесть отдельных кораблей не подсчитал, а подсчитал только живучесть змейки - как бы контейнера, их всех содержащего. Но одна идея у меня есть.
Идея следующая. Змейка - это специальная последовательность (по-моему красивая) клеток игрового поля, состоящего из 10х10 = 100 клеток. Змейка имеет определенную емкость, измеряемую числом возможных расстановок в ней 10 кораблей игры "Морской бой". Это число обычно очень велико (но может быть и нулевым). С другой стороны, любую игровую расстановку можно заключить в такую змейку.
Вычеркнем из змейки одну клетку, ее емкость уменьшится или, в лучшем случае, сохранится. Это уменьшение - детримент (ущерб) detr - характеризует данную клетку, а суммарный по всем клеткам детримент описывает саму змейку. Для игры кажется естественным расставлять корабли так, чтобы суммарный детримент всех 20 клеток расстановки кораблей был минимальным, максимизирующим остаточную емкость (неопределенность) змейки. Абсолютным рекордсменом по идее будет расстановка с наибольшей остаточной емкостью ее змейки.
Единственное ограничение, налагаемое, чтобы избежать неподъемных вычислений, - это требование упорядоченности расстановки кораблей: по ходу змейки они должны идти по рангу (линкор, крейсера, эсминцы, катера) или наоборот; эти порядки я обозначаю dir (прямой порядок) и rev (обратный). Так что если вы зададите свою собственную расстановку кораблей, чтобы оценить ее ущербность, она должна быть упорядоченной - в рамках подходящей змейки.
Для эксперимента я обсчитал всё те же 10 случайных змеек длиной 50 клеток и 10 случайных змеек длиной 60 клеток. В целом у змеек длиной 60 емкость существенно выше, а относительный (отнесенный к detr самой змейки) минимальный детримент расстановок заметно ниже.
Вот две из этих змеек длиной 50 и 60 клеток. Числа обозначают детримент клеток, отнесенный к детрименту змейки и выраженный для точности в десятых долях процента, промилле ‰. Расстановки, имеющие минимальный декремент, я намеренно не привожу, хотя и знаю их (здесь они единственные, да и в общем случае их вряд ли много, 1-2-3, мало отличающихся друг от друга). Можете попробовать отыскать вручную (по ‰) расстановки, имеющие минимальный детримент (в %), и, может статься, меня посрамить.
Обе змейки в целом идут сверху вниз и у обеих минимальная расстановка получится rev (поскольку противоидущие - dir - выйдут только хуже).
Вы можете возразить, что просто суммировать детрименты клеток, составляющих флотилию, для определения ее детримента это неправильно. По-хорошему, надо вычесть из змейки всю флотилию целиком и только после этого подсчитывать остаточную емкость змейки с целью ее максимизации по всем флотилиям, вмещаемым исходной змейкой. Да, правильно, но технически это очень сложно. Представьте себе, что емкость змейки составляет миллиард флотилий, которую надо сначала подсчитать, и для каждой из них остаточная емкость змейки составляет хотя бы десять флотилий, если снова не миллиард не миллион...
Промежуточный шаг, который можно сделать, - это вычитать из змейки не отдельные клетки и не целиком флотилии, а корабли. Это лучше, но возражение все равно останется.
Немного осовременил пост #235. Детримент теперь считается чуть правильнее, более соответствует идее, а главное, в конце я вычитаю из змейки полученную рекордную расстановку (флотилию) и вычисляю остаточную емкость змейки. Пусть я и не могу гарантировать максимальность этого остатка (он может оказаться и нулевым), но это хоть какая-то рациональность. К сожалению, программа стала работать вдвое дольше. Обсчет 10 змеек длиной 60 клеток - правда в фоновом режиме - длился почти 6 часов (а длиной 50 клеток - 6 минут).
Рекордные упорядоченные флотилии (рекордные в смысле минимальности суммы детриментов их клеток) я по-прежнему не привожу - во избежание своего возможного посрамления. Но это не мешает вам поискать их вручную, все ‰ для этого приведены. Более того, даже вручную могут обнаружиться неупорядоченные флотилии, которые лучше рекордных (по указанной минимальности), но упорядоченных.
Ниже даны емкости m (измеряемые числом флотилий) все тех же 10 змеек длиной 50 клеток и 10 змеек длиной 60 клеток, а также их остаточные емкости sub m после удаления клеток рекордных (в указанном смысле) упорядоченных флотилий.
Непосредственно видно, во-первых, что удаляемых флотилий может быть не одна, а две, и, во-вторых, что остаточные емкости могут как разниться, так и одновременно обнуляться.
Змейкам, изображенным в посте #235, соответствуют строчка 9 в первой таблице и строчка 8 во второй.
Промежуточный шаг, который можно сделать, - это вычитать из змейки не отдельные клетки и не целиком флотилии, а корабли.
Проделал это с прежними змейками длиной 50 клеток (но уже не за 6, а за 12 минут). В четырех случаях (см. предыдущий пост) результат улучшился (остаточная емкость - sub m - увеличилась), в трех случаях ухудшился и в трех не изменился. В общем, так себе.
А затем я сделал финт ушами: заново вычислил детрименты клеток, суммировав детрименты кораблей, начинающихся в этих точках, и снова все посчитал, но уже по старой схеме. Увы, результат только ухудшился.
Можно было бы попробовать сочетать детрименты клеток с детриментами кораблей по-другому, но у меня есть идея получше.