Menghasilkan urutan total atau parsial dari relasi yang tidak konsisten
Bayangkan saya ingin membuat urutan total dari satu set elemen, $E$, tetapi fungsi perbandingan menghasilkan hasil yang non-deterministik. Saya membuat daftar pasangan elemen (e, e) melalui aplikasi berulang dari fungsi perbandingan, sehingga setiap elemen dalam himpunan diwakili setidaknya satu kali.
Bagaimana saya bisa menggunakan input ini untuk menghasilkan pesanan total? Apa kelas algoritma yang dapat diterapkan di sini?
Untuk lebih jelasnya, saya akan memberikan contoh konkret.
Apa topping pizza terbaik?
Kumpulan elemen saya $E$ termasuk beberapa topping pizza populer: pepperoni, keju, jamur, nanas, paprika, zaitun.
Kemudian untuk setiap teman saya, saya memilih subset topping berukuran acak dan meminta teman saya untuk menyusunnya dari yang terbaik ke yang terburuk. Teman-teman saya dengan patuh membalas, dan membuat masukan untuk algoritme saya:
- keju, pepperoni, zaitun
- keju, nanas, jamur, zaitun
- paprika, jamur, zaitun
- pepperoni, keju, zaitun
- keju, bellpepper
Tampaknya ada urutan yang tidak jelas di sini (semua orang setuju zaitun adalah yang terburuk) tetapi teman-teman saya belum mencapai kesepakatan tentang topping pizza mana yang lebih baik: keju atau pepperoni. Mempertimbangkan di mana item muncul di input, dan seberapa sering terjadi, saya mungkin akan membuat pesanan seperti ini.
- keju> pepperoni> paprika> nanas> jamur> zaitun
Saya hanya tidak yakin bagaimana cara memformalkan ini dan membuatnya berfungsi untuk input yang jauh lebih besar.
Saya pikir solusinya mungkin melibatkan grafik dan tepi berbobot, tetapi saya kurang terbiasa dengan algoritma grafik untuk mengenali apakah ini adalah bidang studi bernama. Saya sudah menemukan "penyortiran topologis" tetapi itu hanya berfungsi untuk grafik asiklik terarah , dan saya secara khusus tertarik pada masukan yang tidak dapat menghasilkan DAG.
Saya juga memperhatikan bahwa masalah ini tampaknya serupa dengan pemungutan suara untuk perwakilan terpilih. Apakah ini sebenarnya merupakan kelas masalah yang sama?
Jawaban
Sulit untuk mengatakannya tanpa lebih banyak konteks dan lebih banyak model. Dibutuhkan beberapa asumsi tentang bagaimana hasil fungsi perbandingan berhubungan dengan total order (tersembunyi) yang diinginkan.
Mungkin Anda menginginkan model Bradley-Terry-Luce . Jika demikian, ada banyak algoritme standar. Lihat jugahttps://cs.stackexchange.com/a/85204/755.
Mungkin Anda menginginkan beberapa sistem peringkat, seperti Elo, dll.
Mungkin Anda menginginkan sistem pemungutan suara berperingkat , seperti IRV, metode Condorcet, hitungan Borda, atau banyak lainnya. Mereka semua memiliki berbagai kekurangan dan pengorbanan. Ada bukti bahwa tidak ada sistem yang memiliki semua properti yang mungkin kita inginkan - lihat, misalnya, teorema Arrow dan masalah non-transitivitas (bahwa meskipun preferensi individu masing-masing teman Anda bersifat transitif, yaitu urutan total, maka tidak ada jaminan bahwa terdapat tatanan total global yang konsisten dengan semuanya).