Memesan elemen agar beberapa elemen tidak muncul di antara yang lain

Diberikan bilangan bulat dan himpunan kembar tiga bilangan bulat yang berbeda cari algoritma yang dapat menemukan permutasi dari set sedemikian rupa sehingga atau dengan tepat menentukan bahwa tidak ada permutasi yang ada. Kurang formal, kami ingin menyusun ulang angka 1 hingga ; setiap rangkap tiga dalam menunjukkan bahwa harus muncul sebelum dalam orde baru, tetapi tidak boleh muncul di antara $n$

S \subseteq {(i, j, k) ∣ 1 \leq i, j, k \leq n, i \neq j, j \neq k, i \neq k},

$S \subseteq \{(i, j, k) \mid 1\le i,j,k \le n, i \neq j, j \neq k, i \neq k\},$

π

$\pi$

{1, 2, \dots, n}

$\{1, 2, \dots, n\}$

(i, j, k) \in S ⟹ (π (j) < π (i) < π (k)) \lor (π (i) < π (k) < π (j))

$(i,j,k) \in S \implies (\pi(j)<\pi(i)<\pi(k)) ~\lor~ (\pi(i)<\pi(k)<\pi(j))$

n

$n$

(i, j, k)

$(i,j,k)$

S

$S$

i

$i$

k

$k$

j

$j$

i

$i$ dan .

k

$k$

Contoh 1

Misalkan dan . Kemudian $n=5$ $S = \{(1,2,3), (2,3,4)\}$

$\pi = (5, 4, 3, 2, 1)$ adalah tidak permutasi valid, karena , tapi . $(1, 2, 3)\in S$ $\pi(1) > \pi(3)$
$\pi = (1, 2, 4, 5, 3)$ adalah tidak permutasi valid, karena tetapi . $(1, 2, 3) \in S$ $\pi(1) < \pi(3) < \pi(5)$
$(2, 4, 1, 3, 5)$ adalah permutasi yang valid.

Contoh 2

Jika dan , tidak ada permutasi yang valid. Demikian pula, tidak ada permutasi yang valid jika dan ( Saya pikir, mungkin telah membuat kesalahan di sini). $n=5$ $S = \{(1, 2, 3), (2, 1, 3)\}$ $n=5$ $S = \{(1,2,3), (3,4,5), (2,5,3), (2,1,4)\}$

Bonus: Properti menentukan apakah ada solusi yang layak? $S$

algorithms optimization scheduling Patrick87
sumber

Mengapa tidak ulangi kondisi kedua sebagai ? Maka Anda memiliki masalah kepuasan kendala yang langsung, lebih-atau-kurang. (Perhatikan bahwa saya telah menyederhanakan kondisi berdasarkan asumsi lain.)

(σ_{m_{i}}, σ_{m_{j}}, σ_{m_{k}}) \in S ⟹ (i > j \lor j > k)

$(\sigma_{m_i},\sigma_{m_j},\sigma_{m_k})\in S\Longrightarrow (i>j \vee j>k)$

Dave Clarke

BTW: Apa motivasi untuk masalah ini?

Dave Clarke

@DaveClarke Lihat hasil edit saya. Masalah ini telah diabstraksi dari diskusi seputar masalah penjadwalan yang saya diskusikan dengan beberapa siswa lain di lab. Pada dasarnya, idenya adalah bahwa Anda memiliki banyak pekerjaan, beberapa di antaranya harus dijalankan dalam urutan tertentu. Namun, Anda tidak ingin beberapa pekerjaan dijadwalkan antara pekerjaan secara berurutan, mungkin karena alasan yang sangat halus.

Patrick87

Mengapa sigma? Cukup tentukan . Subskrip bersarang membuat bayi Yesus menangis.

Σ = {1, 2, \dots, n}

$\Sigma = \{1,2,\dots,n\}$

JeffE

