#algorithm #graph #greedy
#алгоритм #График #жадный
Вопрос:
Я должен выяснить пороговое значение осадков, которые блокируют трафик.
Итак, я должен напечатать пороговое значение осадков, чтобы блокировать трафик.
например)
3 3
0 1 2
1 2 3
0 2 6
вывод: 3
Существуют ли какие-либо хорошие алгоритмы или ключевые слова для этой проблемы?
Спасибо
Комментарии:
1. Что вы подразумеваете под «блокировкой трафика»? Отключить сеть?
2. Да, виды. Для примера 1, когда количество осадков равно 3, город (вершины)-1 не связан с другими узлами. 0-> 1 (отключен), 1-> 2 (отключен), в противном случае 0-> 2 (подключен, потому что у него на 3 емкости больше)
3. Посмотрите, как работают алгоритмы минимального связующего дерева, они могут помочь вам определить, когда график отключается
Ответ №1:
Найдите связующее дерево с максимальной общей пропускной способностью. Наименьшая пропускная способность ребра в этом дереве является порогом, при котором сеть отключается.
Дерево «максимальной емкости» совпадает с остовным деревом минимального веса с весами ребер, равными отрицательной емкости, поэтому вы можете найти это дерево, используя алгоритм Крускала или Прима.
Алгоритм Крускала, очевидно, делает именно то, что вы хотите — обрабатывает ребра в порядке убывания пропускной способности, пока сеть не будет подключена:https://en.wikipedia.org/wiki/Kruskal’s_algorithm
Если вы не знакомы со структурой данных disjoint set, удивительно то, что это очень быстро.
Любой алгоритм для нахождения минимального связующего дерева также выполнит ту же работу, но это требует небольшой работы, чтобы доказать это.
Комментарии:
1. Но как я могу реализовать это в графе с направленным весом? Насколько я знаю, связующее дерево работает на косвенном графике..,
2. Все дороги односторонние?
3. Ну, в принципе, ничего не гарантировано. Дорога является направленной, но также возможно двунаправленное движение с разным весом.
4. Тогда вам понадобится другой алгоритм, и снова становится трудно сказать, чего вы хотите. В примере 1, когда количество осадков равно 2, вы больше не можете добраться до v1 через какие-либо направленные ребра, и я не знаю, почему это не будет считаться заблокированным трафиком.