Algoritma penjatuhan bom

212

Saya memiliki n x mmatriks yang terdiri dari bilangan bulat non-negatif. Sebagai contoh:

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

"Menjatuhkan bom" berkurang satu nomor sel target dan delapan tetangganya, ke minimum nol.

x x x 
x X x
x x x

Apa algoritma yang akan menentukan jumlah minimum bom yang diperlukan untuk mengurangi semua sel menjadi nol?

Opsi B (Karena saya tidak menjadi pembaca yang cermat)

Sebenarnya versi pertama masalah bukanlah yang saya cari jawabannya. Saya tidak hati-hati membaca seluruh tugas, ada kendala tambahan, katakanlah:

Bagaimana dengan masalah sederhana, ketika urutan berturut-turut harus tidak meningkat:

8 7 6 6 5 mungkin urutan input

7 8 5 5 2 tidak mungkin karena 7 -> 8 tumbuh secara berurutan.

Mungkin menemukan jawaban untuk kasus "lebih mudah" akan membantu dalam menemukan solusi untuk yang lebih sulit.

PS: Saya percaya bahwa ketika kita memiliki beberapa situasi yang sama membutuhkan bom minimum untuk membersihkan baris atas, kita memilih yang menggunakan sebagian besar bom di "sisi kiri" barisan. Masih ada bukti yang mungkin benar?

Kostek
sumber
4
Yah saya baru saja menemukan bahwa beberapa bidang dapat dilewati seperti pada contoh 2 3 1 5 Menjatuhkannya pada 2,3,1 tidak ada gunanya, karena menjatuhkannya menyebabkan beberapa kerusakan subset yang dapat kita sebabkan dengan menjatuhkan 5. Tapi tidak bisa temukan cara membuatnya bekerja secara global (jika itu cara yang benar). Kliring 2 membutuhkan penggunaan 2 bom yang dijatuhkan pada salah satu tetangga dan 5 berisi set kerusakan lain. Tapi kemudian saya tidak tahu apa yang harus dilakukan nanti karena ketika Anda menulis ulang (setelah menurun), maka Anda memiliki dua pilihan (tidak ada satu set kerusakan yang uber).
abc
23
Apakah NP-keras ini kebetulan? Tampaknya merupakan varian dari Masalah Cakupan Maksimum .
Mysticial
14
+1 untuk memberi saya sesuatu yang menarik untuk dipikirkan
Nick Mitchinson
3
@ Kostek, masalah hebat! Silakan kirim tautannya.
Kolonel Panic
5
mungkin Anda harus mengklarifikasi, Anda mengatakan pertanyaannya adalah: what's the minimum amount of bombs required to clean the board?Apakah ini berarti tidak perlu menemukan pola pemboman yang sebenarnya, tetapi hanya jumlah bom yang minimal?
Lie Ryan

Jawaban:

38

Ada cara untuk mengurangi ini menjadi sub-masalah sederhana.

Ada 2 bagian penjelasan, algoritma, dan alasan algoritma menyediakan solusi optimal. Yang pertama tidak akan masuk akal tanpa yang kedua, jadi saya akan mulai dengan alasannya.

Jika Anda berpikir untuk mengebom persegi panjang (asumsikan persegi panjang besar - belum ada kasus tepi), Anda dapat melihat bahwa satu-satunya cara untuk mengurangi persegi panjang berongga pada perimeter menjadi 0 adalah dengan membom baik perimeter atau mengebom persegi panjang berongga dari kotak di dalam perimeter. Saya akan memanggil lapisan perimeter 1, dan persegi panjang di dalamnya lapisan 2.

Wawasan penting adalah bahwa tidak ada titik bom lapisan 1, karena "radius ledakan" yang Anda dapatkan dari hal itu selalu terkandung dalam radius ledakan persegi lain dari lapisan 2. Anda harus dapat dengan mudah meyakinkan diri sendiri tentang hal ini.

Jadi, kita dapat mengurangi masalah untuk menemukan cara optimal untuk mengebom perimeter, lalu kita dapat mengulanginya sampai semua kotak adalah 0.

Tapi tentu saja, itu tidak akan selalu menemukan solusi optimal jika memungkinkan untuk mengebom perimeter dengan cara yang kurang optimal, tetapi dengan menggunakan X bom tambahan membuat masalah mengurangi lapisan dalam lebih mudah dengan bom> X. Jadi, jika kita menyebut permiter layer satu, jika kita menempatkan bom X tambahan di suatu tempat di layer 2 (tepat di dalam layer 1), dapatkah kita mengurangi upaya kemudian membom layer 2 lebih dari X? Dengan kata lain, kita harus membuktikan bahwa kita bisa rakus dalam mengurangi batas luar.

Tapi, kita tahu kita bisa serakah. Karena tidak ada bom di lapisan 2 yang bisa lebih efisien dalam mengurangi lapisan 2 menjadi 0 daripada bom yang ditempatkan secara strategis di lapisan 3. Dan untuk alasan yang sama seperti sebelumnya - selalu ada bom yang bisa kita tempatkan di lapisan 3 yang akan mempengaruhi setiap kotak. dari layer 2 yang ditempatkan bom di layer 2 bisa. Jadi, tidak ada salahnya kita menjadi tamak (dalam arti serakah).

Jadi, yang harus kita lakukan adalah menemukan cara optimal untuk mengurangi permiter menjadi 0 dengan mengebom lapisan dalam berikutnya.

Kita tidak pernah terluka dengan terlebih dahulu membom sudut ke 0, karena hanya sudut lapisan dalam yang dapat mencapainya, jadi kita benar-benar tidak punya pilihan (dan, setiap bom di perimeter yang dapat mencapai sudut memiliki radius ledakan yang terkandung di dalam radius ledakan dari sudut lapisan dalam).

Setelah kami melakukannya, kotak pada perimeter yang berdekatan dengan sudut 0 hanya dapat dicapai dengan 2 kotak dari lapisan dalam:

0       A       B

C       X       Y

D       Z

Pada titik ini perimeter secara efektif merupakan loop tertutup 1 dimensi, karena setiap bom akan mengurangi 3 kotak yang berdekatan. Kecuali untuk beberapa keanehan dekat sudut - X dapat "menekan" A, B, C, dan D.

Sekarang kita tidak dapat menggunakan trik radius ledakan - situasi setiap kotak simetris, kecuali untuk sudut-sudut aneh, dan bahkan tidak ada radius ledakan adalah subset dari yang lain. Perhatikan bahwa jika ini adalah garis (seperti yang dibahas Kolonel Panic) alih-alih loop tertutup solusinya adalah sepele. Titik akhir harus dikurangi menjadi 0, dan itu tidak pernah merugikan Anda untuk mengebom titik yang berdekatan dengan titik akhir, lagi karena jari-jari ledakan adalah superset. Setelah Anda membuat titik akhir 0, Anda masih memiliki titik akhir baru, jadi ulangi (sampai semua 0).

Jadi, jika kita dapat secara optimal mengurangi satu kotak di layer menjadi 0, kita memiliki algoritma (karena kita telah memotong lingkaran dan sekarang memiliki garis lurus dengan titik akhir). Saya percaya pemboman yang berdekatan dengan alun-alun dengan nilai terendah (memberi Anda 2 pilihan) sehingga nilai tertinggi dalam 2 kotak dari nilai terendah adalah minimum yang mungkin (Anda mungkin harus membagi pemboman Anda untuk mengelola ini) akan optimal tetapi saya belum (belum?) punya bukti.

psr
sumber
+1 - Saya akan menulis sesuatu yang serupa. Saya pikir Anda sudah mendapatkannya!
Rex Kerr
5
@ speaker, harap baca masalahnya dengan cermat. Mengebom sebuah kotak mengurangi kedelapan tetangganya, jadi asumsinya di sana sebenarnya benar.
darksky
20
But, we do know we can be greedy...- Saya tidak membeli ini. Pertimbangkan 1 1 2 1 1 2perimeter. Jumlah minimum bom adalah 4, tetapi ada tiga solusi berbeda. Setiap solusi memiliki dampak yang berbeda pada lapisan berikutnya. Selama ada beberapa solusi minimal untuk perimeter, Anda tidak bisa sepenuhnya mengisolasi perimeter tanpa mempertimbangkan lapisan dalam. Saya benar-benar tidak berpikir masalah ini dapat diselesaikan tanpa mundur.
user1354557
4
Saya sedang memikirkan solusi ini, tetapi terlihat sederhana. Memang benar, bahwa Anda dapat menjatuhkan bom di layer2 untuk membersihkan, layer1, tetapi jika ada beberapa solusi, mereka mempengaruhi solusi untuk lapisan yang lebih tinggi.
Luka Rahne
12
@psr: Ini tidak berfungsi. Metode pengeboman yang optimal untuk lapisan luar mungkin tidak optimal secara global. Contoh: 0011100 0100010 0000000 0000000 1110111. Cara optimal untuk mengebom lapisan pertama adalah dengan mengebom di tengah baris kedua, mengambil total tiga bom untuk membunuh lapisan luar. Tapi kemudian Anda perlu dua bom untuk merawat lapisan berikutnya. Optimal hanya membutuhkan empat bom total: dua untuk dua baris pertama dan dua untuk baris terakhir.
nneonneo
26

Pólya mengatakan, "Jika Anda tidak dapat memecahkan masalah, maka ada masalah yang lebih mudah yang bisa Anda pecahkan: temukan."

