Алгоритм сбрасывания бомб

У меня есть n x mматрица, состоящая из неотрицательных целых чисел. Например:

2 3 4 7 1
1 5 2 6 2
4 3 4 2 1
2 1 2 4 1
3 1 3 4 1
2 1 4 3 2
6 9 1 6 4

«Сбрасывание бомбы» уменьшает на единицу число целевой ячейки и всех восьми ее соседей до минимума нуля.

x x x 
x X x
x x x

Что такое алгоритм, который бы определял минимальное количество бомб, необходимое для сокращения всех ячеек до нуля?

Вариант Б (из-за того, что я не внимательный читатель)

На самом деле, первая версия проблемы не та, на которую я ищу ответ. Я не внимательно прочитал всю задачу, есть дополнительные ограничения, скажем так:

Как насчет простой проблемы, когда последовательность в строке не должна увеличиваться:

8 7 6 6 5 возможна входная последовательность

7 8 5 5 2 невозможно, так как 7 -> 8 растет в последовательности.

Возможно, поиск ответа для «более простого» случая поможет найти решение для более сложного.

PS: я считаю, что когда у нас несколько одинаковых ситуаций, требующих минимального количества бомб для очистки верхней линии, мы выбираем тот, который использует большинство бомб с «левой стороны» ряда. Все еще есть доказательства, которые могут быть верными?

Есть способ свести это к простой подзадаче.

Объяснение состоит из двух частей: алгоритм и причина, по которой алгоритм обеспечивает оптимальное решение. Первое не имеет смысла без второго, поэтому я начну с «почему».

Если вы думаете о бомбардировке прямоугольника (предположим, большой прямоугольник - без краевых случаев), вы можете увидеть, что единственный способ уменьшить полый прямоугольник квадратов по периметру до 0 - это бомбить либо периметр, либо бомбить полый прямоугольник квадраты только внутри периметра. Я назову слой периметра 1, а прямоугольник внутри него слоем 2.

Важное понимание заключается в том, что нет точечного бомбардировочного слоя 1, потому что «радиус взрыва», который вы получаете при этом, всегда содержится в радиусе взрыва другого квадрата от слоя 2. Вы должны быть в состоянии легко убедить себя в этом.

Таким образом, мы можем свести проблему к поиску оптимального способа бомбардировки периметра, тогда мы можем повторять это, пока все квадраты не станут равными 0.

Но, конечно, это не всегда найдет оптимальное решение, если можно будет бомбардировать периметр менее чем оптимальным способом, но при использовании X дополнительных бомб упрощается проблема уменьшения внутреннего слоя с помощью> X бомб. Итак, если мы назовем слой разрешения первым, если мы разместим дополнительные X бомб где-нибудь в слое 2 (только внутри слоя 1), сможем ли мы уменьшить усилие последующей бомбардировки слоя 2 более чем на X? Другими словами, мы должны доказать, что можем быть жадными в уменьшении внешнего периметра.

Но мы знаем, что можем быть жадными. Потому что никакая бомба в слое 2 не может быть более эффективной в уменьшении слоя 2 до 0, чем стратегически размещенная бомба в слое 3. И по той же причине, что и раньше - всегда есть бомба, которую мы можем разместить в слое 3, которая затронет каждый квадрат слоя 2, что бомба, помещенная в слой 2, может. Таким образом, нам никогда не повредит быть жадным (в этом смысле жадным).

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

Мы никогда не пострадаем от первой бомбардировки угла до 0, потому что только угол внутреннего слоя может достичь его, поэтому у нас действительно нет выбора (и любая бомба по периметру, которая может достичь угла, имеет радиус взрыва, содержащийся в радиус взрыва от угла внутреннего слоя).

Как только мы это сделаем, квадраты по периметру, прилегающие к углу 0, могут быть достигнуты только через 2 квадрата от внутреннего слоя:

0       A       B

C       X       Y

D       Z

В этот момент периметр фактически представляет собой замкнутую одномерную петлю, потому что любая бомба уменьшит 3 соседних квадрата. За исключением некоторых странностей возле углов - X может «ударить» по A, B, C и D.

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

Итак, если мы можем оптимально уменьшить один квадрат в слое до 0, у нас есть алгоритм (потому что мы сократили цикл и теперь имеем прямую линию с конечными точками). Я считаю, что бомбардировка рядом с квадратом с наименьшим значением (что дает вам 2 варианта), так что максимальное значение в пределах 2 квадратов этого минимального значения является минимально возможным (вам, возможно, придется разделить бомбардировку, чтобы справиться с этим), будет оптимальным, но я нет (пока?) доказательств.

Поля говорит: «Если вы не можете решить проблему, то есть более простая проблема, которую вы можете решить: найти ее».

Очевидной более простой проблемой является одномерная задача (когда сетка представляет собой одну строку). Давайте начнем с самого простого алгоритма - жадно бомбить самую большую цель. Когда это идет не так?

Учитывая 1 1 1, что жадный алгоритм безразличен, в какую ячейку он бомбит первым. Конечно, центральная ячейка лучше - она ​​обнуляет все три ячейки одновременно. Это предполагает новый алгоритм А, «бомба, чтобы минимизировать оставшуюся сумму». Когда этот алгоритм не работает?

Учитывая 1 1 2 1 1, алгоритм A безразличен между бомбардировкой 2-й, 3-й или 4-й ячейки. Но бомбить 2-ю ячейку, чтобы уйти 0 0 1 1 1, лучше, чем бомбить 3-ю ячейку, чтобы уйти 1 0 1 0 1. Как это исправить? Проблема с бомбардировкой 3-й камеры заключается в том, что она оставляет нам работу слева и справа, что должно быть сделано отдельно.

Как насчет «бомбы, чтобы минимизировать оставшуюся сумму, но максимизировать минимум слева (от того, где мы бомбили) плюс минимум справа». Назовите этот алгоритм B. Когда этот алгоритм работает не так?

Изменить: После прочтения комментариев, я согласен, гораздо более интересная проблема будет изменена одномерная проблема, так что концы соединяются. Хотелось бы увидеть какой-либо прогресс в этом.

Мне пришлось остановиться только на частичном решении, так как у меня не было времени, но, надеюсь, даже это частичное решение даст некоторое представление об одном потенциальном подходе к решению этой проблемы.

Столкнувшись с трудной проблемой, мне нравится придумывать более простые проблемы, чтобы развить интуицию о проблемном пространстве. Здесь первый шаг, который я предпринял, состоял в том, чтобы превратить эту двумерную задачу в одномерную. Рассмотрим строку:

0 4 2 1 3 0 1

Так или иначе, вы знаете, что вам нужно будет бомбить 44 раза или около этого места, чтобы уменьшить его до 0. Так как слева от пятна находится меньшее число, нет никакой выгоды в том, чтобы бомбить 0или 4перебрасывать бомбу 2. На самом деле, я верю (но не в строгом доказательстве), что бомбардировка 2до тех пор, пока 4точка не опустится до 0, по крайней мере так же хороша, как и любая другая стратегия, чтобы 4снизить ее до 0. В стратегии можно двигаться вниз по линии слева направо. как это:

index = 1
while index < line_length
  while number_at_index(index - 1) > 0
    bomb(index)
  end
  index++
end
# take care of the end of the line
while number_at_index(index - 1) > 0
  bomb(index - 1)
end

Пара образцов заказов бомбардировки:

0 4[2]1 3 0 1
0 3[1]0 3 0 1
0 2[0]0 3 0 1
0 1[0]0 3 0 1
0 0 0 0 3[0]1
0 0 0 0 2[0]0
0 0 0 0 1[0]0
0 0 0 0 0 0 0

4[2]1 3 2 1 5
3[1]0 3 2 1 5
2[0]0 3 2 1 5
1[0]0 3 2 1 5
0 0 0 3[2]1 5
0 0 0 2[1]0 5
0 0 0 1[0]0 5
0 0 0 0 0 0[5]
0 0 0 0 0 0[4]
0 0 0 0 0 0[3]
0 0 0 0 0 0[2]
0 0 0 0 0 0[1]
0 0 0 0 0 0 0

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

Следующий шаг в сложности, где поиск хотя бы хорошего , все еще возможен, находится на краю доски. Для меня ясно, что никогда не будет никакой строгой выгоды бомбить внешний край; вам лучше бомбить спот один и получить три других места бесплатно. Учитывая это, мы можем сказать, что бомбардировка кольца внутри края, по крайней мере, так же хороша, как бомбардировка края. Более того, мы можем объединить это с интуицией, что бомбардировка правого внутри ребра на самом деле является единственным способом уменьшить пространство ребер до 0. Более того, определить оптимальную стратегию тривиально просто (поскольку не хуже, чем любая другая стратегия) уменьшить число углов до 0. Мы сложим все это вместе и сможем приблизиться к решению в двумерном пространстве.

Учитывая наблюдение за угловыми фигурами, мы можем с уверенностью сказать, что мы знаем оптимальную стратегию перехода от любой стартовой доски к доске с нулями на всех углах. Это пример такой доски (я позаимствовал числа из двух линейных досок выше). Я пометил некоторые пробелы по-разному, и я объясню почему.

0 4 2 1 3 0 1 0
4 x x x x x x 4
2 y y y y y y 2
1 y y y y y y 1
3 y y y y y y 3
2 y y y y y y 2
1 y y y y y y 1
5 y y y y y y 5
0 4 2 1 3 0 1 0

Заметим, что в верхнем ряду очень похоже на линейный пример, который мы видели ранее. Вспоминая наше предыдущее наблюдение, что оптимальный способ получить верхний ряд до 0 - это бомбить второй ряд ( xряд). Нет никакого способа очистить верхний ряд, бомбя любой из yрядов, и нет никакой дополнительной выгоды от бомбардировки верхнего ряда по сравнению с бомбардировкой соответствующего пространства в xряду.

