Построение графа

Question

Я работал над интересной проблемой из своего урока информатики (не домашней работы). Вопрос в том, что турнир продолжается. Если у каждого игрока есть 2 «характеристики», сила и выносливость, то один игрок побьет другого, если и только если его сила и выносливость больше, чем у другого. Как бы я построить график, чтобы показать это? Таким образом, каждый игрок, который доминирует над другим доктором aws, имеет преимущество между ними.

Очевидно, что существует алгоритм O (n ^ 2): просто попробуйте каждый попарно протестировать и нарисовать преимущество, если есть доминирование. Но есть ли более умный способ? Например, если игрок A доминирует над B, а B доминирует над C, то A доминирует над C и тестирование не требуется. Спасибо.

Answer 1

Отношение "доминирует" определяет частичный порядок , поэтому это тесно связано с проблемой сортировки частично упорядоченного множества (poset). Это не та же проблема, что и у вас, потому что вы не хотите размещать узлы в некотором отсортированном порядке - вы хотите найти все ребра. Но они являются связанными проблемами, потому что оба хотят использовать преимущество переходного свойства для тестирования меньшего количества пар узлов.

Сортировка поозет тем быстрее, чем больше ребер, потому что чем больше ребер, тем больше выгоды от переходного свойства, и требуется меньше тестов. В худшем случае сортировка poset занимает Θ (n ² ), когда есть Θ (n) узлов без ребер между ними.

Однако, поскольку ваш вывод должен быть графом с для всех ребер также потребуется Θ (n ² ), чтобы на самом деле создать вывод в противоположном случае, когда имеется много ребер. График с ребрами Θ (n ² ) не может быть выведен за меньшее время, чем это.

Так что даже при использовании умного алгоритма, потребуется четыре квадрата c времени, когда график имеет немного ребер, и это также займет квадратичное c время, когда граф имеет много ребер. Учитывая это, алгоритм грубой силы, вероятно, в порядке.