Algorytm zrzucania bomb

Mam n x mmacierz składającą się z nieujemnych liczb całkowitych. Na przykład:

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

„Zrzucenie bomby” zmniejsza o jeden liczbę komórki docelowej i wszystkich ośmiu jej sąsiadów do minimum zero.

x x x 
x X x
x x x

Jaki jest algorytm, który określałby minimalną liczbę bomb wymaganych do zredukowania wszystkich komórek do zera?

Opcja B (Ze względu na to, że nie jestem uważnym czytelnikiem)

Właściwie pierwsza wersja problemu nie jest tą, na którą szukam odpowiedzi. Nie przeczytałem dokładnie całego zadania, istnieją dodatkowe ograniczenia, powiedzmy:

A co z prostym problemem, gdy sekwencja w rzędzie musi się nie zwiększać:

8 7 6 6 5 możliwa sekwencja wprowadzania

7 8 5 5 2 nie jest możliwe, ponieważ 7 -> 8 rośnie w sekwencji.

Może znalezienie odpowiedzi na „łatwiejszą” sprawę pomogłoby znaleźć rozwiązanie na trudniejsze.

PS: Uważam, że gdy mamy kilka takich samych sytuacji wymagających minimalnej liczby bomb do wyczyszczenia górnej linii, wybieramy taką, która używa większości bomb po „lewej stronie” rzędu. Nadal masz jakiś dowód, który może być poprawny?

Istnieje sposób, aby zredukować to do prostego pod-problemu.

Wyjaśnienie obejmuje 2 części, algorytm i powód, dla którego algorytm zapewnia optymalne rozwiązanie. Pierwszy nie będzie miał sensu bez drugiego, więc zacznę od tego, dlaczego.

Jeśli myślisz o zbombardowaniu prostokąta (załóż duży prostokąt - nie ma jeszcze skrzynek krawędziowych), możesz zauważyć, że jedynym sposobem na zmniejszenie pustego prostokąta kwadratów na obwodzie do 0 jest zbombardowanie albo obwodu, albo zbombardowanie pustego prostokąta kwadraty na obwodzie. Zadzwonię do warstwy obwodowej 1, a prostokąt w jej warstwie 2.

Ważnym spostrzeżeniem jest to, że nie ma punktu bombardowania warstwy 1, ponieważ uzyskany w ten sposób „promień wybuchu” jest zawsze zawarty w promieniu wybuchu innego kwadratu z warstwy 2. Powinieneś być w stanie łatwo o tym przekonać.

Możemy więc zredukować problem do znalezienia optymalnego sposobu na zbombardowanie obwodu, a następnie możemy to powtarzać, aż wszystkie kwadraty osiągną zero.

Ale oczywiście nie zawsze znajdzie to optymalne rozwiązanie, jeśli możliwe będzie zbombardowanie obwodu w mniej niż optymalny sposób, ale użycie X dodatkowych bomb upraszcza problem zmniejszenia warstwy wewnętrznej o> X bomb. Jeśli więc nazwiemy warstwę permiterową pierwszą, jeśli umieścimy dodatkowe bomby X gdzieś w warstwie 2 (tylko w warstwie 1), czy możemy zmniejszyć wysiłek późniejszego bombardowania warstwy 2 o więcej niż X? Innymi słowy, musimy udowodnić, że możemy być chciwi w zmniejszaniu zewnętrznego obwodu.

Ale wiemy, że możemy być chciwi. Ponieważ żadna bomba w warstwie 2 nigdy nie może być bardziej skuteczna w zmniejszaniu warstwy 2 do 0 niż strategicznie umieszczona bomba w warstwie 3. I z tego samego powodu jak poprzednio - zawsze jest bomba, którą możemy umieścić w warstwie 3, która wpłynie na każdy kwadrat warstwy 2, którą może bomba umieszczona w warstwie 2. Tak więc nigdy nie zaszkodzi nam być chciwym (w tym sensie chciwości).

Więc wszystko, co musimy zrobić, to znaleźć optymalny sposób na zmniejszenie permiter'a do zera poprzez bombardowanie następnej warstwy wewnętrznej.

Najpierw nigdy nas nie boli bombardowanie rogu do zera, ponieważ tylko narożnik warstwy wewnętrznej może do niego dotrzeć, więc naprawdę nie mamy wyboru (a każda bomba na obwodzie, która może dotrzeć do narożnika, ma promień wybuchu zawarty w promień piaskowania od rogu warstwy wewnętrznej).

Gdy to zrobimy, kwadraty na obwodzie sąsiadującym z rogiem 0 można osiągnąć tylko 2 kwadraty od wewnętrznej warstwy:

0       A       B

C       X       Y

D       Z

W tym momencie obwód jest faktycznie zamkniętą pętlą 1-wymiarową, ponieważ każda bomba zmniejszy 3 sąsiednie kwadraty. Z wyjątkiem niektórych dziwności w pobliżu rogów - X może „trafić” A, B, C i D.

Teraz nie możemy używać żadnych sztuczek w promieniu wybuchu - sytuacja każdego kwadratu jest symetryczna, z wyjątkiem dziwnych narożników, i nawet tam żaden promień wybuchu nie jest podzbiorem innego. Zauważ, że gdyby była to linia (jak omawia pułkownik Panic) zamiast zamkniętej pętli, rozwiązanie jest trywialne. Punkty końcowe muszą zostać zmniejszone do 0 i nigdy nie zaszkodzi ci zbombardować punkty przylegające do punktów końcowych, ponieważ promień wybuchu jest nadzbiorem. Po utworzeniu punktu końcowego 0 nadal masz nowy punkt końcowy, więc powtórz (dopóki linia nie będzie równa 0).

Tak więc, jeśli możemy optymalnie zmniejszyć pojedynczy kwadrat w warstwie do zera, mamy algorytm (ponieważ przecięliśmy pętlę i teraz mamy linię prostą z punktami końcowymi). Uważam, że bombardowanie przylegające do kwadratu o najniższej wartości (daje 2 opcje), tak że najwyższa wartość w granicach 2 kwadratów od tej najniższej wartości jest minimalną możliwą (być może będziesz musiał podzielić bombardowanie, aby sobie z tym poradzić) będzie optymalna, ale ja nie masz (jeszcze?) dowodu.

Pólya mówi: „Jeśli nie możesz rozwiązać problemu, istnieje łatwiejszy do rozwiązania problem: znajdź go”.

Oczywistym prostszym problemem jest problem 1-wymiarowy (gdy siatka jest pojedynczym rzędem). Zacznijmy od najprostszego algorytmu - łapczywie bombardującego największy cel. Kiedy to pójdzie nie tak?

Biorąc pod uwagę 1 1 1, chciwy algorytm jest obojętny, do której komórki najpierw bombarduje. Oczywiście środkowa komórka jest lepsza - zeruje wszystkie trzy komórki jednocześnie. Sugeruje to nowy algorytm A, „bomba w celu zminimalizowania pozostałej kwoty”. Kiedy ten algorytm się psuje?