Masalah yang lebih sederhana jelas adalah masalah 1 dimensi (ketika grid adalah satu baris). Mari kita mulai dengan algoritma paling sederhana - dengan rakus membom target terbesar. Kapan ini salah?

Mengingat 1 1 1, algoritma serakah tidak peduli dengan sel yang dibomnya terlebih dahulu. Tentu saja, sel tengah lebih baik - itu nol ketiga sel sekaligus. Ini menyarankan algoritma baru A, "bom untuk meminimalkan jumlah yang tersisa". Kapan algoritma ini salah?

Diberikan 1 1 2 1 1, algoritma A tidak peduli antara pemboman sel ke-2, ke-3 atau ke-4. Tetapi mengebom sel ke-2 untuk pergi 0 0 1 1 1lebih baik daripada mengebom sel ke-3 untuk pergi1 0 1 0 1 . Bagaimana cara memperbaikinya? Masalah dengan pemboman sel ke-3 adalah ia membuat kita bekerja ke kiri dan bekerja ke kanan yang harus dilakukan secara terpisah.

Bagaimana dengan "bom untuk meminimalkan jumlah yang tersisa, tetapi maksimalkan minimum ke kiri (dari tempat kami dibom) ditambah minimum ke kanan". Sebut algoritma ini B. Kapan algoritma ini salah?


Sunting: Setelah membaca komentar, saya setuju masalah yang jauh lebih menarik adalah masalah satu dimensi diubah sehingga ujungnya bergabung. Ingin melihat kemajuan apa pun tentang itu.

Kolonel Panic
sumber
40
Saya tidak yakin mengapa jawaban ini mendapatkan begitu banyak upvotes - kasus 1D hampir sepele, selalu mengebom elemen di sebelah kanan elemen positif pertama. Ini berfungsi karena selalu ada tepat satu cara optimal untuk mengebom elemen apa pun yang hanya berisi 0 di sebelah kirinya. Ini dapat diperluas ke 2D untuk secara optimal menghapus kotak sudut, tapi saya tidak melihat cara yang jelas untuk memperpanjangnya di luar itu ...?
BlueRaja - Danny Pflughoeft
3
@BueueRaja, saya membenarkan karena jelas menggambarkan bahwa pendekatan serakah yang dibahas dalam jawaban lain tidak cukup (setidaknya, perlu ditambah dengan kriteria tambahan). Beberapa pilihan target, bahkan jika mereka menghasilkan pengurangan yang sama dalam jumlah total, dapat membuat hal-hal lebih menyebar daripada yang lain. Saya pikir ini adalah wawasan yang berguna untuk masalah 2D.
Tim Goodman
3
Dan secara umum "Jika Anda terjebak pada case 2D, coba case 1D terlebih dahulu" adalah saran yang bagus.
Tim Goodman
21
@Tim: "'coba kasus 1D dulu' adalah saran yang bagus" Ya itu, yang akan membuatnya menjadi komentar yang sangat baik; tapi itu bukan jawaban ...
BlueRaja - Danny Pflughoeft
3
Saya pikir Anda memiliki poin yang baik bahwa kasus 1D mungkin agak menyesatkan di sini karena memiliki solusi sederhana yang tidak siap meluas ke dimensi yang lebih tinggi. Saya pikir kasus 1D dengan kondisi batas periodik (bungkus sekitar kasus) mungkin lebih baik.
Tim Goodman
12

Saya harus berhenti hanya pada solusi parsial karena saya kehabisan waktu, tetapi semoga solusi parsial ini memberikan beberapa wawasan tentang satu pendekatan potensial untuk menyelesaikan masalah ini.

Ketika dihadapkan dengan masalah yang sulit, saya suka memunculkan masalah yang lebih sederhana untuk mengembangkan intuisi tentang ruang masalah. Di sini, langkah pertama yang saya ambil adalah mengurangi masalah 2-D ini menjadi masalah 1-D. Pertimbangkan satu baris:

0 4 2 1 3 0 1

Entah bagaimana atau lain, Anda tahu Anda perlu mengebom di atau sekitar 4tempat 4 kali untuk turun ke 0. Karena kiri tempat itu adalah angka yang lebih rendah, tidak ada manfaatnya untuk mengebom 0atau 4membom yang berlebihan 2. Bahkan, saya percaya (tetapi tidak memiliki bukti yang kuat) bahwa pemboman 2sampai4 titik turun menjadi setidaknya sama baiknya dengan strategi lain untuk mendapatkan yang 4ke 0. Seseorang dapat melanjutkan ke garis kiri ke kanan dalam strategi seperti ini:

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

Beberapa contoh pesanan pemboman:

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

Gagasan untuk memulai dengan angka yang perlu diturunkan dengan cara tertentu adalah ide yang menarik karena tiba-tiba menjadi mungkin untuk menemukan solusi yang oleh beberapa orang mengklaim setidaknya sama baiknya. dengan semua solusi lainnya.

Langkah selanjutnya dalam kompleksitas di mana pencarian ini setidaknya sama baiknya masih layak ada di ujung papan. Jelas bagi saya bahwa tidak pernah ada manfaat ketat untuk membom tepi luar; Anda lebih baik membom tempat satu dan mendapatkan tiga ruang lainnya secara gratis. Dengan ini, kita dapat mengatakan bahwa membom cincin yang ada di dalam tepi setidaknya sama baiknya dengan membom tepi. Selain itu, kita dapat menggabungkan ini dengan intuisi bahwa mengebom yang tepat di dalam tepi sebenarnya adalah satu-satunya cara untuk mendapatkan ruang tepi ke 0. Bahkan lebih mudah untuk mengetahui strategi yang optimal (dalam hal ini adalah pada paling tidak sebagus strategi lainnya) untuk mendapatkan angka sudut menjadi 0. Kami menggabungkan semua ini dan bisa lebih dekat dengan solusi dalam ruang 2-D.

Mengingat pengamatan tentang potongan sudut, kita dapat mengatakan dengan pasti bahwa kita tahu strategi optimal untuk beralih dari papan awal ke papan dengan nol di semua sudut. Ini adalah contoh dari papan seperti itu (saya meminjam angka dari dua papan linear di atas). Saya telah memberi label beberapa spasi secara berbeda, dan saya akan menjelaskan alasannya.

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

Satu akan melihat pada baris atas benar-benar mirip dengan contoh linear kita lihat sebelumnya. Ingat pengamatan kami sebelumnya bahwa cara optimal untuk mendapatkan baris atas semua ke 0 adalah dengan mengebom baris kedua ( xbaris). Tidak ada cara untuk menghapus baris atas dengan mengebom salah satu ybaris dan tidak ada manfaat tambahan untuk membom baris atas daripada membom ruang yang sesuai pada xbaris.

Kita bisa menerapkan strategi linier dari atas (mengebom ruang-ruang yang sesuai pada xbaris), mengenai diri kita hanya dengan baris atas dan tidak ada yang lain. Ini akan seperti ini:

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

Kelemahan dalam pendekatan ini menjadi sangat jelas dalam dua pemboman terakhir. Jelas, mengingat bahwa satu-satunya situs bom yang mengurangi 4angka di kolom pertama di baris kedua adalah yang pertama xdan yang y. Dua pemboman terakhir jelas lebih rendah daripada hanya membom yang pertama x, yang akan melakukan hal yang sama persis (berkenaan dengan tempat pertama di baris atas, yang kita tidak punya cara lain untuk membersihkan). Karena kami telah menunjukkan bahwa strategi kami saat ini adalah suboptimal, modifikasi dalam strategi jelas diperlukan.

Pada titik ini, saya dapat mengambil langkah mundur dalam kompleksitas dan fokus hanya satu sudut. Mari kita pertimbangkan yang ini:

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

Hal ini jelas satu-satunya cara untuk mendapatkan ruang dengan 4turun ke nol adalah untuk mengebom beberapa kombinasi dari x, y, dan z. Dengan beberapa akrobat di pikiran saya, saya cukup yakin solusi optimal untuk mengebom xtiga kali dan akemudian b. Sekarang adalah masalah mencari tahu bagaimana saya mencapai solusi itu dan jika itu mengungkapkan intuisi yang dapat kita gunakan untuk menyelesaikan masalah lokal ini. Saya perhatikan bahwa tidak ada pemboman ydan zruang. Mencoba menemukan sudut tempat pemboman ruang-ruang itu masuk akal menghasilkan sudut yang terlihat seperti ini:

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

Untuk yang ini, jelas bagi saya bahwa solusi optimal adalah mengebom y5 kali dan z5 kali. Mari kita melangkah lebih jauh.

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

Di sini, rasanya sama intuitifnya bahwa solusi optimal adalah mengebom adan b6 kali dan kemudian x4 kali.

Sekarang ini menjadi permainan bagaimana mengubah intuisi menjadi prinsip-prinsip yang bisa kita bangun.

Semoga bisa dilanjutkan!

Steven Xu
sumber
10

Untuk pertanyaan yang diperbarui, algoritma serakah sederhana memberikan hasil yang optimal.

Jatuhkan bom [0,0] ke sel A [1,1], lalu jatuhkan bom [1,0] ke sel A [2,1], dan lanjutkan proses ini ke bawah. Untuk membersihkan sudut kiri bawah, jatuhkan bom max (A [N-1,0], A [N-2,0], A [N-3,0]) ke sel A [N-2,1]. Ini akan sepenuhnya membersihkan 3 kolom pertama.

