Разделение игроков на «победителей» и «проигравших»: как доказать, что жадное решение дает оптимальный результат?

Question

У меня есть проблема, которая гласит следующее:

n игроков (где n четно) играют в игры друг против друга.Каждый не обязательно будет играть, но игрок может играть против кого-то еще только один раз.Если два человека решат играть друг против друга, у нас один проигравший и один победитель.Затем я хочу разделить своих n игроков на два набора размера n / 2: победители (W) и проигравшие (L).Я хочу, чтобы все игроки в моем наборе победителей никогда не проигрывали против кого-то из моего набора проигравших.

Это невозможно, напр.для 4 игроков и игр p1 выиграл против p2, p2 выиграл против p3, p3 выиграл против p4 и p4 выиграл против p1, тогда невозможно разделить игроков на W и L. Я делаю следующее лучшее, что я хотел бысвести к минимуму мою ошибку: количество пар игроков, в которых игрок в W проиграл игроку в L (не играть друг против друга - это не потеря).

Я (думаю) я нашелжадное решение этой проблемы.Я просто сортирую игроков по количеству проигрышей и помещаю людей с наименьшими потерями в мой набор W и заполняю остаток до L. Как мне доказать, что мой жадный подход действительно оптимален?Я провел несколько случайных тестов и могу показать, что мой подход даст реальное решение, но я не знаю, как показать, что это фактически минимизирует мою ошибку.

Answer 1

Рассмотрим следующие результаты:

Winner    Loser
Adam      John
Bob       John
John      Charles
John      David
John      Ernest
John      Frank
John      George

Мы подсчитываем потери и сортируем в порядке возрастания:

Player    Losses
Adam      0
Bob       0
Charles   1
David     1
Ernest    1
Frank     1
George    1
John      2

Ваш алгоритм делит игроков следующим образом:

Winners    Losers
Adam       Ernest
Bob        Frank
Charles    George
David      John

Ошибки: (Чарльз, Джон) и (Дэвид, Джон);Есть две ошибки.Вместо этого рассмотрим следующее деление:

Winners    Losers
Adam       David
Bob        Ernest
Charles    Frank
John       George

В этом делении нет ошибки: нет победителя, проигравшего проигравшему.Это лучшее разделение с меньшим количеством ошибок;поэтому ваш алгоритм, как указано, не является оптимальным.

Основная проблема вашего алгоритма заключается в том, что он учитывает только количество потерь;Плодовитые игроки могут показаться хуже в этом алгоритме, чем на самом деле, просто потому, что у них больше потерь, чем у других, несмотря на то, что, возможно, у них гораздо больше выигрышей.

Answer 2

Ваш жадный алгоритм не оптимален.Сбой для:

 W      L
===    ===
 A  vs  x
 B  vs  y
 C  vs  z
 B  vs  A
 C  vs  A
 x  vs  y

Оптимальным является раздел W = (A, B, C), L = (x, y, z), но вы положите A в набор проигравших, потому чтоу него 2 потери.

Вы говорите, что сделали несколько рандомизированных тестов.Как вы убедились, что ваш жадный алгоритм дал правильные результаты для этих тестов?