Comments 4
Выстрелы в a1, a3, в1, в3 гарантирует попадание, но не дает дополнительно информации о расположении кораблей.
В реальных правилах (по крайней мере, по которым мы играли) это не так. Там кроме ответа «попал — не попал» сообщается ещё «потоплен ли корабль, в который попали». Так что 4 выстрела по углам полностью определят конфигурацию, без единого промаха.
А «жадный» алгоритм, стреляющий в поле, вероятность заполнения которого близка к 1/2, не учитывает, что в клетку, гарантированно занятую кораблём, всё равно придётся стрелять. Он может быстрее распознать ситуацию, но потом ему придётся тратить время на все известные клетки. Похоже, что стрелять в клетку с наибольшей вероятностью заполнения было бы выгоднее — мы тратим в среднем 1-p хода, а получаем -p*log(p)-(1-p)*log(1-p) информации. Количество полученной информации на затраченное число ходов при p->1 стремится к бесконечности.
кроме ответа «попал — не попал» сообщается ещё «потоплен ли корабль, в который попали»
ох, а вот это я выпустил из виду… попробую придумать что-нибудь, но простой таблицей для распознавания уже
не отделаться, поскольку есть зависимость от порядка выстрелов
стрелять в клетку с наибольшей вероятностью заполнения было бы выгоднее
и здесь вы правы. Вечером поиграю с измененным алгоритмом и отпишусь, что получилось.
Sign up to leave a comment.
Морской бой как задача распознавания