Saya memiliki n x m
matriks 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?
sumber
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?Jawaban:
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:
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.
sumber
But, we do know we can be greedy...
- Saya tidak membeli ini. Pertimbangkan1 1 2 1 1 2
perimeter. 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.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.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 pergi0 0 1 1 1
lebih 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.
sumber
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:
Entah bagaimana atau lain, Anda tahu Anda perlu mengebom di atau sekitar
4
tempat 4 kali untuk turun ke 0. Karena kiri tempat itu adalah angka yang lebih rendah, tidak ada manfaatnya untuk mengebom0
atau4
membom yang berlebihan2
. Bahkan, saya percaya (tetapi tidak memiliki bukti yang kuat) bahwa pemboman2
sampai4
titik turun menjadi setidaknya sama baiknya dengan strategi lain untuk mendapatkan yang4
ke 0. Seseorang dapat melanjutkan ke garis kiri ke kanan dalam strategi seperti ini:Beberapa contoh pesanan pemboman:
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.
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 (
x
baris). Tidak ada cara untuk menghapus baris atas dengan mengebom salah satuy
baris dan tidak ada manfaat tambahan untuk membom baris atas daripada membom ruang yang sesuai padax
baris.Kita bisa menerapkan strategi linier dari atas (mengebom ruang-ruang yang sesuai pada
x
baris), mengenai diri kita hanya dengan baris atas dan tidak ada yang lain. Ini akan seperti ini:Kelemahan dalam pendekatan ini menjadi sangat jelas dalam dua pemboman terakhir. Jelas, mengingat bahwa satu-satunya situs bom yang mengurangi
4
angka di kolom pertama di baris kedua adalah yang pertamax
dan yangy
. Dua pemboman terakhir jelas lebih rendah daripada hanya membom yang pertamax
, 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:
Hal ini jelas satu-satunya cara untuk mendapatkan ruang dengan
4
turun ke nol adalah untuk mengebom beberapa kombinasi darix
,y
, danz
. Dengan beberapa akrobat di pikiran saya, saya cukup yakin solusi optimal untuk mengebomx
tiga kali dana
kemudianb
. 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 pembomany
danz
ruang. Mencoba menemukan sudut tempat pemboman ruang-ruang itu masuk akal menghasilkan sudut yang terlihat seperti ini:Untuk yang ini, jelas bagi saya bahwa solusi optimal adalah mengebom
y
5 kali danz
5 kali. Mari kita melangkah lebih jauh.Di sini, rasanya sama intuitifnya bahwa solusi optimal adalah mengebom
a
danb
6 kali dan kemudianx
4 kali.Sekarang ini menjadi permainan bagaimana mengubah intuisi menjadi prinsip-prinsip yang bisa kita bangun.
Semoga bisa dilanjutkan!
sumber
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.
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.
sumber
Anda dapat mewakili masalah ini sebagai masalah pemrograman bilangan bulat . (ini hanyalah salah satu solusi yang mungkin untuk mendekati masalah ini)
Memiliki poin:
kita dapat menulis 16 persamaan di mana untuk titik f misalnya berlaku
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.
sumber
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:
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:
Kita dapat membidik sudut dengan menempatkan bom di sudut kedua untuk memberikan papan baru:
Sejauh ini baik. Kami membutuhkan 13 bom untuk membersihkan sudut.
Sekarang perhatikan angka 6, 4, 3, dan 2 yang ditandai di bawah ini:
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:
minimums
daftar.minimums
daftar untuk mendapatkan batas bawah.sumber
Ini akan menjadi pendekatan serakah:
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)
Memindahkan baris dengan bijak, temukan dan pilih posisi pertama dengan skor tertinggi (katakan (i, j)).
Bom (i, j). Tingkatkan jumlah bom.
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)
Diberikan Matriks M dari pesanan dan Xm. Jika semua elemen M adalah nol, maka kembalikan 0.
Hitung matriks "skor" M.
Biarkan k posisi berbeda P1, P2, ... Pk (1 <= k <= n * m), jadilah posisi dalam M dengan skor tertinggi.
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".
sumber
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.
sumber
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.
Untuk contoh yang diberikan dalam masalah:
Keluaran
Bagi siapa pun yang membaca ini dengan algoritma serakah
Coba kode Anda pada masalah 10x10 berikut:
Ini dia dipisahkan koma:
Untuk masalah ini, solusi saya mengandung 208 bom. Inilah solusi yang mungkin (saya bisa menyelesaikan ini dalam waktu sekitar 12 detik).
Sebagai cara untuk menguji hasil yang dihasilkan Mathematica, lihat apakah algoritma serakah Anda bisa lebih baik.
sumber
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:
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.
sumber
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.
sumber
Tampaknya pendekatan pemrograman linier bisa sangat membantu di sini.
Mari P m xn menjadi matriks dengan nilai-nilai posisi:
Sekarang mari kita mendefinisikan matriks bom B (x, y) mxn , dengan 1 ≤ x ≤ m , 1 ≤ y ≤ n seperti di bawah ini
sedemikian rupa itu
Sebagai contoh:
Jadi kita mencari untuk matriks B m xn = [ b ij ] yang
Dapat didefinisikan sebagai jumlah matriks bom:
( q ij akan maka jumlah bom kita akan turun di posisi p ij )
p ij - b ij ≤ 0 (lebih succint, mari kita katakan sebagai P - B ≤ 0 )
Juga, B harus meminimalkan jumlahnya .
Kita juga bisa menulis B sebagai matriks jelek di depan:
dan karena P - B ≤ 0 (yang berarti P ≤ B ) kami memiliki sistem ketimpangan linear yang cukup berikut di bawah ini:
Sedang q mn x 1 didefinisikan sebagai
p mn x 1 didefinisikan sebagai
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
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 )
sumber
"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.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 ++:
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.
sumber
"0110","1110","1110"
. Anda hanya perlu 1 tembakan, tapi saya yakin algoritma Anda akan menggunakan 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.
sumber
1010101
,0010100
(baris atas, baris bawah) Pendekatan Anda akan membutuhkan 3. Hal ini dapat dilakukan dalam 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
sumber
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):
Tantangannya adalah
choose_a_perfect_drop_point
. Pertama, mari kita tentukan apa itu drop point yang sempurna.(x, y)
menurunkan nilai dalam(x, y)
. Ini juga dapat menurunkan nilai di sel lain.(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.(x, y)
are setara jika mereka menurunkan set yang sama sel.(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:
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.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)
.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).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:
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:
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:sumber
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.
sumber
1010101
,0010100
mungkin contoh tandingan yang membuktikan pendekatan ini tidak optimal. Pendekatan ini membutuhkan 3. Hal ini dapat dilakukan dalam 2.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.
sumber
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:
nilai sel +1 untuk setiap sel yang berdekatan dengan nilai lebih tinggi dari 0
sumber
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:
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.
sumber
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
Pendekatan saya akan menjatuhkan bom pada B3 dan C2, ketika menjatuhkan B2 akan cukup
sumber
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:
ulangi sampai TOP = BOTTOM dan LEFT = RIGHT
Saya akan mencoba menulis kode yang sebenarnya nanti
sumber
Anda dapat menggunakan perencanaan ruang negara. Sebagai contoh, menggunakan A * (atau salah satu variannya) ditambah dengan heuristik
f = g + h
seperti ini:sumber
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:
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)]
sumber
Tampaknya ada substruktur pencocokan non-bipartit di sini. Pertimbangkan contoh berikut:
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
.ans
file 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?)
sumber
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!).
Pola pemboman yang dihasilkan adalah keluaran sebagai berikut (nilai bidang di sebelah kiri, metrik di sebelah kanan)
sumber
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.
Algoritma ini benar karena
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.
sumber
fungsi evaluasi, jumlah total:
fungsi objektif:
menghancurkan fungsi:
fungsi tujuan:
fungsi maksimalisasi linear:
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
sumber
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:
sumber
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,
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):
Kelas yang Anda butuhkan:
sumber
09090
Pendekatan ini membutuhkan 18 bom. Itu bisa dilakukan di 9.1010101
,0010100
?