Мы могли бы применить линейную стратегию сверху (бомбардировать соответствующие пробелы в xряду), касаясь только верхнего ряда и ничего больше. Было бы что-то вроде этого:

0 4 2 1 3 0 1 0
4 x[x]x x x x 4
2 y y y y y y 2
1 y y y y y y 1
3 y y y y y y 3
2 y y y y y y 2
1 y y y y y y 1
5 y y y y y y 5
0 4 2 1 3 0 1 0

0 3 1 0 3 0 1 0
4 x[x]x x x x 4
2 y y y y y y 2
1 y y y y y y 1
3 y y y y y y 3
2 y y y y y y 2
1 y y y y y y 1
5 y y y y y y 5
0 4 2 1 3 0 1 0

0 2 0 0 3 0 1 0
4 x[x]x x x x 4
2 y y y y y y 2
1 y y y y y y 1
3 y y y y y y 3
2 y y y y y y 2
1 y y y y y y 1
5 y y y y y y 5
0 4 2 1 3 0 1 0

0 1 0 0 3 0 1 0
4 x[x]x x x x 4
2 y y y y y y 2
1 y y y y y y 1
3 y y y y y y 3
2 y y y y y y 2
1 y y y y y y 1
5 y y y y y y 5
0 4 2 1 3 0 1 0

0 0 0 0 3 0 1 0
4 x x x x x x 4
2 y y y y y y 2
1 y y y y y y 1
3 y y y y y y 3
2 y y y y y y 2
1 y y y y y y 1
5 y y y y y y 5
0 4 2 1 3 0 1 0

Недостаток такого подхода становится очень очевидным в последних двух бомбардировках. Понятно, учитывая, что единственными местами бомб, которые уменьшают 4число в первом столбце во втором ряду, являются первый xи второй y. Последние две бомбардировки явно уступают первой бомбардировке x, что было бы точно так же (в отношении первого места в верхнем ряду, которое у нас нет другого способа очистки). Поскольку мы продемонстрировали, что наша текущая стратегия является неоптимальной, явно необходима модификация стратегии.

На этом этапе я могу сделать шаг назад по сложности и сосредоточиться только на одном углу. Давайте рассмотрим это:

0 4 2 1
4 x y a
2 z . .
1 b . .

Это ясно , что единственный способ получить пространство с 4до нуля, чтобы бомбить некоторую комбинацию x, yи z. С некоторой акробатикой в ​​моем уме, я вполне уверен, что оптимальное решение - бомбить xтри раза, а aзатем b. Теперь нужно выяснить, как я достиг этого решения, и если оно покажет какую-то интуицию, которую мы можем использовать, чтобы даже решить эту локальную проблему. Я заметил, что там нет бомбежек yи zпробелов. Попытка найти угол, где бомбардировка этих мест имеет смысл, дает угол, который выглядит следующим образом:

0 4 2 5 0
4 x y a .
2 z . . .
5 b . . .
0 . . . .

Для этого ясно, что оптимальным решением является бомбардировка y5 раз и z5 раз. Давайте сделаем еще один шаг вперед.

0 4 2 5 6 0 0
4 x y a . . .
2 z . . . . .
5 b . . . . .
6 . . . . . .
0 . . . . . .
0 . . . . . .

Здесь он чувствует себя так же интуитивно , что оптимальное решение бомбить aи в b6 раз , а затем x4 раза.

Теперь это игра о том, как превратить эту интуицию в принципы, на которых мы можем опираться.

Надеюсь, продолжение будет продолжено!

Для уточненного вопроса простой жадный алгоритм дает оптимальный результат.

Сбросьте бомбы A [0,0] в ячейку A [1,1], затем сбросьте бомбы A [1,0] в ячейку A [2,1] и продолжите этот процесс вниз. Чтобы убрать левый нижний угол, сбросьте макс (A [N-1,0], A [N-2,0], A [N-3,0]) бомбы в ячейку A [N-2,1]. Это полностью очистит первые 3 столбца.

При таком же подходе очистите столбцы 3,4,5, затем столбцы 6,7,8 и т. Д.

К сожалению, это не помогает найти решение исходной проблемы.

«Большая» задача (без ограничения «без увеличения») может оказаться NP-трудной. Вот набросок доказательства.

Предположим, у нас есть планарный граф степени до 3. Давайте найдем минимальное покрытие вершин для этого графа. Согласно статье в Википедии, эта проблема является NP-трудной для плоских графов степени до 3. Это может быть доказано сокращением от Planar 3SAT. А твердость Planar 3SAT - снижением с 3SAT. Оба эти доказательства представлены в недавних лекциях "Алгоритмические нижние оценки" проф. Эрик Демейн (лекции 7 и 9).

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

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

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

Имея очки:

a b c d
e f g h
i j k l
m n o p

можно написать 16 уравнений, где для точки f, например, выполняется

f <= ai + bi + ci + ei + fi + gi + ii + ji + ki   

минимизируется сумма всех индексов и целочисленное решение.

Решение, конечно, сумма этих показателей.

Это можно еще больше упростить, установив все значения xi на границах 0, поэтому в этом примере вы получите уравнение 4 + 1.

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

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

В плате размером 3х3 и меньше решение всегда является ячейкой с наибольшим номером.

В досках размером более 4х4 первая очевидная нижняя граница - это сумма углов:

*2* 3  7 *1*
 1  5  6  2
 2  1  3  2
*6* 9  6 *4*

как бы вы ни расставляли бомбы, невозможно очистить эту доску 4х4 с менее чем 2 + 1 + 6 + 4 = 13 бомбами.

В других ответах упоминалось, что размещение бомбы на втором углу для устранения угла никогда не бывает хуже, чем размещение бомбы на самом углу, поэтому с учетом доски:

*2* 3  4  7 *1*
 1  5  2  6  2
 4  3  4  2  1
 2  1  2  4  1
 3  1  3  4  1
 2  1  4  3  2
*6* 9  1  6 *4*

Мы можем обнулить углы, поместив бомбы на второй угол, чтобы дать новую доску:

 0  1  1  6  0
 0  3  0  5  1
 2  1  1  1  0
 2  1  2  4  1
 0  0  0  0  0
 0  0  0  0  0
 0  3  0  2  0

Все идет нормально. Нам нужно 13 бомб, чтобы очистить углы.

Теперь соблюдайте числа 6, 4, 3 и 2, отмеченные ниже:

 0  1  1 *6* 0
 0  3  0  5  1
 2  1  1  1  0
*2* 1  2 *4* 1
 0  0  0  0  0
 0  0  0  0  0
 0 *3* 0  2  0

Там нет никакого способа бомбить любые два из этих ячеек одной бомбой, поэтому минимальная бомба увеличилась на 6 + 4 + 3 + 2, поэтому, добавив к числу бомб, которые мы использовали для очистки углов, мы получаем, что минимум Количество бомб, необходимых для этой карты, составило 28 бомб. Невозможно очистить эту карту с менее чем 28 бомбами, это нижняя граница для этой карты.

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

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

Алгоритм нахождения нижней границы следующий:

1. Выберите элемент с наибольшим номером, назовите его P.
2. Отметьте все ячейки в двух шагах от P и P как не поддающиеся проверке.
3. Добавьте P в minimumsсписок.
4. Повторяйте к шагу 1, пока все ячейки не станут непроницаемыми.
5. Суммируйте minimumsсписок, чтобы получить нижнюю границу.

Это был бы жадный подход:

1. Вычислите матрицу «оценок» порядка n X m, где оценка [i] [j] - это общее вычитание точек в матрице, если позиция (i, j) подвергается бомбардировке. (Максимальное количество баллов - 9, минимальное - 0)

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

3. Бомба (I, J). Увеличьте количество бомб.

4. Если все элементы исходной матрицы не равны нулю, перейдите к 1.

У меня есть сомнения, что это оптимальное решение.

Редактировать:

Подход Greedy, который я опубликовал выше, хотя и работает, скорее всего, не дает нам оптимального решения. Поэтому я решил добавить некоторые элементы DP к нему.

Я думаю, что мы можем согласиться с тем, что в любой момент времени должна быть выбрана одна из позиций с наивысшим «счетом» (оценка [i] [j] = общая сумма вычета очков, если (i, j) подвергнут бомбардировке). Исходя из этого предположения, вот новый подход:

NumOfBombs (M): (возвращает минимальное количество необходимых взрывов)

1. Дана матрица M порядка n X m. Если все элементы M равны нулю, вернуть 0.

2. Рассчитаем «балл» по матрице М.

   Пусть k различных позиций P1, P2, ... Pk (1 <= k <= n * m) будут позициями в M с наивысшими баллами.

3. return (1 + мин (NumOfBombs (M1), NumOfBombs (M2), ..., NumOfBombs (Mk)))

   где M1, M2, ..., Mk - результирующие матрицы, если мы бомбим положения P1, P2, ..., Pk соответственно.

Кроме того, если мы хотим, чтобы порядок позиций обнулялся в дополнение к этому, мы должны были бы отслеживать результаты "min".

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

Обратите внимание, что левый столбец содержит самые высокие цифры. Поэтому любое оптимальное решение должно сначала уменьшить этот столбец до нуля. Таким образом, мы можем выполнить 1-D бомбардировку над этим столбцом, уменьшив каждый элемент в нем до нуля. Мы позволяем бомбам падать на второй столб, чтобы они наносили максимальный урон. Я думаю, что здесь много постов, посвященных 1D делу, поэтому я чувствую себя в безопасности, пропуская это дело. (Если вы хотите, чтобы я это описал, я могу.) Из-за убывающего свойства все три крайних левых столбца будут сведены к нулю. Но мы, вероятно, будем использовать здесь минимальное количество бомб, потому что левый столбец должен быть обнулен.

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

