В поисках псевдокода для расчета множества Смита и Шварца - PullRequest
Новая
       27

В поисках псевдокода для расчета множества Смита и Шварца

1 голос
/ 04 апреля 2019

Я читал Википедию о наборе Смита , наборе Шварца , Алгоритм Косараю , Алгоритм Тарьяна и сильно компонентные алгоритмы на основе путей ; однако мой опыт работы с такими алгоритмами… отсутствует. Википедия также говорит, что вы можете использовать версию алгоритма Косараджу для генерации множества Шварца - и что эти алгоритмы могут вычислять множество Смита.

В Википедии также есть некоторый псевдокод для алгоритма Тарьяна, но нет других; и это не характерно для этого относительно чувствительного приложения. Я также не уверен на 100%, что проще всего реализовать - в нем реализована наименьшая вероятность ошибок при реализации.

Мне бы хотелось, чтобы какой-то более прямой псевдокод охватывал вычисления множества Смита и Шварца по одному из этих алгоритмов, учитывая набор ранжированных бюллетеней. Мне легче понять концепции, когда у меня есть практический процесс, по которому я могу ходить. Я сам превращу это в реальный код.

Рассмотрим следующую структуру данных: 

Type Ballot {
  Array Votes[] {
    Candidate Candidate; // We do this in C#
    int Rank;
  }
}

Для набора бюллетеней каждый отдельный бюллетень будет содержать массив голосов, таких как: 

Ballot b.Votes[] =
  [ Vote(Alex.ID, 1),
    Vote(Chris.ID, 3),
    Vote(Sam.ID, 2) ];

Это соответствует голосованию избирателей Alex>Sam>Chris, и могут быть другие кандидаты, которые в равной степени менее предпочтительны, чем Крис.

Я полагаю, что первым шагом будет подсчет отдельных голосов и график победы. Например: если 100 избирателей оценивают Алекса выше Сэма (Алекс = 1, Сэм> = 2) и 50 избирателей оценивают Сэма выше Алекса, Алекс побеждает Сэма. Таким образом, я предполагаю, что будет структура данных как таковая: 

Type GraphNode {
  Candidate Candidate;
  GraphNode Array Defeats[];
  GraphNode Array Ties[];
  GraphNode Array DefeatedBy[];
}

При этом в GraphNode для Алекса в Defeats[] будет элемент, указывающий на GraphNode для Сэма, и наоборот.

Учитывая эти GraphNodes, что мне делать с ним для идентификации множеств Смита и Шварца?

Заранее спасибо.

1 Ответ

1 голос
/ 05 апреля 2019

Полагаю, Python достаточно близок к псевдокоду.

Допустим, у нас есть n кандидатов, пронумерованных от 0 до n - 1.

Сначала вы можете вычислить матрицу beats[i][j], равную True, если кандидат i превосходит кандидата j и False в противном случае.

Теперь вычислите транзитивное замыкание матрицы, используя алгоритм Флойда-Варшалла: 

for k in range(n):
    for i in range(n):
        for j in range(n):
            beats[i][j] = beats[i][j] or (beats[i][k] and beats[k][j])

После этого матрица имеет немного другое значение: beats[i][j] означает, что существует «путь биения» i -> c1 -> c2 -> ... -> j, такой, что i бьет c1, c1 бьет c2 и так далее до j.

Компоненты Schwartz - это те, в которых во всех парах i, j есть пути биения, идущие в обе стороны, и нет другого кандидата, который победил бы ни один из них (см. Раздел Википедии о свойствах, в которых упоминается top цикл ).

В основном для каждого кандидата i попробуйте построить вокруг него компонент, например: 

schwartz_components = []

for i in range(n):
    schwartz_component = {i}
    is_schwartz = True
    for j in range(n):
        if beats[j][i]:
            if beats[i][j]:
                schwartz_component.add(j)
            else:
                is_schwartz = False
    if is_schwartz:
         schwartz_components.append(schwartz_component)

schwartz_set = set.union(*schwartz_components)
print(schwartz_set)

Для набора Смита все будет немного по-другому, вам нужно начать с cannot_beat[i][j] = not beats[i][j], использовать Floyd-Warshall для этого, а затем построить набор вокруг каждого i, добавив всех кандидатов с путем к это через отношение cannot_beat.

Я думаю, что это будет примерно так (после шага Флойда-Варшалла): 

smith_candidates = []

for i in range(n):
    smith_candidate = {i}
    for j in range(n):
        if cannot_beat[i][j]:
            smith_candidate.add(j)
    smith_candidates.append(smith_candidate)

# Take the smallest candidate
smith_set = min(smith_candidates, key=len)

Возможно, где-то есть ошибка, но это примерно так.

...