Dengan pendekatan yang sama membersihkan kolom 3,4,5, lalu kolom 6,7,8, dll.

Sayangnya ini tidak membantu menemukan solusi untuk masalah awal.


Masalah "Lebih besar" (tanpa kendala "non-peningkatan") dapat terbukti NP-hard. Berikut ini sketsa bukti.

Misalkan kita memiliki grafik planar derajat hingga 3. Mari kita temukan penutup simpul minimum untuk grafik ini. Menurut artikel Wikipedia masalah ini adalah NP-hard untuk grafik planar derajat hingga 3. Ini bisa dibuktikan dengan pengurangan dari Planar 3SAT. Dan kekerasan Planar 3SAT - dengan pengurangan dari 3SAT. Kedua bukti ini disajikan dalam kuliah baru-baru ini di "Batas Bawah Algoritma" oleh Prof. Erik Demaine (kuliah 7 dan 9).

Jika kita membagi beberapa tepi grafik asli (grafik kiri pada diagram), masing-masing dengan jumlah genap genap, grafik yang dihasilkan (grafik kanan pada diagram) harus persis sama dengan penutup simpul minimum untuk simpul asli. Transformasi semacam itu memungkinkan untuk menyelaraskan simpul grafik ke posisi acak di grid.

masukkan deskripsi gambar di sini

Jika kita menempatkan simpul grafik hanya pada baris dan kolom yang rata (sedemikian rupa sehingga tidak ada dua sisi yang timbul pada satu titik membentuk sudut akut), masukkan "yang" di mana pun ada tepi, dan masukkan "nol" ke posisi grid lainnya, kita bisa menggunakan solusi apa pun untuk masalah awal untuk menemukan penutup vertex minimum.

Evgeny Kluev
sumber
Dari mana datangnya grafik dari kiri? Maaf, saya tidak begitu mengerti penjelasan Anda!
ryyst
1
@ryyst: grafik dari kiri hanyalah contoh grafik planar. Ini digunakan untuk mendemonstrasikan bagaimana mengubah grafik planar derajat hingga 4 ke grafik grid-aligned dan kemudian ke matriks n * m. Algoritma "menjatuhkan bom" yang diterapkan pada matriks ini akan menyelesaikan masalah penutup simpul untuk grafik yang diubah ini dan oleh karena itu untuk grafik "kiri" itu.
Evgeny Kluev
Ah, saya mengerti sekarang, dan saya percaya transformasi Anda benar. Terima kasih!
ryyst
@ EvgenyKluev, saya pikir sekarang Anda perlu membuktikan bahwa penutup simpul masih NP-keras untuk "grafik planar derajat hingga 4".
Shahbaz
@ Shahbaz: Saya khawatir bukti ini akan terlalu panjang. Jadi saya menambahkan tautan ke buktinya.
Evgeny Kluev
9

Anda dapat mewakili masalah ini sebagai masalah pemrograman bilangan bulat . (ini hanyalah salah satu solusi yang mungkin untuk mendekati masalah ini)

Memiliki poin:

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

kita dapat menulis 16 persamaan di mana untuk titik f misalnya berlaku

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

diminimalkan atas jumlah semua indeks dan solusi integer.

Solusi tentu saja jumlah dari indeks ini.

Ini dapat lebih disederhanakan dengan menetapkan semua xi pada batas 0, sehingga Anda akhirnya memiliki 4 + 1 persamaan dalam contoh ini.

Masalahnya adalah tidak ada algoritme sepele untuk menyelesaikan masalah tersebut. Saya tidak ahli dalam hal ini, tetapi menyelesaikan masalah ini karena pemrograman linier adalah NP yang sulit.

Luka Rahne
sumber
8
Semua masalah dalam NP dapat dirumuskan sebagai masalah pemrograman bilangan bulat, jadi ini tidak sangat membantu, kecuali kita sudah tahu bahwa masalahnya adalah NP-Lengkap
BlueRaja - Danny Pflughoeft
1
Saya setuju. Juga tidak perlu mengetahui langkah-langkah tepat yang harus dilakukan untuk mengetahui solusi apa.
Luka Rahne
1
Saat Anda menetapkan batas ke 0, jumlah ketidaksetaraan masih 16.
darksky
9

Ini adalah jawaban parsial, saya mencoba menemukan batas bawah dan batas atas yang bisa menjadi jumlah bom yang mungkin.

Dalam papan 3x3 dan lebih kecil, solusinya selalu sel bernomor terbesar.

Pada papan yang lebih besar dari 4x4, batas bawah jelas pertama adalah jumlah sudut:

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

Bagaimanapun Anda mengatur bom, tidak mungkin untuk menghapus papan 4x4 ini dengan kurang dari 2 + 1 + 6 + 4 = 13 bom.

Telah disebutkan dalam jawaban lain bahwa menempatkan bom pada sudut kedua ke ujung untuk menghilangkan sudut tidak pernah lebih buruk daripada menempatkan bom pada sudut itu sendiri, oleh karena itu diberikan papan:

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

Kita dapat membidik sudut dengan menempatkan bom di sudut kedua untuk memberikan papan baru:

 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

Sejauh ini baik. Kami membutuhkan 13 bom untuk membersihkan sudut.

Sekarang perhatikan angka 6, 4, 3, dan 2 yang ditandai di bawah ini:

 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

Tidak ada cara untuk membom dua orang sel itu menggunakan bom tunggal, sehingga bom minimum telah meningkat sebesar 6 + 4 + 3 + 2, jadi menambah jumlah bom yang kami gunakan untuk membersihkan sudut, kami mendapatkan minimum jumlah bom yang dibutuhkan untuk peta ini telah menjadi 28 bom. Tidak mungkin untuk menghapus peta ini dengan kurang dari 28 bom, ini adalah batas bawah untuk peta ini.

Anda dapat menggunakan algoritma serakah untuk membangun batas atas. Jawaban lain menunjukkan bahwa algoritma serakah menghasilkan solusi yang menggunakan 28 bom. Karena kami telah membuktikan sebelumnya bahwa tidak ada solusi optimal yang dapat memiliki kurang dari 28 bom, oleh karena itu 28 bom memang merupakan solusi optimal.

Ketika serakah dan metode untuk menemukan batas minimal yang saya sebutkan di atas tidak menyatu, saya kira Anda harus kembali memeriksa semua kombinasi.

Algoritma untuk menemukan batas bawah adalah sebagai berikut:

  1. Pilih elemen dengan jumlah tertinggi, beri nama P.
  2. Tandai semua sel yang berjarak dua langkah dari P dan P itu sendiri sebagai tidak dapat dipilih.
  3. Tambahkan P ke minimumsdaftar.
  4. Ulangi ke langkah 1 sampai semua sel tidak dapat dipangkas.
  5. Jumlahkan minimumsdaftar untuk mendapatkan batas bawah.
Lie Ryan
sumber
9

Ini akan menjadi pendekatan serakah:

  1. Hitung matriks "skor" dari urutan n X m, di mana skor [i] [j] adalah total pengurangan poin dalam matriks jika posisi (i, j) dibom. (Skor maksimum poin adalah 9 dan skor min adalah 0)

  2. Memindahkan baris dengan bijak, temukan dan pilih posisi pertama dengan skor tertinggi (katakan (i, j)).

  3. Bom (i, j). Tingkatkan jumlah bom.

  4. Jika semua elemen dari matriks asli tidak nol, maka kebagian 1.

Saya ragu bahwa ini adalah solusi optimal.

Edit:

Pendekatan Greedy yang saya posting di atas, ketika berhasil, kemungkinan besar tidak memberi kami solusi optimal. Jadi saya pikir harus menambahkan beberapa elemen DP ke dalamnya.

Saya pikir kita dapat menyetujui bahwa pada suatu titik waktu, salah satu posisi dengan "skor" tertinggi (skor [i] [j] = total pengurangan poin jika (i, j) dibom) harus ditargetkan. Dimulai dengan asumsi ini, inilah pendekatan baru:

NumOfBombs (L): (mengembalikan jumlah minimum pemboman yang diperlukan)

  1. Diberikan Matriks M dari pesanan dan Xm. Jika semua elemen M adalah nol, maka kembalikan 0.

  2. Hitung matriks "skor" M.

    Biarkan k posisi berbeda P1, P2, ... Pk (1 <= k <= n * m), jadilah posisi dalam M dengan skor tertinggi.

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

    di mana M1, M2, ..., Mk adalah matriks yang dihasilkan jika kita mengebom posisi masing-masing P1, P2, ..., Pk.

Selain itu, jika kita ingin urutan posisi untuk nuklir di samping ini, kita harus melacak hasil "min".

SidR
sumber
3
Saya ingin tahu apakah menetapkan skor sebagai jumlah nilai saat ini akan menghasilkan hasil yang lebih baik. Itu pada dasarnya akan meratakan tanah lebih efisien.
Eugene
@Eugene: Poin yang sangat menarik. Saya tidak dapat memikirkan alasan mengapa cara Anda tidak seharusnya menghasilkan hasil yang lebih baik ...
SidR
@Eugene: Mungkin jumlah nilai saat ini di sekitarnya dapat digunakan untuk ukuran "prioritas"? Nuke node dengan skor tertinggi dan prioritas tertinggi ..
SidR
Baca saja jawaban ini, saya pikir ini mirip dengan jawaban kedua yang baru saja saya posting (mungkin dijabarkan lebih dalam jawaban saya). Saya pikir itu akan optimal jika selalu ada ruang tunggal dengan skor maksimal, karena Anda akan dijamin bahwa setiap pengeboman memiliki pengaruh terbesar yang mungkin terjadi. The rangka pemboman tidak peduli, jadi pergi dengan satu yang terbaik di setiap langkah harus optimal. Tetapi karena mungkin ada ikatan untuk "terbaik", mungkin untuk solusi optimal Anda harus mundur dan mencoba keduanya ketika ada dasi.
Tim Goodman
1
@Eugene, mungkin saya tidak mengikuti Anda. Apa perbedaan antara reduksi terbesar, dan jumlah terkecil dari semua nilai yang tersisa? Jumlah nilai yang tersisa (setelah pemboman) hanyalah nilai total saat ini dikurangi pengurangan dari pemboman ruang itu, jadi bukankah ini setara?
Tim Goodman
8

