Menemukan bentuk dalam Array 2D, lalu mengoptimalkan

Saya baru saja diizinkan gambar ... Gambar di bawah ini dari permainan saya menunjukkan beberapa blok yang gelap, yang telah diakui sebagai bagian dari bentuk "T". Seperti dapat dilihat, kode tersebut telah menggelapkan blok dengan bintik-bintik merah, dan tidak melihat bentuk "T" dengan garis hijau.

Kode saya loop melalui x / y, menandai blok seperti yang digunakan, memutar bentuk, mengulangi, mengubah warna, mengulangi.

Saya sudah mulai mencoba untuk memperbaiki pemeriksaan ini dengan gentar. Gagasan saat ini adalah untuk:

• loop melalui grid dan catat semua kemunculan pola (BUKAN menandai blok seperti yang digunakan), dan menempatkan ini ke array
• loop melalui grid lagi, kali ini mencatat blok mana yang ditempati oleh pola mana, dan karena itu yang ditempati oleh beberapa pola.
• mengulang melalui grid lagi, kali ini mencatat pola mana yang menghalangi pola mana

Itu terasa benar ... Apa yang harus saya lakukan sekarang?

Saya pikir saya harus melakukannya

• coba berbagai kombinasi bentuk yang saling bertentangan, mulai dengan yang paling menghambat pola lainnya. Bagaimana saya mendekati yang ini?
• gunakan rasional yang mengatakan saya memiliki 3 bentuk yang saling bertentangan menempati 8 blok, dan bentuk masing-masing 4 blok, oleh karena itu saya hanya dapat memiliki maksimum dua bentuk.

(Saya juga bermaksud untuk menggabungkan bentuk-bentuk lain, dan mungkin akan ada bobot skor yang perlu dipertimbangkan ketika melewati bentuk-bentuk yang saling bertentangan, tetapi itu bisa jadi lain hari)

Saya tidak berpikir itu masalah pengemasan bin, tapi saya tidak yakin apa yang harus dicari. Harapan itu masuk akal, terima kasih atas bantuan Anda

EDIT Meskipun ada kejelasan pertanyaan, semua orang tampaknya mengerti, ya,

Saya ingin menemukan bentuk "T" maksimum dalam setiap warna

(karena jika saya memberi Anda poin untuk dua dan Anda telah membuat tiga, Anda akan sedikit kesal)

Biarkan saya melihat apakah saya sudah benar, blok bertanda merah, berwarna biru dan algoritma menemukan bentuk T dan menandai mereka merah, apakah itu benar? Tujuan Anda adalah untuk menemukan sebanyak mungkin bentuk T dengan blok warna yang sama, saya harap sejauh ini. Saat ini Anda menandai mereka setelah Anda menemukannya dan itu mengurangi kegunaan algoritma (Karena Anda bisa kehilangan solusi optimal). Anda berencana mencari semua bentuk dan memilih yang mana yang akan digunakan dan mana yang tidak digunakan. Apakah saya benar sejauh ini? Karena Anda ingin memaksimalkan jumlah blok yang terkandung di dalam bentuk T ketika algoritma dilakukan.

Jika saya benar, berikut ini adalah solusi optimal untuk situasi Anda menurut saya.

Kami akan menggunakan Integer Linear Programming.

Saya percaya saya menggunakan yang ini di masa lalu:

http://sourceforge.net/projects/lpsolve/

http://lpsolve.sourceforge.net/5.5/Java/README.html

(Anda bisa menggunakannya dengan banyak bahasa, saya menggunakannya dengan PHP, Java, dan C)

Apa yang akan kita lakukan adalah mendaftarkan setiap bentuk T yang mungkin di papan tulis dan kemudian menggunakan ILP untuk memaksimalkan jumlah blok yang dicakup. ILP sangat kompleks secara eksponensial. Mempertimbangkan ukuran papan Anda, itu tidak akan menjadi masalah. Saya telah menjalankan pertanyaan min / max yang jauh lebih rumit pada grafik dengan ILP dan hanya butuh sepersekian detik untuk menyelesaikan dan hingga 30-90 detik dengan ratusan simpul (dalam kasus Anda jatuh dalam sepersekian detik).

Apa yang akan saya rekomendasikan untuk dilakukan:

1. Temukan semua bentuk Garis yang mungkin
2. Temukan semua persimpangan antara bentuk garis dengan warna yang sama
3. Temukan semua bentuk T yang mungkin, cari semua persimpangan.
4. Tentukan variabel Boolean dalam Masalah Linear untuk setiap bentuk T ( 0 <= Bi <= 1) Karena nilainya adalah bilangan bulat, yang menyisakan 0 atau 1.
5. Buat kondisi untuk setiap pasangan bentuk T yang berpotongan ( Bi + Bj <= 1)
6. Fungsi obyektif adalah (jumlah blok dalam bentuk "T" (i) * Bi)
7. Jalankan solver dan gelapkan bentuk T di mana Boolean (s) yang sesuai solver di mana 1 dalam solusi optimal.

Ini adalah pengetahuan yang berharga, saya sering menggunakan pemecah linear untuk proyek kerja.

