Создание худших сценариев с помощью алгоритма Крускала
У меня есть реализация алгоритма Крускала в C ++ (с использованием несвязанной структуры набора данных). Я пытаюсь найти возможные способы создания сценариев худшего сценария для общего времени выполнения алгоритма. Однако я запутался в том, что может заставить алгоритм привести к наихудшему сценарию при попытке создания контрольных примеров, и подумал, может ли кто-нибудь здесь знать о возможных сценариях, которые действительно могут заставить алгоритм Крускала бороться.
На данный момент основным тестом, который я рассматривал, который теоретически может проверить границы алгоритма Крускала, будут тестовые случаи, когда все веса одинаковы. Пример будет выглядеть следующим образом:
4 4
(4, 4) 4 //(4,4) vertex and weight = 4
(4, 4) 4
(4, 4) 4
(4, 4) 4
В итоге я сталкиваюсь с тем, что независимо от того, что я делаю, если я пытаюсь замедлить алгоритм, я просто получаю минимальное связующее дерево и в итоге не могу проверить границы алгоритма.
Решение
Чтобы подчеркнуть алгоритм Крускала, вам нужен граф с максимально возможным количеством избыточных ребер и по крайней мере с одним необходимым ребром, которое будет считаться последним (поскольку алгоритм Крускала сортирует ребра по весу). Вот пример.
Ребра с весом 1 необходимы, и будут приняты в первую очередь. Ребра с весом 2 являются избыточными и заставят алгоритм Крускала тратить время, прежде чем добраться до края с весом 3.
Обратите внимание, что время выполнения алгоритма Крускала определяется в первую очередь временем сортировки ребер по весу. Добавление дополнительных избыточных ребер среднего веса увеличит время сортировки, а также время поиска.
Другие решения
Алгоритм Крускала состоит из двух этапов — сортировка ребер и выполнение поиска объединения. Если вы реализуете второй этап с использованием леса несвязанных множеств и применяете сжатие и объединение путей по эвристике рангов, сортировка будет намного медленнее, чем на втором этапе. Таким образом, чтобы создать наихудший сценарий для Kruskal, вы должны просто сгенерировать наихудший сценарий для используемого алгоритма сортировки. Если вы используете встроенную сортировку, у нее есть оптимизация, которая фактически заставит ее работать намного быстрее для уже отсортированного массива.