상위 질문
타임라인
채팅
관점
슐츠 방법
위키백과, 무료 백과사전
Remove ads
슐츠 방법(Schulze method)은 1997년 마커스 슐츠가 개발한 선거 제도이다. 이 방법으로 승자들의 정렬된 목록을 만들어낼 수 있다.
예시
요약
관점
후보자가 5명(A, B, C, D, E)이고 투표자가 45명인 예시를 살펴보자.
- 짝 대결 그래프

경로의 강도(strength)는 가장 약한 고리(=노드)의 강도를 말한다. 다음 표는 후보자 각 쌍에 대해 한 후보자 X에서 다른 후보자 Y로 가는 최강 경로를 보여준다. 이들 최강경로에서 가장 약한 고리는 밑줄로 표시되어 있다.
E 후보자는, 모든 다른 후보자 X에 대하여 p[E,X] ≥ p[X,E]이므로 잠재적 승자이다.
- 25 = p[E,A] > p[A,E] = 24이므로 후보자 E는 후보자 A보다 선호된다.
- 28 = p[E,B] > p[B,E] = 24이므로 후보자 E는 후보자 B보다 선호된다.
- 28 = p[E,C] > p[C,E] = 24이므로 후보자 E는 후보자 C보다 선호된다.
- 31 = p[E,D] > p[D,E] = 24이므로 후보자 E는 후보자 D보다 선호된다.
- 28 = p[A,B] > p[B,A] = 25이므로 후보자 A는 후보자 B보다 선호된다.
- 28 = p[A,C] > p[C,A] = 25이므로 후보자 A는 후보자 C보다 선호된다.
- 30 = p[A,D] > p[D,A] = 25이므로 후보자 A는 후보자 D보다 선호된다.
- 29 = p[C,B] > p[B,C] = 28이므로 후보자 C는 후보자 B보다 선호된다.
- 29 = p[C,D] > p[D,C] = 28이므로 후보자 C는 후보자 D보다 선호된다.
- 33 = p[B,D] > p[D,B] = 28이므로 후보자 B는 후보자 D보다 선호된다.
그러므로 슐츠 순위는 E > A > C > B > D 순이다.
Remove ads
구현
후보자 수를 C라고 하자. 그러면 플로이드-워셜 알고리듬으로 가장 강력한 경로의 강도를 계산할 수 있다. 아래의 파스칼 유사코드는 그러한 경로 판단을 나타낸 것이다.
- 입력: d[i,j]는 i후보를 j후보보다 강력하게 선호하는 투표자 수이다.
- 출력: p[i,j]는 i후보에서 j후보로 가는 가장 강력한 경로의 강도이다.
for i : = 1 to C
begin
for j : = 1 to C
begin
if ( i ≠ j ) then
begin
if ( d[i,j] > d[j,i] ) then
begin
p[i,j] : = d[i,j]
end
else
begin
p[i,j] : = 0
end
end
end
end
for i : = 1 to C
begin
for j : = 1 to C
begin
if ( i ≠ j ) then
begin
for k : = 1 to C
begin
if ( i ≠ k ) then
begin
if ( j ≠ k ) then
begin
p[j,k] : = max ( p[j,k], min ( p[j,i], p[i,k] ) )
end
end
end
end
end
end
Remove ads
외부 링크
위키미디어 공용에 슐츠 방법 관련 미디어 분류가 있습니다.
Wikiwand - on
Seamless Wikipedia browsing. On steroids.
Remove ads