Помните, упоминалась выигрышная стратегия в игре "Морской бой": большие корабли размещаем компактно, максимизируя неопределенность в размещении катеров. Я решил проверить эту стратегию если не прямо, то косвенно.
Сначала я размещаю в змейке линкор и два крейсера, оставляя позади них минимальное место для эсминцев и катеров. Затем независимо я размещаю эсминцы, оставляя минимальное место спереди и сзади для линкора с крейсерами и катеров. Потом независимо я размещаю катера, оставляя минимальное место спереди для всех больших кораблей. После этого линкор и крейсера я соединяю с эсминцами, одно множество кораблей с другим. И наконец, к большим кораблям я присоединяю катера, к одному множеству другое. В итоге получается множество флотилий, помещающихся в данную змейку (число их обозначено m). Среди этого множества надо найти флотилию, после удаления клеток которой из змейки в ней, в остаточной змейке, помещается максимально возможное число (sub m) флотилий. Непосредственно найти ее (и sub m) я не могу, а нахожу определенное рекордное решение, одну или несколько рекордных флотилий (и sub m).
Так вот, в духе выигрышной стратегии будем искать рекордсменов не на всем множестве флотилий, а только среди флотилий, оставляющих наибольший простор для катеров. Так сказать, немного поможем рекордсменам, сориентируем их. Результат для наших 10 змеек длиной 50 клеток следующий - не хуже, чем в самый первый раз, а в двух случаях лучше; для удобства сравнения я привожу тот первый результат справа.
Это если определять детрименты поклеточно, как в самый первый раз. А если определять их покорабельно, то результат, как и раньше, получается так себе.
Таким образом, косвенно подтверждается, что катера должны иметь наибольший простор для размещения.
Конечно, по большому счету логичнее всего иметь дело с рекордсменами наиболее емкой змейки, здесь последней из 10.
Несколько иначе сориентировал поиск в духе стратегии, более правильно (заодно исправил несерьезную ошибочку, вылезшую в конце третьей и пятой строчек). Результаты заметно изменились, и поклеточно и покорабельно.
Стратегия если и подтверждается, то не для самых емких змеек. Но стратегию это не опровергает, потому что оптимизация непрямая.
Перепробовал кучу идей, но ничего особо интересного не обнаружил. Вот, пожалуй, единственное исключение.
Если ограничиться стратегией предыдущего поста, то число соответствующих ей флотилий, помещающихся в 10 наших змеек длиной 50 клеток, относительно невелико и остаточное число флотилий для каждой удаляемой флотилии можно посчитать непосредственно (примерно за полчаса в целом), не вычисляя никаких детриментов, и тем самым оценить точность метода последних.
Видно, если сравнивать sub m из предыдущего поста с этими sub m (всегда не меньшими тех), что метод детриментов работает в общем неплохо.
Например, в 4-й строчке число sub m равно 0. В данном случае существует 3784 флотилии, удовлетворяющие стратегии (из 106 066 возможных упорядоченных флотилий, которые все оказались rev, а dir отсутствуют), но после удаления любой из них, в змейке не хватает места ни для одной упорядоченной флотилии (из 106 066). Напротив, в случае 10-й строки существует одна (единственная) стратегическая флотилия, после удаления которой в змейку все еще помещается 86 650 упорядоченных флотилий - максимум локальный и - для всех 10 змеек - глобальный.
Напрашивается следующая идея, идея седловой точки. С одной стороны, за большими кораблями флотилии (упорядоченной) идут ее катера и каждой расстановке больших кораблей соответствует множество возможных расстановок катеров. С другой стороны, катерам предшествуют большие корабли и каждой расстановке катеров отвечает множество возможных расстановок больших кораблей. И одно множество и другое можно как минимизировать, так и максимизировать, чтобы для седловой клетки или флотилии иметь minmax = maxmin. Но сколько я ни старался, ничего путного из этой идеи у меня не получилось. ((
Зато удалось определить длину "тела" и "хвоста" змейки. Рассмотрим клетку, принадлежащую змейке и лежащую между большими кораблями флотилии, размещенной в змейке, и ее катерами. Этих клеток может быть много, тем более что они зависят и от флотилии и от змейки. Поэтому рассмотрим такую клетку, которая является промежуточной для наибольшего числа флотилий данной змейки. Эта клетка (изредка неединственная) и будет - по определению - разделять "тело" и "хвост" змейки. Для эксперимента я взял по 10 змеек длиной 50, 55, 60, 61, 62, 63 и 64 клетки. В итоге, в среднем, указанная клетка оказалась промежуточной примерно для 40% флотилий, а длина "хвоста" составила менее 30% длины всей змейки, причем я считал и измерял в обоих направлениях (dir и rev).
Погуглил для сравнения: у собственно змей средняя длина хвоста составляет до 20% их длины, вроде как. ))
Вот, изобразил для примера змейку максимальной длины, 64 клетки. Тело цвета охры имеет длину 45 клеток, хвост коричневый из 18 клеток, красная, 46-я клетка - "точка перегиба" - лежит между ними у 828 854 упорядоченных флотилий, которых в прямом направлении змейки насчитывается 2 153 018 штук, т.е. в 38.5% случаев.
Заметил такую вещь, что в прямом направлении - от начала к концу змейки по построению - хвост в среднем (у змеек всех длин) немного длиннее, чем в обратном направлении. В данном примере длина тела в обратном направлении была бы 47 клеток, а хвост был бы из 16 клеток, красная клетка была бы 48-й и промежуточной в 88494/237418 = 37.3% случаев.
Не знаю, как эту красную клетку назвать биологически по-научному.
Еще одна идея, которая напрашивается, - это определить размерность змейки. Вроде бы одномерная, одновременно она существенно покрывает всю доску и как бы двумерная, что намекает на ее промежуточную, фрактальную размерность. С одной стороны, у змейки есть емкость. С другой стороны, у нее есть длина. И нужно их как-то связать степенной зависимостью, но так, чтобы показатель степени был бы между 1 и 2. И сделать это естественным образом, не вводя никаких "эффективных" величин, так любимых физиками. )) Тем более что у змейки, если понадобится, есть тело, хвост (до головы я не додумался) и клетки, которые можно удалять.
Тоже вот бросается в глаза: если удалить из змейки любую размещенную в ней флотилию, то змейка станет сильно дырявой и похожей на Канторово множество, знаменито фрактальное.
Каноническая задача в информатике — поиск кратчайшего пути к каждой точке сети. Новый подход превосходит классический алгоритм, изучаемый в учебниках.
Если вы хотите решить сложную задачу, часто помогает организация. Например, можно разбить задачу на части и начать с самых простых. Но такая сортировка имеет свою цену. Вы можете потратить слишком много времени на раскладывание частей по порядку.
Эта дилемма особенно актуальна для одной из самых известных задач в информатике: поиска кратчайшего пути от заданной начальной точки сети до любой другой точки. Это как улучшенная версия задачи, которую приходится решать каждый раз при переезде: найти оптимальный маршрут от нового дома до работы, спортзала и супермаркета.
Интуитивно понятно, что проще всего найти кратчайший путь к ближайшим пунктам назначения. Поэтому, если вы хотите разработать максимально быстрый алгоритм для задачи поиска кратчайшего пути, кажется разумным начать с поиска ближайшей точки, затем следующей по близости и так далее. Но для этого вам потребуется многократно определять, какая точка ближе всего.
Вы будете сортировать точки по расстоянию по мере продвижения. Существует фундаментальное ограничение скорости для любого алгоритма, использующего этот подход: вы не можете двигаться быстрее времени, необходимого для сортировки.
Сорок лет назад исследователи, разрабатывавшие алгоритмы поиска кратчайших путей, столкнулись с этим «барьером сортировки». Теперь группа исследователей разработала новый алгоритм, который его преодолевает . Он не сортирует, но работает быстрее любого алгоритма, который это делает.