ILP pada dasarnya adalah cara untuk memecahkan masalah pemilihan di mana Anda ingin mencapai maksimum atau minimum untuk beberapa fungsi linier.

Anda dapat membaca lebih lanjut di sini, menggunakan Integer Linear Programming dan Linear Programming adalah sama untuk programmer hanya bahwa Integer jauh lebih kompleks untuk komputer yang dapat mengakibatkan waktu berjalan yang lama. Tidak dalam kasus Anda, Ini sangat sederhana dan hanya membutuhkan waktu kurang dari milidetik dalam kasus terburuk.

Saya kira Anda bisa membaca lebih lanjut di sini:

http://en.wikipedia.org/wiki/Integer_linear_programming#Integer_unknowns

Ini menjelaskannya dengan baik:

http://fisher.osu.edu/~croxton_4/tutorial/

Ini pada dasarnya adalah pemecah masalah keputusan, bagaimana membuat keputusan yang memaksimalkan hasil yang Anda inginkan. Ini mengasumsikan fungsi yang menilai hasilnya linier yang dalam kasus spesifik Anda saat ini. Fungsi yang menilai hasil dalam kasus ini, meringkas blok untuk semua bentuk T yang Anda putuskan untuk digelapkan.

Secara matematis, cara mengatur variabel: dalam kasus kami saat ini Boolean (Apakah saya menggelapkan bentuk T dengan indeks i atau tidak) ke nilai optimal untuk memaksimalkan hasil yang kita inginkan: menggelapkan sebanyak mungkin blok tanpa menggelapkan bentuk T yang gelap. Selama hasil yang Anda inginkan dapat dihitung dengan fungsi linear ketika Anda memiliki semua variabel yang ditetapkan, itu akan menyelesaikannya. Dalam kasus kami, kami memeriksa bentuk T mana yang digelapkan dan menjumlahkan blok yang dicakupnya.

Saya tahu ini bukan hal sepele jadi jika Anda memilih untuk melakukan lompatan, jangan ragu untuk berkomentar dan saya akan menguraikan.

Setelah Anda memiliki daftar semua (mungkin tumpang tindih) bentuk-T yang terjadi di kisi-kisi Anda, yang tersisa hanyalah masalah pengemasan set maksimum .

Secara umum, ini adalah masalah NP-complete. Namun, kisi Anda cukup kecil (dan biasanya dipecah menjadi subproblem independen yang bahkan lebih kecil) sehingga layak untuk mendapatkan solusi yang tepat.

Tambahan: Berikut adalah algoritma pencarian backtracking dasar yang mungkin melakukan trik:

function max_packing_recursive ( set A, set S, set M ):
    if |M| < |S| then let M = S;
    for each shape X in A do:
        remove X from A;
        let B = A;
        remove all shapes that intersect with X from B;
        if |M| < |B| + |S| + 1 then:        // upper bound
            let M = max_packing_recursive( B, S + {X}, M );
        end if
        if |M| >= |A| + |S| then return M;  // shortcut
    end for
    return M;
end function

function max_packing( set A ):
    return max_packing_recursive( A, {}, {} );
end function

Di sini, {X, Y, Z}menunjukkan set yang berisi elemen X, Ydan Z(dengan {}menjadi set kosong), dan |Q|menunjukkan ukuran set Q.

Dalam fungsi rekursif, set Aberisi bentuk yang tersedia untuk solusi yang tersisa, Sberisi bentuk dalam kandidat solusi saat ini, dan Mmerupakan solusi maksimal sejauh ini (yang mungkin ingin Anda simpan sebagai variabel global alih-alih mengembalikannya ke atas. rantai panggilan). Optimalisasi penting adalah pada baris yang ditandai dengan // upper bound, yang memangkas cabang-cabang pohon pencarian yang tidak mungkin menghasilkan solusi yang lebih baik daripada M.

(Sebenarnya, karena kita tahu bahwa setiap bentuk-T mengandung tepat empat situs, batas atas yang jauh lebih baik dapat diperoleh dengan mengganti |B|dengan jumlah situs berbeda yang dicakup oleh bentuk-bentuk dalam B, dibagi empat dan dibulatkan (dan demikian pula untuk |A|pada baris ditandai dengan // shortcut). Algoritme seperti yang diberikan di atas, bagaimanapun, berfungsi untuk koleksi bentuk yang sewenang-wenang.)

Kemungkinan pengoptimalan tambahan, yang belum saya terapkan di atas, adalah untuk memeriksa di awal fungsi rekursif apakah Aterbagi menjadi beberapa himpunan bagian yang independen, dalam arti bahwa tidak ada bentuk di himpunan bagian yang berbeda tumpang tindih, dan jika demikian, terapkan algoritma untuk masing-masing himpunan bagian secara terpisah. (Bagaimanapun, Anda pasti ingin melakukan ini setidaknya sekali di tingkat atas sebelum memanggil algoritma rekursif.) Menyortir bentuk secara Atepat sebelum mengulanginya, misalnya dalam meningkatkan urutan dengan jumlah bentuk yang tumpang tindih, juga dapat membantu .