Biorąc pod uwagę 1 1 2 1 1, algorytm A jest obojętny między bombardowaniem 2., 3. lub 4. komórki. Ale bombardowanie drugiej komórki, aby odejść, 0 0 1 1 1jest lepsze niż bombardowanie trzeciej komórki, aby odejść 1 0 1 0 1. Jak to naprawić? Problem z bombardowaniem trzeciej komórki polega na tym, że pozostawia nam pracę w lewo i pracę w prawo, co należy wykonać osobno.

Co powiesz na „bombę, aby zminimalizować pozostałą sumę, ale zmaksymalizować minimum w lewo (tam, gdzie zbombardowaliśmy) plus minimum w prawo”. Wywołaj ten algorytm B. Kiedy ten algorytm nie działa?

Edycja: Po przeczytaniu komentarzy zgadzam się, że o wiele bardziej interesującym problemem byłby jednowymiarowy problem zmieniony, tak aby końce się połączyły. Chciałbym zobaczyć wszelkie postępy w tym zakresie.

Musiałem zatrzymać się tylko na częściowym rozwiązaniu, ponieważ nie miałem czasu, ale mam nadzieję, że nawet to częściowe rozwiązanie zapewnia pewne spostrzeżenia na temat jednego potencjalnego podejścia do rozwiązania tego problemu.

W obliczu trudnego problemu lubię wymyślać prostsze problemy, aby rozwinąć intuicję dotyczącą przestrzeni problemów. Pierwszym krokiem, jaki podjąłem, było zredukowanie problemu 2D do problemu 1-D. Rozważ linię:

0 4 2 1 3 0 1

W ten czy inny sposób wiesz, że będziesz musiał zbombardować 44 razy w miejscu lub w pobliżu miejsca, aby obniżyć go do 0. Ponieważ na lewo od miejsca znajduje się niższa liczba, bombardowanie 0lub 4nadmierne bombardowanie nie przynosi żadnych korzyści 2. W rzeczywistości uważam (ale nie ma ścisłego dowodu), że bombardowanie, 2dopóki 4miejsce nie spadnie do zera, jest co najmniej tak dobre, jak każda inna strategia, aby 4obniżyć to do zera. W strategii można przejść od lewej do prawej lubię to:

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

Kilka przykładowych rozkazów bombardowania:

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

Pomysł, aby zacząć od liczby, która musi zejść w ten czy inny sposób, jest atrakcyjny, ponieważ nagle staje się możliwe znalezienie rozwiązania, które jak niektórzy twierdzą, że jest co najmniej tak dobre, jak wszystkie inne rozwiązania.

Kolejny krok w złożoności, w którym to wyszukiwanie co najmniej tak dobrego jest nadal możliwe, znajduje się na krawędzi planszy. Jest dla mnie jasne, że zbombardowanie zewnętrznej krawędzi nigdy nie przyniesie żadnych konkretnych korzyści; lepiej zbombarduj jedno miejsce i zdobądź trzy inne miejsca za darmo. Biorąc to pod uwagę, możemy powiedzieć, że bombardowanie pierścienia wewnątrz krawędzi jest co najmniej tak dobre, jak bombardowanie krawędzi. Co więcej, możemy połączyć to z intuicją, że bombardowanie prawej krawędzi jest tak naprawdę jedynym sposobem na zmniejszenie odległości między krawędziami do 0. Co więcej, banalnie proste jest ustalenie optymalnej strategii (ponieważ jest to co najmniej tak dobry, jak każda inna strategia), aby zmniejszyć liczbę rzutów rożnych do 0. Zebraliśmy to wszystko razem i możemy znacznie zbliżyć się do rozwiązania w przestrzeni 2-D.

Biorąc pod uwagę spostrzeżenia na temat elementów narożnych, możemy z całą pewnością stwierdzić, że znamy optymalną strategię przejścia z dowolnej planszy początkowej na planszę z zerami na wszystkich rogach. To jest przykład takiej tablicy (pożyczyłem liczby od dwóch liniowych tablic powyżej). Niektóre spacje oznaczyłem inaczej i wyjaśnię dlaczego.

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

W górnym rzędzie można zauważyć, że bardzo przypomina liniowy przykład, który widzieliśmy wcześniej. Przywołując naszą wcześniejszą obserwację, że optymalnym sposobem na doprowadzenie górnego rzędu do zera jest zbombardowanie drugiego rzędu ( xrzędu). Nie ma sposobu na wyczyszczenie górnego rzędu przez zbombardowanie któregokolwiek z yrzędów i nie ma dodatkowej korzyści z bombardowania górnego rzędu nad bombardowaniem odpowiedniego miejsca w xrzędzie.

My mogliśmy zastosować strategię liniowy z góry (bombardowanie odpowiednie miejsca na xwiersz), dotyczące się tylko z górnego rzędu i nic innego. Poszłoby coś takiego:

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

Wada tego podejścia staje się bardzo oczywista w ostatnich dwóch bombardowaniach. Jest jasne, biorąc pod uwagę, że jedynymi miejscami bombowymi, które zmniejszają 4liczbę w pierwszej kolumnie w drugim rzędzie, są pierwsze xi drugie y. Ostatnie dwa bombardowania są wyraźnie gorsze od samego bombardowania pierwszego x, co zrobiłoby dokładnie to samo (w odniesieniu do pierwszego miejsca w górnym rzędzie, którego nie mamy innego sposobu wyczyszczenia). Ponieważ wykazaliśmy, że nasza obecna strategia nie jest optymalna, zmiana strategii jest wyraźnie potrzebna.

W tym momencie mogę cofnąć się w kierunku złożoności i skupić się tylko na jednym rogu. Rozważmy to:

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

Jest oczywiste, że jedynym sposobem, aby dostać się z miejsca 4na dół do zera są bombardować jakąś kombinację x, yoraz z. Biorąc pod uwagę niektóre akrobacje, jestem całkiem pewien, że optymalnym rozwiązaniem jest xtrzykrotne bombardowanie, a apotem b. Teraz chodzi o ustalenie, w jaki sposób doszedłem do tego rozwiązania i jeśli ujawni to jakąkolwiek intuicję, której możemy użyć, aby rozwiązać ten lokalny problem. Zauważam, że nie ma bombardowania yi zspacji. Próba znalezienia rogu, w którym bombardowanie tych przestrzeni ma sens, daje kąt, który wygląda następująco:

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

W tym przypadku jest dla mnie jasne, że optymalnym rozwiązaniem jest bombardowanie y5 razy i z5 razy. Idźmy o krok dalej.

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

Tutaj wydaje się podobnie intuicyjne, że optymalnym rozwiązaniem jest bombardowanie ai b6 razy, a następnie x4 razy.

Teraz staje się grą, w jaki sposób zamienić te intuicje w zasady, na których możemy budować.

