Количество состояний в "морском бое" уменьшается экспоненциально с каждым выстрелом, а метод перебора сходится к решению линейно.Сообщение от GriV
Совершенно верно, об этом я и говорил, когда обосновывал необходимость стрелять в те клетки, где рассчитанная вероятность нахождения корабля максимальна, поскольку даже при промахе в этих клетках подмножество оставшихся вариантов сокращается быстрее всего.
Вот, ты пришел к тому же выводу, что и я в предыдущем сообщении. Более того, хранение базы данных дебютов в "Морском бое" можно сделать довольно глубоким, до 7-8 ходов и более. Это ведь в шахматах каждый ход имеет очень много вариантов, поэтому базы данных дебютов имеют большой размер, а в "морском бое" все проще.
Вот именно, наша задача как раз и заключается в максимальном сокращении кол-ва выстрелов, чтобы противник не успел за это же количество выстрелов уничтожить наш флот.
Но ты не учитываешь, что можно ведь в случае неудачи сначала обстрелять все клетки вокруг корабля, а только потом подбить сам корабль, т.е. окружение его ореолом клеток после подбития само по себе уже не поможет в такой ситуации сократить поле для дальнейшего поиска.
Я вот не знаю пока, можно ли обосновать для конкретной методики максимальное количество выстрелов до потопления флота противника в наихудшем случае, т.е. при самой неудачной стрельбе. Может быть мы вернемся к этому вопросу после полного составления алгоритма для стрельбы.
Существует разница между тем, какие комбинации подвергаются анализу алгоритмом, который я ранее описал, и какие из них являются допустимыми по правилам "Морского боя". Я вот пока не нашел способа, чтобы до анализа комбинации, определить, допустима ли она по правилам. Или, иначе говоря, генерировать только такие расположения кораблей, которые заведомо являются допустимыми. Поэтому нет, сокращение вариантов для оставшихся не учитывается. Мой алгоритм должен перебрать все расположения, как допустимые, так и недопустимые, но конечно же, в результат расчета вероятностей эти недопустимые расположения не включаются. А вот во время выполнения программы они включаются, к сожалению.
Я сильно подозреваю, что множество допустимых расположений кораблей значительно, в сотни раз меньше, чем общее множество всех координат кораблей, по которому я веду перебор своим алгоритмом. О точном соотношении количества элементов в этих двух множествах мы еще поговорим - это не праздный вопрос.
Как ты получил это и следующие числа, можно подробнее?
Рассмотрим следующую ситуацию. Допустим, у тебя 4-палубник стоит вертикально в координате (4,1). Ты при этом не можешь разместить трехпалубник горизонтально в клетках типа (1,1), потому что он будет соприкасаться с четырехпалубником, хотя вроде бы клетки в прямоугольнике с диагональю (1,1)-(2,5) свободны. Учитывает ли твой расчет такие ситуации, особенно когда кораблей на поле уже несколько?
миллиард секунд - 30 лет примерно, у нас было около 100 миллиардов секунд - что и составляет 3000 лет; тут в общем-то точность прикидок и не важна особо, всяко ведь не доживем
Это да. Шутки шутками, но для составления базы дебютов вполне можно себе позволить погонять свои компы с недельку-другую, а если еще с товарищами объединиться - то и вовсе дело в шляпе. Ну, проги для расчетов, понятное дело, желательно будет оптимизировать, чтобы зря электричество не жечь.
Ответить с цитированием
