Почему алгоритм Крускала находит минимальное остовное дерево, если оно жадно? Не является ли минимальным остовным деревом проблема глобальной оптимизации? Разве не то, чтобы быть жадным, так это то, что вы не найдете оптимального решения? Итак, как может Крускал найти минимальное связующее дерево, а также быть жадным?Почему алгоритм Крускала находит минимальное остовное дерево, если оно жадно?
Хорошо, давайте предположим, что вы правы, поэтому алгоритм Крускаля не находит оптимального решения. Пусть решение найдено по алгоритму Крускала S и оптимальному решению T.
Должно быть ребро e = (u, v), которое отображается на S, но не на T. Поскольку T является связующим деревом, должен быть путь между узлом u и узлом v.
Теперь мы должны заметить, что по крайней мере один край на пути u-v имеет вес не менее e. В противном случае алгоритм Крускаля выбрал бы все ребра на пути u-v вместо края e.
Это означает, что если мы удалим этот край и добавим e на решение T, решение не ухудшится. И поскольку мы предположили, что T является оптимальным, после этого изменения дерево по-прежнему является оптимальным. Если мы будем применять эту логику повторно, мы всегда можем сделать S.
Я не уверен, что вы имеете в виду.
Однако, википедия говорит:. Алгоритм
Крускала алгоритм минимального остовного дерева, которое находит край наименьшего возможного веса, который соединяет любые два дерева в лесу [1] Это жадный алгоритм в теории графов, так как он находит минимальное связующее дерево для связанного взвешенного графа, добавляя увеличивающиеся дуги затрат на каждом шаге. [1] Это означает, что он находит подмножество ребер, которые образуют дерево, которое включает в себя каждую вершину, где общий вес всех ребер в дереве минимизируется. Если граф не подключен, он находит минимальный остовный лес (минимальное связующее дерево для каждого подключенного компонента).
В то же время, около минимального покрывающего дерева, википедия говорит:
минимальное покрывающее дерево (МСТ) или минимальный вес связующего дерева представляет собой подмножество ребер связной кромки-взвешенный неориентированный граф, который соединяет все вершины вместе, без каких-либо циклов и с минимально возможным общим весом кромки. То есть это связующее дерево, сумма суммарного веса края которого как можно меньше. В более общем плане любой неориентированный граф (не обязательно связанный) имеет минимальный остовный лес, который является объединением минимальных связующих деревьев для его связных компонент.
Итак, комбинируя эти два: Kruskal в основном находит минимальное остовное дерево или лес, используя жадный подход поиска.
я мог постигать askings как следующий вопрос- Жадный не всегда является оптимальным, то почему алгоритм Крускала получает оптимальное решение? Так что на этот вопрос можно ответить в двух частях:
1. Предлагает ли алгоритм Kruskal оптимальное решение? Это уже ответил @miheyan.
2. Если жадный всегда дает оптимальное решение? В целом NO, Greedy не дает оптимального решения всегда, но существует множество проблем, для которых Greedy-подход дает оптимальное решение, а алгоритм Kruskal лежит в этом множестве.
Давайте рассмотрим проблему. Есть два игрока (игрок A и игрок B), которым дается куча денег с разным наименованием. Предположим, что есть 4 валютных банкноты со значениями - 100, 50, 20, 10. Игроки будут выбирать одну валютную ноту за раз, и они будут выбирать в качестве альтернативы. Игрок А начинает игру. Победителем будет тот, кто получает больше денег. Игроки играют оптимально. Кто выиграет игру? Теперь попытайтесь решить эту проблему с жадным подходом и посмотрите, дает ли жадный подход оптимальное решение или нет? Принимайте разные значения, разные примеры и выполняйте свою домашнюю работу.
Таким образом, нижняя строка - для набора проблем. Жадное решение всегда оптимально, но не для всех проблем. Надеюсь, это поможет!