Mam nadzieję, że będzie kontynuowany!

W przypadku zaktualizowanego pytania prosty, zachłanny algorytm daje optymalny wynik.

Zrzuć bomby A [0,0] do komórki A [1,1], a następnie zrzuć bomby A [1,0] do komórki A [2,1] i kontynuuj ten proces w dół. Aby wyczyścić lewy dolny róg, zrzuć bomby maks. (A [N-1,0], A [N-2,0], A [N-3,0]) do komórki A [N-2,1]. Spowoduje to całkowite wyczyszczenie pierwszych 3 kolumn.

Przy takim samym podejściu wyczyść kolumny 3,4,5, a następnie kolumny 6,7,8 itd.

Niestety nie pomaga to w znalezieniu rozwiązania pierwotnego problemu.

Problem „większego” (bez ograniczenia „nie-rosnącego”) może być trudny do NP. Oto szkic dowodu.

Załóżmy, że mamy płaski wykres stopnia do 3. Znajdźmy minimalną osłonę wierzchołków dla tego wykresu. Zgodnie z artykułem Wikipedii problem ten jest trudny w NP dla płaskich wykresów stopnia do 3. Można to udowodnić przez redukcję z Planar 3SAT. I twardość Planar 3SAT - poprzez redukcję od 3SAT. Oba te dowody zostały przedstawione w ostatnich wykładach w „Algorytmicznych dolnych granicach” przez prof. Erik Demaine (wykłady 7 i 9).

Jeśli podzielimy niektóre krawędzie oryginalnego wykresu (lewy wykres na diagramie), każdy z parzystą liczbą dodatkowych węzłów, powstały wykres (prawy wykres na diagramie) powinien mieć dokładnie taką samą minimalną osłonę wierzchołków dla oryginalnych wierzchołków. Taka transformacja pozwala wyrównać wierzchołki wykresu do dowolnych pozycji na siatce.

Jeśli umieścimy wierzchołki wykresu tylko na równych wierszach i kolumnach (w taki sposób, że żadne dwie krawędzie padające na jeden wierzchołek nie tworzą ostrego kąta), wstawimy „jedynki” wszędzie tam, gdzie jest krawędź, i wstawiamy „zera” do innych pozycji siatki, możemy użyć dowolnego rozwiązania pierwotnego problemu, aby znaleźć minimalną osłonę wierzchołków.

Możesz reprezentować ten problem jako problem programowania liczb całkowitych . (jest to tylko jedno z możliwych rozwiązań tego problemu)

Posiadanie punktów:

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

można napisać 16 równań, w których na przykład zachowuje się punkt f

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

zminimalizowane ponad sumę wszystkich indeksów i rozwiązania liczb całkowitych.

Rozwiązaniem jest oczywiście suma tych indeksów.

Można to dodatkowo uprościć, ustawiając wszystkie xi na granicach 0, więc w tym przykładzie otrzymamy równanie 4 + 1.

Problem polega na tym, że nie ma trywialnego algorytmu rozwiązywania takich problemów. Nie jestem w tym ekspertem, ale rozwiązanie tego problemu, ponieważ programowanie liniowe jest trudne.

To jest częściowa odpowiedź, próbuję znaleźć dolną i górną granicę, która może być możliwą liczbą bomb.

W przypadku płyt 3x3 i mniejszych rozwiązaniem jest zawsze największa numerowana komórka.

Na planszach większych niż 4x4 pierwszą oczywistą dolną granicą jest suma narożników:

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

bez względu na to, jak zorganizujesz bombę, nie możesz wyczyścić tej planszy 4x4 za pomocą mniej niż 2 + 1 + 6 + 4 = 13 bomb.

W innych odpowiedziach wspomniano, że umieszczenie bomby na drugim rogu w celu wyeliminowania rogu nigdy nie jest gorsze niż umieszczenie bomby na samym rogu, więc biorąc pod uwagę tablicę:

*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*

Możemy wyzerować rogi, umieszczając bomby w drugim rogu, aby uzyskać nową deskę:

 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

Na razie w porządku. Potrzebujemy 13 bomb, aby oczyścić rogi.

Teraz obserwuj cyfry 6, 4, 3 i 2 oznaczone poniżej:

 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

Nie ma sposobu na zbombardowanie dwóch komórek za pomocą jednej bomby, więc minimalna bomba wzrosła o 6 + 4 + 3 + 2, więc zwiększając liczbę bomb, których użyliśmy do wyczyszczenia narożników, otrzymujemy to minimum liczba bomb wymaganych na tej mapie stała się 28 bombami. Nie można wyczyścić tej mapy przy użyciu mniej niż 28 bomb, jest to dolna granica dla tej mapy.

Możesz użyć chciwego algorytmu, aby ustalić górną granicę. Inne odpowiedzi wykazały, że zachłanny algorytm wytwarza rozwiązanie wykorzystujące 28 bomb. Ponieważ wcześniej udowodniliśmy, że żadne optymalne rozwiązanie nie może mieć mniej niż 28 bomb, dlatego 28 bomb jest rzeczywiście optymalnym rozwiązaniem.

Kiedy chciwość i metoda znajdowania minimalnej granicy, o której wspomniałem powyżej, nie są zbieżne, myślę, że musisz wrócić do sprawdzania wszystkich kombinacji.

Algorytm znajdowania dolnej granicy jest następujący:

1. Wybierz element o najwyższym numerze, nazwij go P.
2. Oznacz wszystkie komórki dwa kroki od P i samej P jako niemożliwe do wyszukania.
3. Dodaj P do minimumslisty.
4. Powtarzaj krok 1, dopóki wszystkie komórki nie będą możliwe do wyszukania.
5. Zsumuj minimumslistę, aby uzyskać dolną granicę.

To byłoby chciwe podejście:

1. Oblicz macierz „wyniku” rzędu n X m, gdzie wynik [i] [j] jest całkowitym odjęciem punktów w macierzy, jeżeli pozycja (i, j) jest zbombardowana. (Maksymalny wynik punktu to 9, a minimalny wynik to 0)

2. Poruszając się mądrze, znajdź i wybierz pierwszą pozycję z najwyższym wynikiem (powiedzmy (i, j)).

3. Bomb (i, j). Zwiększ liczbę bomb.

4. Jeśli wszystkie elementy oryginalnej macierzy nie są równe zero, to dostaniesz 1.

Mam jednak wątpliwości, że jest to optymalne rozwiązanie.

Edytować:

Podejście Chciwe, które zamieściłem powyżej, choć działa, najprawdopodobniej nie daje nam optymalnego rozwiązania. Pomyślałem, że powinienem dodać do niego kilka elementów DP.

Myślę, że możemy się zgodzić, że w dowolnym momencie jedna z pozycji o najwyższym „wyniku” (wynik [i] [j] = całkowite odjęcie punktów, jeśli (i, j) jest zbombardowana) musi być ukierunkowana. Począwszy od tego założenia, oto nowe podejście:

