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

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

В Википедии также есть некоторый псевдокод для алгоритма Тарьяна, но не для других; и это не относится к этому относительно чувствительному приложению. Я также не уверен на 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, что мне делать с ними, чтобы идентифицировать множества Смита и Шварца?

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


algorithm voting pseudocode
person John Moser    schedule 04.04.2019    source источник
comment
Насколько это должно быть эффективно? В статьях Википедии также упоминается алгоритм Флойда-Уоршалла, который будет медленнее, но гораздо проще в реализации.   -  person gus    schedule 04.04.2019
comment
Если это та же временная сложность, то все в порядке. Скорее всего, максимальный размер графа всегда будет равен 9, поэтому верхняя граница многократного пересчета любого набора будет равна 7 прогонам. Скорее всего, подойдет любой из этих алгоритмов, даже O(n^3).   -  person John Moser    schedule 05.04.2019
comment
На таком маленьком графике можно даже попробовать все подмножества, всего 2^9 = 512 возможностей. Тем не менее подход O(n^3) Флойда-Уоршалла может быть даже проще.   -  person gus    schedule 05.04.2019
comment
Я не уверен, что понимаю, как применим Флойд-Уоршалл. Он определяет кратчайший путь, но я смотрю на сильно связанные компоненты. Если A побеждает B, B побеждает C, C побеждает A, и каждый из {A,B,C} побеждает все {D,E,F,G}, тогда набор Смита равен {A,B,C}. Я полагаю, что если C связан только с A, набор Смита — это {A,B,C}, а набор Шварца — {A}.   -  person John Moser    schedule 05.04.2019

Ответы (1)


arrow_upward
2
arrow_downward

Я думаю, что 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.

Компоненты Шварца — это те, в которых все пары i, j имеют пути биения в обе стороны, и нет другого кандидата, который превосходит любой из них (см. раздел Википедии о свойствах, в которых упоминается верхний цикл).

По сути, для каждого кандидата 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], использовать для этого Флойда-Уоршалла, а затем построить набор вокруг каждого 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)

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

person gus    schedule 04.04.2019
comment
Ага! Что помогает. Итак, если я правильно понимаю, первая итерация k находит только вещи, которые сразу побеждают друг друга (если A побеждает B побеждает C, мы не знаем, что A побеждает C); но для (n) узлов он повторно проходит граф (n) раз, и на проходе (k) мы идентифицировали все пути ударов (k) длиной. Да, хорошо, это сработает, и это чертовски просто. Спасибо! - person John Moser; 05.04.2019