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

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

алгоритмические задачки 17 Апр 2020 11:59 #241

  • Sam Sebe
  • Sam Sebe's Avatar
  • OFFLINE
  • Боярин
  • Posts: 1309
  • Thank you received: 28
  • Karma: 3
Помните, упоминалась выигрышная стратегия в игре "Морской бой": большие корабли размещаем компактно, максимизируя неопределенность в размещении катеров. Я решил проверить эту стратегию если не прямо, то косвенно.

Сначала я размещаю в змейке линкор и два крейсера, оставляя позади них минимальное место для эсминцев и катеров. Затем независимо я размещаю эсминцы, оставляя минимальное место спереди и сзади для линкора с крейсерами и катеров. Потом независимо я размещаю катера, оставляя минимальное место спереди для всех больших кораблей. После этого линкор и крейсера я соединяю с эсминцами, одно множество кораблей с другим. И наконец, к большим кораблям я присоединяю катера, к одному множеству другое. В итоге получается множество флотилий, помещающихся в данную змейку (число их обозначено m). Среди этого множества надо найти флотилию, после удаления клеток которой из змейки в ней, в остаточной змейке, помещается максимально возможное число (sub m) флотилий. Непосредственно найти ее (и sub m) я не могу, а нахожу определенное рекордное решение, одну или несколько рекордных флотилий (и sub m).

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

detrikletka_50_reduced.png
m-tabl-50_2020-04-17.png



Это если определять детрименты поклеточно, как в самый первый раз. А если определять их покорабельно, то результат, как и раньше, получается так себе.

detrisudno_50_reduced.png


Таким образом, косвенно подтверждается, что катера должны иметь наибольший простор для размещения.

Конечно, по большому счету логичнее всего иметь дело с рекордсменами наиболее емкой змейки, здесь последней из 10.
Сам себе доктор наук
Last Edit: 17 Апр 2020 12:54 by Sam Sebe.

алгоритмические задачки 17 Апр 2020 14:35 #242

  • Sam Sebe
  • Sam Sebe's Avatar
  • OFFLINE
  • Боярин
  • Posts: 1309
  • Thank you received: 28
  • Karma: 3
Несколько иначе сориентировал поиск в духе стратегии, более правильно (заодно исправил несерьезную ошибочку, вылезшую в конце третьей и пятой строчек). Результаты заметно изменились, и поклеточно и покорабельно.

detrikletka_50_reduced_rep.png


detrisudno_50_reduced_rep.png


Стратегия если и подтверждается, то не для самых емких змеек. Но стратегию это не опровергает, потому что оптимизация непрямая.
Сам себе доктор наук
Last Edit: 19 Апр 2020 12:06 by Sam Sebe.

алгоритмические задачки 22 Апр 2020 18:59 #243

  • Sam Sebe
  • Sam Sebe's Avatar
  • OFFLINE
  • Боярин
  • Posts: 1309
  • Thank you received: 28
  • Karma: 3
Перепробовал кучу идей, но ничего особо интересного не обнаружил. Вот, пожалуй, единственное исключение.

Если ограничиться стратегией предыдущего поста, то число соответствующих ей флотилий, помещающихся в 10 наших змеек длиной 50 клеток, относительно невелико и остаточное число флотилий для каждой удаляемой флотилии можно посчитать непосредственно (примерно за полчаса в целом), не вычисляя никаких детриментов, и тем самым оценить точность метода последних.

opt_50.png


Видно, если сравнивать sub m из предыдущего поста с этими sub m (всегда не меньшими тех), что метод детриментов работает в общем неплохо.

Например, в 4-й строчке число sub m равно 0. В данном случае существует 3784 флотилии, удовлетворяющие стратегии (из 106 066 возможных упорядоченных флотилий, которые все оказались rev, а dir отсутствуют), но после удаления любой из них, в змейке не хватает места ни для одной упорядоченной флотилии (из 106 066). Напротив, в случае 10-й строки существует одна (единственная) стратегическая флотилия, после удаления которой в змейку все еще помещается 86 650 упорядоченных флотилий - максимум локальный и - для всех 10 змеек - глобальный.
Сам себе доктор наук
Last Edit: 22 Апр 2020 19:49 by Sam Sebe.

алгоритмические задачки 26 Апр 2020 09:52 #244

  • Sam Sebe
  • Sam Sebe's Avatar
  • OFFLINE
  • Боярин
  • Posts: 1309
  • Thank you received: 28
  • Karma: 3
Напрашивается следующая идея, идея седловой точки. С одной стороны, за большими кораблями флотилии (упорядоченной) идут ее катера и каждой расстановке больших кораблей соответствует множество возможных расстановок катеров. С другой стороны, катерам предшествуют большие корабли и каждой расстановке катеров отвечает множество возможных расстановок больших кораблей. И одно множество и другое можно как минимизировать, так и максимизировать, чтобы для седловой клетки или флотилии иметь minmax = maxmin. Но сколько я ни старался, ничего путного из этой идеи у меня не получилось. ((

Зато удалось определить длину "тела" и "хвоста" змейки. Рассмотрим клетку, принадлежащую змейке и лежащую между большими кораблями флотилии, размещенной в змейке, и ее катерами. Этих клеток может быть много, тем более что они зависят и от флотилии и от змейки. Поэтому рассмотрим такую клетку, которая является промежуточной для наибольшего числа флотилий данной змейки. Эта клетка (изредка неединственная) и будет - по определению - разделять "тело" и "хвост" змейки. Для эксперимента я взял по 10 змеек длиной 50, 55, 60, 61, 62, 63 и 64 клетки. В итоге, в среднем, указанная клетка оказалась промежуточной примерно для 40% флотилий, а длина "хвоста" составила менее 30% длины всей змейки, причем я считал и измерял в обоих направлениях (dir и rev).

Погуглил для сравнения: у собственно змей средняя длина хвоста составляет до 20% их длины, вроде как. ))
Сам себе доктор наук
Last Edit: 26 Апр 2020 10:12 by Sam Sebe.

алгоритмические задачки 26 Апр 2020 15:42 #245

  • Sam Sebe
  • Sam Sebe's Avatar
  • OFFLINE
  • Боярин
  • Posts: 1309
  • Thank you received: 28
  • Karma: 3
Вот, изобразил для примера змейку максимальной длины, 64 клетки. Тело цвета охры имеет длину 45 клеток, хвост коричневый из 18 клеток, красная, 46-я клетка - "точка перегиба" - лежит между ними у 828 854 упорядоченных флотилий, которых в прямом направлении змейки насчитывается 2 153 018 штук, т.е. в 38.5% случаев.

zmejka_45118.png


Заметил такую вещь, что в прямом направлении - от начала к концу змейки по построению - хвост в среднем (у змеек всех длин) немного длиннее, чем в обратном направлении. В данном примере длина тела в обратном направлении была бы 47 клеток, а хвост был бы из 16 клеток, красная клетка была бы 48-й и промежуточной в 88494/237418 = 37.3% случаев.

Не знаю, как эту красную клетку назвать биологически по-научному. :)
Сам себе доктор наук
Last Edit: 26 Апр 2020 18:54 by Sam Sebe.

алгоритмические задачки 28 Апр 2020 15:59 #246

  • Sam Sebe
  • Sam Sebe's Avatar
  • OFFLINE
  • Боярин
  • Posts: 1309
  • Thank you received: 28
  • Karma: 3
Еще одна идея, которая напрашивается, - это определить размерность змейки. Вроде бы одномерная, одновременно она существенно покрывает всю доску и как бы двумерная, что намекает на ее промежуточную, фрактальную размерность. С одной стороны, у змейки есть емкость. С другой стороны, у нее есть длина. И нужно их как-то связать степенной зависимостью, но так, чтобы показатель степени был бы между 1 и 2. И сделать это естественным образом, не вводя никаких "эффективных" величин, так любимых физиками. )) Тем более что у змейки, если понадобится, есть тело, хвост (до головы я не додумался) и клетки, которые можно удалять.

Тоже вот бросается в глаза: если удалить из змейки любую размещенную в ней флотилию, то змейка станет сильно дырявой и похожей на Канторово множество, знаменито фрактальное.
Сам себе доктор наук
Last Edit: 28 Апр 2020 16:00 by Sam Sebe.
Moderators: Grigoriy
Рейтинг@Mail.ru

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