상위 질문
타임라인
채팅
관점

슐츠 방법

위키백과, 무료 백과사전

Remove ads

슐츠 방법(Schulze method)은 1997년 마커스 슐츠가 개발한 선거 제도이다. 이 방법으로 승자들의 정렬된 목록을 만들어낼 수 있다.

예시

요약
관점

후보자가 5명(A, B, C, D, E)이고 투표자가 45명인 예시를 살펴보자.

자세한 정보 선호순서, 투표자수 ...
자세한 정보 d[*,A], d[*,B] ...
짝 대결 그래프
Thumb

경로의 강도(strength)는 가장 약한 고리(=노드)의 강도를 말한다. 다음 표는 후보자 각 쌍에 대해 한 후보자 X에서 다른 후보자 Y로 가는 최강 경로를 보여준다. 이들 최강경로에서 가장 약한 고리는 밑줄로 표시되어 있다.

자세한 정보 → A, → B ...
자세한 정보 p[*,A], p[*,B] ...

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

외부 링크

  • 위키미디어 공용에 슐츠 방법 관련 미디어 분류가 있습니다.
Loading related searches...

Wikiwand - on

Seamless Wikipedia browsing. On steroids.

Remove ads