Целочисленное линейное программирование Mathematica с использованием ветвлений и границ

Как уже упоминалось, эта проблема может быть решена с помощью целочисленного линейного программирования (то есть NP-Hard ). Mathematica уже имеет встроенный ILP. "To solve an integer linear programming problem Mathematica first solves the equational constraints, reducing the problem to one containing inequality constraints only. Then it uses lattice reduction techniques to put the inequality system in a simpler form. Finally, it solves the simplified optimization problem using a branch-and-bound method."[См. Ограниченная оптимизация Учебник по в Mathematica ..]

Я написал следующий код, который использует библиотеки ILP Mathematica. Это удивительно быстро.

solveMatrixBombProblem[problem_, r_, c_] := 
 Module[{}, 
  bombEffect[x_, y_, m_, n_] := 
   Table[If[(i == x || i == x - 1 || i == x + 1) && (j == y || 
        j == y - 1 || j == y + 1), 1, 0], {i, 1, m}, {j, 1, n}];
  bombMatrix[m_, n_] := 
   Transpose[
    Table[Table[
      Part[bombEffect[(i - Mod[i, n])/n + 1, Mod[i, n] + 1, m, 
        n], (j - Mod[j, n])/n + 1, Mod[j, n] + 1], {j, 0, 
       m*n - 1}], {i, 0, m*n - 1}]];
  X := x /@ Range[c*r];
  sol = Minimize[{Total[X], 
     And @@ Thread[bombMatrix[r, c].X >= problem] && 
      And @@ Thread[X >= 0] && Total[X] <= 10^100 && 
      Element[X, Integers]}, X];
  Print["Minimum required bombs = ", sol[[1]]];
  Print["A possible solution = ", 
   MatrixForm[
    Table[x[c*i + j + 1] /. sol[[2]], {i, 0, r - 1}, {j, 0, 
      c - 1}]]];]

Для примера, представленного в задаче:

solveMatrixBombProblem[{2, 3, 4, 7, 1, 1, 5, 2, 6, 2, 4, 3, 4, 2, 1, 2, 1, 2, 4, 1, 3, 1, 3, 4, 1, 2, 1, 4, 3, 2, 6, 9, 1, 6, 4}, 7, 5]

Выходы

Для тех, кто читает это с жадным алгоритмом

Попробуйте свой код на следующую проблему 10x10:

5   20  7   1   9   8   19  16  11  3  
17  8   15  17  12  4   5   16  8   18  
4   19  12  11  9   7   4   15  14  6  
17  20  4   9   19  8   17  2   10  8  
3   9   10  13  8   9   12  12  6   18  
16  16  2   10  7   12  17  11  4   15  
11  1   15  1   5   11  3   12  8   3  
7   11  16  19  17  11  20  2   5   19  
5   18  2   17  7   14  19  11  1   6  
13  20  8   4   15  10  19  5   11  12

Здесь это разделено запятыми:

5, 20, 7, 1, 9, 8, 19, 16, 11, 3, 17, 8, 15, 17, 12, 4, 5, 16, 8, 18, 4, 19, 12, 11, 9, 7, 4, 15, 14, 6, 17, 20, 4, 9, 19, 8, 17, 2, 10, 8, 3, 9, 10, 13, 8, 9, 12, 12, 6, 18, 16, 16, 2, 10, 7, 12, 17, 11, 4, 15, 11, 1, 15, 1, 5, 11, 3, 12, 8, 3, 7, 11, 16, 19, 17, 11, 20, 2, 5, 19, 5, 18, 2, 17, 7, 14, 19, 11, 1, 6, 13, 20, 8, 4, 15, 10, 19, 5, 11, 12

Для этой проблемы мое решение содержит 208 бомб. Вот возможное решение (мне удалось решить это примерно за 12 секунд).

Чтобы проверить результаты, которые дает Mathematica, посмотрите, может ли ваш жадный алгоритм работать лучше.

Нет необходимости преобразовывать задачу в линейные подзадачи.

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

В данном примере четыре угла: {2, 1, 6, 4}. Для каждого угла нет лучшего движения, чем бомбить ячейку с диагональю угла, поэтому мы точно знаем, что наши первые 2 + 1 + 6 + 4 = 13 бомбардировок должны быть в этих диагональных ячейках. После бомбардировки у нас осталась новая матрица:

2 3 4 7 1      0 1 1 6 0      0 1 1 6 0     1 1 6 0     0 0 5     0 0 0 
1 5 2 6 2      0 3 0 5 1      0 3 0 5 1  => 1 0 4 0  => 0 0 3  => 0 0 0  
4 3 4 2 1      2 1 1 1 0      2 1 1 1 0     0 0 0 0     0 0 0     0 0 3  
2 1 2 4 1  =>  2 1 2 4 1  =>  2 1 2 4 1     0 0 3 0     0 0 3      
3 1 3 4 1      0 0 0 0 0      0 0 0 0 0 
2 1 4 3 2      0 0 0 0 0      0 0 0 0 0 
6 9 1 6 4      0 3 0 2 0      0 0 0 0 0 

После первых 13 взрывов мы используем эвристику для устранения 3 0 2 посредством трех взрывов. Теперь у нас есть 2 новых угла, {2, 1} в 4-м ряду. Мы бомбим тех, еще 3 бомбежки. Мы сократили матрицу до 4 х 4 сейчас. Есть один угол, левый верхний. Мы бомбим это. Теперь у нас осталось 2 угла, {5, 3}. Так как 5 - самый большой угол, мы сначала бомбим 5 бомб, а затем, наконец, бомбим 3 в другом углу. Всего 13 + 3 + 3 + 1 + 5 + 3 = 28.

Это делает поиск в поисках кратчайшего пути (серии бомбардировок) через этот «лабиринт» позиций. Нет, я не могу доказать, что нет более быстрого алгоритма, извините.

#!/usr/bin/env python

M = ((1,2,3,4),
     (2,3,4,5),
     (5,2,7,4),
     (2,3,5,8))

def eachPossibleMove(m):
  for y in range(1, len(m)-1):
    for x in range(1, len(m[0])-1):
      if (0 == m[y-1][x-1] == m[y-1][x] == m[y-1][x+1] ==
               m[y][x-1]   == m[y][x]   == m[y][x+1] ==
               m[y+1][x-1] == m[y+1][x] == m[y+1][x+1]):
        continue
      yield x, y

def bomb(m, (mx, my)):
  return tuple(tuple(max(0, m[y][x]-1)
      if mx-1 <= x <= mx+1 and my-1 <= y <= my+1
      else m[y][x]
      for x in range(len(m[y])))
    for y in range(len(m)))

def findFirstSolution(m, path=[]):
#  print path
#  print m
  if sum(map(sum, m)) == 0:  # empty?
    return path
  for move in eachPossibleMove(m):
    return findFirstSolution(bomb(m, move), path + [ move ])

def findShortestSolution(m):
  black = {}
  nextWhite = { m: [] }
  while nextWhite:
    white = nextWhite
    nextWhite = {}
    for position, path in white.iteritems():
      for move in eachPossibleMove(position):
        nextPosition = bomb(position, move)
        nextPath = path + [ move ]
        if sum(map(sum, nextPosition)) == 0:  # empty?
          return nextPath
        if nextPosition in black or nextPosition in white:
          continue  # ignore, found that one before
        nextWhite[nextPosition] = nextPath

def main(argv):
  if argv[1] == 'first':
    print findFirstSolution(M)
  elif argv[1] == 'shortest':
    print findShortestSolution(M)
  else:
    raise NotImplementedError(argv[1])

if __name__ == '__main__':
  import sys
  sys.exit(main(sys.argv))

Кажется, что подход линейного программирования может быть очень полезным здесь.

Пусть P _{m xn} - матрица со значениями позиций:

Теперь давайте определим матрицу бомб B (x, y) _mxn , где 1 ≤ x ≤ m , 1 ≤ y ≤ n, как _{показано} ниже

таким образом, что

Например:

Итак, мы смотрим на матрицу B _{m xn} = [ b _ij ], которая

1. Может быть определена как сумма матриц бомб:

   

   ( Q _IJ будет тогда количеством бомб, которое мы сбросим в позиции p _ij )

2. p _ij - b _ij ≤ 0 (чтобы быть более кратким, скажем это как P - B ≤ 0 )

Кроме того, B должен минимизировать сумму .

Мы также можем написать B как некрасивую матрицу впереди:

и так как P - B ≤ 0 (что означает P ≤ B ), мы имеем следующую довольно линейную систему неравенства:

Быть д _{mn x 1} определяется как

п _{mn x 1} определяется как

Мы можем сказать, что у нас есть система Система ниже представлена как произведение матриц http://latex.codecogs.com/gif.download?S%5Cmathbf%7Bq%7D&space;%5Cge&space;%5Cmathbf%7Bp%7D быть S _{млн х Миннесота} матрицы на обратном , чтобы решить эту систему. Я не расширил это сам, но я считаю, что это должно быть легко сделать в коде.

Теперь у нас есть минимальная проблема, которая может быть сформулирована как

Я полагаю, что что-то легко, почти тривиально, решить с помощью чего-то вроде симплексного алгоритма (в этом есть довольно крутой документ ). Тем не менее, я почти не знаю линейного программирования (я буду проходить курс об этом на Coursera, но это только в будущем ...), у меня были некоторые головные боли, пытающиеся понять это, и у меня есть огромная внештатная работа, чтобы закончить, поэтому я просто сдавайся здесь. Это может быть , что я сделал что - то неправильно в какой - то момент, или что он не может идти дальше, но я считаю , что это путь в конечном итоге может привести к к решению. В любом случае, я с нетерпением жду ваших отзывов.

(Отдельное спасибо за этот удивительный сайт для создания картинок из выражений LaTeX )

Это жадное решение кажется правильным :