NumOfBombs (M): (zwraca minimalną wymaganą liczbę bombardowań)

1. Biorąc pod uwagę macierz M rzędu n X m. Jeśli wszystkie elementy M są równe zero, to zwróć 0.

2. Oblicz macierz „score” M.

   Niech k odrębnymi pozycjami P1, P2, ... Pk (1 <= k <= n * m), będą pozycjami w M o najwyższych wynikach.

3. return (1 + min (NumOfBombs (M1), NumOfBombs (M2), ..., NumOfBombs (Mk)))

   gdzie M1, M2, ..., Mk są macierzami wynikowymi, jeśli zbombardujemy odpowiednio pozycje P1, P2, ..., Pk.

Ponadto, jeśli chcemy, aby kolejność pozycji nuke była dodatkowo, musielibyśmy śledzić wyniki „min”.

Twój nowy problem z nie zmniejszającymi się wartościami w wierszach jest dość łatwy do rozwiązania.

Zauważ, że lewa kolumna zawiera najwyższe liczby. Dlatego każde optymalne rozwiązanie musi najpierw zredukować tę kolumnę do zera. W ten sposób możemy wykonać 1-D bombardowanie nad tą kolumną, redukując każdy element w niej do zera. Pozwalamy bombom spaść na drugą kolumnę, aby zadawały maksymalne obrażenia. Myślę, że jest tu wiele postów dotyczących sprawy 1D, więc mogę bezpiecznie pominąć tę sprawę. (Jeśli chcesz, żebym to opisał, mogę.). Ze względu na malejącą właściwość wszystkie trzy skrajnie lewe kolumny zostaną zredukowane do zera. Ale z pewnością użyjemy tutaj minimalnej liczby bomb, ponieważ lewa kolumna musi zostać wyzerowana.

Teraz, gdy lewa kolumna zostanie wyzerowana, po prostu odetniemy trzy kolumny najbardziej lewe, które są teraz wyzerowane i powtórzymy z teraz zmniejszoną macierzą. To musi dać nam optymalne rozwiązanie, ponieważ na każdym etapie używamy możliwej do udowodnienia minimalnej liczby bomb.

Mathematica Integer Programowanie liniowe przy użyciu odgałęzień

Jak już wspomniano, problem ten można rozwiązać za pomocą programowania liniowego liczb całkowitych (czyli NP-Hard ). Mathematica ma już wbudowaną 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." [Patrz Samouczek optymalizacji optymalizacji w Mathematica ..]

Napisałem następujący kod, który wykorzystuje biblioteki ILP Mathematica. Jest zaskakująco szybki.

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}]]];]

Na przykład podany w problemie:

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]

Wyjścia

Dla każdego, kto czyta to za pomocą chciwego algorytmu

Wypróbuj kod dotyczący następującego problemu 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

Tutaj jest rozdzielony przecinkami:

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

W przypadku tego problemu moje rozwiązanie zawiera 208 bomb. Oto możliwe rozwiązanie (udało mi się to rozwiązać w około 12 sekund).

Jako sposób na przetestowanie wyników, które wytwarza Mathematica, sprawdź, czy Twój chciwy algorytm może zrobić coś lepszego.

Nie ma potrzeby przekształcania problemu w podproblemy liniowe.

Zamiast tego użyj prostej chciwej heurystyki, która polega na bombardowaniu rogów , zaczynając od największej.

W podanym przykładzie są cztery rogi {2, 1, 6, 4}. Dla każdego rogu nie ma lepszego ruchu niż bombardowanie przekątnej komórki do rogu, więc wiemy, że nasze pierwsze bombardowania 2 + 1 + 6 + 4 = 13 muszą odbywać się w tych ukośnych komórkach. Po bombardowaniu zostaje nam nowa matryca:

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 

Po pierwszych 13 bombardowaniach używamy heurystyki, aby wyeliminować 3 0 2 za pomocą trzech bombardowań. Teraz mamy 2 nowe rogi, {2, 1} w czwartym rzędzie. Bombardujemy te, kolejne 3 bombardowania. Zmniejszyliśmy teraz matrycę do 4 x 4. Jest jeden róg, w lewym górnym rogu. Bombardujemy to. Teraz pozostały nam 2 rogi, {5, 3}. Ponieważ 5 jest największym zakrętem, bombardujemy najpierw, 5 bombardowań, a następnie bombardujemy 3 w drugim rogu. Suma wynosi 13 + 3 + 3 + 1 + 5 + 3 = 28.

Robi to dogłębne poszukiwanie najkrótszej ścieżki (serii bombardowań) przez ten „labirynt” pozycji. Nie, nie mogę udowodnić, że nie ma szybszego algorytmu, przepraszam.

#!/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))

Wydaje się, że podejście programowania liniowego może być tutaj bardzo pomocne.

Niech P _{m xn} będzie macierzą z wartościami pozycji:

Teraz zdefiniujmy macierz bomb B (x, y) _mxn , z 1 ≤ x ≤ m , 1 ≤ y ≤ n jak poniżej

w taki sposób, że

Na przykład:

Szukamy więc macierzy B _{m xn} = [ b _ij ] tego

1. Można zdefiniować jako sumę macierzy bomb:

   

   ( q _ij byłoby wtedy liczba bomb , które spadlibyśmy na pozycję p _ij )

2. p _ij - b _ij ≤ 0 (aby być bardziej prostym, powiedzmy to jako P - B ≤ 0 )

Ponadto B powinien zminimalizować sumę .

Możemy również napisać B jako brzydką macierz przed sobą:

a ponieważ P - B ≤ 0 (co oznacza P ≤ B ) poniżej mamy następujący dość liniowy system nierówności:

Będąc q _{mn x 1} zdefiniowane jako

p _{mn x 1} zdefiniowany jako

Możemy powiedzieć, że mamy system Poniższy system reprezentowany jest jako iloczyn macierzy http://latex.codecogs.com/gif.download?S%5Cmathbf%7Bq%7D&space;%5Cge&space;%5Cmathbf%7Bp%7D jest S _{mn x mn} macierz, która ma zostać odwrócona, aby rozwiązać system. Nie rozwinąłem go sam, ale uważam, że powinno to być łatwe do zrobienia w kodzie.

Teraz mamy minimalny problem, który można określić jako

Uważam, że rozwiązanie tego problemu jest proste, niemal trywialne dzięki algorytmowi simpleks (jest na ten temat fajny dokument ). Jednak nie znam prawie żadnego programowania liniowego (wezmę kurs na ten temat na Coursera, ale to dopiero w przyszłości ...), miałem pewne problemy z głową, próbując to zrozumieć i mam ogromną pracę freelancera do ukończenia, więc po prostu się poddaj. Może się okazać, że zrobiłem coś nie tak w pewnym momencie, lub że nie może iść dalej, ale uważam, że ta ścieżka może doprowadzić do w roztworze. Tak czy inaczej, zależy mi na twojej opinii.

