Temukan angka minimum 1 sehingga matriks terdiri dari 1 wilayah terhubung 1

8

Membiarkan M. menjadi (0,1)matriks. Kami mengatakan dua entri bertetangga jika berbatasan horizontal atau vertikal, dan kedua entri berbatasan1ini Seseorang ingin menemukan jumlah minimum1untuk ditambahkan, jadi setiap 1 dapat mencapai yang lain melalui urutan tetangga.

Contoh:

100
000
001

Di sini kita perlu 3 1:

100
100
111

Bagaimana kita dapat secara efisien menemukan jumlah minimum 1untuk ditambahkan, dan di mana?

algorithms graph-theory matrices Chao Xu
sumber
Hal ini sering membantu untuk melemparkan masalah sebagai masalah tipe lain; misalnya saat ini masalah matriks sebagai masalah grafik. Ini memberi Anda semua alat teori grafik untuk bekerja dengannya. Pada pandangan pertama, masalah Anda tampak seperti masalah jalur terpendek bagi saya.
Juho

Jawaban:

5

Jika Anda memodelkan masalah Anda dengan grafik, masalah Anda seperti masalah Steiner Tree :

Lihat di sini untuk definisi sesederhana mungkin.

Diberikan grafik berbobot di mana subset simpul diidentifikasi sebagai terminal, temukan subgraf terhubung bobot minimum yang mencakup semua terminal.

Seperti yang Anda lihat itu adalah NPC pada umumnya, tetapi dalam kasus Anda grafik Anda adalah grafik kotak, mungkin Anda dapat menemukan solusi yang baik untuk itu, tetapi untuk contoh Anda saat ini (ketika terminal berada dalam batas) Anda dapat melihat pohon Steiner di kertas grafik grid .

Lagi pula ada heuristik yang sangat baik untuk masalah Steiner Tree, Anda dapat menerapkan pendekatan yang serupa dengan masalah Anda.

PS: Anda dapat mengasumsikan tetangga 1 adalah node yang terhubung, setelah itu Anda dapat mengontrak sisi-sisinya untuk membuat grafik baru, grafik baru yang Anda buat adalah planar, dan jika Anda dapat memecahkan Steiner Tree untuk itu Anda dapat menyelesaikan masalah Anda, tetapi mungkin ada solusi yang baik untuk masalah Anda yang independen dari Steiner Tree.


sumber
2
Jika ada yang bertanya-tanya, masalahnya tetap NP-lengkap bahkan jika tepi memiliki satuan berat.
Juho
@ mrm, Ya, sebenarnya tautan wikipedia, mengatakan tentang versi tidak berbobot (secara implisit) Lihat generalisasi . Saya pikir mungkin wiki link tidak jelas dalam pandangan pertama, Jadi saya mengutip definisi yang sederhana.
Perhatikan juga bahwa tidak semua 1 harus berada pada batas matriks untuk berada pada batas grafik kotak yang dihasilkan
Joe
Anda tampaknya mengurangi masalah OP menjadi Stiener Tree, yang mengatakan bahwa Stiener Tree setidaknya sekeras masalah OP. Bukan sebaliknya: yaitu kalimat pertama menyesatkan. Tentu saja, halaman wiki yang Anda tautkan, juga berbicara tentang masalah Stiener Tree Rectilinear, yang tampaknya cukup relevan.
Aryabhata
@Aryabhata, Tidak, saya tidak melakukan pengurangan, hanya beberapa format masalah OPs persis sama dengan masalah Stiener Tree, Jadi setidaknya sekeras Stiener Tree, tapi seperti yang saya sebutkan itu, masalah OP bekerja pada grid, dan jika Stiener Tree dapat dipecahkan pada grid, ia dapat melakukan ini untuk masalahnya, tetapi kasing kotak lebih sulit daripada kisi, pada kenyataannya, kisi adalah kasus khusus dari grafik bujursangkar, jadi saya menyarankan kertas untuk grafik kisi, yang dapat memecahkan kasus khusus dalam kisi di P, Secara keseluruhan saya tidak pernah mengatakan bahwa masalahnya adalah NPC atau sesuatu seperti ini, dan jika Anda pikir saya mengatakan ini, tolong beritahu saya untuk menghapusnya.