Как указано в комментариях, в 2D это не получится. Но, может быть, вы можете улучшить это.

Для 1D:
если есть хотя бы 2 числа, вам не нужно стрелять в крайнее левое положение, потому что стрельба во вторую не хуже . Так что стреляйте во второе, а first не 0, потому что вы должны это сделать. Перейти к следующей ячейке. Не забывай о последней камере.

C ++ код:

void bombs(vector<int>& v, int i, int n){
    ans += n;
    v[i] -= n;
    if(i > 0)
        v[i - 1] -= n;
    if(i + 1< v.size())
        v[i + 1] -= n;
}

void solve(vector<int> v){
    int n = v.size();
    for(int i = 0; i < n;++i){
        if(i != n - 1){
            bombs(v, i + 1, v[i]);
        }
        else
            bombs(v, i, v[i])
    }
}

Так что для 2D:
Опять же: вам не нужно стрелять в первом ряду (если есть второй). Так что стреляйте ко второму. Решите 1D задачу для первого ряда. (потому что вам нужно сделать его нулевым). Опускаться. Не забудьте последний ряд.

Чтобы минимизировать количество бомб, мы должны максимизировать эффект каждой бомбы. Чтобы достичь этого, на каждом шаге мы должны выбрать лучшую цель. Для каждой точки суммирования ее и ее восьми соседей - можно было бы использовать в качестве показателя эффективности бомбардировки этой точки. Это обеспечит близкую к оптимальной последовательность бомб.

UPD : Нужно также учитывать количество нулей, потому что бомбить их неэффективно. На самом деле проблема состоит в том, чтобы минимизировать количество хитированных нулей. Но мы не можем знать, как любой шаг приближает нас к этой цели. Я согласен с идеей, что проблема является NP-полной. Я предлагаю жадный подход, который даст ответ, близкий к реальному.

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

var oMatrix = [
[2,3,4,7,1],
[1,5,2,6,2],
[4,3,4,2,1],
[2,1,2,4,1],
[3,1,3,4,1],
[2,1,4,3,2],
[6,9,1,6,4]
]

var nBombs = 0;
do
{
    var bSpacesLeftToBomb = false;
    var nHigh = 0;
    var nCellX = 0;
    var nCellY = 0;
    for(var y = 1 ; y<oMatrix.length-1;y++) 
        for(var x = 1 ; x<oMatrix[y].length-1;x++)  
        {
            var nValue = 0;
            for(var yy = y-1;yy<=y+1;yy++)
                for(var xx = x-1;xx<=x+1;xx++)
                    nValue += oMatrix[yy][xx];

            if(nValue>nHigh)
            {
                nHigh = nValue;
                nCellX = x;
                nCellY = y; 
            }

        }
    if(nHigh>0)
    {
        nBombs++;

        for(var yy = nCellY-1;yy<=nCellY+1;yy++)
        {
            for(var xx = nCellX-1;xx<=nCellX+1;xx++)
            {
                if(oMatrix[yy][xx]<=0)
                    continue;
                oMatrix[yy][xx] = --oMatrix[yy][xx];
            }
        }
        bSpacesLeftToBomb = true;
    }
}
while(bSpacesLeftToBomb);

alert(nBombs+'bombs');

Вот решение, которое обобщает хорошие свойства углов.

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

dropped_bomb_count = 0
while there_are_cells_with_non_zero_count_left
  coordinates = choose_a_perfect_drop_point
  drop_bomb(coordinates)
  dropped_bomb_count += 1
end
return dropped_bomb_count

Задача есть choose_a_perfect_drop_point. Во-первых, давайте определимся, что такое идеальная точка отбрасывания.

• Точка опускания для (x, y)уменьшения значения в (x, y). Это может также уменьшить значения в других клетках.
• Капля точка для это лучше , чем в точке падения Ь для , если она уменьшает значения в надлежащем надмножестве клеток, б уменьшается.(x, y)(x, y)
• Точка опускания максимальна, если нет другой лучшей точки опускания.
• Две капли для очков (x, y)являются эквивалентными , если они уменьшают тот же набор клеток.
• Точка падения для (x, y)является совершенной , если оно эквивалентно всеми точками максимального падения для (x, y).

Если есть идеальная точка сброса (x, y), вы не можете уменьшить значение (x, y)более эффективно, чем сбросить бомбу на одну из идеальных точек опускания (x, y).

Идеальная точка опускания для данного поля - идеальная точка опускания для любой из его ячеек.

Вот несколько примеров:

1 0 1 0 0
0 0 0 0 0
1 0 0 0 0
0 0 0 0 0
0 0 0 0 0

Идеальная точка падения для ячейки (0, 0)( от нуля индекс) (1, 1). Все остальные точки падения для (1, 1), то есть (0, 0), (0, 1)и (1, 0), снижения меньше клеток.

0 0 0 0 0
0 0 0 0 0
0 0 1 0 0
0 0 0 0 0
0 0 0 0 0

Идеальные каплепадения для ячейки (2, 2)( от нуля индекса) (2, 2), а также все окружающие клетки (1, 1), (1, 2), (1, 3), (2, 1), (2, 3), (3, 1), (3, 2), и (3, 3).

0 0 0 0 1
0 0 0 0 0
0 0 1 0 0
0 0 0 0 0
0 0 0 0 0

совершенное падение точки для ячейки (2, 2)является (3, 1): Это уменьшает значение (2, 2), и значение (4, 0). Все остальные точки отбрасывания (2, 2)не максимальны, так как они уменьшаются на одну ячейку меньше. Идеальная точка опускания (2, 2)также является идеальной точкой опускания (4, 0), и это единственная идеальная точка опускания для поля. Это приводит к идеальному решению для этой области (одна капля бомбы).

1 0 0 0 0
0 0 0 0 0
0 0 1 0 0
0 0 0 0 0
1 0 0 0 0

Не существует идеальной точки отбрасывания для (2, 2): И, (1, 1)и (1, 3)уменьшение, (2, 2)и другая ячейка (они являются максимальными точками отбрасывания (2, 2)), но они не эквивалентны. Тем не менее, (1, 1)это идеальная точка опускания для (0, 0), и (1, 3)это идеальная точка опускания для (0, 4).

С этим определением идеальных точек отбрасывания и определенным порядком проверок я получаю следующий результат для примера в вопросе:

Drop bomb on 1, 1
Drop bomb on 1, 1
Drop bomb on 1, 5
Drop bomb on 1, 5
Drop bomb on 1, 5
Drop bomb on 1, 6
Drop bomb on 1, 2
Drop bomb on 1, 2
Drop bomb on 0, 6
Drop bomb on 0, 6
Drop bomb on 2, 1
Drop bomb on 2, 5
Drop bomb on 2, 5
Drop bomb on 2, 5
Drop bomb on 3, 1
Drop bomb on 3, 0
Drop bomb on 3, 0
Drop bomb on 3, 0
Drop bomb on 3, 0
Drop bomb on 3, 0
Drop bomb on 3, 4
Drop bomb on 3, 4
Drop bomb on 3, 3
Drop bomb on 3, 3
Drop bomb on 3, 6
Drop bomb on 3, 6
Drop bomb on 3, 6
Drop bomb on 4, 6
28

Однако алгоритм работает только в том случае, если после каждого шага есть хотя бы одна идеальная точка отбрасывания. Можно построить примеры, где нет идеальных точек сброса:

0 1 1 0
1 0 0 1
1 0 0 1
0 1 1 0

Для этих случаев мы можем изменить алгоритм так, чтобы вместо идеальной точки отбрасывания мы выбирали координату с минимальным выбором максимальных точек отбрасывания, а затем вычисляли минимум для каждого выбора. В приведенном выше случае все ячейки со значениями имеют две максимальные точки отбрасывания. Например, (0, 1)имеет максимальные точки падения (1, 1)и (1, 2). Выбор одного из них, а затем вычисление минимума приводит к следующему результату:

Drop bomb on 1, 1
Drop bomb on 2, 2
Drop bomb on 1, 2
Drop bomb on 2, 1
2

Вот еще одна идея:

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

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

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

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

Бомба нового места наибольшего веса, и повторите процедуру.

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

Изменить: контрпример Mysticial ниже демонстрирует, что на самом деле это не гарантированно будет оптимальным, независимо от весовых коэффициентов. В некоторых случаях максимально возможное уменьшение веса на данном этапе фактически оставляет оставшиеся бомбы слишком разбросанными, чтобы достигнуть кумулятивного уменьшения после второго шага настолько высокого, насколько вы могли бы иметь с немного менее жадным выбором на первом этапе. Я был несколько введен в заблуждение тем, что результаты нечувствительны к порядку взрывов. Oни являютсянечувствителен к порядку, так как вы можете взять любую серию бомбардировок и переиграть их с самого начала в другом порядке и в итоге получить ту же самую доску. Но из этого не следует, что вы можете рассматривать каждую бомбардировку самостоятельно. Или, по крайней мере, каждая бомбардировка должна рассматриваться таким образом, чтобы учитывать, насколько хорошо она настраивает доску для последующих бомбардировок.

Хорошо, предположим, что мы нумеруем позиции на доске 1, 2, ..., nx m. Любая последовательность сбрасывания бомб может быть представлена ​​последовательностью чисел в этом наборе, где числа могут повторяться. Тем не менее, эффект на доске одинаков, независимо от того, в каком порядке вы сбрасываете бомбы, поэтому любой сброс бомб может быть представлен в виде списка чисел nxm, где первое число представляет количество бомб, сброшенных на позицию 1. второе число представляет количество бомб, сброшенных на позицию 2, и т. д. Давайте назовем этот список чисел nxm «ключом».