Masalah baru Anda , dengan nilai nececreasing di seluruh baris, cukup mudah untuk dipecahkan.

Perhatikan bahwa kolom kiri berisi angka tertinggi. Oleh karena itu, setiap solusi optimal harus terlebih dahulu mengurangi kolom ini menjadi nol. Jadi, kita bisa melakukan pemboman 1-D di kolom ini, mengurangi setiap elemen di dalamnya menjadi nol. Kami membiarkan bom jatuh di kolom kedua sehingga mereka melakukan kerusakan maksimum. Ada banyak posting di sini yang berhubungan dengan case 1D, saya pikir, jadi saya merasa aman dalam melewatkan case itu. (Jika Anda ingin saya menggambarkannya, saya bisa.) Karena properti yang menurun, tiga kolom paling kiri akan dikurangi menjadi nol. Tapi, kami terbukti akan menggunakan jumlah minimum bom di sini karena kolom kiri harus di-zeroed.

Sekarang, setelah kolom kiri memusatkan perhatian, kita hanya memotong tiga kolom paling kiri yang sekarang memusatkan perhatian dan mengulangi dengan matriks yang sekarang dikurangi. Ini harus memberi kita solusi optimal karena pada setiap tahap kita menggunakan jumlah bom minimum yang bisa dibuktikan.

nneonneo
sumber
Saya mengerti. Saya memikirkan ide serupa. : S Lain kali saya akan membaca lebih cermat. Tetapi berkat itu banyak orang memiliki 'masalah' yang bagus untuk diselesaikan.
abc
4

Mathematica Integer Linear Programming menggunakan cabang-dan-terikat

Seperti yang telah disebutkan, masalah ini dapat dipecahkan menggunakan integer linear programming (yang NP-Hard ). Mathematica sudah memiliki ILP bawaan. "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."[Lihat Optimalisasi Terkini Tutorial Terkini di Matematika].

Saya telah menulis kode berikut yang menggunakan perpustakaan ILP dari Mathematica. Ini sangat cepat.

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

Untuk contoh yang diberikan dalam masalah:

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]

Keluaran

masukkan deskripsi gambar di sini

Bagi siapa pun yang membaca ini dengan algoritma serakah

Coba kode Anda pada masalah 10x10 berikut:

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

Ini dia dipisahkan koma:

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

Untuk masalah ini, solusi saya mengandung 208 bom. Inilah solusi yang mungkin (saya bisa menyelesaikan ini dalam waktu sekitar 12 detik).

masukkan deskripsi gambar di sini

Sebagai cara untuk menguji hasil yang dihasilkan Mathematica, lihat apakah algoritma serakah Anda bisa lebih baik.

rev darksky
sumber
Saya dapat melakukannya di 219 dengan jawaban ini: stackoverflow.com/questions/15300149/bomb-dropping-algorithm/...
Anthony Queen
3

Tidak perlu mengubah masalah menjadi sub-masalah linier.

Alih-alih menggunakan heuristik serakah sederhana, yaitu untuk mengebom sudut , dimulai dengan yang terbesar.

Dalam contoh yang diberikan ada empat sudut, {2, 1, 6, 4}. Untuk setiap sudut tidak ada langkah yang lebih baik daripada membom sel diagonal ke sudut, jadi kita tahu pasti 2 + 1 + 6 + 4 = 13 bom pertama kita harus dalam sel diagonal ini. Setelah melakukan pengeboman kita dibiarkan dengan matriks baru:

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 

Setelah 13 pemboman pertama kami menggunakan heuristik untuk menghilangkan 3 0 2 melalui tiga pemboman. Sekarang, kita memiliki 2 sudut baru, {2, 1} di baris ke-4. Kami mengebom itu, 3 pemboman lainnya. Kami telah mengurangi matriks menjadi 4 x 4 sekarang. Ada satu sudut, kiri atas. Kami mengebom itu. Sekarang kita memiliki 2 sudut tersisa, {5, 3}. Karena 5 adalah sudut terbesar kami mengebom yang pertama, 5 pemboman, lalu akhirnya membom 3 di sudut lainnya. Totalnya adalah 13 + 3 + 3 + 1 + 5 + 3 = 28.

Tyler Durden
sumber
1
Saya tidak mengerti apa yang Anda lakukan dalam kasus umum setelah sudut pemboman
RiaD
Membom sudut tidak pernah lebih efektif daripada membom secara diagonal ke dalam dari sudut.
psr
1
psr Anda salah paham posting saya, saya sedang melakukan pengeboman secara diagonal dari sudut, membaca ulang posting
Tyler Durden
11
@ TylerDurden: ini hanya berfungsi karena matriksnya kecil. Pada matriks yang lebih besar, setelah membom sudut, Anda biasanya tidak dapat memotong ujungnya lagi.
Lie Ryan
3

Ini melakukan pencarian luas untuk jalur terpendek (serangkaian pemboman) melalui "labirin" posisi ini. Tidak, saya tidak dapat membuktikan bahwa tidak ada algoritma yang lebih cepat, maaf.

#!/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))
Alfe
sumber
1
Algoritma ini akan menemukan jumlah gerakan paling sedikit, tetapi bisa memakan waktu yang sangat lama. Sudahkah Anda menjalankan ini pada set data yang diberikan? Itu akan memberikan dasar untuk algoritma lain untuk dibandingkan.
Ryan Amos
1
Subset 5x4 dari matriks yang diberikan diselesaikan dalam waktu sekitar 2 detik, 5x5 sudah memakan waktu lebih dari 2 menit. Saya belum mencoba lagi ;-) Ya, algoritma ini tidak dioptimalkan untuk apa pun kecuali tugas asli: Temukan solusi terpendek.
Alfe
2
Begitulah keindahan kompleksitas eksponensial.
Ryan Amos
3

Tampaknya pendekatan pemrograman linier bisa sangat membantu di sini.

Mari P m xn menjadi matriks dengan nilai-nilai posisi:

Matriks posisi

Sekarang mari kita mendefinisikan matriks bom B (x, y) mxn , dengan 1 ≤ x ≤ m , 1 ≤ y ≤ n seperti di bawah ini

Matriks bom

sedemikian rupa itu

Nilai posisi dalam matriks bom

Sebagai contoh:

B (3, 3)

Jadi kita mencari untuk matriks B m xn = [ b ij ] yang

  1. Dapat didefinisikan sebagai jumlah matriks bom:

    B sebagai jumlah matriks bom

    ( q ij akan maka jumlah bom kita akan turun di posisi p ij )

  2. p ij - b ij ≤ 0 (lebih succint, mari kita katakan sebagai P - B ≤ 0 )

Juga, B harus meminimalkan jumlahnya jumlah bom.

Kita juga bisa menulis B sebagai matriks jelek di depan:

B sebagai matriks jumlah kuantitas

dan karena P - B ≤ 0 (yang berarti P ≤ B ) kami memiliki sistem ketimpangan linear yang cukup berikut di bawah ini:

Hubungan antara jumlah bom dijatuhkan dan nilai di posisi

Sedang q mn x 1 didefinisikan sebagai

Vektor kuantitas

p mn x 1 didefinisikan sebagai

Nilai P didistribusikan sebagai vektor

Kita dapat mengatakan bahwa kita memiliki sistem . Sistem di bawah ini direpresentasikan sebagai produk dari matriks http://latex.codecogs.com/gif.download?S%5Cmathbf%7Bq%7D&space;%5Cge&space;%5Cmathbf%7Bp%7D menjadi S mn x M N matriks yang akan dibalik untuk menyelesaikan sistem. Saya tidak mengembangkannya sendiri tetapi saya percaya seharusnya mudah melakukannya dalam kode.

Sekarang, kami memiliki masalah minimum yang dapat dinyatakan sebagai

Sistem yang harus kita pecahkan

Saya percaya ini adalah sesuatu yang mudah, hampir sepele untuk diselesaikan dengan sesuatu seperti algoritma simpleks (ada dokumen yang agak keren tentang hal ini ). Namun, saya tahu hampir tidak ada pemrograman linier (saya akan mengambil kursus tentang hal itu di Coursera tetapi hanya di masa depan ...), saya memiliki beberapa sakit kepala yang mencoba memahaminya dan saya memiliki pekerjaan lepas yang sangat besar untuk diselesaikan sehingga saya menyerah saja di sini. Hal ini dapat bahwa saya melakukan sesuatu yang salah di beberapa titik, atau bahwa hal itu tidak bisa pergi lebih jauh, tapi saya percaya jalan ini akhirnya dapat menyebabkan para solusi. Bagaimanapun, saya ingin sekali atas tanggapan Anda.

