Tworzenie całkowitego lub częściowego porządku z niespójnej relacji
Wyobraź sobie, że chcę skonstruować całkowite zamówienie z zestawu elementów, $E$, ale funkcja porównania daje wyniki, które nie są deterministyczne. Tworzę listę par elementów (e, e) poprzez wielokrotne zastosowanie funkcji porównania, tak aby każdy element w zestawie był reprezentowany przynajmniej raz.
Jak mogę użyć tych danych wejściowych, aby uzyskać całkowite zamówienie? Jaka jest klasa algorytmów, które można tutaj zastosować?
Dla większej jasności podam konkretny przykład.
Jakie są najlepsze dodatki do pizzy?
Mój zestaw elementów $E$ zawiera kilka popularnych dodatków do pizzy: pepperoni, ser, pieczarki, ananas, papryka, oliwka.
Następnie dla każdego z moich znajomych wybieram podzbiory dodatków o losowych rozmiarach i proszę przyjaciela, aby ułożył je w kolejności od najlepszego do najgorszego. Moi przyjaciele posłusznie odpowiadają i tworzą dane wejściowe dla mojego algorytmu:
- ser, pepperoni, oliwka
- ser, ananas, pieczarki, oliwka
- papryka, grzyby, oliwka
- pepperoni, ser, oliwka
- ser, papryka
Wydaje się, że jest tu niejasna kolejność (wszyscy zgadzają się, że oliwki są najgorsze), ale moi przyjaciele nie doszli do porozumienia co do tego, która z pizzy jest lepsza: ser czy pepperoni. Biorąc pod uwagę, gdzie pojawiają się pozycje w wejściach i jak często się pojawiają, prawdopodobnie stworzyłbym takie zamówienie.
- sery> pepperoni> papryka> ananas> pieczarki> oliwka
Po prostu nie jestem pewien, jak sformalizować to i sprawić, by działało dla znacznie większych nakładów.
Myślę, że rozwiązanie prawdopodobnie obejmuje wykresy i wyważone krawędzie, ale brakuje mi wystarczającej znajomości algorytmów grafowych, aby rozpoznać, czy jest to nazwany obszar badań. Natknąłem się już na „sortowanie topologiczne”, ale działa ono tylko w przypadku ukierunkowanych grafów acyklicznych i jestem szczególnie zainteresowany danymi wejściowymi, które nie mogą wytworzyć DAG.
Zauważyłem też, że ten problem wydaje się podobny do głosowania na wybranych przedstawicieli. Czy w rzeczywistości jest to ta sama klasa problemów?
Odpowiedzi
Trudno powiedzieć bez większego kontekstu i większego modelowania. Będzie to wymagało pewnych założeń dotyczących tego, jak wyniki funkcji porównania odnoszą się do (ukrytego) pożądanego porządku całkowitego.
Możliwe, że chcesz model Bradley-Terry-Luce . Jeśli tak, istnieje wiele standardowych algorytmów. Zobacz teżhttps://cs.stackexchange.com/a/85204/755.
Możliwe, że chcesz mieć jakiś system rankingowy, taki jak Elo itp.
Możliwe, że chcesz mieć rankingowy system głosowania , taki jak IRV, metoda Condorcet, licznik Borda lub dowolny z wielu innych. Wszystkie mają różne wady i kompromisy. Jest dowód na to, że żaden system nie będzie miał wszystkich właściwości, jakich byśmy chcieli - zobacz np . Twierdzenie Arrowa i problem nieprzechodniości (że nawet jeśli indywidualne preferencje twojego przyjaciela są przechodnie, tj. nie ma gwarancji, że istnieje globalny porządek całkowity, który jest zgodny z nimi wszystkimi).