Temukan pemesanan yang optimal

Saya menemukan masalah ini dan berusaha menemukan cara untuk mendekatinya. Pikiran apa pun akan sangat dihargai!

Misalkan kita diberi matriks , misalnya,$\{-1, 0, 1\}^{n\ \times\ k}$

$$\begin{bmatrix} 1 & 0 & 1 & 0 & -1 \\ -1 & 0 & 0 & 0 & 1 \\ 0 & 1 & 1 & 0 & -1 \\ -1 & -1 & 0 & 1 & 1 \\ 1 & 0 & 0 & 0 & -1 \end{bmatrix}$$

Tanpa mencoba setiap permutasi tunggal, temukan pengurutan kolom yang memaksimalkan jumlah baris dengan elemen non-nol pertama adalah .$c_i$$1$

Untuk contoh di atas, satu urutan seperti itu (itu tidak unik!) Adalah , yaitu,$(c_3, c_4, c_1, c_2, c_5)$

Di sini, untuk dari baris elemen non-nol pertama adalah .$4$$5$$1$

Masalah ini, yang saya sebut CO untuk Pemesanan Kolom, adalah NP-hard . Berikut adalah pengurangan dari NP-hard Vertex Cover (VC) masalah untuk itu:

Bentuk masalah keputusan VC dan CO

Biarkan instance input VC menjadi . Ini mewakili pertanyaan: "Dengan grafik , apakah mungkin untuk memilih satu set paling banyak simpul dari sedemikian rupa sehingga setiap tepi dalam adalah insiden pada setidaknya satu titik yang dipilih?" Kami akan membuat turunan CO yang mewakili pertanyaan: "Mengingat matriks dengan elemen dalam , apakah mungkin untuk mengubah urutan kolom sedemikian rupa sehingga 1 muncul sebelum -1 pada setidaknya rows? " Dua masalah ini dinyatakan dalam masalah keputusan$(V, E, k)$$(V, E)$$k$$V$$E$$(A, k')$$A$$\{-1, 0, 1\}$$A$$k'$formulir, di mana jawaban untuk masing-masing adalah YA atau TIDAK: secara formal, ini adalah bentuk masalah yang NP-lengkap (atau tidak). Tidak terlalu sulit untuk melihat bahwa bentuk masalah optimasi yang lebih alami yang dinyatakan dalam pertanyaan OP kira-kira setara dalam hal kompleksitas: pencarian biner pada parameter ambang batas dapat digunakan untuk menyelesaikan masalah optimisasi menggunakan pemecah masalah keputusan, sedangkan satu doa pemecah masalah optimisasi, diikuti oleh satu perbandingan, cukup untuk menyelesaikan masalah keputusan.

Membangun instance CO dari instance VC

Biarkandan. Kami akan membangun matriks dengan baris dan kolom. Baris atas akan dibentuk dari blok masing-masing dari baris, dengan masing-masing blok mewakili suatu tepi yang perlu ditutup . Bagian bawah baris mengandung vertex "flags", yang akan menyebabkan kolom (yang sesuai dengan vertex) dikenakan biaya tetap jika dimasukkan di sisi kiri solusi CO (sesuai dengan vertex yang termasuk dalam vertex). penutup solusi VC).$n=|V|$$m=|E|$$A$$(n+1)m + n$$n+1$$(n+1)m$$m$$n+1$n$n$

Untuk setiap simpul , buat kolom di mana:$v_i$

• di antara baris atas , blok ke- dari baris semuanya berisi +1 ketika tepi adalah insiden pada , dan 0 sebaliknya, dan$(n+1)m$$j$$n+1$$e_j$$v_i$
• baris bawah semua 0 kecuali untuk -th, yaitu -1.$n$$i$

Buat satu lagi "pagar" kolom yang terdiri dari salinan -1, diikuti oleh salinan +1.$(n+1)m$$n$

Akhirnya, tetapkan ambang untuk instance CO yang dibangun: . Dengan kata lain, kami mengizinkan paling banyak baris di mana -1 muncul sebelum +1. Mari kita sebut jumlah baris melanggar ini sebagai "biaya" dari solusi CO.$k'$$(n+1)m + n - k$$k$

Bukti

Korespondensi antara solusi untuk instance CO dan satu set simpul dalam instance VC asli adalah: Setiap kolom di sebelah kiri pagar berkorespondensi dengan sebuah vertex yang ada di set, dan setiap kolom di sebelah kanan pagar sesuai dengan sebuah simpul yang tidak.

