Algorytm porównywania oparty na porównaniu

Question

Chciałbym uszeregować lub posortować kolekcję przedmiotów (o potencjalnie większych rozmiarach niż 100 000), gdzie przedmioty w kolekcji nie mają wewnętrznej (porównywalnej) wartości, zamiast tego wszystko, co mam, to porównania między dowolnymi dwie pozycje, które zostały dostarczone przez użytkowników w subiektywny sposób.

Przykład: Rozważ kolekcję z elementami [a, b, c, d] i porównania użytkowników: b > a, a > d, d > c. Prawidłowa kolejność tej kolekcji to [b, a, d, c].

Ten przykład jest prosty, jednak nie może być bardziej skomplikowane przypadki:

• Ponieważ porównania są subiektywne, użytkownik może również powiedzieć, że c > b. W takim przypadku spowoduje to konflikt z powyższym zamówieniem.
• Możesz także nie mieć porównań, które "łączą" wszystkie elementy, tj. b > a, d > c. W takim przypadku zamówienie jest niejednoznaczne. Może to być [b, a, d, c] lub [d, c, b, a]. W takim przypadku zamawianie jest dopuszczalne.

W miarę możliwości dobrze byłoby uwzględnić wiele przypadków tego samego porównania i zwiększyć masę zdarzeń o większej liczbie wystąpień. Ale rozwiązanie bez tego warunku byłoby nadal dopuszczalne.

Podobną aplikację tego algorytmu wykorzystała aplikacja Zapperberga w FaceMash, gdzie oceniał ludzi na podstawie porównań (o ile dobrze zrozumiałem), ale nie byłem w stanie znaleźć tego, czym był ten algorytm.

Czy istnieje już algorytm, który może rozwiązać powyższy problem? Nie chciałbym spędzać wysiłku próbując wymyślić jeden, jeśli tak jest. Jeśli nie ma określonego algorytmu, czy są jakieś rodzaje algorytmów lub technik, które możesz wskazać mi?

Answer 1

Jest to problem, który już wystąpił w innej arenie: konkurencyjnych gier! Tutaj także celem jest przypisanie każdemu graczowi globalnej "rangi" na podstawie serii porównań 1 do 1. Trudność polega oczywiście na tym, że porównania nie są przechodnie (w twoim pytaniu biorę "subiektywny" w znaczeniu "dostarczony przez człowieka"). Kasparov bije bity Fischera (nie znamy innego szachisty!), Bob pokonuje Kasparowa, potencjalnie.

To czyni bezużytecznymi algorytmy, które opierają się na przechodniości (tj. a > b and b > c => a > c), gdy kończy się to (prawdopodobnie) bardzo cyklicznym wykresem.

Kilka systemów oceny zostało opracowanych w celu rozwiązania tego problemu.

Najbardziej znanym systemem jest prawdopodobnie Elo algorithm/score dla konkurencyjnych szachistów. Jego potomkowie (na przykład Glicko rating system) są bardziej wyrafinowani i biorą pod uwagę właściwości statystyczne rekordu wygranych/strat - innymi słowy, jak wiarygodne są oceny? Jest to podobne do twojego pomysłu ważenia bardziej ciężkich płyt z większą liczbą "gier". Glicko stanowi także podstawę dla TrueSkill system używanego w Xbox Live do gier wideo dla wielu graczy.

Answer 2

Być może zainteresuje Cię minimalny problem z układem sprzężenia zwrotnego. Zasadniczo problemem jest znalezienie minimalnej liczby porównań, które "pójdą w złą stronę", jeśli elementy są uporządkowane liniowo w pewnym porządku. Jest to to samo, co ustalenie minimalnej liczby krawędzi, które muszą zostać usunięte, aby wykres był acykliczny. Niestety, rozwiązanie problemu jest bardzo trudne.

Kilka linków, które omawiają problem:

http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.86.8157&rep=rep1&type=pdf

http://en.wikipedia.org/wiki/Feedback_arc_set

Answer 3

google na to uwagę, szukać rozdziale 12.3, sortowanie topologiczne i głębi fi rst Szukaj

http://www.cs.cmu.edu/~avrim/451f09/lectures/lect1006.pdf

Twój zestaw relacjach opisują skierowany graf acykliczny (oby acykliczny), a więc wykres sortowanie topologiczne jest dokładnie czego potrzebujesz.