Вы можете попытаться сначала вычислить все состояния доски, полученные в результате 1 сброса бомбы, а затем использовать их для вычисления всех состояний доски, полученных в результате 2 падений бомбы, и т. Д., Пока не получите все нули. Но на каждом шаге вы должны кэшировать состояния, используя ключ, который я определил выше, поэтому вы можете использовать эти результаты при вычислении следующего шага (подход «динамического программирования»).

Но в зависимости от размера n, m и чисел в сетке требования к памяти при таком подходе могут быть чрезмерными. Вы можете выбросить все результаты для N сбросов бомб, как только вы рассчитали все результаты для N + 1, так что есть некоторая экономия. И, конечно, вы не можете ничего кешировать за счет того, что это займет гораздо больше времени - подход динамического программирования меняет память на скорость.

Если вам нужно абсолютно оптимальное решение для очистки платы, вам придется использовать классический возврат, но если матрица очень большая, то понадобится много времени, чтобы найти лучшее решение, если вы хотите «возможное» оптимальное решение, вы можете использовать жадный алгоритм , если вам нужна помощь в написании алгоритма, я могу помочь вам

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

2 3 5 -> (2+(1*3)) (3+(1*5)) (5+(1*3))
1 3 2 -> (1+(1*4)) (3+(1*7)) (2+(1*4))
1 0 2 -> (1+(1*2)) (0+(1*5)) (2+(1*2))

значение ячейки +1 для каждой соседней ячейки со значением выше 0

Грубая сила !

Я знаю, что он неэффективен, но даже если вы найдете более быстрый алгоритм, вы всегда можете проверить этот результат, чтобы узнать, насколько он точен.

Используйте некоторую рекурсию, например так:

void fn(tableState ts, currentlevel cl)
{
  // first check if ts is all zeros yet, if not:
  //
  // do a for loop to go through all cells of ts, 
  // for each cell do a bomb, and then
  // call: 
  // fn(ts, cl + 1);

}

Вы можете сделать это более эффективным путем кэширования, если по-разному приводите к одному и тому же результату, вам не следует повторять одни и те же шаги.

Разработать:

если бомбардировка ячейки 1,3,5 приводит к тому же результату, что и бомбардировка ячейки 5,3,1, то вам не следует повторять все последующие шаги снова для обоих случаев, достаточно только 1, вам следует хранить где-то все таблица состояний и использовать ее результаты.

Хэш таблицы статистики может быть использован для быстрого сравнения.

1. Никогда не бомбите границу (если у квадрата нет соседа без границ)
2. Нулевой угол.
3. К нулевому углу, уменьшите значение угла на одну квадратную диагонали (единственный сосед без границ)
4. Это создаст новые углы. Перейти к 2

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

В примере OP: сброс 2 (как 1 + 1 или 2) на что-либо, кроме 5, не приводит к попаданию в любой квадрат, который попадет на 5. Таким образом, мы просто должны сбросить 2 на 5 (и 6 в левом нижнем углу 1 ...)

После этого есть только один способ, как очистить (в верхнем левом углу) то, что было изначально 1 (теперь 0), и это сбросить 0 на B3 (отличная запись). И так далее.

Только после очистки всех столбцов A и E и 1 и 7 строк, начинайте очистку на один уровень глубже.

Считайте, что очищены только те, которые намеренно очищены, очистка углов значений 0 ничего не стоит и упрощает обдумывание.

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

После хорошего сна я понял, что это не так. Рассматривать

  ABCDE    
1 01000
2 10000
3 00000
4 00000

Мой подход будет сбрасывать бомбы на B3 и C2, когда падения на B2 будет достаточно

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

Во-первых, как сказал @Luka Rahne в одном из комментариев, порядок, в котором вы бомбите, не важен - только комбинация.

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

Это создает основу для моей версии алгоритма: мы можем бомбить «1-off из углов» первым или последним, это не имеет значения (в теории) Мы сначала бомбим их, потому что это облегчает последующие решения (на практике) Мы бомбим точку, которая влияет на большинство точек, одновременно бомбардируя эти углы.

Давайте определим Точки Сопротивления, чтобы они были точками на доске с наибольшим количеством не подлежащих бомбардировке точек + наибольшим числом нулей вокруг них.

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

Я также определю 4 границы, которые будут обрабатывать нашу область видимости: Top = 0, Left = 0, Bottom = k, right = j. (значения для начала)

Наконец, я определю оптимальные бомбы как бомбы, которые сбрасываются на точки, которые примыкают к точкам сопротивления и касаются (1) самой высокой точки сопротивления и (2) наибольшего количества возможных точек.

Что касается подхода - очевидно, мы работаем извне. Мы сможем работать с 4 «бомбардировщиками» одновременно.

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

Алгоритм:

1. Найдите 4 оптимальных пункта бомбы.
2. Если точка бомбардировки бомбит точку сопротивления, которая касается 2 границ (то есть угла), бомбить до этой точки будет 0. В противном случае, бомбить каждую, пока одна из точек сопротивления, касающаяся оптимальной точки бомбы, не станет 0.
3. для каждой границы: if (sum (bound) == 0) предварительная оценка

повторять до тех пор, пока верх = низ и лево = право

Я постараюсь написать актуальный код позже

Вы можете использовать государственное планирование пространства. Например, используя A * (или один из его вариантов) в сочетании с эвристикой, f = g + hподобной этой:

• г: количество бомб, сброшенных до сих пор
• h: сумма по всем значениям сетки, деленная на 9 (что является наилучшим результатом, то есть у нас допустимая эвристика)

У меня также 28 ходов. Я использовал два теста для лучшего следующего хода: сначала ход, производящий минимальную сумму для доски. Во-вторых, для равных сумм движение, создающее максимальную плотность, определяется как:

number-of-zeros / number-of-groups-of-zeros

Это Хаскелл. «Решить доска» показывает решение двигателя. Вы можете играть в игру, набрав «основной», затем введите целевую точку, «лучший» для рекомендации или «выйти», чтобы выйти.

РЕЗУЛЬТАТ:
* Main> решаем доска
[(4,4), (3,6), (3,3), (2,2), (2,2), (4,6), (4,6), (2,6), (3,2), (4,2), (2,6), (3,3), (4,3), (2,6), (4,2), (4 , 6), (4,6), (3,6), (2,6), (2,6), (2,4), (2,4), (2,6), (3,6 ), (4,2), (4,2), (4,2), (4,2)]

import Data.List
import Data.List.Split
import Data.Ord
import Data.Function(on)

board = [2,3,4,7,1,
         1,5,2,6,2,
         4,3,4,2,1,
         2,1,2,4,1,
         3,1,3,4,1,
         2,1,4,3,2,
         6,9,1,6,4]

n = 5
m = 7

updateBoard board pt =
  let x = fst pt
      y = snd pt
      precedingLines = replicate ((y-2) * n) 0
      bomb = concat $ replicate (if y == 1
                                    then 2
                                    else min 3 (m+2-y)) (replicate (x-2) 0 
                                                         ++ (if x == 1 
                                                                then [1,1]
                                                                else replicate (min 3 (n+2-x)) 1)
                                                                ++ replicate (n-(x+1)) 0)
  in zipWith (\a b -> max 0 (a-b)) board (precedingLines ++ bomb ++ repeat 0)

