일치하지 않는 관계에서 전체 또는 부분 주문 생성
일련의 요소에서 전체 주문을 구성하고 싶다고 가정 해 보겠습니다. $E$그러나 비교 함수는 비 결정적 결과를 생성합니다. 비교 함수를 반복적으로 적용하여 요소 쌍 (e, e) 목록을 생성하여 세트의 각 요소가 한 번 이상 표시되도록합니다.
이 입력을 사용하여 총 주문을 생성하려면 어떻게해야합니까? 여기에 적용 할 수있는 알고리즘의 종류는 무엇입니까?
더 명확하게하기 위해 구체적인 예를 제공하겠습니다.
최고의 피자 토핑은 무엇입니까?
내 요소 세트 $E$ 페퍼로니, 치즈, 버섯, 파인애플, 벨 페퍼, 올리브 등 인기있는 피자 토핑이 포함됩니다.
그런 다음 각 친구에 대해 무작위 크기의 토핑 하위 집합을 선택하고 친구에게 최고에서 최악의 순서로 정렬하도록 요청합니다. 내 친구들은 성실하게 답장하고 내 알고리즘에 대한 입력을 만듭니다.
- 치즈, 페퍼로니, 올리브
- 치즈, 파인애플, 버섯, 올리브
- 벨 페퍼, 버섯, 올리브
- 페퍼로니, 치즈, 올리브
- 치즈, 벨 페퍼
여기에는 모호한 주문이있는 것 같지만 (모든 사람이 올리브가 최악이라는 데 동의 함) 내 친구들은 더 나은 피자 토핑 인 치즈 또는 페퍼로니에 대한 합의에 도달하지 못했습니다. 입력에서 항목이 발생하는 위치와 발생 빈도를 고려하면 아마도 이와 같은 주문을 생성 할 것입니다.
- 치즈> 페퍼로니> 벨 페퍼> 파인애플> 버섯> 올리브
나는 이것을 공식화하고 훨씬 더 큰 입력에 대해 작동하도록 만드는 방법을 잘 모르겠습니다.
이 솔루션은 아마도 그래프와 가중 모서리를 포함한다고 생각하지만, 이것이 명명 된 연구 영역인지 여부를 인식 할 수있는 그래프 알고리즘에 대한 충분한 지식이 부족합니다. 나는 이미 "토폴로지 정렬"을 발견했지만 방향성 비순환 그래프 에서만 작동하며 특히 DAG를 생성 할 수없는 입력에 관심이 있습니다.
나는 또한이 문제가 선출 된 대표에 대한 투표와 유사하다는 것을 알아 차렸다. 사실 같은 종류의 문제입니까?
답변
더 많은 맥락과 더 많은 모델링 없이는 말하기가 어렵습니다. 비교 함수의 결과가 (숨겨진) 원하는 총 주문과 어떻게 관련되는지에 대한 몇 가지 가정이 필요합니다.
Bradley-Terry-Luce 모델을 원할 수도 있습니다 . 그렇다면 많은 표준 알고리즘이 있습니다. 또한보십시오https://cs.stackexchange.com/a/85204/755.
Elo 등과 같은 순위 시스템을 원할 수도 있습니다.
IRV, Condorcet 방법, Borda 개수 또는 기타 여러 가지와 같은 순위 투표 시스템을 원할 수 있습니다. 그들은 모두 다양한 결점과 장단점이 있습니다. 어떤 시스템이 우리가 원하는 수있는 모든 속성이 없다는 것을 증거가있다 - 참조, 예를 들어, 화살표의 정리 와 비 이행 성의 문제 (즉, 친구의 개인 환경 설정의 각각의 전이, 즉, 전체 순서, 다음 경우에도 그들 모두와 일치하는 글로벌 총 주문이 존재한다는 보장은 없습니다).