(Terima kasih khusus untuk situs luar biasa ini untuk membuat gambar dari ekspresi LaTeX )

brandizzi
sumber
Apakah Anda yakin ketidaksetaraan Anda tidak terbalik? Itu Sq> = P? yaitu, jumlah total kali sebuah kotak dibom lebih besar dari atau sama dengan matriks yang diberikan.
darksky
1
Ketika variabel dari program linier dibatasi ke integer, kami menyebutnya "integer linear programming" (IP). Berbeda dengan kasus kontinu, IP adalah NP-Lengkap. Sayangnya, algoritma simpleks tidak membantu, kecuali jika aproksimasi dapat diterima. Dan IP telah disebutkan dalam jawaban lain .
BlueRaja - Danny Pflughoeft
@ BlueRaja-DannyPflughoeft benar. "Despite the many crucial applications of this problem, and intense interest by researchers, no efficient algorithm is known for it.lihat halaman 254. Integer linear programming adalah masalah komputasi yang sangat sulit. Satu-satunya harapan kami untuk menjadi efisien adalah dengan mengeksploitasi properti intrinsik tentang matriks S. Anda, tidak semena - mena.
darksky
3

Solusi serakah ini tampaknya benar :

Seperti yang ditunjukkan dalam komentar, itu akan gagal dalam 2D. Tapi mungkin Anda bisa memperbaikinya.

Untuk 1D:
Jika setidaknya ada 2 angka, Anda tidak perlu menembak ke yang paling kiri karena menembak ke yang kedua tidak lebih buruk . Jadi tembak ke yang kedua, sedangkan yang pertama bukan 0, karena Anda harus melakukannya. Pindah ke sel berikutnya. Jangan lupa tentang sel terakhir.

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

Jadi untuk 2D:
Lagi: Anda tidak perlu memotret di baris pertama (jika ada yang kedua). Jadi tembak ke yang kedua. Selesaikan tugas 1D untuk baris pertama. (karena Anda harus membuatnya nol). Turun. Jangan lupa baris terakhir.

RiaD
sumber
5
A-balik: "0110","1110","1110". Anda hanya perlu 1 tembakan, tapi saya yakin algoritma Anda akan menggunakan 2.
maniek
2

Untuk meminimalkan jumlah bom, kita harus memaksimalkan efek setiap bom. Untuk mencapai ini, pada setiap langkah kita harus memilih target terbaik. Untuk setiap titik penjumlahan dan delapan tetangganya - dapat digunakan sebagai jumlah efisiensi pemboman titik ini. Ini akan memberikan urutan bom yang mendekati optimal.

UPD : Kita juga harus memperhitungkan angka nol, karena bom itu tidak efisien. Sebenarnya masalahnya adalah untuk meminimalkan jumlah nol yang dipukul. Tetapi kita tidak bisa tahu bagaimana langkah apa pun membuat kita lebih dekat dengan tujuan ini. Saya setuju dengan gagasan bahwa masalahnya adalah NP-complete. Saya menyarankan pendekatan serakah, yang akan memberikan jawaban mendekati nyata.

Noofiz
sumber
Ini tidak optimal. Counter-contoh: 1010101, 0010100(baris atas, baris bawah) Pendekatan Anda akan membutuhkan 3. Hal ini dapat dilakukan dalam 2.
Mysticial
2

Saya percaya bahwa untuk meminimalkan jumlah bom, Anda hanya perlu memaksimalkan jumlah kerusakan .. untuk itu perlu memeriksa area yang memiliki kekuatan terkuat .. jadi pertama-tama Anda menganalisis lapangan dengan kernel 3x3 dan memeriksa di mana jumlahnya lebih kuat .. dan bom di sana .. dan lakukan sampai bidangnya rata .. untuk ini diajukan jawabannya adalah 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');
CaldasGSM
sumber
Ini adalah algoritma yang sama dengan beberapa jawaban yang lain, tetapi jauh di kemudian hari.
psr
@psr Tidak hanya itu. Itu tidak optimal.
Mysticial
Saya mempostingnya, karena, sementara algoritma ini diusulkan, saya tidak menemukan kode atau "konsep konsep". jadi saya pikir ini bisa membantu pemecahan .. tapi .. btw @Mysticial Anda punya prof bahwa ada cara yang lebih optimal?
CaldasGSM
@CaldasGSM Jangan khawatir, masalah asli (tanpa urutan) sulit. Sejauh ini hanya ada satu jawaban yang menyelesaikannya secara optimal, tetapi berjalan dalam waktu yang eksponensial.
Mysticial
2

Berikut adalah solusi yang menggeneralisasi properti sudut yang baik.