showBoard board = 
  let top = "   " ++ (concat $ map (\x -> show x ++ ".") [1..n]) ++ "\n"
      chunks = chunksOf n board
  in putStrLn (top ++ showBoard' chunks "" 1)
       where showBoard' []     str count = str
             showBoard' (x:xs) str count =
               showBoard' xs (str ++ show count ++ "." ++ show x ++ "\n") (count+1)

instances _ [] = 0
instances x (y:ys)
  | x == y    = 1 + instances x ys
  | otherwise = instances x ys

density a = 
  let numZeros = instances 0 a
      groupsOfZeros = filter (\x -> head x == 0) (group a)
  in if null groupsOfZeros then 0 else numZeros / fromIntegral (length groupsOfZeros)

boardDensity board = sum (map density (chunksOf n board))

moves = [(a,b) | a <- [2..n-1], b <- [2..m-1]]               

bestMove board = 
  let lowestSumMoves = take 1 $ groupBy ((==) `on` snd) 
                              $ sortBy (comparing snd) (map (\x -> (x, sum $ updateBoard board x)) (moves))
  in if null lowestSumMoves
        then (0,0)
        else let lowestSumMoves' = map (\x -> fst x) (head lowestSumMoves) 
             in fst $ head $ reverse $ sortBy (comparing snd) 
                (map (\x -> (x, boardDensity $ updateBoard board x)) (lowestSumMoves'))   

solve board = solve' board [] where
  solve' board result
    | sum board == 0 = result
    | otherwise      = 
        let best = bestMove board 
        in solve' (updateBoard board best) (result ++ [best])

main :: IO ()
main = mainLoop board where
  mainLoop board = do 
    putStrLn ""
    showBoard board
    putStr "Pt: "
    a <- getLine
    case a of 
      "quit"    -> do putStrLn ""
                      return ()
      "best"    -> do putStrLn (show $ bestMove board)
                      mainLoop board
      otherwise -> let ws = splitOn "," a
                       pt = (read (head ws), read (last ws))
                   in do mainLoop (updateBoard board pt)

Кажется, здесь есть недвойственная подходящая подструктура. Рассмотрим следующий пример:

0010000
1000100
0000001
1000000
0000001
1000100
0010000

Оптимальное решение для этого случая имеет размер 5, поскольку это размер минимального покрытия вершин 9-цикла его ребрами.

Этот случай, в частности, показывает, что ослабление линейного программирования, которое опубликовали несколько человек, не является точным, не работает, и все эти другие плохие вещи. Я почти уверен, что смогу уменьшить «покрыть вершины моего плоского кубического графа как можно меньшим числом ребер» в вашей задаче, что заставляет меня усомниться, сработает ли какое-либо из жадных / восхождений.

Я не вижу способа решить это за полиномиальное время в худшем случае. Может быть очень умное решение для двоичного поиска и DP, которое я не вижу.

РЕДАКТИРОВАТЬ : я вижу, что конкурс ( http://deadline24.pl ) не зависит от языка; они посылают вам кучу входных файлов, а вы отправляете им выходные данные. Таким образом, вам не нужно что-то, что работает в наихудшем полиномиальном времени. В частности, вы можете посмотреть на вход !

На входе есть несколько небольших случаев. Тогда есть случай 10x1000, случай 100x100 и случай 1000x1000. Все три больших дела очень хорошо себя ведут. Горизонтально смежные записи обычно имеют одинаковое значение. На относительно громоздкой машине я могу решить все случаи с помощью грубого принуждения с помощью CPLEX всего за пару минут. Мне повезло на 1000х1000; Релаксация ЛП имеет интегральное оптимальное решение. Мои решения согласуются с .ansфайлами, предоставленными в комплекте тестовых данных.

Могу поспорить, что вы можете использовать структуру входных данных гораздо более прямым образом, чем я, если вы посмотрите на нее; кажется, что вы можете просто срезать первый ряд, или два, или три несколько раз, пока у вас ничего не останется. (Похоже, что в 1000x1000 все строки не увеличиваются? Я полагаю, отсюда ваша "часть B"?)

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

Таким образом, мой метод состоит в том, чтобы вычислить показатель эффективности бомбардировки для каждой ячейки, бомбить ячейку с самым высоким значением, .... повторять процесс, пока я не сгладю все. Некоторые выступают за использование простого потенциального урона (т. Е. От 0 до 9) в качестве метрики, но этого не хватает, колотя по ячейкам с высокой стоимостью и не используя перекрытие повреждений. Я бы вычислил cell value - sum of all neighbouring cells, сбросил любое положительное значение на 0 и использовал бы абсолютное значение любого отрицательного значения. Интуитивно понятно, что эта метрика должна сделать выбор, который поможет максимизировать перекрытие урона в ячейках с высоким счетом вместо того, чтобы наносить их непосредственно.

Приведенный ниже код достигает полного уничтожения испытательного поля в 28 бомбах (обратите внимание, что использование потенциального ущерба в качестве метрики дает 31!).

using System;
using System.Collections.Generic;
using System.Linq;

namespace StackOverflow
{
  internal class Program
  {
    // store the battle field as flat array + dimensions
    private static int _width = 5;
    private static int _length = 7;
    private static int[] _field = new int[] {
        2, 3, 4, 7, 1,
        1, 5, 2, 6, 2,
        4, 3, 4, 2, 1,
        2, 1, 2, 4, 1,
        3, 1, 3, 4, 1,
        2, 1, 4, 3, 2,
        6, 9, 1, 6, 4
    };
    // this will store the devastation metric
    private static int[] _metric;

    // do the work
    private static void Main(string[] args)
    {
        int count = 0;

        while (_field.Sum() > 0)
        {
            Console.Out.WriteLine("Round {0}:", ++count);
            GetBlastPotential();
            int cell_to_bomb = FindBestBombingSite();
            PrintField(cell_to_bomb);
            Bomb(cell_to_bomb);
        }
        Console.Out.WriteLine("Done in {0} rounds", count);
    } 

    // convert 2D position to 1D index
    private static int Get1DCoord(int x, int y)
    {
        if ((x < 0) || (y < 0) || (x >= _width) || (y >= _length)) return -1;
        else
        {
            return (y * _width) + x;
        }
    }

    // Convert 1D index to 2D position
    private static void Get2DCoord(int n, out int x, out int y)
    {
        if ((n < 0) || (n >= _field.Length))
        {
            x = -1;
            y = -1;
        }
        else
        {
            x = n % _width;
            y = n / _width;
        }
    }

    // Compute a list of 1D indices for a cell neighbours
    private static List<int> GetNeighbours(int cell)
    {
        List<int> neighbours = new List<int>();
        int x, y;
        Get2DCoord(cell, out x, out y);
        if ((x >= 0) && (y >= 0))
        {
            List<int> tmp = new List<int>();
            tmp.Add(Get1DCoord(x - 1, y - 1));
            tmp.Add(Get1DCoord(x - 1, y));
            tmp.Add(Get1DCoord(x - 1, y + 1));
            tmp.Add(Get1DCoord(x, y - 1));
            tmp.Add(Get1DCoord(x, y + 1));
            tmp.Add(Get1DCoord(x + 1, y - 1));
            tmp.Add(Get1DCoord(x + 1, y));
            tmp.Add(Get1DCoord(x + 1, y + 1));

            // eliminate invalid coords - i.e. stuff past the edges
            foreach (int c in tmp) if (c >= 0) neighbours.Add(c);
        }
        return neighbours;
    }

    // Compute the devastation metric for each cell
    // Represent the Value of the cell minus the sum of all its neighbours
    private static void GetBlastPotential()
    {
        _metric = new int[_field.Length];
        for (int i = 0; i < _field.Length; i++)
        {
            _metric[i] = _field[i];
            List<int> neighbours = GetNeighbours(i);
            if (neighbours != null)
            {
                foreach (int j in neighbours) _metric[i] -= _field[j];
            }
        }
        for (int i = 0; i < _metric.Length; i++)
        {
            _metric[i] = (_metric[i] < 0) ? Math.Abs(_metric[i]) : 0;
        }
    }

    //// Compute the simple expected damage a bomb would score
    //private static void GetBlastPotential()
    //{
    //    _metric = new int[_field.Length];
    //    for (int i = 0; i < _field.Length; i++)
    //    {
    //        _metric[i] = (_field[i] > 0) ? 1 : 0;
    //        List<int> neighbours = GetNeighbours(i);
    //        if (neighbours != null)
    //        {
    //            foreach (int j in neighbours) _metric[i] += (_field[j] > 0) ? 1 : 0;
    //        }
    //    }            
    //}

    // Update the battle field upon dropping a bomb
    private static void Bomb(int cell)
    {
        List<int> neighbours = GetNeighbours(cell);
        foreach (int i in neighbours)
        {
            if (_field[i] > 0) _field[i]--;
        }
    }

    // Find the best bombing site - just return index of local maxima
    private static int FindBestBombingSite()
    {
        int max_idx = 0;
        int max_val = int.MinValue;
        for (int i = 0; i < _metric.Length; i++)
        {
            if (_metric[i] > max_val)
            {
                max_val = _metric[i];
                max_idx = i;
            }
        }
        return max_idx;
    }

    // Display the battle field on the console
    private static void PrintField(int cell)
    {
        for (int x = 0; x < _width; x++)
        {
            for (int y = 0; y < _length; y++)
            {
                int c = Get1DCoord(x, y);
                if (c == cell)
                    Console.Out.Write(string.Format("[{0}]", _field[c]).PadLeft(4));
                else
                    Console.Out.Write(string.Format(" {0} ", _field[c]).PadLeft(4));
            }
            Console.Out.Write(" || ");
            for (int y = 0; y < _length; y++)
            {
                int c = Get1DCoord(x, y);
                if (c == cell)
                    Console.Out.Write(string.Format("[{0}]", _metric[c]).PadLeft(4));
                else
                    Console.Out.Write(string.Format(" {0} ", _metric[c]).PadLeft(4));
            }
            Console.Out.WriteLine();
        }
        Console.Out.WriteLine();
    }           
  }
}

Результирующая схема бомбардировки выводится следующим образом (значения полей слева, метрика справа)

Round 1:
  2   1   4   2   3   2   6  ||   7  16   8  10   4  18   6
  3   5   3   1   1   1   9  ||  11  18  18  21  17  28   5
  4  [2]  4   2   3   4   1  ||  19 [32] 21  20  17  24  22
  7   6   2   4   4   3   6  ||   8  17  20  14  16  22   8
  1   2   1   1   1   2   4  ||  14  15  14  11  13  16   7

Round 2:
  2   1   4   2   3   2   6  ||   5  13   6   9   4  18   6
  2   4   2   1   1  [1]  9  ||  10  15  17  19  17 [28]  5
  3   2   3   2   3   4   1  ||  16  24  18  17  17  24  22
  6   5   1   4   4   3   6  ||   7  14  19  12  16  22   8
  1   2   1   1   1   2   4  ||  12  12  12  10  13  16   7

Round 3:
  2   1   4   2   2   1   5  ||   5  13   6   7   3  15   5
  2   4   2   1   0   1   8  ||  10  15  17  16  14  20   2
  3  [2]  3   2   2   3   0  ||  16 [24] 18  15  16  21  21
  6   5   1   4   4   3   6  ||   7  14  19  11  14  19   6
  1   2   1   1   1   2   4  ||  12  12  12  10  13  16   7

Round 4:
  2   1   4   2   2   1   5  ||   3  10   4   6   3  15   5
  1   3   1   1   0   1   8  ||   9  12  16  14  14  20   2
  2   2   2   2   2  [3]  0  ||  13  16  15  12  16 [21] 21
  5   4   0   4   4   3   6  ||   6  11  18   9  14  19   6
  1   2   1   1   1   2   4  ||  10   9  10   9  13  16   7

Round 5:
  2   1   4   2   2   1   5  ||   3  10   4   6   2  13   3
  1   3   1   1   0  [0]  7  ||   9  12  16  13  12 [19]  2
  2   2   2   2   1   3   0  ||  13  16  15  10  14  15  17
  5   4   0   4   3   2   5  ||   6  11  18   7  13  17   6
  1   2   1   1   1   2   4  ||  10   9  10   8  11  13   5

Round 6:
  2   1   4   2   1   0   4  ||   3  10   4   5   2  11   2
  1   3   1   1   0   0   6  ||   9  12  16  11   8  13   0
  2   2   2   2   0   2   0  ||  13  16  15   9  14  14  15
  5   4  [0]  4   3   2   5  ||   6  11 [18]  6  11  15   5
  1   2   1   1   1   2   4  ||  10   9  10   8  11  13   5

Round 7:
  2   1   4   2   1   0   4  ||   3  10   4   5   2  11   2
  1   3   1   1   0   0   6  ||   8  10  13   9   7  13   0
  2  [1]  1   1   0   2   0  ||  11 [15] 12   8  12  14  15
  5   3   0   3   3   2   5  ||   3   8  10   3   8  15   5
  1   1   0   0   1   2   4  ||   8   8   7   7   9  13   5

Round 8:
  2   1   4   2   1   0   4  ||   1   7   2   4   2  11   2
  0   2   0   1   0   0   6  ||   7   7  12   7   7  13   0
  1   1   0   1   0   2   0  ||   8   8  10   6  12  14  15
  4   2   0   3   3  [2]  5  ||   2   6   8   2   8 [15]  5
  1   1   0   0   1   2   4  ||   6   6   6   7   9  13   5

Round 9:
  2   1   4   2   1   0   4  ||   1   7   2   4   2  11   2
  0   2   0   1   0   0   6  ||   7   7  12   7   6  12   0
  1   1   0   1   0  [1]  0  ||   8   8  10   5  10 [13] 13
  4   2   0   3   2   2   4  ||   2   6   8   0   6   9   3
  1   1   0   0   0   1   3  ||   6   6   6   5   8  10   4

Round 10:
  2   1   4   2   1   0   4  ||   1   7   2   4   2  10   1
  0   2  [0]  1   0   0   5  ||   7   7 [12]  7   6  11   0
  1   1   0   1   0   1   0  ||   8   8  10   4   8   9  10
  4   2   0   3   1   1   3  ||   2   6   8   0   6   8   3
  1   1   0   0   0   1   3  ||   6   6   6   4   6   7   2

Round 11:
  2   0   3   1   1   0   4  ||   0   6   0   3   0  10   1
  0   1   0   0   0  [0]  5  ||   4   5   5   5   3 [11]  0
  1   0   0   0   0   1   0  ||   6   8   6   4   6   9  10
  4   2   0   3   1   1   3  ||   1   5   6   0   5   8   3
  1   1   0   0   0   1   3  ||   6   6   6   4   6   7   2

Round 12:
  2   0   3   1   0   0   3  ||   0   6   0   2   1   7   1
  0   1   0   0   0   0   4  ||   4   5   5   4   1   7   0
  1   0   0   0   0  [0]  0  ||   6   8   6   4   5  [9]  8
  4   2   0   3   1   1   3  ||   1   5   6   0   4   7   2
  1   1   0   0   0   1   3  ||   6   6   6   4   6   7   2

Round 13:
  2   0   3   1   0   0   3  ||   0   6   0   2   1   6   0
  0   1   0   0   0   0   3  ||   4   5   5   4   1   6   0
  1  [0]  0   0   0   0   0  ||   6  [8]  6   3   3   5   5
  4   2   0   3   0   0   2  ||   1   5   6   0   4   6   2
  1   1   0   0   0   1   3  ||   6   6   6   3   4   4   0

Round 14:
  2   0   3   1   0  [0]  3  ||   0   5   0   2   1  [6]  0
  0   0   0   0   0   0   3  ||   2   5   4   4   1   6   0
  0   0   0   0   0   0   0  ||   4   4   4   3   3   5   5
  3   1   0   3   0   0   2  ||   0   4   5   0   4   6   2
  1   1   0   0   0   1   3  ||   4   4   5   3   4   4   0

Round 15:
  2   0   3   1   0   0   2  ||   0   5   0   2   1   4   0
  0   0   0   0   0   0   2  ||   2   5   4   4   1   4   0
  0   0   0   0   0   0   0  ||   4   4   4   3   3   4   4
  3   1   0   3   0  [0]  2  ||   0   4   5   0   4  [6]  2
  1   1   0   0   0   1   3  ||   4   4   5   3   4   4   0

Round 16:
  2  [0]  3   1   0   0   2  ||   0  [5]  0   2   1   4   0
  0   0   0   0   0   0   2  ||   2   5   4   4   1   4   0
  0   0   0   0   0   0   0  ||   4   4   4   3   3   3   3
  3   1   0   3   0   0   1  ||   0   4   5   0   3   3   1
  1   1   0   0   0   0   2  ||   4   4   5   3   3   3   0

Round 17:
  1   0   2   1   0   0   2  ||   0   3   0   1   1   4   0
  0   0   0   0   0   0   2  ||   1   3   3   3   1   4   0
  0   0   0   0   0   0   0  ||   4   4   4   3   3   3   3
  3   1  [0]  3   0   0   1  ||   0   4  [5]  0   3   3   1
  1   1   0   0   0   0   2  ||   4   4   5   3   3   3   0

Round 18:
  1   0   2   1   0   0   2  ||   0   3   0   1   1   4   0
  0   0   0   0   0   0   2  ||   1   3   3   3   1   4   0
  0   0   0   0   0   0   0  ||   3   3   2   2   2   3   3
  3  [0]  0   2   0   0   1  ||   0  [4]  2   0   2   3   1
  1   0   0   0   0   0   2  ||   2   4   2   2   2   3   0

Round 19:
  1   0   2   1   0  [0]  2  ||   0   3   0   1   1  [4]  0
  0   0   0   0   0   0   2  ||   1   3   3   3   1   4   0
  0   0   0   0   0   0   0  ||   2   2   2   2   2   3   3
  2   0   0   2   0   0   1  ||   0   2   2   0   2   3   1
  0   0   0   0   0   0   2  ||   2   2   2   2   2   3   0

Round 20:
  1  [0]  2   1   0   0   1  ||   0  [3]  0   1   1   2   0
  0   0   0   0   0   0   1  ||   1   3   3   3   1   2   0
  0   0   0   0   0   0   0  ||   2   2   2   2   2   2   2
  2   0   0   2   0   0   1  ||   0   2   2   0   2   3   1
  0   0   0   0   0   0   2  ||   2   2   2   2   2   3   0

Round 21:
  0   0   1   1   0   0   1  ||   0   1   0   0   1   2   0
  0   0   0   0   0   0   1  ||   0   1   2   2   1   2   0
  0   0   0   0   0   0   0  ||   2   2   2   2   2   2   2
  2   0   0   2   0  [0]  1  ||   0   2   2   0   2  [3]  1
  0   0   0   0   0   0   2  ||   2   2   2   2   2   3   0

Round 22:
  0   0   1   1   0   0   1  ||   0   1   0   0   1   2   0
  0   0   0   0   0   0   1  ||   0   1   2   2   1   2   0
 [0]  0   0   0   0   0   0  ||  [2]  2   2   2   2   1   1
  2   0   0   2   0   0   0  ||   0   2   2   0   2   1   1
  0   0   0   0   0   0   1  ||   2   2   2   2   2   1   0

Round 23:
  0   0   1   1   0   0   1  ||   0   1   0   0   1   2   0
  0   0  [0]  0   0   0   1  ||   0   1  [2]  2   1   2   0
  0   0   0   0   0   0   0  ||   1   1   2   2   2   1   1
  1   0   0   2   0   0   0  ||   0   1   2   0   2   1   1
  0   0   0   0   0   0   1  ||   1   1   2   2   2   1   0

Round 24:
  0   0   0   0   0   0   1  ||   0   0   0   0   0   2   0
  0   0   0   0   0   0   1  ||   0   0   0   0   0   2   0
  0   0  [0]  0   0   0   0  ||   1   1  [2]  2   2   1   1
  1   0   0   2   0   0   0  ||   0   1   2   0   2   1   1
  0   0   0   0   0   0   1  ||   1   1   2   2   2   1   0

Round 25:
  0   0   0   0   0  [0]  1  ||   0   0   0   0   0  [2]  0
  0   0   0   0   0   0   1  ||   0   0   0   0   0   2   0
  0   0   0   0   0   0   0  ||   1   1   1   1   1   1   1
  1   0   0   1   0   0   0  ||   0   1   1   0   1   1   1
  0   0   0   0   0   0   1  ||   1   1   1   1   1   1   0

Round 26:
  0   0   0   0   0   0   0  ||   0   0   0   0   0   0   0
  0   0   0   0   0   0   0  ||   0   0   0   0   0   0   0
 [0]  0   0   0   0   0   0  ||  [1]  1   1   1   1   0   0
  1   0   0   1   0   0   0  ||   0   1   1   0   1   1   1
  0   0   0   0   0   0   1  ||   1   1   1   1   1   1   0

Round 27:
  0   0   0   0   0   0   0  ||   0   0   0   0   0   0   0
  0   0   0   0   0   0   0  ||   0   0   0   0   0   0   0
  0   0  [0]  0   0   0   0  ||   0   0  [1]  1   1   0   0
  0   0   0   1   0   0   0  ||   0   0   1   0   1   1   1
  0   0   0   0   0   0   1  ||   0   0   1   1   1   1   0

Round 28:
  0   0   0   0   0   0   0  ||   0   0   0   0   0   0   0
  0   0   0   0   0   0   0  ||   0   0   0   0   0   0   0
  0   0   0   0   0   0   0  ||   0   0   0   0   0   0   0
  0   0   0   0   0  [0]  0  ||   0   0   0   0   0  [1]  1
  0   0   0   0   0   0   1  ||   0   0   0   0   0   1   0

Done in 28 rounds

Это можно решить с помощью дерева глубины O (3 ^ (n)). Где n - сумма всех квадратов.

Сначала предположим, что решить задачу с деревом O (9 ^ n) тривиально, просто рассмотрим все возможные места бомбардировки. Для примера см. Реализацию Alfe .

Затем поймите, что мы можем работать, чтобы бомбить снизу вверх, и при этом получить минимальную схему бомбардировки.

1. Начните с нижнего левого угла.
2. Бомба это забвение с единственными играми, которые имеют смысл (вверх и вправо).
3. Переместить один квадрат вправо.
4. В то время как цель имеет значение больше нуля, рассмотрим каждую из 2 игр, которые имеют смысл (прямо вверх или вверх и вправо), уменьшите значение цели на единицу и сделайте новую ветвь для каждой возможности.
5. Переместить другой вправо.
6. В то время как цель имеет значение больше нуля, рассмотрим каждую из 3 игр, которые имеют смысл (вверх, влево, вверх и вверх вправо), уменьшите значение цели на единицу и сделайте новую ветвь для каждой возможности.
7. Повторите шаги 5 и 6, пока ряд не будет устранен.
8. Двигайтесь вверх по ряду и повторяйте шаги с 1 по 7, пока головоломка не будет решена.

Этот алгоритм является правильным, потому что

1. Необходимо завершить каждый ряд в какой-то момент.
2. Завершение строки всегда требует игры либо сверху, либо снизу, либо внутри этой строки.
3. Всегда лучше или лучше выбрать игру выше самой низкой неочищенной строки, чем игру в строке или ниже строки.

На практике этот алгоритм будет регулярно работать лучше, чем его теоретический максимум, потому что он будет регулярно бомбить соседей и уменьшать размер поиска. Если мы предположим, что каждая бомбардировка уменьшает значение 4 дополнительных целей, тогда наш алгоритм будет работать в O (3 ^ (n / 4)) или приблизительно O (1,3 ^ n).

Поскольку этот алгоритм все еще экспоненциальный, было бы целесообразно ограничить глубину поиска. Мы могли бы ограничить число разрешенных веток некоторым числом, X, и, как только мы окажемся настолько глубокими, мы заставим алгоритм выбрать лучший путь, который он определил до сих пор (тот, который имеет минимальную общую сумму платы в одном из своих терминальных листов). ). Тогда наш алгоритм гарантированно запустится за O (3 ^ X) времени, но не гарантируется получение правильного ответа. Тем не менее, мы всегда можем увеличить X и проверить эмпирически, имеет ли смысл компромисс между увеличением вычислений и лучшими ответами.

оценочная функция, общая сумма:

int f (int ** matrix, int width, int height, int x, int y)
{
    int m[3][3] = { 0 };

    m[1][1] = matrix[x][y];
    if (x > 0) m[0][1] = matrix[x-1][y];
    if (x < width-1) m[2][1] = matrix[x+1][y];

    if (y > 0)
    {
        m[1][0] = matrix[x][y-1];
        if (x > 0) m[0][0] = matrix[x-1][y-1];
        if (x < width-1) m[2][0] = matrix[x+1][y-1];
    }

    if (y < height-1)
    {
        m[1][2] = matrix[x][y+1];
        if (x > 0) m[0][2] = matrix[x-1][y+1];
        if (x < width-1) m[2][2] = matrix[x+1][y+1];
    }

    return m[0][0]+m[0][1]+m[0][2]+m[1][0]+m[1][1]+m[1][2]+m[2][0]+m[2][1]+m[2][2];
}

целевая функция:

Point bestState (int ** matrix, int width, int height)
{
    Point p = new Point(0,0);
    int bestScore = 0;
    int b = 0;

    for (int i=0; i<width; i++)
        for (int j=0; j<height; j++)
        {
            b = f(matrix,width,height,i,j);

            if (b > bestScore)
            {
                bestScore = best;
                p = new Point(i,j);
            }
        }

    retunr p;
}

уничтожить функцию:

void destroy (int ** matrix, int width, int height, Point p)
{
    int x = p.x;
    int y = p.y;

    if(matrix[x][y] > 0) matrix[x][y]--;
    if (x > 0) if(matrix[x-1][y] > 0) matrix[x-1][y]--;
    if (x < width-1) if(matrix[x+1][y] > 0) matrix[x+1][y]--;

    if (y > 0)
    {
        if(matrix[x][y-1] > 0) matrix[x][y-1]--;
        if (x > 0) if(matrix[x-1][y-1] > 0) matrix[x-1][y-1]--;
        if (x < width-1) if(matrix[x+1][y-1] > 0) matrix[x+1][y-1]--;
    }

    if (y < height-1)
    {
        if(matrix[x][y] > 0) matrix[x][y+1]--;
        if (x > 0) if(matrix[x-1][y+1] > 0) matrix[x-1][y+1]--;
        if (x < width-1) if(matrix[x+1][y+1] > 0) matrix[x+1][y+1]--;
    }
}

целевая функция:

bool isGoal (int ** matrix, int width, int height)
{
    for (int i=0; i<width; i++)
        for (int j=0; j<height; j++)
            if (matrix[i][j] > 0)
                return false;
    return true;
}

линейная функция максимизации:

void solve (int ** matrix, int width, int height)
{
    while (!isGoal(matrix,width,height))
    {
        destroy(matrix,width,height, bestState(matrix,width,height));
    }
}

Это не оптимально, но может быть оптимизировано путем поиска лучшей функции оценки.

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

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

memo = {}

def bomb(matrix,i,j):
    # bomb matrix at i,j

def bombsRequired(matrix,i,j):
    # bombs required to zero matrix[i,j]

def distance(m1, i, len1, m2, j, len2):
    key = hash(m1)
    if memo[key] != None: 
        return memo[key]

    if len1 == 0: return len2
    if len2 == 0: return len1

    cost = 0
    if m1 != m2: cost = m1[i,j]
    m = bomb(m1,i,j)
    dist = distance(str1,i+1,len1-1,str2,j+1,len2-1)+cost)
    memo[key] = dist
    return dist

Это был ответ на первый заданный вопрос. Я не заметил, что он изменил параметры.

Создайте список всех целей. Присвойте значение цели, основываясь на количестве положительных значений, на которые воздействует капля (сама и все соседи). Наибольшее значение будет девять.

Сортируйте цели по количеству затронутых целей (По убыванию), с вторичной сортировкой по убыванию по сумме каждой пораженной цели.

Бросьте бомбу на цель с самым высоким рейтингом, затем пересчитайте цели и повторяйте, пока все значения целей не станут равны нулю.

Согласитесь, это не всегда самый оптимальный вариант. Например,

100011
011100
011100
011100
000000
100011

Этот подход потребует 5 бомб, чтобы очистить. Оптимально, однако, вы могли бы сделать это в 4. Тем не менее, чертовски близко, и нет возврата назад. Для большинства ситуаций это будет оптимально или очень близко.

Используя исходные номера задач, этот подход решает 28 бомб.

Добавляем код для демонстрации этого подхода (используя форму с кнопкой):

         private void button1_Click(object sender, EventArgs e)
    {
        int[,] matrix = new int[10, 10] {{5, 20, 7, 1, 9, 8, 19, 16, 11, 3}, 
                                         {17, 8, 15, 17, 12, 4, 5, 16, 8, 18},
                                         { 4, 19, 12, 11, 9, 7, 4, 15, 14, 6},
                                         { 17, 20, 4, 9, 19, 8, 17, 2, 10, 8},
                                         { 3, 9, 10, 13, 8, 9, 12, 12, 6, 18}, 
                                         {16, 16, 2, 10, 7, 12, 17, 11, 4, 15},
                                         { 11, 1, 15, 1, 5, 11, 3, 12, 8, 3},
                                         { 7, 11, 16, 19, 17, 11, 20, 2, 5, 19},
                                         { 5, 18, 2, 17, 7, 14, 19, 11, 1, 6},
                                         { 13, 20, 8, 4, 15, 10, 19, 5, 11, 12}};


        int value = 0;
        List<Target> Targets = GetTargets(matrix);
        while (Targets.Count > 0)
        {
            BombTarget(ref matrix, Targets[0]);
            value += 1;
            Targets = GetTargets(matrix);
        }
        Console.WriteLine( value);
        MessageBox.Show("done: " + value);
    }

    private static void BombTarget(ref int[,] matrix, Target t)
    {
        for (int a = t.x - 1; a <= t.x + 1; a++)
        {
            for (int b = t.y - 1; b <= t.y + 1; b++)
            {
                if (a >= 0 && a <= matrix.GetUpperBound(0))
                {
                    if (b >= 0 && b <= matrix.GetUpperBound(1))
                    {
                        if (matrix[a, b] > 0)
                        {
                            matrix[a, b] -= 1;
                        }
                    }
                }
            }
        }
        Console.WriteLine("Dropped bomb on " + t.x + "," + t.y);
    }

    private static List<Target> GetTargets(int[,] matrix)
    {
        List<Target> Targets = new List<Target>();
        int width = matrix.GetUpperBound(0);
        int height = matrix.GetUpperBound(1);
        for (int x = 0; x <= width; x++)
        {
            for (int y = 0; y <= height; y++)
            {
                Target t = new Target();
                t.x = x;
                t.y = y;
                SetTargetValue(matrix, ref t);
                if (t.value > 0) Targets.Add(t);
            }
        }
        Targets = Targets.OrderByDescending(x => x.value).ThenByDescending( x => x.sum).ToList();
        return Targets;
    }

    private static void SetTargetValue(int[,] matrix, ref Target t)
    {
        for (int a = t.x - 1; a <= t.x + 1; a++)
        {
            for (int b = t.y - 1; b <= t.y + 1; b++)
            {
                if (a >= 0 && a <= matrix.GetUpperBound(0))
                {
                    if (b >= 0 && b <= matrix.GetUpperBound(1))
                    {
                        if (matrix[ a, b] > 0)
                        {
                            t.value += 1;
                            t.sum += matrix[a,b];
                        }

                    }
                }
            }
        }

    }

Класс вам понадобится:

        class Target
    {
        public int value;
        public int sum;
        public int x;
        public int y;
    }