Antrian prioritas untuk prioritas yang dipesan sebagian dengan infima

16

Saya memiliki beberapa objek dengan prioritas yaitu tipe majemuk dan hanya dipesan sebagian . Saya perlu memilih objek dalam urutan prioritas ini (yaitu menghasilkan item minimal setiap kali). Tetapi alih-alih menyelesaikan pesanan secara sewenang-wenang, saya lebih suka jika antrian stabil dalam arti bahwa jika ada lebih dari satu elemen minimal, itu harus mengembalikan yang tertua terlebih dahulu.

Apakah ada struktur tumpukan data yang akan berfungsi dengan pemesanan parsial? Atau modifikasi antrian prioritas reguler untuk bekerja dengannya? Pilihan umum untuk algoritma yang saya butuhkan adalah tumpukan biner atau 4-ary sederhana, tetapi itu tidak bekerja dengan pemesanan parsial.

Nilai-nilai prioritas mendukung:

$\preccurlyeq$ $a \preccurlyeq b$ $b \preccurlyeq a$ $a \not\lesseqgtr b$
Menemukan infima (glb) dan suprema (lub). adalah maksimal sehingga . Menghitung nilai maksimum membutuhkan waktu. Jumlah maksimum (dan supremum) dari setiap perangkat ada. $\inf(x_i)$ $y$ $y \preccurlyeq x_i$ $n$ $O(n)$
Ekstensi linear untuk pemesanan parsial dapat ditentukan. Menggunakannya untuk antrian prioritas adalah jalan keluar yang mudah karena algoritme berfungsi seperti itu. Tetapi urutan mempengaruhi kinerja dan urutan penyisipan sepertinya yang terbaik dalam menghindari kasus terburuk.

Selain itu algoritma yang ingin saya gunakan ini perlu mengetahui infinite dari semua prioritas dalam antrian.

Prioritas memiliki beberapa makna dunia nyata, tetapi dapat berubah, sehingga tampaknya tidak layak untuk mengandalkan properti lain yang bisa mereka miliki.

Catatan: Biner tumpukan tidak berfungsi dengan pemesanan parsial. Asumsikan tumpukan biner dengan $a$ , $b$ dan $c$ , di mana $a \preccurlyeq c$ dan $a \not\lesseqgtr b$ dan $a \not\lesseqgtr c$ . Mereka diposisikan dalam urutan itu, jadi

     a (0)
   /   \
 b (1)   c (2)

sekarang d dimasukkan. Posisi bebas berikutnya adalah 3, anak kiri dari $b$ , jadi kita dapatkan

        a (0)
      /   \
    b (1)   c (2)
  /
d (3)

Jika (yang menyiratkan dari transitivitas, tetapi tidak mengatakan apa-apa tentang dan ) dan , maka tidak ditukar dengan , karena tidak kurang. Tapi itu sebenarnya kurang dari , tapi itu tidak dibandingkan dengan itu, jadi sekarang invarian tumpukan utama tidak berlaku; top tidak minimal. $d \preccurlyeq a$ $d \preccurlyeq c$ $d$ $b$ $d \not\lesseqgtr b$ $d$ $b$ $a$

Saya curiga ada tumpukan hutan dengan gaya tumpukan binomial yang bisa digunakan untuk bekerja. Pada dasarnya, penting untuk selalu membandingkan nilai-nilai baru dengan root dan hanya menghubungkan elemen-elemen yang sebanding. Itu akan membuat pohon-pohon di hutan berukuran acak dan dengan demikian membuat kerumitan tergantung pada jumlah set yang tak tertandingi di tumpukan. Saya agak curiga kerumitan tidak dapat diperbaiki (kita harus terus membandingkan sampai kita mencapai elemen yang sebanding) Saya mungkin telah melewatkan sesuatu, jadi saya membiarkan ini terbuka.