(Specjalne podziękowania za tę niesamowitą stronę do tworzenia zdjęć z wyrażeń LaTeX )

To chciwe rozwiązanie wydaje się poprawne :

Jak wskazano w komentarzach, nie powiedzie się w 2D. Ale może możesz to poprawić.

Dla 1D:
Jeśli są co najmniej 2 liczby, nie musisz strzelać do lewej, ponieważ strzelanie do drugiej nie jest gorsze . Strzelaj do drugiego, a pierwszy nie jest równy 0, bo musisz to zrobić. Przejdź do następnej komórki. Nie zapomnij o ostatniej komórce.

Kod 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])
    }
}

Tak więc dla 2D:
Znowu: nie musisz strzelać w pierwszym rzędzie (jeśli jest drugi). Strzelaj do drugiego. Rozwiąż zadanie 1D dla pierwszego rzędu. (ponieważ musisz ustawić wartość null). Spadać. Nie zapomnij ostatniego rzędu.

Aby zminimalizować liczbę bomb, musimy zmaksymalizować efekt każdej bomby. Aby to osiągnąć, na każdym kroku musimy wybrać najlepszy cel. Za każdy punkt sumujący go i ośmiu sąsiadów - może być wykorzystany jako efektywna ilość bombardowania tego punktu. Zapewni to prawie optymalną sekwencję bomb.

UPD : Powinniśmy również wziąć pod uwagę liczbę zer, ponieważ bombardowanie ich jest nieefektywne. W rzeczywistości problemem jest zminimalizowanie liczby trafionych zer. Ale nie możemy wiedzieć, w jaki sposób jakikolwiek krok przybliża nas do tego celu. Zgadzam się z pomysłem, że problem jest NP-zupełny. Sugeruję chciwe podejście, które da odpowiedź zbliżoną do rzeczywistej.

Uważam, że aby zminimalizować liczbę bomb, wystarczy zmaksymalizować ilość obrażeń. Aby to się stało, musisz sprawdzić obszar o największej sile. Więc najpierw przeanalizuj pole za pomocą jądra 3x3 i sprawdź, gdzie suma jest silniejszy ... i bombarduje tam ... i robi, dopóki pole nie będzie płaskie .. dla tego pola odpowiedź brzmi 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');

Oto rozwiązanie, które uogólnia dobre właściwości narożników.

Załóżmy, że możemy znaleźć idealny punkt zrzutu dla danego pola, czyli najlepszy sposób na zmniejszenie wartości w nim. Następnie, aby znaleźć minimalną liczbę bomb do zrzucenia, może być pierwszy szkic algorytmu (kod jest wklejany z implementacji 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

Wyzwanie jest choose_a_perfect_drop_point. Najpierw określmy, czym jest idealny punkt zrzutu.

• ZA zrzutu dla (x, y)zmniejsza wartość w (x, y). Może również zmniejszać wartości w innych komórkach.
• Spadek punkt przez to lepsze niż temperaturę kropienia b(x, y) dla (x, y)jeżeli zmniejsza wartości w odpowiedniej rozszerzeniem komórek, które b maleje.
• Punkt zrzutu jest maksymalny, jeśli nie ma innego lepszego punktu zrzutu.
• Dwa punkty zrzutu dla (x, y) są równoważne, jeśli zmniejszają ten sam zestaw komórek.
• Punkt zrzutu dla (x, y)jest idealny, jeśli jest równoważny wszystkim maksymalnym punktom zrzutu dla(x, y) .

Jeśli istnieje idealny punkt upuszczenia (x, y), nie można zmniejszyć wartości o(x, y) efektywniej niż zrzucenie bomby na jeden z idealnych punktów zrzutu (x, y).

Idealny punkt zrzutu dla danego pola to idealny punkt zrzutu dla dowolnej jego komórki.

Oto kilka przykładów:

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

Idealny punkt upuszczenia dla komórki (0, 0)(indeks zerowy) to (1, 1). Wszystkie inne punkty drop dla (1, 1), to znaczy (0, 0), (0, 1)i (1, 0)zmniejsz mniej komórek.

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

Idealny punkt kropli na komórki (2, 2)(wskaźnik zera) jest (2, 2), jak również wszystkich otaczających komórki (1, 1), (1, 2), (1, 3), (2, 1), (2, 3), (3, 1), (3, 2), i (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

idealne punkty upuszczenia dla komórki (2, 2)to (3, 1): Zmniejsza wartość w (2, 2), a wartość w (4, 0). Wszystkie pozostałe punkty upuszczenia (2, 2)nie są maksymalne, ponieważ zmniejszają o jedną komórkę mniej. Idealny punkt zrzutu (2, 2)to również idealny punkt zrzutu (4, 0)i jest to jedyny idealny punkt zrzutu na polu. Prowadzi to do idealnego rozwiązania dla tego pola (jedna kropla bomby).

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

Nie ma idealnego punktu zrzutu dla (2, 2): Zarówno (1, 1)i (1, 3)spadku, jak (2, 2)i innej komórki (są to maksymalne punkty zrzutu dla (2, 2)), ale nie są równoważne. Jednakże, (1, 1)jest to doskonały punkt na spadek (0, 0), i (1, 3)jest doskonałą bazą do spadku (0, 4).

Dzięki tej definicji idealnych punktów zrzutu i pewnej kolejności kontroli otrzymuję następujący wynik dla przykładu w pytaniu:

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

Algorytm działa jednak tylko wtedy, gdy po każdym kroku jest co najmniej jeden idealny punkt zrzutu. Możliwe jest budowanie przykładów, w których nie ma idealnych punktów zrzutu:

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

W takich przypadkach możemy zmodyfikować algorytm, aby zamiast idealnego punktu zrzutu wybrać współrzędną z minimalnym wyborem maksymalnych punktów zrzutu, a następnie obliczyć minimum dla każdego wyboru. W powyższym przypadku wszystkie komórki z wartościami mają dwa maksymalne punkty upuszczenia. Na przykład (0, 1)ma maksymalne punkty zrzutu (1, 1)i (1, 2). Wybór jednego, a następnie obliczenie minimum prowadzi do tego wyniku:

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

Oto kolejny pomysł:

Zacznijmy od przypisania wagi każdemu polu na planszy, ile liczb zostanie zmniejszonych przez zrzucenie tam bomby. Więc jeśli przestrzeń ma niezerową liczbę, otrzymuje punkt, a jeśli dowolna sąsiadująca z nią przestrzeń ma niezerową liczbę, otrzymuje dodatkowy punkt. Więc jeśli istnieje siatka 1000 na 1000, mamy wagę przypisaną do każdego z 1 miliona spacji.

Następnie posortuj listę spacji według wagi i zbombarduj tę o największej wadze. To, że tak powiem, najbardziej zyskuje na naszej złotówki.

Następnie zaktualizuj wagę każdej przestrzeni, na którą bomba ma wpływ. Będzie to przestrzeń, którą zbombardowałeś, i każde pole bezpośrednio do niej przylegające oraz każde pole bezpośrednio do nich przylegające. Innymi słowy, każda przestrzeń, której wartość mogła zostać zmniejszona do zera przez bombardowanie, lub wartość sąsiedniej przestrzeni zmniejszona do zera.

Następnie ponownie posortuj spacje listy według wagi. Ponieważ bombardowanie zmieniło tylko niewielką część przestrzeni, nie trzeba uciekać się do całej listy, wystarczy przesunąć te na liście.

Bombarduj nową przestrzeń o największej masie i powtórz procedurę.

Gwarantuje to, że każde bombardowanie redukuje jak najwięcej pól (w zasadzie uderza w jak najmniejszą liczbę pól, które już są zerowe, jak to możliwe), więc byłoby optymalne, z tym wyjątkiem, że mogą to być remisy. Więc może być konieczne wykonanie śledzenia wstecznego, gdy istnieje remis dla najwyższej wagi. Liczy się tylko remis dla najwyższej wagi, a nie inne remisy, więc mam nadzieję, że nie będzie to zbyt wiele wstecznego śledzenia.

Edycja: Kontrprzykład Mysticial poniżej pokazuje, że w rzeczywistości nie jest to gwarantowane optymalne, niezależnie od powiązań wagowych. W niektórych przypadkach zmniejszenie ciężaru tak bardzo, jak to możliwe na danym etapie, faktycznie pozostawia pozostałe bomby zbyt rozłożone, aby osiągnąć tak wysokie skumulowane zmniejszenie po drugim etapie, jak można to zrobić przy nieco mniej chciwym wyborze w pierwszym kroku. Byłem nieco wprowadzony w błąd przez pogląd, że wyniki są niewrażliwe na kolejność bombardowań. one sąniewrażliwy na kolejność, ponieważ możesz wziąć dowolną serię bombardowań i odtworzyć je od początku w innej kolejności, aby uzyskać tę samą wynikową planszę. Ale nie wynika z tego, że możesz rozważyć każde bombardowanie niezależnie. Lub przynajmniej każde bombardowanie musi być rozpatrywane w sposób uwzględniający to, jak dobrze układa planszę do kolejnych bombardowań.

Załóżmy, że policzymy pozycje planszy 1, 2, ..., nx m. Każda sekwencja zrzutów bomb może być reprezentowana przez sekwencję liczb w tym zestawie, gdzie liczby mogą się powtarzać. Jednak efekt na planszy jest taki sam, niezależnie od kolejności zrzucania bomb, więc tak naprawdę każdy wybór zrzutów bomb może być reprezentowany jako lista liczb NXM, gdzie pierwsza liczba reprezentuje liczbę bomb zrzuconych na pozycję 1 , druga liczba reprezentuje liczbę bomb zrzuconych na pozycję 2 itd. Nazwijmy tę listę liczb nxm „kluczem”.

Możesz najpierw spróbować obliczyć wszystkie stany planszy wynikające z 1 zrzutu bomby, a następnie użyć ich do obliczenia wszystkich stanów planszy wynikających z 2 zrzutów bomby itp., Aż do uzyskania wszystkich zer. Ale na każdym kroku buforowałbyś stany za pomocą klucza, który zdefiniowałem powyżej, więc możesz wykorzystać te wyniki przy obliczaniu następnego kroku (podejście „programowania dynamicznego”).

Ale w zależności od wielkości n, m oraz liczb w siatce wymagania pamięciowe tego podejścia mogą być nadmierne. Możesz wyrzucić wszystkie wyniki dla N bombardowania po obliczeniu wszystkich wyników dla N + 1, więc są pewne oszczędności. I oczywiście nie można cache'ować niczego kosztem dużo dłużej - podejście programowania dynamicznego handluje pamięci dla prędkości.

Jeśli chcesz, aby absolutnie optymalne rozwiązanie oczyściło płytę, będziesz musiał użyć klasycznego backtracka, ale jeśli matryca jest bardzo duża, znalezienie najlepszego rozwiązania zajmie wieki, jeśli chcesz „możliwego” optymalnego rozwiązania, możesz użyć chciwego algorytmu , jeśli potrzebujesz pomocy w napisaniu algorytmu, mogę Ci pomóc

Pomyśl, że to najlepszy sposób. Zrób kolejną macierz, w której przechowujesz punkty, które usuwasz, zrzucając tam bombę, a następnie wybierz komórkę z maksymalną liczbą punktów i upuść bombę tam zaktualizuj macierz punktów i kontynuuj. Przykład:

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))

wartość komórki +1 dla każdej sąsiedniej komórki o wartości większej niż 0

Brutalna siła !

Wiem, że to nie jest wydajne, ale nawet jeśli znajdziesz szybszy algorytm, zawsze możesz przetestować ten wynik, aby sprawdzić jego dokładność.

Użyj rekurencji, takiej jak ta:

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);

}

Możesz uczynić to bardziej wydajnym przez buforowanie, jeśli inny sposób prowadzi do tego samego wyniku, nie powinieneś powtarzać tych samych kroków.

Opracować:

jeśli bombardowanie komórki 1,3,5 prowadzi do tego samego wyniku co bombardowanie komórki 5,3,1, to nie powinieneś ponownie wykonywać wszystkich kolejnych kroków w obu przypadkach, wystarczy tylko 1, powinieneś gdzieś przechowywać wszystko stany tabeli i użyj ich wyników.

Do szybkiego porównania można użyć skrótu statystyk tabeli.

1. Nigdy nie bombarduj granicy (chyba że kwadrat nie ma sąsiada niebędącego granicą)
2. Zero rogu.
3. Aby wyzerować narożnik, upuść wartość narożnika o jeden kwadrat po przekątnej (jedyny sąsiad bez granic)
4. To stworzy nowe rogi. Idź do 2

Edycja: nie zauważyłem, że Kostek zasugerował prawie takie samo podejście, więc teraz mocniej twierdzę: jeśli narożniki do usunięcia są wybierane tak, aby zawsze znajdowały się na najbardziej zewnętrznej warstwie, jest to optymalne.

W przykładzie OP: upuszczenie 2 (jako 1 + 1 lub 2) na czymkolwiek innym niż na 5 nie prowadzi do trafienia w pole, które trafiłoby na 5. Więc musimy po prostu upuścić 2 na 5 (i 6 w lewym dolnym rogu 1 ...)

Po tym jest tylko jeden sposób, aby wyczyścić (w lewym górnym rogu) to, co pierwotnie było 1 (teraz 0), a mianowicie poprzez upuszczenie 0 na B3 (cel jak notacja). I tak dalej.

Dopiero po wyczyszczeniu całych kolumn A i E oraz 1 i 7 wierszy rozpocznij czyszczenie jednej warstwy głębiej.