Secara intuitif, -1s di bagian atas kolom "pagar" memaksa pemilihan subset kolom yang akan ditempatkan di sebelah kirinya yang bersama-sama berisi +1 di semua posisi ini - sesuai dengan subset dari simpul yang terjadi pada setiap tepi. Masing-masing kolom ini yang muncul di sebelah kiri "pagar" memiliki -1 pada baris yang berbeda di suatu tempat di bagian bawah baris, menimbulkan biaya 1; +1 di bagian bawah "pagar" memastikan bahwa semua kolom yang ditempatkan di sebelah kanan tidak dikenakan biaya.$n$

Jelas sebuah solusi VC menggunakan paling banyak simpul menghasilkan solusi untuk turunan CO yang dibangun dengan biaya paling banyak : Hanya memesan kolom yang sesuai dengan simpul dalam penutup simpul secara sewenang-wenang, diikuti oleh kolom pagar, diikuti oleh semua kolom yang tersisa dalam urutan apa pun .$k$$k$

Tetap menunjukkan bahwa solusi untuk instance CO dengan biaya paling banyak sesuai dengan penutup simpul dengan paling banyak simpul .$k$$k$

Misalkan sebaliknya bahwa ada solusi untuk turunan CO dengan biaya paling banyak yang meninggalkan beberapa baris di atas baris dengan -1 sebelum +1. Baris ini milik blok baris yang sesuai dengan tepi tertentu . Setiap baris dalam blok ini dalam instance asli identik dengan konstruksi; kolom permutasi dapat mengubah baris ini, tetapi tidak mempengaruhi fakta bahwa mereka identik. Dengan demikian masing-masing baris identik ini memiliki -1 sebelum +1 dalam solusi, menyiratkan biaya setidaknya . Tetapi : kontradiksi.$k$$(n+1)m$$(n+1)$$uv$$A$$n+1$$n+1$$k \le n < n+1$

Karena setiap blok dari baris di bagian atas baris memiliki +1 sebelum -1, masing-masing tepi yang sesuai ditutupi oleh titik yang sesuai dengan kolom di sebelah kiri pagar: yaitu , bagian dari simpul ini merupakan penutup simpul. Karena tidak ada baris atas memiliki -1 sebelum +1, satu-satunya tempat di mana biaya dapat bertambah dalam solusi adalah di bawah baris, dari kolom yang ditempatkan di sebelah kiri pagar. Setiap kolom tersebut memiliki biaya tepat 1, sehingga mengingat bahwa biayanya paling banyak , harus ada paling banyak kolom tersebut, dan karenanya paling banyak simpul dalam penutup.$m$$(n+1)m$$(n+1)m$$n$$k$$k$$k$

Akhirnya, jelas bahwa turunan CO dapat dibangun dalam waktu polinomial dari instance VC, yang berarti bahwa jika algoritma waktu polinomial ada untuk menyelesaikan CO, setiap instance VC juga dapat diselesaikan dalam waktu polinomial dengan terlebih dahulu membangun turunan CO seperti yang dijelaskan di atas dan kemudian menyelesaikannya. Karena VC adalah NP-hard, CO juga.

Saya tidak tahu apakah sebenarnya ada solusi polinomial. Namun demikian berdasarkan komentar Pål GD, Anda dapat membangun fungsi penyederhanaan. Matriks awal simplificated sebagai Anda membangun urutan output .$S$

function simplification:
while(true)
    if any row i$ has no 1 or no -1 left, remove it
    if any column j has no -1 then,
       remove it and put j on the leftmost available position in S,
       remove all rows where column j has 1.
    if any column j has no 1 then, 
       remove it and put j on the rightmost available position in S.
    if no modification has been done on this loop, break

Maka Anda harus melakukan eksplorasi lengkap dari kombinatorik menggunakan iteratif pilih fungsi:

function pick(k):
    put column k on the leftmost available position in S
    remove any row where column k is -1 or 1

Setelah setiap pemungutan, Anda dapat melakukan penyederhanaan untuk mengurangi kemungkinan penjelajahan. Saya sarankan untuk mengeksplorasi dengan rakus dimulai dengan kolom yang memiliki -1 kurang, sehingga Anda dapat mencapai batas bawah membuat kriteria berhenti.

Pada contoh yang diberikan, penyederhanaan pertama memberi (seperti dijelaskan Pål GD dalam komentar)

• $S[0] = c3$ , hapus r1, r3
• $S[1] = c4$ , hapus r4
• $S[2] = c2$ ini memungkinkan Anda dengan matriks sederhana untuk dijelajahi. $$\begin{bmatrix} -1 & 1 \\ 1 & -1 \\ \end{bmatrix}$$

Saya pikir matriks membuat metode ini cukup tidak efisien akan memiliki tepat 1, dan satu -1 per baris / kolom, sesuatu seperti

Namun demikian, penyederhanaan masih menyisakan sekitar setengah langkah eksplorasi. Dan jenis matriks ini dapat dibagi menjadi beberapa sub-matriks independen.