@ Jeff Jujur, saya hanya suka alasan untuk bermain dengan hal persamaan. Ada sesuatu yang sangat memuaskan secara visual tentang penulisan kode yang mengkompilasi ke itu. Jangan ambil itu dariku, kawan.

σ

$\sigma$

Patrick87

Jawaban:

Berikut ini adalah algoritma yang naif. Ini pada akhirnya bergantung pada kekuatan kasar, tetapi kadang-kadang dapat bekerja dengan baik.

Setiap kendala terdiri dari dua konjungsi; sebut saja mereka tipe- , , dan tipe- , . Setiap batasan tipe dapat secara ekuivalen ditulis sebagai disjungsi , dengan mengandalkan fakta bahwa . $(\sigma_{m_i}, \sigma_{m_j}, \sigma_{m_k}) \in S \implies i < k \wedge \neg(i < j < k)$ $A$ $i < k$ $B$ $\neg(i < j < k)$ $B$ $i>j \vee j>k$ $i\neq j,j\neq k$

Kumpulkan semua kendala tipe- . Sebut ini . Periksa apakah mereka konsisten, yaitu bahwa ini adalah linierisasi pemesanan. Ini membutuhkan -waktu dalam jumlah kendala menggunakan penyortiran topologis. $A$ $\Theta$ $O(|S|)$
Untuk masing-masing disjungsi dalam kendala tipe- , periksa apakah konsisten dengan urutan parsial . Jika tidak konsisten, lepaskan disjunct. Jika kedua disjunct tidak konsisten dengan , maka gagal. Setiap kali hanya satu kendala tipe dihapus, tambahkan yang tersisa ke . Langkah ini adalah . $B$ $\Theta$ $\Theta$ $B$ $\Theta$ $O(|S|^2)$
Sekarang ada algoritma yang jelas untuk menemukan solusi, yaitu untuk mempertimbangkan semua kombinasi pasangan disjungsi tipe- dan menguji konsistensinya dengan , tetapi ini jelas eksponensial dalam. Satu heuristik untuk meningkatkan kinerja adalah memperlakukan pasangan disjungsi tipe sebagai cabang-cabang pohon --- satu pasang membentuk akar, itu anak-anak diberikan oleh pasangan kedua, anak-anak mereka oleh yang ketiga dan seterusnya. Menggunakan struktur data ini, solusinya ditemukan dengan melintasi pohon secara mendalam-pertama. Setiap kali kendala baru ditambahkan (menggunakan label pada cabang), konsistensi dapat diperiksa. Sub pohon yang tidak konsisten dapat dipangkas. $B$ $\Theta$ $|S|$
$B$
Jika daun pohon tercapai, maka kita memiliki seperangkat kendala yang konsisten yang terdiri dari semua kendala tipe- dan satu terlepas dari kendala tipe- . Linearkan hasilnya untuk mendapatkan pemesanan yang diinginkan. $A$ $B$

Pendekatan pilihan saya sebenarnya adalah untuk menyandikannya menjadi seperangkat kendala dan menggunakan pemecah kendala seperti Choco. Saya akan memperkenalkan variabel integer dalam kisaran dan mengharuskan mereka semua berbeda. Kemudian saya akan menyandikan setiap kendala di atas secara langsung sebagai kendala dan kemudian membiarkan Choco melakukan bisnisnya. $n$ $x_i$ $[0,n-1]$

Dave Clarke
sumber

Ini jawaban parsial:

Jika Anda menghapus kendala pada masing-masing tiga maka masalah Anda menjadi masalah Non-Betweeness yang -Lengkap dan ada tidak ada dikenal algoritma efisien untuk masalah seperti itu. Tapi dengan kendala, mungkin memaksa beberapa struktur yang bagus yang dapat dimanfaatkan untuk menemukan algoritma waktu polinomial untuk masalah Anda. $i \lt k$ $NP$ $i \lt k$

Mohammad Al-Turkistany
sumber