Rozważ wyczyszczenie tylko tych celowo wyczyszczonych, wyczyszczenie rogów wartości 0 nic nie kosztuje i upraszcza myślenie o tym.

Ponieważ wszystkie bomby zrzucone w ten sposób muszą zostać zrzucone, a to prowadzi do wyczyszczonych pól, jest to optymalne rozwiązanie.

Po dobrym śnie uświadomiłem sobie, że to nieprawda. Rozważać

  ABCDE    
1 01000
2 10000
3 00000
4 00000

Moje podejście zrzuciłoby bomby na B3 i C2, gdy wystarczyło by zrzucić na B2

Oto moje rozwiązanie .. Nie wypiszę go jeszcze w kodzie, ponieważ nie mam czasu, ale uważam, że powinno to przynieść optymalną liczbę ruchów za każdym razem - choć nie jestem pewien, jak efektywne byłoby znalezienie punkty do bombardowania.

Po pierwsze, jak stwierdził @Luka Rahne w jednym z komentarzy, kolejność bombardowania nie jest ważna - tylko kombinacja.

Po drugie, jak wielu innych stwierdziło, bombardowanie 1-przekątnej z rogów jest optymalne, ponieważ dotyka większej liczby punktów niż narożników.

To generuje podstawę dla mojej wersji algorytmu: możemy zbombardować „1-off od narożników” pierwszy lub ostatni, to nie ma znaczenia (teoretycznie) Bombardujemy je jako pierwsze, ponieważ ułatwia to późniejsze decyzje (w praktyce) Bombardujemy punkt, który wpływa na najwięcej punktów, jednocześnie bombardując te rogi.

Zdefiniujmy Punkty Oporu, aby były to punkty na planszy z największą liczbą punktów niepodlegających bombardowaniu + największą liczbą zer wokół nich

punkty niepodlegające bombardowaniu można zdefiniować jako punkty, które nie istnieją w naszym obecnym zakresie planszy, na którą patrzymy.

Zdefiniuję również 4 granice, które będą obsługiwać nasz zakres: Góra = 0, Lewo = 0, Dół = k, Prawo = j. (wartości na początek)

Na koniec zdefiniuję optymalne bomby jako bomby zrzucane na punkty przylegające do punktów oporu i dotykające (1) punktu oporu o najwyższej wartości i (2) największej możliwej liczby punktów.

Jeśli chodzi o podejście - to oczywiste, że pracujemy z zewnątrz. Będziemy mogli pracować z 4 bombowcami jednocześnie.

Pierwsze punkty oporu to oczywiście nasze rogi. Punkty „poza granicami” nie są bombardowane (dla każdego rogu jest 5 punktów poza zakresem). Najpierw bombardujemy punkty po przekątnej jeden za rogiem.

Algorytm:

1. Znajdź 4 optymalne punkty bombowe.
2. Jeśli punkt bomby bombarduje punkt oporu, który dotyka 2 granic (tj. Rogu), bombarduj, aż do tego punktu wyniesie 0. W przeciwnym razie bombarduj każdy, dopóki jeden z punktów oporu dotykających optymalnego punktu bomby nie wyniesie 0.
3. dla każdej granicy: if (suma (granica) == 0) granica zaliczki

powtarzaj, aż GÓRA = DÓŁ i LEWO = PRAWO

Spróbuję później napisać właściwy kod

Możesz użyć planowania przestrzeni stanu. Na przykład użycie A * (lub jednego z jego wariantów) w połączeniu z taką heurystyką f = g + h:

• g: liczba zrzuconych dotychczas bomb
• h: suma wszystkich wartości siatki podzielonych przez 9 (co jest najlepszym wynikiem, co oznacza, że ​​mamy dopuszczalną heurystykę)

Mam także 28 ruchów. Użyłem dwóch testów dla najlepszego następnego ruchu: pierwszy ruch dający minimalną sumę dla planszy. Po drugie, dla równych kwot ruch dający maksymalną gęstość, zdefiniowany jako:

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

To jest Haskell. „tablica rozwiązywania” pokazuje rozwiązanie silnika. Możesz zagrać w grę, wpisując „główny”, a następnie wprowadź punkt docelowy, „najlepszy”, aby uzyskać rekomendację, lub „wyjdź”, aby wyjść.

WYJŚCIE:
* Główna> rozwiąż planszę
[(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)

Wydaje się, że istnieje tutaj niepasująca do dwóch stron podstruktura. Rozważ następujące wystąpienie:

0010000
1000100
0000001
1000000
0000001
1000100
0010000

Optymalne rozwiązanie tego przypadku ma rozmiar 5, ponieważ jest to rozmiar minimalnego pokrycia wierzchołków 9-cyklowego brzegu.

W szczególności ten przypadek pokazuje, że relaksacja programowania liniowego, którą opublikowało kilka osób, nie jest dokładna, nie działa i wszystkie inne złe rzeczy. Jestem prawie pewien, że mogę zredukować „pokrycie wierzchołków mojego płaskiego wykresu sześciennego o jak najmniejszą liczbę krawędzi” do twojego problemu, co sprawia, że ​​wątpię, czy którekolwiek z zachłannych / wspinaczkowych rozwiązań będzie skuteczne.

W najgorszym przypadku nie widzę sposobu na rozwiązanie tego problemu w czasie wielomianowym. Może być bardzo sprytne rozwiązanie do wyszukiwania binarnego i DP, którego nie widzę.

EDYCJA : Widzę, że konkurs ( http://deadline24.pl ) jest niezależny od języka; wysyłają ci kilka plików wejściowych, a ty wysyłasz im dane wyjściowe. Więc nie potrzebujesz czegoś, co działa w najgorszym przypadku wielomianu. W szczególności możesz spojrzeć na dane wejściowe !

Na wejściu znajduje się kilka małych skrzynek. Potem jest obudowa 10 x 1000, obudowa 100 x 100 i obudowa 1000 x 1000. Wszystkie trzy duże przypadki są bardzo dobrze wychowane. Pozycje sąsiadujące poziomo mają zazwyczaj tę samą wartość. Na stosunkowo mocnej maszynie jestem w stanie rozwiązać wszystkie przypadki, brutalnie zmuszając CPLEX w zaledwie kilka minut. Mam szczęście na 1000x1000; relaksacja LP ma zintegrowane optymalne rozwiązanie. Moje rozwiązania są zgodne z .ansplikami zawartymi w pakiecie danych testowych.

Założę się, że możesz użyć struktury danych wejściowych w znacznie bardziej bezpośredni sposób niż ja, jeśli na to spojrzysz; wygląda na to, że możesz po prostu wytrząsnąć pierwszy rząd lub dwa lub trzy razy, aż nie pozostanie nic. (Wygląda na to, że w 1000 x 1000 wszystkie wiersze nie rosną? Chyba stąd pochodzi Twoja „część B”?)

Nie mogę wymyślić sposobu na obliczenie rzeczywistej liczby bez obliczenia kampanii bombardowania przy użyciu mojej najlepszej heurystyki i mam nadzieję, że uzyskam rozsądny wynik.

Więc moją metodą jest obliczenie wskaźnika wydajności bombardowania dla każdej komórki, zbombardowanie komórki o największej wartości, ... iteracja procesu, aż wszystko spłaszczę. Niektórzy opowiadają się za stosowaniem jako miernika prostej potencjalnej szkody (tj. Oceny od 0 do 9), ale nie wystarcza to, gdy uderzają komórki o wysokiej wartości i nie wykorzystują nakładających się uszkodzeń. Obliczę cell value - sum of all neighbouring cells, zresetuję każdy dodatni na 0 i użyję wartości bezwzględnej dowolnego ujemnego. Intuicyjnie ta metryka powinna dokonać wyboru, który pomoże zmaksymalizować nakładanie się obrażeń na komórki o dużej liczbie, zamiast bezpośredniego ich walenia.

Poniższy kod osiąga całkowite zniszczenie pola testowego w 28 bombach (zauważ, że użycie potencjalnego uszkodzenia jako miary daje 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();
    }           
  }
}

Wynikowy wzorzec bombardowania jest wyprowadzany w następujący sposób (wartości pola po lewej stronie, dane po prawej)

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

Można to rozwiązać za pomocą drzewa o głębokości O (3 ^ (n)). Gdzie n jest sumą wszystkich kwadratów.

Najpierw rozważ, że rozwiązanie problemu z drzewem O (9 ^ n) jest banalne, po prostu weź pod uwagę wszystkie możliwe lokalizacje bombardowań. Na przykład zobacz implementację Alfe .

Następnie zdaj sobie sprawę, że możemy pracować, aby bombardować od podstaw i nadal uzyskać minimalny wzór bombardowania.

1. Zacznij od lewego dolnego rogu.
2. Bombarduj go w zapomnienie jedynymi sensownymi grami (w górę i w prawo).
3. Przesuń jeden kwadrat w prawo.
4. Podczas gdy cel ma wartość większą niż zero, rozważ każdą z 2 sensownych rozgrywek (prosto w górę lub w górę i w prawo), zmniejsz wartość celu o jedną i utwórz nową gałąź dla każdej możliwości.
5. Przesuń inny w prawo.
6. Podczas gdy cel ma wartość większą niż zero, rozważ każdą z 3 sensownych rozgrywek (w górę w lewo, w górę i w górę w prawo), zmniejsz wartość celu o jeden i utwórz nową gałąź dla każdej możliwości.
7. Powtarzaj kroki 5 i 6, aż rząd zostanie wyeliminowany.
8. Przejdź w górę rzędu i powtarzaj kroki od 1 do 7, aż zagadka zostanie rozwiązana.

Ten algorytm jest poprawny, ponieważ

1. Konieczne jest wypełnienie każdego wiersza w pewnym momencie.
2. Wypełnienie rzędu zawsze wymaga gry albo powyżej, albo poniżej, lub w tym rzędzie.
3. Zawsze lepiej lub lepiej jest wybrać grę powyżej najniższego nieoczyszczonego rzędu niż grę w rzędzie lub poniżej tego rzędu.

W praktyce algorytm ten będzie regularnie działał lepiej niż teoretyczne maksimum, ponieważ regularnie bombarduje sąsiadów i zmniejsza rozmiar wyszukiwania. Jeśli założymy, że każde bombardowanie zmniejsza wartość 4 dodatkowych celów, wówczas nasz algorytm będzie działał w O (3 ^ (n / 4)) lub w przybliżeniu O (1,3 ^ n).

Ponieważ ten algorytm jest wciąż wykładniczy, rozsądnie byłoby ograniczyć głębokość wyszukiwania. Możemy ograniczyć liczbę rozgałęzień do pewnej liczby, X, a gdy jesteśmy już tak głęboko, zmuszamy algorytm do wyboru najlepszej ścieżki, którą do tej pory zidentyfikował (tej, która ma minimalną całkowitą sumę płyty w jednym ze swoich listek końcowych ). W takim przypadku nasz algorytm będzie działał w czasie O (3 ^ X), ale nie ma gwarancji uzyskania poprawnej odpowiedzi. Zawsze możemy jednak zwiększyć X i przetestować empirycznie, czy warto skorzystać z kompromisu między zwiększonym obliczeniem a lepszymi odpowiedziami.

funkcja oceny, suma całkowita:

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];
}

funkcja celu:

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;
}

funkcja zniszczenia:

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]--;
    }
}

funkcja celu:

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;
}

funkcja maksymalizacji liniowej:

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

Nie jest to optymalne, ale można je zoptymalizować poprzez znalezienie lepszej funkcji oceny.

.. ale myśląc o tym problemie, myślałem, że jednym z głównych problemów jest w pewnym momencie porzucenie liczb na środku zer, więc przyjmuję inne podejście .. którym jest dominacja minimalnych wartości do zera, a następnie spróbuj zera zerowe, jak to możliwe, co prowadzi do ogólnej minimalizacji minimalnych istniejących wartości lub podobnych

Cały ten problem sprowadza się do obliczenia odległości edycji. Wystarczy obliczyć wariant odległości Levenshteina między daną macierzą a macierzą zerową, w której zmiany są zastępowane bombardowaniem, za pomocą programowania dynamicznego do przechowywania odległości między macierzami pośrednimi. Sugeruję użycie skrótu macierzy jako klucza. W pseudo-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

To była odpowiedź na pierwsze zadane pytanie. Nie zauważyłem, że zmienił parametry.

Utwórz listę wszystkich celów. Przypisz wartość do celu na podstawie liczby dodatnich wartości, na które ma wpływ upuszczenie (sam i wszyscy sąsiedzi). Najwyższą wartością byłoby dziewięć.

Sortuj cele według liczby trafionych celów (Malejąco), z dodatkowym sortowaniem malejącym według sumy każdego trafionego celu.

Zrzuć bombę na najwyżej sklasyfikowany cel, a następnie ponownie oblicz cele i powtarzaj, aż wszystkie wartości będą równe zero.

Uzgodnione, nie zawsze jest to najbardziej optymalne. Na przykład,

100011
011100
011100
011100
000000
100011

Takie podejście wymagałoby usunięcia 5 bomb. Optymalnie jednak można to zrobić w 4. Nadal dość cholernie blisko i nie ma cofania się. W większości sytuacji będzie optymalna lub bardzo bliska.

Wykorzystując oryginalne numery problemów, podejście to rozwiązuje 28 bomb.

Dodanie kodu w celu zademonstrowania tego podejścia (za pomocą formularza z przyciskiem):

         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];
                        }

                    }
                }
            }
        }

    }

Klasa, której będziesz potrzebować:

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