Mari kita asumsikan bahwa kita bisa menemukan titik drop yang sempurna untuk bidang yang diberikan, yaitu, cara terbaik untuk mengurangi nilai di dalamnya. Kemudian untuk menemukan jumlah minimum bom yang akan dijatuhkan, konsep pertama dari suatu algoritma bisa jadi (kode disalin dari implementasi 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

Tantangannya adalah choose_a_perfect_drop_point. Pertama, mari kita tentukan apa itu drop point yang sempurna.

  • Sebuah titik penurunan untuk (x, y)menurunkan nilai dalam (x, y). Ini juga dapat menurunkan nilai di sel lain.
  • Penurunan titik yang selama (x, y)ini lebih baik daripada penurunan titik b untuk (x, y)jika mengurangi nilai dalam sebuah superset yang tepat dari sel-sel yang b berkurang.
  • Drop point maksimal jika tidak ada drop point lain yang lebih baik.
  • Dua drop point untuk (x, y)are setara jika mereka menurunkan set yang sama sel.
  • Sebuah titik drop untuk (x, y)adalah sempurna jika itu adalah setara dengan semua titik penurunan maksimal untuk (x, y).

Jika ada drop point sempurna untuk (x, y), Anda tidak dapat mengurangi nilainya dengan (x, y)lebih efektif daripada menjatuhkan bom pada salah satu drop point sempurna untuk (x, y).

Titik drop sempurna untuk bidang yang diberikan adalah titik drop sempurna untuk setiap selnya.

Berikut ini beberapa contoh:

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

Titik drop sempurna untuk sel (0, 0)(indeks berbasis nol) adalah (1, 1). Semua poin penurunan lainnya untuk (1, 1), yaitu (0, 0), (0, 1), dan (1, 0), menurunkan sel-sel kurang.

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

Titik penurunan sempurna untuk sel (2, 2)(indeks berbasis-nol) adalah (2, 2), dan juga semua sel sekitarnya (1, 1), (1, 2), (1, 3), (2, 1), (2, 3), (3, 1), (3, 2), dan (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

titik drop yang sempurna untuk sel (2, 2)adalah (3, 1): Mengurangi nilai dalam (2, 2), dan nilai dalam (4, 0). Semua drop point (2, 2)lainnya tidak maksimal, karena berkurang satu sel lebih sedikit. Titik drop sempurna untuk (2, 2)juga titik drop sempurna untuk (4, 0), dan itu adalah satu-satunya titik drop sempurna untuk lapangan. Ini mengarah ke solusi sempurna untuk bidang ini (satu tetes bom).

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

Tidak ada titik drop sempurna untuk (2, 2): Keduanya (1, 1)dan (1, 3)penurunan (2, 2)dan sel lain (mereka adalah titik drop maksimal (2, 2)), tetapi mereka tidak setara. Namun, (1, 1)adalah titik drop yang sempurna untuk (0, 0), dan(1, 3) merupakan titik drop sempurna untuk (0, 4).

Dengan definisi titik jatuh sempurna dan urutan cek tertentu, saya mendapatkan hasil berikut untuk contoh dalam pertanyaan:

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

Namun, algoritme hanya berfungsi jika setidaknya ada satu titik jatuh sempurna setelah setiap langkah. Dimungkinkan untuk membuat contoh di mana tidak ada titik drop yang sempurna:

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

Untuk kasus-kasus ini, kami dapat memodifikasi algoritme sehingga alih-alih titik drop yang sempurna, kami memilih koordinat dengan pilihan minimal titik jatuh maksimal, lalu menghitung minimum untuk setiap pilihan. Dalam kasus di atas, semua sel dengan nilai memiliki dua titik jatuh maksimal. Misalnya, (0, 1)memiliki drop point maksimal (1, 1)dan (1, 2). Memilih salah satu dan kemudian menghitung lead minimum untuk hasil ini:

Drop bomb on 1, 1
Drop bomb on 2, 2
Drop bomb on 1, 2
Drop bomb on 2, 1
2
Tammo Freese
sumber
Ini cukup banyak algoritma serakah yang disajikan di atas.
darksky
Yah, itu adalah algoritma serakah juga, tetapi alih-alih fokus pada sudut dan tepi, saya mendefinisikan cara memilih titik drop berikutnya. Dengan contoh kuadrat 5x7, mudah untuk berbicara tentang sudut, pada bidang 1000x1000, tidak terlalu banyak. Jika Anda memeriksa urutan algoritme saya membersihkan bidang, itu bukan dari luar masuk, tetapi atas-ke-bawah / kiri-ke-kanan.
Tammo Freese
2

Ini ide lain:

Mari kita mulai dengan memberi bobot pada setiap ruang di papan tulis untuk berapa banyak angka yang akan dikurangi dengan menjatuhkan bom di sana. Jadi, jika ruang memiliki angka bukan nol, ia mendapat titik, dan jika ada ruang yang berdekatan dengan itu bukan angka nol, ia mendapat titik tambahan. Jadi jika ada kisi 1000-per-1000, kami memiliki bobot yang ditetapkan untuk masing-masing 1 juta ruang.

Kemudian urutkan daftar ruang berdasarkan berat, dan bom satu dengan bobot tertinggi. Ini adalah yang terbaik untuk uang kita, jadi untuk berbicara.

Setelah itu, perbarui berat setiap ruang yang beratnya dipengaruhi oleh bom. Ini akan menjadi ruang yang Anda bom, dan ruang apa pun yang berbatasan langsung dengan itu, dan ruang apa pun yang berbatasan langsung dengan itu. Dengan kata lain, ruang apa pun yang nilainya dapat direduksi menjadi nol oleh pengeboman, atau nilai ruang tetangga direduksi menjadi nol.

Kemudian, ulangi daftar spasi berdasarkan berat. Karena hanya sebagian kecil ruang yang bobotnya diubah oleh pengeboman, Anda tidak perlu menggunakan seluruh daftar, cukup pindahkan yang ada di dalam daftar.

Mengebom ruang berat tertinggi baru, dan ulangi prosedur.

Ini menjamin bahwa setiap pengeboman mengurangi ruang sebanyak mungkin (pada dasarnya, bom itu mengenai sedikitnya ruang yang sudah nol mungkin), sehingga itu akan optimal, kecuali bahwa mereka bisa menjadi ikatan dalam bobot. Jadi, Anda mungkin perlu melakukan pelacakan kembali ketika ada dasi untuk bobot teratas. Hanya dasi untuk masalah berat badan atas, bukan ikatan lainnya, jadi semoga itu tidak terlalu banyak pelacakan.

Sunting: Contoh tandingan Mysticial di bawah ini menunjukkan bahwa sebenarnya ini tidak dijamin optimal, terlepas dari ikatan dalam bobot. Dalam beberapa kasus, mengurangi berat sebanyak mungkin dalam langkah yang diberikan sebenarnya membuat bom yang tersisa terlalu menyebar untuk mencapai pengurangan kumulatif setinggi setelah langkah kedua yang Anda bisa dengan pilihan yang sedikit kurang serakah di langkah pertama. Saya agak menyesatkan dengan anggapan bahwa hasilnya tidak peka terhadap urutan pengeboman. Mereka adalahtidak peka terhadap urutan bahwa Anda dapat melakukan serangkaian pengeboman dan mengulanginya dari awal dengan urutan yang berbeda dan berakhir dengan papan hasil yang sama. Tapi itu tidak berarti bahwa Anda dapat mempertimbangkan setiap pemboman secara independen. Atau, setidaknya, masing-masing pemboman harus dipertimbangkan dengan cara yang memperhitungkan seberapa baik ia mengatur dewan untuk pemboman berikutnya.

Tim Goodman
sumber
masih akan banyak mundur, pada awalnya karena bidang memiliki nol sangat sedikit, bobot sebagian besar sel akan menjadi semua sembilan.
Lie Ryan
Ya, itu poin yang bagus, karena tidak ada kisaran besar dalam kemungkinan bobot (hanya 0 hingga 9).
Tim Goodman
Saya masih belum 100% yakin betapa perlunya backtracking itu ... mungkin bermanfaat untuk membangun grid di mana satu pilihan pengeboman serakah lebih rendah daripada pilihan lain dari pemboman serakah. Mungkin ada beberapa cara yang konsisten untuk mengantisipasi mana yang lebih baik.
Tim Goodman
Sebenarnya, saya melihat Kolonel Panic telah melakukan ini dalam jawabannya. Alasan satu pilihan serakah bisa lebih baik daripada yang lain adalah karena kita membiarkan jumlah yang tersisa lebih tersebar.
Tim Goodman
3
1010101, 0010100mungkin contoh tandingan yang membuktikan pendekatan ini tidak optimal. Pendekatan ini membutuhkan 3. Hal ini dapat dilakukan dalam 2.
Mysticial
1

Nah, misalkan kita beri nomor pada posisi papan 1, 2, ..., nx m. Setiap urutan tetes bom dapat diwakili oleh urutan angka dalam set ini, di mana angka dapat diulang. Namun, efek pada papan adalah sama terlepas dari apa urutan Anda menjatuhkan bom, jadi benar-benar pilihan bom apa pun dapat direpresentasikan sebagai daftar nomor nxm, di mana angka pertama mewakili jumlah bom yang dijatuhkan di posisi 1 , angka kedua mewakili jumlah bom yang dijatuhkan di posisi 2, dll. Mari kita sebut daftar nomor nxm ini sebagai "kunci".

Anda dapat mencoba menghitung semua status papan yang dihasilkan dari 1 penurunan bom, kemudian gunakan ini untuk menghitung semua status papan yang dihasilkan dari 2 penurunan bom, dll hingga Anda mendapatkan semua nol. Tetapi pada setiap langkah Anda akan cache negara menggunakan kunci yang saya tetapkan di atas, sehingga Anda dapat menggunakan hasil ini dalam menghitung langkah berikutnya (pendekatan "pemrograman dinamis").

Tetapi tergantung pada ukuran n, m, dan angka dalam kisi, persyaratan memori dari pendekatan ini mungkin berlebihan. Anda dapat membuang semua hasil untuk N bomb drop setelah Anda menghitung semua hasil untuk N +1, jadi ada beberapa penghematan di sana. Dan tentu saja Anda tidak bisa tembolok apa-apa pada biaya setelah itu mengambil banyak lagi - pendekatan pemrograman dinamis perdagangan memori untuk kecepatan.

Tim Goodman
sumber
1
Keraguan itu mungkin karena (jika saya mengerti Anda dengan benar). n = m. Saya perlu 10 ^ 6 int pointer ke (10 ^ 6) ^ 2 sel int. Saya memiliki papan sebanyak kunci di tabel. 10 ^ 12 ragu saya bisa mengalokasikan begitu banyak dalam mesin 32bit.
abc
Ya, saya baru saja melihat komentar Anda tentang papan hingga 1000 oleh 1000. Jadi itu satu juta int untuk keadaan setiap papan, ditambah satu juta int untuk jumlah bom yang dijatuhkan di setiap posisi. Jadi untuk setiap papan yang Anda simpan, Anda membutuhkan 2 juta int, dan ada banyak kemungkinan papan ...
Tim Goodman
Saya telah menambahkan jawaban kedua yang menggunakan pendekatan yang berbeda.
Tim Goodman
1
Ya. Semacam pendekatan brute force, tapi saya kira tidak terlalu praktis untuk papan besar.
Tim Goodman
@ Kostek, mengapa perkiraan rendah seperti itu? Ini lebih seperti k ^ (m * n) memori dengan k menjadi batas untuk angka-angka pada awalnya papan diisi.
Rotsor
1

Jika Anda ingin solusi optimal mutlak untuk membersihkan papan Anda harus menggunakan backtracking klasik, tetapi jika matriks sangat besar akan butuh waktu lama untuk menemukan solusi terbaik, jika Anda ingin solusi optimal "mungkin" Anda dapat menggunakan algoritma serakah , jika Anda butuh bantuan menulis algoritma saya dapat membantu Anda

Kalau dipikir-pikir itu adalah cara terbaik. Buat matriks lain di sana Anda menyimpan poin yang Anda hapus dengan menjatuhkan bom di sana kemudian memilih sel dengan poin maksimum dan menjatuhkan bom di sana memperbarui matriks poin dan melanjutkan. Contoh:

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

nilai sel +1 untuk setiap sel yang berdekatan dengan nilai lebih tinggi dari 0

cosmin.danisor
sumber
7
akan harus menggunakan backtracking klasik . Apakah Anda punya bukti untuk ini?
Shahbaz
Saya tidak yakin. Ini dari kontes yang saya siapkan (dari tahun sebelumnya). Batasnya adalah 1 <= n, m <= 1000 (tidak tahu apakah besar atau tidak). Pokoknya Anda membutuhkan jawaban yang tepat (ini mirip dengan kontes CERC dan sebagainya). Batas waktu tidak diberikan, tidak ada jawaban, juga tidak ada solusi pada halaman kontes.
abc
baik setiap algoritma lain akan memberikan Anda solusi optimal yang mungkin tetapi sampai Anda mencoba semuanya (backtracking) Anda tidak akan tahu apakah solusi itu yang terbaik
cosmin.danisor
2
Anda tidak perlu menggunakan backtracking karena ini adalah kombinasi yang Anda cari, bukan permutasi. Urutan menjatuhkan bom tidak penting
Luka Rahne
maka Anda bisa mencoba menggunakan variasi rakus. di setiap langkah, buat matriks baru dan setiap titik akan memiliki nilai selnya + 1 untuk setiap sel di sebelahnya> 0 cara ini akan memilih tempat yang lebih baik untuk menjatuhkan bom berikutnya
cosmin.danisor
1

Kasar !

Saya tahu ini tidak efisien, tetapi bahkan jika Anda menemukan algoritma yang lebih cepat, Anda selalu dapat menguji hasil ini untuk mengetahui seberapa akuratnya.

Gunakan rekursi, seperti ini:

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

}

Anda bisa menjadikan ini lebih efisien dengan caching, jika cara yang berbeda mengarah ke hasil yang sama, Anda tidak boleh mengulangi langkah yang sama.

Untuk menguraikan:

jika pemboman sel 1,3,5 mengarah ke hasil yang sama seperti pemboman sel 5,3,1, maka, Anda tidak harus melakukan kembali semua langkah berikutnya lagi untuk kedua kasus, hanya 1 yang cukup, Anda harus menyimpan di suatu tempat semua tabel menyatakan dan menggunakan hasilnya.

Statistik tabel hash dapat digunakan untuk melakukan perbandingan cepat.

sharp12345
sumber
1
  1. Jangan pernah membom perbatasan (kecuali bujur sangkar tidak memiliki tetangga yang tidak berbatasan)
  2. Sudut nol
  3. Ke sudut nol, turunkan nilai sudut satu diagonal jauh persegi (satu-satunya tetangga nonborder)
  4. Ini akan membuat sudut baru. Pergi ke 2

Sunting: tidak melihat bahwa Kostek menyarankan pendekatan yang hampir sama, jadi sekarang saya membuat klaim yang lebih kuat: Jika sudut yang akan dihapus dipilih untuk selalu berada di lapisan paling luar, maka itu optimal.

Dalam contoh OP: menjatuhkan 2 (seperti 1 + 1 atau 2) pada hal lain selain pada 5 tidak mengarah pada memukul kuadrat apa pun yang jatuh pada 5 akan memukul. Jadi kita harus menjatuhkan 2 pada 5 (dan 6 di kiri bawah 1 ...)

Setelah ini, hanya ada satu cara bagaimana menghapus (di kiri atas) sudut apa yang asli 1 (sekarang 0), dan itu adalah dengan menjatuhkan 0 pada B3 (unggul seperti notasi). Dan seterusnya.

Hanya setelah membersihkan seluruh kolom A dan E dan 1 dan 7 baris, mulailah membersihkan satu lapisan lebih dalam.

Pertimbangkan untuk mengosongkan hanya yang disengaja yang disingkirkan, membersihkan sudut nilai 0 tanpa biaya dan menyederhanakan berpikir tentang hal itu.

Karena semua bom yang dijatuhkan dengan cara ini harus dijatuhkan dan ini mengarah ke ladang yang sudah dibersihkan, itu adalah solusi optimal.


Setelah tidur nyenyak saya menyadari bahwa ini tidak benar. Mempertimbangkan

  ABCDE    
1 01000
2 10000
3 00000
4 00000

Pendekatan saya akan menjatuhkan bom pada B3 dan C2, ketika menjatuhkan B2 akan cukup

Alpedar
sumber
Tetapi apakah ini optimal?
Mysticial
7
Sudut-sudut baru dapat menjadi bom pada 2 cara (jika sebagian besar titik sudut mengandung nilai terendah dari semua 4). Yang mana pemboman yang optimal?
abc
Saya sedang memikirkan pendekatan yang serupa, dan ketika Anda mencapai situasi seperti yang dijelaskan Kostek, maka mulailah menggunakan pengulangan ...
Karoly Horvath
Sudut memberi Anda jumlah minimum bom yang akan dijatuhkan di kotak diagonal. Tapi begitu Anda memusatkan perhatian mereka, ubin batas berikutnya tidak akan selalu memiliki titik optimal yang jelas. Ini adalah cara yang baik untuk mengurangi ruang pencarian.
Eugene
Bagaimana dengan memilih sudut diagonal baru yang menghasilkan jumlah total tertinggi di kotak klik?
Hakim Maygarden
1

Inilah solusi saya .. Saya belum akan menuliskannya dalam kode karena saya tidak punya waktu, tetapi saya percaya ini akan menghasilkan jumlah gerakan yang optimal setiap kali - walaupun saya tidak yakin seberapa efisiennya dalam menemukan poin untuk mengebom.

Pertama, seperti yang dikatakan @Luka Rahne di salah satu komentar, urutan di mana Anda mengebom tidak penting - hanya kombinasi.

Kedua, seperti yang telah dinyatakan oleh banyak orang lainnya, pemboman 1-off diagonal dari sudut-sudut adalah optimal karena menyentuh lebih banyak titik daripada sudut-sudut.

Ini menghasilkan dasar untuk versi saya dari algoritma: Kita dapat mengebom '1-off dari sudut' pertama atau terakhir, tidak masalah (dalam teori) Kami mengebom yang pertama karena membuat keputusan kemudian lebih mudah (dalam praktiknya) Kami mengebom titik yang paling mempengaruhi poin, sementara secara bersamaan membom sudut-sudut itu.

Mari kita mendefinisikan Points Of Resistance menjadi poin di papan dengan poin paling non-bombable + angka 0 terbesar di sekitar mereka

poin yang tidak bisa dibom bisa diartikan sebagai poin yang tidak ada dalam ruang lingkup dewan saat ini yang sedang kita lihat.

Saya juga akan mendefinisikan 4 batas yang akan menangani ruang lingkup kami: Atas = 0, Kiri = 0, Bawah = k, kanan = j. (nilai untuk memulai)

Akhirnya, saya akan mendefinisikan bom yang optimal sebagai bom yang dijatuhkan pada titik-titik yang berdekatan dengan titik-titik perlawanan dan menyentuh (1) titik resistensi bernilai tertinggi dan (2) jumlah poin terbesar yang mungkin.

Mengenai pendekatan - jelas kami bekerja dari luar masuk. Kami akan dapat bekerja dengan 4 'pembom' pada saat yang sama.

Poin-poin pertama perlawanan jelas merupakan sudut kami. Poin 'out of bound' tidak dapat dibom (ada 5 poin di luar ruang lingkup untuk setiap sudut). Jadi kita bom poin secara diagonal terlebih dahulu.

Algoritma:

  1. Temukan 4 titik bom optimal.
  2. Jika titik bom mengebom titik resistan yang menyentuh 2 batas (yaitu sudut), bom sampai titik itu adalah 0. Jika tidak, bom masing-masing hingga salah satu titik perlawanan menyentuh titik bom optimal adalah 0.
  3. untuk setiap terikat: jika (jumlah (terikat) == 0) terikat sebelumnya

ulangi sampai TOP = BOTTOM dan LEFT = RIGHT

Saya akan mencoba menulis kode yang sebenarnya nanti

Etai
sumber
1

Anda dapat menggunakan perencanaan ruang negara. Sebagai contoh, menggunakan A * (atau salah satu variannya) ditambah dengan heuristik f = g + hseperti ini:

  • g: jumlah bom yang dijatuhkan sejauh ini
  • h: menjumlahkan semua nilai grid dibagi dengan 9 (yang merupakan hasil terbaik, artinya kita memiliki heuristik yang dapat diterima)
キ キ ジ キ
sumber
1

Saya mendapat 28 gerakan juga. Saya menggunakan dua tes untuk langkah selanjutnya yang terbaik: pertama langkah menghasilkan jumlah minimum untuk dewan. Kedua, untuk jumlah yang sama, gerakan yang menghasilkan kepadatan maksimum, didefinisikan sebagai:

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

Ini Haskell. "memecahkan papan" menunjukkan solusi mesin. Anda dapat memainkan game dengan mengetikkan "main", lalu memasukkan titik target, "terbaik" untuk rekomendasi, atau "berhenti" untuk berhenti.

OUTPUT:
* Main> papan penyelesaian
[(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)
groovy
sumber
1

Tampaknya ada substruktur pencocokan non-bipartit di sini. Pertimbangkan contoh berikut:

0010000
1000100
0000001
1000000
0000001
1000100
0010000

Solusi optimal untuk kasus ini memiliki ukuran 5 karena itulah ukuran penutup minimum dari simpul 9-siklus pada tepinya.

Kasus ini, khususnya, menunjukkan bahwa relaksasi pemrograman linier yang telah diposting oleh beberapa orang tidak tepat, tidak berfungsi, dan semua hal buruk lainnya. Saya cukup yakin saya dapat mengurangi "menutupi simpul dari grafik kubus planar saya dengan tepi sesedikit mungkin" untuk masalah Anda, yang membuat saya ragu apakah ada solusi rakus / mendaki gunung yang akan bekerja.

Saya tidak melihat cara untuk menyelesaikan ini dalam waktu polinomial dalam kasus terburuk. Mungkin ada solusi biner-pencarian-dan-DP yang sangat cerdas yang tidak saya lihat.

EDIT : Saya melihat bahwa kontes ( http://deadline24.pl ) adalah agnostik bahasa; mereka mengirimi Anda banyak file input dan Anda mengirimkan hasilnya. Jadi Anda tidak perlu sesuatu yang berjalan dalam waktu polinomial kasus terburuk. Khususnya, Anda bisa melihat input !

Ada banyak kasus kecil di input. Lalu ada case 10x1000, case 100x100, dan case 1000x1000. Tiga kasus besar semuanya berperilaku sangat baik. Entri yang berdekatan secara horizontal biasanya memiliki nilai yang sama. Pada mesin yang relatif gemuk, saya bisa menyelesaikan semua kasus dengan memaksa menggunakan CPLEX hanya dalam beberapa menit. Saya beruntung pada 1000x1000; relaksasi LP kebetulan memiliki solusi optimal yang tidak terpisahkan. Solusi saya setuju dengan .ansfile yang disediakan dalam bundel data uji.

Saya yakin Anda dapat menggunakan struktur input dengan cara yang lebih langsung daripada yang saya lakukan jika Anda melihatnya; Sepertinya Anda bisa memotong baris pertama, atau dua, atau tiga berulang kali hingga Anda tidak punya apa-apa lagi. (Sepertinya, pada 1000x1000, semua baris tidak bertambah? Saya kira dari sanalah "bagian B" Anda berasal?)

tmyklebu
sumber
Ya. Kadang-kadang saya hanya melewatkan bagian "tidak relevan" dari teks. Secara singkat dapatkan ide dan sebagainya. Kali ini pada dasarnya mengubah level dari semudah menjadi susah sekali: P Pokoknya saya tahu Anda bisa mencoba membuat heuristik dengan set input "dikenal". Di sisi lain saya hanya berpikir bahwa jika jawabannya bukan persentase poin, pasti ada beberapa algoritma yang akan dengan mudah dilakukan selama 5 jam. Semua yang saya temukan memiliki kompleksitas yang terlalu besar. Lalu saya membacanya lebih hati-hati, ketika seseorang bertanya tentang asal :)
abc
Kita dapat mengucapkan terima kasih kepada banyak orang yang memiliki masalah yang bagus, untuk dipikirkan, tetapi keraguan itu bisa dilakukan dalam waktu polinomial. Sangat lucu bagaimana satu kendala sederhana, mengubah tingkat tugas dari mudah menjadi tidak mungkin.
abc
@Kostek: Maaf jika saya tidak jelas. Saya ... sangat buruk dalam memberikan penjelasan pada tingkat yang sesuai untuk audiens. :) Di mana saya tidak jelas?
tmyklebu
1

Saya tidak bisa memikirkan cara untuk menghitung jumlah aktual tanpa hanya menghitung kampanye pengeboman menggunakan heuristik terbaik saya dan berharap saya mendapatkan hasil yang masuk akal.

Jadi metode saya adalah menghitung metrik efisiensi pemboman untuk setiap sel, mengebom sel dengan nilai tertinggi, .... mengulangi prosesnya sampai saya meratakan semuanya. Beberapa telah menganjurkan menggunakan kerusakan potensial sederhana (yaitu skor dari 0 hingga 9) sebagai metrik, tetapi itu gagal dengan memukul sel-sel bernilai tinggi dan tidak menggunakan kerusakan yang tumpang tindih. Saya akan menghitung cell value - sum of all neighbouring cells, mengatur ulang positif ke 0 dan menggunakan nilai absolut dari segala sesuatu yang negatif. Secara intuitif, metrik ini harus membuat pilihan yang membantu memaksimalkan kerusakan yang tumpang tindih pada sel dengan jumlah tinggi alih-alih memukulnya secara langsung.

Kode di bawah ini mencapai penghancuran total bidang uji dalam 28 bom (perhatikan bahwa menggunakan potensi kerusakan sebagai metrik menghasilkan 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();
    }           
  }
}

