Tutarsız bir ilişkiden tam veya kısmi bir sipariş üretmek
Bir dizi öğeden toplam bir düzen oluşturmak istediğimi düşünün $E$, ancak karşılaştırma işlevi deterministik olmayan sonuçlar üretir. Karşılaştırma işlevinin tekrarlanan uygulamasıyla, kümedeki her bir öğenin en az bir kez temsil edileceği şekilde, öğe çiftlerinin bir listesini (e, e) oluşturuyorum.
Bu girdiyi toplam sipariş oluşturmak için nasıl kullanabilirim? Burada uygulanabilecek algoritma sınıfı nedir?
Daha fazla netlik için somut bir örnek vereceğim.
En iyi pizza malzemeleri hangileridir?
Öğelerim $E$ bazı popüler pizza soslarını içerir: biberli, peynir, mantar, ananas, dolmalık biber, zeytin.
Daha sonra arkadaşlarımın her biri için rastgele boyutlandırılmış sos alt kümeleri seçerim ve arkadaşımdan bunları en iyiden en kötüye doğru sıraya koymasını isterim. Arkadaşlarım görev bilinciyle cevap verir ve algoritmam için girdi oluşturur:
- peynir, sucuk, zeytin
- peynir, ananas, mantar, zeytin
- dolmalık biber, mantar, zeytin
- biberli, peynirli, zeytinli
- peynir, dolmalık biber
Burada belirsiz bir düzen var gibi görünüyor (herkes zeytinin en kötüsü olduğunu kabul ediyor) ama arkadaşlarım hangisinin daha iyi pizza olduğu konusunda fikir birliğine varamadı: peynir veya sucuk. Girdilerde öğelerin nerede oluştuğunu ve ne sıklıkla meydana geldiklerini göz önünde bulundurarak, muhtemelen buna benzer bir sipariş üretirdim.
- peynir> biberli> dolmalık biber> ananas> mantar> zeytin
Bunu nasıl resmileştireceğimi ve çok daha büyük girdiler için çalışmasını nasıl sağlayacağımı bilmiyorum.
Çözümün muhtemelen grafikler ve ağırlıklı kenarlar içerdiğini düşünüyorum, ancak bunun adlandırılmış bir çalışma alanı olup olmadığını anlamak için grafik algoritmalarına yeterince aşinalığım yok. Zaten "topolojik sıralama" ile karşılaştım, ancak bu yalnızca yönlendirilmiş döngüsel olmayan grafikler için işe yarıyor ve özellikle bir DAG üretemeyen girdilerle ilgileniyorum.
Ayrıca bu sorunun seçilmiş temsilciler için oy vermeye benzediğini fark ettim. Aslında aynı sorun sınıfı mı?
Yanıtlar
Daha fazla bağlam ve daha fazla modelleme olmadan söylemek zor. Karşılaştırma fonksiyonunun sonuçlarının istenen toplam sıra (gizli) ile nasıl ilişkili olduğuna dair bazı varsayımlar gerektirecektir.
Bradley-Terry-Luce modelini isteyebilirsiniz . Eğer öyleyse, birçok standart algoritma vardır. Ayrıca bakınızhttps://cs.stackexchange.com/a/85204/755.
Elo vb. Gibi bir sıralama sistemi isteyebilirsiniz.
IRV, Condorcet yöntemi, Borda sayısı veya diğerleri gibi sıralı bir oylama sistemi isteyebilirsiniz . Hepsinin çeşitli kusurları ve ödünleri vardır. Hiçbir sistemin isteyebileceğimiz tüm özelliklere sahip olmayacağına dair bir kanıt var - örneğin, Arrow'un teoremi ve geçişsizlik sorunu ( arkadaşınızın bireysel tercihlerinin her biri geçişli olsa bile, yani bir toplam düzen, o zaman hepsiyle tutarlı olan küresel bir toplam düzenin var olduğuna dair hiçbir garanti yoktur).