Проход в штаб противника с минимальными потерями

Автор темы 1sof 
ОбъявленияПоследний пост
ОбъявлениеРаботодателям и кадровым агентствам: Размещение вакансий26.03.2008 03:07
ОбъявлениеЗапущен новый раздел «Задачки и головоломки»29.08.2019 00:42
ОбъявлениеОткрыта свободная публикация вакансий для математиков26.09.2019 16:34
31.10.2019 11:37
Проход в штаб противника с минимальными потерями
Есть квадратное поле боя, разбитое на 100 квадратов. В левом верхнем квадрате база красных, в правом нижнем - белых. Белые минируют каждый квадрат поля боя количеством мин 1,2,3,....., 100. Если красные заходят в квадрат, то теряют столько человек, сколько мин заложено в квадрате. Задача красных - пробиться в штаб белых с минимальными потерями. Задача белых - заминировать поле так, чтобы красные, даже раздобыв список поквадратнго распределение мин, прошли с максимальными потерями. Каковы будут потери при условии, что разведка красных раздобыла этот список и обе стороны придерживаются правильной стратегии?

Штабы минируются, переход между квадратами возможен по горизонтали, вертикали или диагонали.
31.10.2019 20:22
хм
очевидно, что штаб должен минироваться максимальным количеством бомб, так как его клетка наверняка будет посещена. по тем же соображениям соседние клетки минируются оставшимся максимальным количеством и т.д.
31.10.2019 20:39
да, это очевидно
Необходимо привести конкретное число, а не неоднозначно трактуемый алгоритм. Мне пока удалось только оценить это число. Оно лежит в пределах 769-796.
12.11.2019 09:53
хм
Цитата
1sof
Необходимо привести конкретное число, а не неоднозначно трактуемый алгоритм. Мне пока удалось только оценить это число. Оно лежит в пределах 769-796.
Очевидное соображение: рассмотрим участок поля 2 на 2. Очевидно, что кратчайший путь - между крайними диагональными по диагонали, так как независимо от расположения мин в клетках, путь по двум другим угловым путям захватит и диагональные мины и дополнительные. Следовательно, оптимальнейший путь - кратчайший диагональный. Соответственно минирование будет происходить от 100, начиная с базы белых до 92, не доходя до базы красных, которая минируется 1 бомбой. Итого минимальное число бомб, на которых подорвутся красные - не менее 864.
13.11.2019 14:33
Боюсь, что это слишком много
http://forumimage.ru/uploads/20191030/157244064204211327.jpg

Попробуйте улучшить стратегию белых, составив подобную таблицу сумма значений в клетках пути которой будет не ниже приведенной Вами оценки.

По моим соображениям, которые основаны на расчетах, оптимальное значение не выше 796.

Путь -то кратчайший по диагонали, но вовсе не очевидно, что он окажется оптимальным.



Редактировалось 2 раз(а). Последний 13.11.2019 14:51.
13.11.2019 16:51
хм
во-первых нет необходимости минировать большим количеством бомб лагерь красных. или они еще не вышли и уже подорвались? во вторых очевидно, что как вблизи лагеря белых так и вблизи лагеря красных число бомб долждно быть максимальным, так что 88 и 87 должны быть у правого нижнего угла.
13.11.2019 19:52
Да, немного можно оптимизировать таким образом,
Но такая оптимизация не позволяет достичь заявленного Вами нижнего предела. Кстати, абсолютно непонятно откуда Вы взяли это значение. Уж не с потолка ли? Или может компьютерный перебор? Я решал систему уравнений, чтобы получить примерно нижний предел и оценить верхний. А Вы откуда взяли число?

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



Редактировалось 2 раз(а). Последний 13.11.2019 20:00.
Извините, только зарегистрированные пользователи могут публиковать сообщения в этом форуме.

Кликните здесь, чтобы войти