Pola pemboman yang dihasilkan adalah keluaran sebagai berikut (nilai bidang di sebelah kiri, metrik di sebelah kanan)

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
zeFrenchy
sumber
1

Ini dapat diselesaikan dengan menggunakan pohon kedalaman O (3 ^ (n)). Di mana n adalah jumlah dari semua kotak.

Pertama-tama anggap sepele untuk menyelesaikan masalah dengan pohon O (9 ^ n), cukup pertimbangkan semua lokasi pemboman yang mungkin. Sebagai contoh, lihat implementasi Alfe .

Selanjutnya sadari bahwa kita dapat bekerja untuk mengebom dari bawah ke atas dan masih mendapatkan pola pemboman minimum.

  1. Mulai dari sudut kiri bawah.
  2. Bom itu untuk dilupakan dengan satu-satunya permainan yang masuk akal (ke atas dan ke kanan).
  3. Pindahkan satu kotak ke kanan.
  4. Sementara target memiliki nilai lebih besar dari nol, pertimbangkan masing-masing dari 2 permainan yang masuk akal (lurus ke atas atau ke atas dan ke kanan), kurangi nilai target dengan satu, dan buat cabang baru untuk setiap kemungkinan.
  5. Pindahkan yang lain ke kanan.
  6. Sementara target memiliki nilai lebih besar dari nol, pertimbangkan masing-masing dari 3 permainan yang masuk akal (kiri, atas, dan kanan atas), kurangi nilai target dengan satu, dan buat cabang baru untuk setiap kemungkinan.
  7. Ulangi langkah 5 dan 6 sampai baris dihilangkan.
  8. Bergerak ke atas satu baris dan ulangi langkah 1 hingga 7 hingga puzzle dipecahkan.