Catatan: Pemesanan sebagian dan meskipun ada cara untuk menentukan ekstensi linier untuk itu, menambahkan cap waktu dan menggunakannya sebagai kriteria sekunder bukan salah satunya. Misalkan kita menetapkan timestamp untuk masing-masing dan mendefinisikan urutan sebagai iff atau ( dan . Maka anggaplah kita memiliki berbeda , , , sehingga dan . Kemudian dan $t(a)$ $a$ $\preccurlyeq'$ $a \preccurlyeq' b$ $a \preccurlyeq b$ $b \not\preccurlyeq a$ $t(a) \le t(b)$ $a$ $b$ $c$ $t(a) \le t(b) \le t(c)$ $c \le a$ $a \preccurlyeq' b$ $b \preccurlyeq' c$ , tetapi , jadi relasinya tidak transitif dan karenanya bukan urutan sama sekali. Perpanjangan seperti ini hanya berfungsi untuk pesanan yang lemah, tetapi tidak untuk sebagian. $c \preccurlyeq' a$

Sunting: Saya menyadari bahwa tidak hanya jumlah maksimum dari setiap set yang ditentukan, tetapi saya benar-benar harus dapat memperoleh elemen maksimum saat ini dalam antrian secara efisien. Jadi saya sekarang merenungkan apakah menambahkan node khusus yang mengandung infima subtree ke beberapa struktur heap umum akan membantu.

data-structures priority-queues Jan Hudec
sumber

Sudahkah Anda mempertimbangkan Antrian Prioritas Terindeks?

@ Hulkmeister: Bisakah Anda jelaskan bagaimana memiliki antrian diindeks membuatnya bekerja dengan pemesanan parsial (tidak, tumpukan biner biasa tidak bekerja dengan pemesanan parsial)?

1

Pikir saya adalah bahwa ketika dua item tidak dapat dibandingkan, Anda dapat menggunakan indeks untuk melacak urutan penyisipan. Jadi buat prioritas dengan indeks, dan Anda memiliki kunci unik yang dapat dibandingkan bahkan ketika prioritas tidak. Jika ini terdengar seperti yang Anda inginkan, saya bisa memasukkannya ke dalam jawaban yang lengkap.

1

@ Hulkmeister: Yah, masalahnya jauh lebih dalam dari itu. Ketika item baru dimasukkan, antrian prioritas biasanya membandingkannya dengan beberapa elemen. Tetapi jika mereka tak tertandingi, itu hanya tidak tahu di mana memasukkannya. Dan disambiguasi dengan indeks tidak akan berhasil, karena indeks berubah dan karena itu mungkin tidak akan memberikan total pemesanan yang konsisten dengan prioritas.

Bisakah Anda memberikan beberapa contoh dari jenis senyawa ini, dan ketika itu tidak ada bandingannya? Apakah mungkin untuk menganggap nilai-nilai 'tak tertandingi' ini sama? Jika demikian, Anda bisa menyimpannya di simpul yang sama dalam urutan penyisipan.

3

Meskipun masalah yang diajukan dalam pertanyaan awal tampaknya sulit (dan saya akan tertarik pada solusi untuk masalah itu, terutama bagian penemuan infima). Saya hanya ingin mencatat bahwa jika set yang dipesan sebagian memang terdiri dari vektor menggunakan pesanan produk, dan jika itu cukup untuk hanya memiliki jaminan bahwa antrian prioritas mengembalikan nilai dalam urutan yang "kompatibel" dengan pesanan parsial ( artinya, elemen yang lebih kecil selalu dikembalikan sebelum elemen yang lebih besar), maka ada cara yang cukup mudah untuk melakukannya.

Idenya pada dasarnya adalah untuk menemukan pemesanan topologi dari set yang dipesan sebagian. Yaitu, total order ' ' sedemikian rupa sehingga . Untuk vektor yang menggunakan pesanan produk, ini cukup mudah: cukup gunakan urutan leksikografis ' ', di mana "komponen" pertama adalah jumlah semua komponen yang digunakan untuk pesanan produk (sisa komponen pada dasarnya sewenang-wenang, jadi Anda juga bisa tetap berpegang pada urutan yang lemah). Kita kemudian dapat melihat bahwa dan $\le_T$ $\mathbf{a}\le\mathbf{b}\implies \mathbf{a}\le_T\mathbf{b}$ $\le_S$

a < b ⟹ \forall_{i} (a_{i} \leq b_{i}) and \exists_{i} (a_{i} < b_{i}) ⟹ (\sum_{i} a_{i}) < (\sum_{i} b_{i}) ⟹ a \leq_{S} b

$\mathbf{a}<\mathbf{b}\implies \forall_i(a_i\le b_i)\text{ and }\exists_i(a_i<b_i)\implies(\sum_i a_i)<(\sum_i b_i)\implies\mathbf{a}\le_S\mathbf{b}$

a = b ⟹ \forall_{i} (a_{i} = b_{i}) ⟹ (\sum_{i} a_{i}) = (\sum_{i} b_{i}) ⟹ a \leq_{S} b,

$\mathbf{a}=\mathbf{b}\implies \forall_i(a_i=b_i)\implies(\sum_i a_i)=(\sum_i b_i)\implies\mathbf{a}\le_S\mathbf{b},$ dan dengan demikian itu . Dengan demikian, kami dapat menggunakan pesanan ini dengan antrian prioritas dan memastikan bahwa elemen yang lebih kecil (dalam urutan produk) akan selalu diekstraksi sebelum elemen yang lebih besar.

a \leq b ⟹ a \leq_{S} b

$\mathbf{a}\le\mathbf{b}\implies\mathbf{a}\le_S\mathbf{b}$

Jasper
sumber

Ada banyak opsi lainnya. Menggunakan salah satu komponen, minimum, maksimum, setiap kombinasi linear dengan koefisien non-negatif setidaknya. Pilihan ekstensi memengaruhi seberapa cepat algoritma overlay akan.

Jan Hudec

2

Apa yang salah dengan membuat pemesanan parsial Anda selesai?

Tetapi alih-alih menyelesaikan pesanan secara sewenang-wenang, saya lebih suka jika antrian stabil dalam arti bahwa jika ada lebih dari satu elemen minimal, itu harus mengembalikan yang tertua terlebih dahulu.

Jika Anda lebih suka 'tertua dulu', maka pesanan Anda secara efektif selesai; item 'tak tertandingi' sebanding dengan usia.

Tambahkan stempel waktu (atau bilangan bulat lain yang tumbuh secara monoton) ke setiap item dan gunakan jika perbandingan 'nyata' tidak mungkin.

sumber

3

Itu akan lebih bagus jika bisa dibuat perpanjangan linear dari pemesanan parsial. Tapi ternyata tidak. Mari kita memiliki 3 nilai berbeda, disisipkan dalam urutan a , b , c , sehingga c ≤ a dan b tidak dapat dibandingkan dengan keduanya. Ekstensi dengan cap waktu mengisi a ≤ 'b dan b ≤' c , jadi dari transitivitas sekarang a harus kurang dari c , tetapi itu bertentangan dengan pemesanan yang sebenarnya.

Mungkin Anda bingung dengan lemahnya pemesanan. Dalam urutan lemah elemen tak tertandingi membentuk kelas kesetaraan, sehingga Anda dapat menambahkan kriteria tambahan sewenang-wenang. Untuk pemesanan parsial Anda tidak bisa.

1

EDIT: ini tampaknya menjadi masalah yang menarik, dan saya punya sedikit riset tentang itu. Saya sarankan Anda membaca yang berikut:

Darell Raymond. Database pesanan parsial, Tesis PhD, Universitas Waterloo.

Saya sarankan Anda membaca makalah ini: Daskalakis, Constantinos, et al. "Penyortiran dan seleksi dalam poset." Jurnal SIAM tentang Komputasi 40.3 (2011): 597-622.

Di sini penulis menyajikan struktur data yang disebut ChainMerge yang menerima poset dan dekomposisi rantai poset ke dalam rantai . Ukuran struktur data adalah . Para penulis menyajikan algoritma untuk menemukan minimas yang berjalan di mana adalah batas atas pada lebar poset. .. Saya pikir mungkin ini menarik. $q$ $O(n q)$ $O(w n)$ $w$

Catatan: Saya menghapus jawaban naif sebelumnya. Silakan klik edit untuk melihatnya.

Dipotong
sumber

0

Penggunaan terminologi saya mungkin salah. Harap edit jawaban saya langsung untuk memperbaiki masalah yang Anda temukan.

Pertama, perangkat yang tidak dapat dibandingkan harus dideteksi dari input.

Misalnya, mungkin ada 5 objek a, b, c, d, e,, tetapi urutan parsialnya membentuk dua grafik yang terputus:

a ≤ b ≤ c
d ≤ e
tapi semua {a, b, c}tidak ada bandingannya dengan {d, e}.

Set yang tidak tertandingi ini perlu dideteksi terlebih dahulu, sebelum objek dapat disimpan ke dalam struktur data yang sesuai. Ini dapat dilakukan dengan algoritma Union find

Untuk efisiensi, penyisipan objek baru perlu memiliki cara yang efisien untuk menemukan "daftar objek yang ada yang dapat dibandingkan dengan objek baru ini".

Sekarang, dalam setiap subset (masing {a, b, c}- masing dan {d, e}), minimum harus didefinisikan dengan baik. (Untuk setiap subset mungkin ada satu atau lebih minimal, karena pemesanan parsial.)

Saya melihat ini sebagai grafik asiklik terarah . Mencoba memasukkannya ke dalam tumpukan sepertinya merupakan bencana.

Untuk mengekstrak minima dari struktur data komposit ini, langkah selanjutnya adalah mendapatkan daftar semua minima dari semua himpunan bagian, pilih yang dengan cap waktu paling awal, dan hapus dan kembalikan objek ini.

rwong
sumber

Sayangnya saya tidak melihat cara untuk secara efisien menemukan daftar objek yang sebanding.

Set yang dipesan sebagian memang dapat dilihat sebagai grafik asiklik terarah. Tapi yang diberikan oleh tabel adjacency (fungsi, sebenarnya) daripada daftar adjacency. Menemukan minimum poset yang diberikan oleh daftar adjacency itu mudah, tetapi untuk tabel adjacency itu masalah.

Minima didefinisikan dengan baik dalam set aslinya juga. Saya tidak melihat bagaimana menemukan komponen yang terhubung dapat membantu, karena mereka bukan grafik lengkap.

1

Anda tampaknya berasumsi bahwa diagram Hasse adalah hutan pohon unary (ekuivalen jalur grafik), tetapi pertanyaannya sudah menyatakan bahwa itu adalah pesanan produk, jadi kisi multi-dimensi.

Peter Taylor

0

Sebuah proyek yang sedang saya kerjakan melibatkan masalah yang sama (kebetulan saya juga menggunakan urutan sebagian vektor). Kami sudah memiliki algoritma waktu kuadrat untuk mengurutkan daftar yang diurutkan secara acak, dan saya mengembangkan algoritma penyisipan dengan mengamati perilakunya ketika hanya satu objek yang rusak. Kami tidak tahu apakah ini adalah implementasi secepat mungkin.

Inilah beberapa kodesemu.

class PartialOrderPriorityQueue
   q <- empty list
   method insert (n):
     for i <- 0 to (q.length - 1):
       if q[i] <= n:
         t <- q[i]
         q[i] <- n
         n <- t
     q.append(n)

   method pop():
     return q.remove(0)

Daftar Jeremy
sumber

-1

Perilaku tumpukan biasa adalah menambahkan nilai baru ke belakang, dan kemudian menyaring sementara itu membandingkan lebih besar dari induknya.

Jika Anda menulis perbandingan yang mengembalikan yang sama untuk orang tua dan anak bukan kasus yang sebanding karena untuk orang tua lebih besar dari anak , pengayakan harus tetap berakhir pada titik yang tepat.

Apakah itu dianggap sebagai pemesanan yang cukup stabil untuk keperluan Anda?

Untuk memperjelas, ambil contoh dari komentar Anda: a> b , dan c tidak dapat dibandingkan dengan a atau b :

a lalu b lalu c => a, b, c ... ini sudah dalam urutan tumpukan, dan tidak ada yang bergerak dalam penyaringan
b, a, c => a, b, c ... a diayak ke tempat yang benar, dan sekali lagi kita berada dalam urutan tumpukan yang benar
a, c, b => a, c, b ... b tidak dapat menyaring karena tidak sebanding dengan c, tapi ini membuat mereka dalam urutan FIFO seperti yang Anda minta
c, b, a => c, a, b ... a dan b berada dalam urutan relatif yang benar, tetapi tidak ada yang bisa maju c karena mereka tidak dapat dibandingkan dengan itu

jadi, hasilnya tergantung pada urutan penyisipan - ini tampaknya cocok dengan yang Anda minta, tapi saya tidak yakin apakah itu benar-benar yang Anda inginkan. Jika tidak, bisakah Anda menunjukkan hasil yang ingin Anda lihat?

OK, jadi dari komentar Anda (dan edit untuk pertanyaan Anda), Anda ingin elemen "sebanding" melompati elemen "tidak sebanding" dan menemukan tempat yang tepat di bawah pemesanan, jika ada. Saya bertanya tentang ini karena saya tidak yakin bagaimana menafsirkannya

jika beberapa elemen tidak tertandingi, itu mengembalikannya dalam urutan yang dimasukkan

(d dan b secara berpasangan tak tertandingi dalam pengeditan Anda, tetapi Anda tidak menginginkannya dalam urutan yang dimasukkan).

Pertanyaan saya berikutnya adalah tentang hubungan antara elemen "sebanding" dan "tidak sebanding", tetapi saya melihat Anda telah mengungkapkan sekarang bahwa mereka adalah vektor dalam urutan produk (tidak jelas apakah beberapa elemen berpasangan- tidak sebanding dengan segalanya , seperti NaN, atau apa).

Jadi, jika saya mengambil contoh baru Anda dan menetapkan nilai vektor, apakah benar bahwa ini adalah contoh di mana b tidak dapat dibandingkan dengan yang lain:

        a (1,1)
      /      \
    b (0,4)   c (3,3)
  /
d (2,2)

dan itu harus diurutkan ke ini:

        a (1,1)
      /      \
    d (2,2)   c (3,3)
  /
b (0,4)

?

Tak berguna
sumber

Saya secara eksplisit menyebutkan dalam pertanyaan bahwa itu tidak akan berhasil, karena saya pikir saya memiliki contoh tandingan, tetapi saya tidak begitu yakin dengan itu sekarang. Dapatkah Anda membuktikan bahwa antrian tersebut akan menjadi suara (untuk deletemin, insert dan update juga)? Dan ingat, bahwa mungkin saja ≤ b , tetapi c tidak dapat dibandingkan (dan karena itu akan membandingkan "sama" dengan aturan di atas) dengan salah satu dari mereka.

Yah, itu belum bukti. Jangan pedulikan pesanan dan buktikan bahwa tumpukan seperti itu selalu memiliki elemen minimal di atas (catatan: (lebih) konvensi umum dan kebutuhan sebenarnya dari algoritma minimal di atas, jadi jika a> b , b yang diutamakan ).

Sebenarnya saya curiga ada contoh yang berlawanan. Misalkan a , b dan c berada di heap, a ≤ b dan ≤ c , a adalah top, b adalah anak kiri, c adalah anak kanan. Sekarang d muncul d ≤ c dan tidak dapat dibandingkan dengan a dan b . Dimasukkan sebagai anak b , tidak kurang dan tetap di sana. Sekarang datang e yang c ≤ e (dengan demikian juga a ≤ e ) dan tidak dapat dibandingkan dengan b . Jadi e masuk sebagai anak kanan bdan tetap. Sekarang ekstrak a (OK, a minimal), e akan ditukar di tempat itu dan diayak. Tidak sebanding dengan b , tetapi kurang dari c , jadi bertukar dengan c . Sekarang ekstrak c , SALAH , d ≤ c .

Jika Anda menemukan kesalahan dalam komentar sebelumnya (yang perlu memiliki bentuk ketidaksetaraan yang harus dipegang karena transitivitas dan saya melewatkannya), Anda masih memiliki peluang. Kalau tidak, itu tidak akan berhasil.

1

Ok, contoh kontra yang lebih sederhana. Misalkan a , b dan c berada di heap, a ≤ c , b tidak dapat dibandingkan dengan keduanya. a adalah atas, b adalah anak kiri, c adalah anak kanan. d masuk sehingga d ≤ a (dengan demikian d ≤ c ) dan tidak dapat dibandingkan dengan b . Slot bebas berikutnya adalah sebagai anak kiri dari b dan d yang tidak ada bandingannya, sehingga tetap di sana. Sekarang ekstrak a , SALAH , d ≤ a . Perhatikan bahwa apakah ≤ catau tidak masalah, situasinya sama jika mereka tak tertandingi.

Antrian prioritas untuk prioritas yang dipesan sebagian dengan infima

Jawaban: