Produzindo um pedido total ou parcial a partir de uma relação inconsistente
Imagine que eu queira construir um pedido total de um conjunto de elementos, $E$, mas a função de comparação produz resultados não determinísticos. Eu produzo uma lista de pares de elementos (e, e) por meio da aplicação repetida da função de comparação, de modo que cada elemento do conjunto seja representado pelo menos uma vez.
Como posso usar essa entrada para produzir um pedido total? Qual é a classe de algoritmos que pode ser aplicada aqui?
Para maior clareza, fornecerei um exemplo concreto.
Quais são as melhores coberturas de pizza?
Meu conjunto de elementos $E$ inclui algumas coberturas populares de pizza: calabresa, queijo, cogumelo, abacaxi, pimentão, azeitona.
Em seguida, para cada um dos meus amigos, eu escolho subconjuntos de coberturas de tamanhos aleatórios e peço ao meu amigo para colocá-los em ordem do melhor para o pior. Meus amigos respondem obedientemente e criam a entrada para meu algoritmo:
- queijo, calabresa, azeitona
- queijo, abacaxi, cogumelo, azeitona
- bellpepper, cogumelo, azeitona
- calabresa, queijo, azeitona
- queijo, bellpepper
Parece haver uma ordem difusa aqui (todos concordam que azeitonas são as piores), mas meus amigos não chegaram a um consenso sobre qual é a melhor cobertura de pizza: queijo ou pepperoni. Considerando onde os itens ocorrem nas entradas e com que frequência ocorrem, provavelmente produziria um pedido mais ou menos assim.
- queijo> pepperoni> bellpepper> abacaxi> cogumelo> azeitona
Só não tenho certeza de como formalizar isso e fazer funcionar para entradas muito maiores.
Acho que a solução provavelmente envolve gráficos e arestas ponderadas, mas não tenho familiaridade suficiente com algoritmos de gráfico para reconhecer se essa é uma área de estudo nomeada. Já me deparei com "classificação topológica", mas isso só funciona para gráficos acíclicos direcionados e estou especificamente interessado em entradas que não podem produzir um DAG.
Também percebi que esse problema parece semelhante ao voto para representantes eleitos. É, de fato, a mesma classe de problema?
Respostas
É difícil dizer sem mais contexto e mais modelagem. Isso exigirá algumas suposições sobre como os resultados da função de comparação se relacionam com a ordem total desejada (oculta).
É possível que você queira o modelo Bradley-Terry-Luce . Nesse caso, existem muitos algoritmos padrão. Veja tambémhttps://cs.stackexchange.com/a/85204/755.
É possível que você queira algum sistema de classificação, como Elo, etc.
É possível que você queira um sistema de votação classificado , como IRV, método Condorcet, contagem de Borda ou qualquer um de muitos outros. Todos eles têm várias falhas e vantagens e desvantagens. Há uma prova de que nenhum sistema terá todas as propriedades que podemos desejar - veja, por exemplo, o teorema de Arrow e o problema da não transitividade (que mesmo se cada uma das preferências individuais do seu amigo for transitiva, ou seja, uma ordem total, então não há garantia de que exista uma ordem global total que seja consistente com todos eles).