Algoritma ini benar karena

  1. Anda perlu menyelesaikan setiap baris di beberapa titik.
  2. Menyelesaikan baris selalu membutuhkan permainan baik di atas, di bawah, atau di dalam baris itu.
  3. Itu selalu baik atau lebih baik untuk memilih permainan yang di atas baris tidak jelas terendah daripada bermain di baris atau di bawah baris.

Dalam praktiknya algoritma ini secara teratur akan melakukan lebih baik daripada maksimum teoretisnya karena secara teratur akan membom tetangga dan mengurangi ukuran pencarian. Jika kami menganggap bahwa setiap pengeboman mengurangi nilai 4 target tambahan, maka algoritma kami akan berjalan dalam O (3 ^ (n / 4)) atau sekitar O (1,3 ^ n).

Karena algoritma ini masih eksponensial, alangkah baiknya untuk membatasi kedalaman pencarian. Kami mungkin membatasi jumlah cabang yang diizinkan untuk beberapa angka, X, dan setelah kami sedalam ini kami memaksakan algoritma untuk memilih jalur terbaik yang telah diidentifikasi sejauh ini (cabang yang memiliki jumlah total papan minimum di salah satu daun terminalnya) ). Kemudian algoritma kami dijamin berjalan dalam waktu O (3 ^ X), tetapi tidak dijamin mendapatkan jawaban yang benar. Namun, kita selalu dapat meningkatkan X dan menguji secara empiris jika pertukaran antara peningkatan perhitungan dan jawaban yang lebih baik bermanfaat.

Ben Haley
sumber
1

fungsi evaluasi, jumlah total:

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

fungsi objektif:

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

menghancurkan fungsi:

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

fungsi tujuan:

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

fungsi maksimalisasi linear:

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

Ini tidak optimal, tetapi dapat dioptimalkan melalui menemukan fungsi evaluasi yang lebih baik ..

..tapi memikirkan masalah ini, saya berpikir bahwa salah satu masalah utama adalah mendapatkan angka yang ditinggalkan di tengah-tengah angka nol di beberapa titik, jadi saya akan mengambil pendekatan lain .. yang mendominasi nilai minimal menjadi nol, lalu mencoba untuk keluar dari nol sebanyak mungkin, yang mengarah pada minimalisasi umum dari nilai minimal yang ada atau lebih

Khaled A Khunaifer
sumber
0

Semua masalah ini intinya adalah menghitung jarak sunting. Cukup hitung varian jarak Levenshtein antara matriks yang diberikan dan matriks nol, di mana pengeditan diganti dengan pengeboman, menggunakan pemrograman dinamis untuk menyimpan jarak antara array menengah. Saya sarankan menggunakan hash dari matriks sebagai kunci. Dalam 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
Aerimore
sumber
0

Ini adalah jawaban untuk pertanyaan pertama yang diajukan. Saya tidak memperhatikan bahwa dia mengubah parameter.

Buat daftar semua target. Tetapkan nilai untuk target berdasarkan jumlah nilai positif yang dipengaruhi oleh setetes (itu sendiri, dan semua tetangga). Nilai tertinggi adalah sembilan.

Urutkan target dengan jumlah target yang terkena dampak (Turun), dengan sortir sekunder menurun pada jumlah masing-masing target yang terkena dampak.

Jatuhkan bom pada target peringkat tertinggi, lalu hitung ulang target dan ulangi sampai semua nilai target nol.

Setuju, ini tidak selalu yang paling optimal. Sebagai contoh,

100011
011100
011100
011100
000000
100011

Pendekatan ini akan membutuhkan 5 bom untuk dibersihkan. Namun secara optimal, Anda bisa melakukannya di 4. Namun, cukup dekat dan tidak ada kemunduran. Untuk sebagian besar situasi akan optimal, atau sangat dekat.

Menggunakan nomor masalah asli, pendekatan ini diselesaikan dalam 28 bom.

Menambahkan kode untuk menunjukkan pendekatan ini (menggunakan formulir dengan tombol):

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

                    }
                }
            }
        }

    }

Kelas yang Anda butuhkan:

        class Target
    {
        public int value;
        public int sum;
        public int x;
        public int y;
    }
Anthony Queen
sumber
1
Tidak maksimal. Contoh tandingan: 09090Pendekatan ini membutuhkan 18 bom. Itu bisa dilakukan di 9.
Mysticial
@Mysticial Anda tidak membaca jawaban secara menyeluruh. Karena didasarkan pada jumlah bidang non-nol yang terkena dampak, algoritma ini akan mengebom tengah nol dan akan dilakukan dalam 9 tetes. Nilai tinggi dari 9 adalah karena ada hingga delapan tetangga dan itu sendiri.
Anthony Queen
Lalu bagaimana 1010101, 0010100?
Mysticial
@Mysticial Untuk yang pertama, Pertama nol, lalu nol terakhir akan dipukul. Itu akan menjadi dua tetes. Itu karena setiap kali menjatuhkan bom, itu menghitung ulang target terbaik berikutnya. Untuk contoh terakhir, nol tengah lagi; Satu tetes.
Anthony Queen
1
@AnthonyQueen: ini tidak berhasil. silakan lihat chat.stackoverflow.com/transcript/message/8224273#8224273 untuk counterexample saya.
nneonneo