Аля Сапёр, олимпиадная задача Опции

[hardcase]

Вот задача про "Минное поле чудес" (постил Я) брутальная задачка
Меня интересует просто алгоритм. Честно говоря я не представляю, как её можно сделать.

Конечно, сперва надо действовать как в игре Сапёр - с этим проблем нету.
Проблема - как потом считать вероятности?

Сообщение отредактировано: hardcase - 25.01.2006 14:20

[Lapp]

Ага, я подозревал, что задача про расстановки мин появилась неспроста! Вот и продолжение..
Вот тут я решал задачу про расстановку мин, но правда не в прямоугольнике, а линейную (причем, по требованию клиента, решил двумя способами..). Думаю, переделать в двумерный вариант не очень сложно.

Далее, по мере просмотра вариантов нужно просто считать количество мин для каждой клетке. Поясняю. Сначала заводим массив целых чисел размером с поле. Когда найден очередной вариант расстановки, инкрементим те клетки этого массива, где в найденном варианте стоят мины. В конце получим массив, показывающий суммарное число появлений мин в каждой клетке. Осталось поделить эти числа на количество вариантов - все вероятность готова, извольте кушать! Только не забудьте разложить по риал-тарелкам..

Беда только в том, что задача либо довольно долго считается (для нормальных размеров, типа 20) - так как прибавление одного поля даже в линейном варианте удваивает (кажется) количество вычислений, либо жрет памяти немеряно (мой гигабайт ушел играючи на длину массива, кажется, меньше 30). Короче, не все так просто..

[hardcase]

Ага, я подозревал, что задача про расстановки мин появилась неспроста! Вот и продолжение..

Короче идея мне ясна.
Брутфорс расстановок....
Но сдаётся мне можно и без полного перечисления. Правда, в условии сказано, что максимальный размер поля 20х20...
Можно пробовать выделять области, в которых вероятности нахождения мин равны - тогда задачка немного упрощается и брутфорсить надо только в местах, где открытые области соприкасаются с закрытыми.

Кстати про гигабайты - там было ограничение на количество памяти, кажется 64МБ.

Сообщение отредактировано: hardcase - 25.01.2006 17:24

[Lapp]

Извиняюсь за серость, это об оперативной памяти речь идет ?

О ней, родимой. Динамическое программирование (ДП) заключается в том, что ты запоминаешь промежуточные результаты, которые не нужны собственно для окончательно ответа, но потребуются при продолжении расчетов. Поскольку надобятся они в произвольном порядке, то класть это в файл на диск нельзя. Но это ускоряет вычисления (пока хватает памяти). Простейший пример: допустим, тебе в расчетах нужен факториал. Ты пишешь функцию с обычным перемножением чисел. Сначала тебе нужен 20!, потом 15!, потом типа 30! ... Можно все вычислять честно, но тогда на каждом вычислении нужно производить все умножения. А можно иначе: вычислил, скажем, 20! - и запомнил.. Потом, когда понадобился 30! - вынул и домножил на десять чисел. И тоже запомнил - пригодится, когда будет вычисляться типа 33! Это, конечно, очень простой пример..

Брутфорс расстановок....
Но сдаётся мне можно и без полного перечисления. Правда, в условии сказано, что максимальный размер поля 20х20...

Мне так не сдается. Условия слишком специфические, никаких общих принципов тут не присобачишь. Подумай, конечно - может, я что упустил.. Но, судя по тому, что она давалась setare как объект для ДП, я все же прав..

Можно пробовать выделять области, в которых вероятности нахождения мин равны - тогда задачка немного упрощается и брутфорсить надо только в местах, где открытые области соприкасаются с закрытыми.

Перебор есть перебор, и перебирать надо все. Там все слишком завязано на нижнем уровне, оптимизировать не получается (у меня). Для того, чтобы в этом убедиться (или меня разубедить), нужно поиграть с условиями в уме.

Кстати про гигабайты - там было ограничение на количество памяти, кажется 64МБ.

Значит, решать нужно без ДП. Но 20х20 - терпимо. На моей машинке (двойной Athlon MP 2200+) этот размер пролетал за секунды. Введение двумерности усложнит расчет раза в три-четыре (не больше порядка, это точно) на каждой строке, да умножить на кол-во строк.. Короче, вполне терпимо еще, на ночь оставлять не потребуется
Задачка действительно неплохая, респект!