У нас есть ориентированный граф (без весов), G(V, E), с двумя вершинами s и t, так что входящая степень s и исходящая степень t равны 0. мы хотим найти максимальное количество путей с разными ребрами от s до t. с помощью какого алгоритма мы можем это сделать. Беллман-Форд, Дийкестра, Хаффман и Network Flow. Я думаю, что Хаффман настолько неактуален, но как насчет других? Я думаю, что Network Flow — это ответ, но я понятия не имею, почему? стекеры, помогите пожалуйста!
Bellman-Ford или Network Flow для поиска максимального количества различных путей?
17.03.2015
- Что отличает два пути? Если у них нет общих ребер, или у них не должно быть общих узлов? 17.03.2015
- (В любом случае, сетевой поток является ответом, но более очевидным является только непересекающееся ребро.) 17.03.2015
- @IVlad, теперь все в порядке, см. правки. 17.03.2015
- @DavidEisenstat, хорошо... 17.03.2015
Ответы:
1
Вы можете сделать это с помощью Network Flow. Он даже рассказывает, как в Википедии:
Максимальный непересекающийся путь
Для заданного ориентированного графа G = (V, E) и двух вершин s и t нам нужно найти максимальное количество реберно-непересекающихся путей из s в t. Эту задачу можно преобразовать в задачу о максимальном потоке, построив сеть N = (V, E) из G, где s и t являются источником и стоком N соответственно, и назначив каждому ребру единичную пропускную способность.
Интуиция, стоящая за этим, заключается в том, что алгоритмы максимального потока в основном решают вашу проблему при поиске увеличивающих путей. Что такое увеличивающий путь, лучше всего объясняется в этот вопрос SO Я думаю, Ивайло Странджев:
Увеличивающий путь — это простой путь — путь, не содержащий циклов — через граф, использующий только ребра с положительной пропускной способностью от источника к приемнику. Таким образом, приведенное выше утверждение в чем-то очевидно — если вы не можете найти путь от источника к приемнику, который использует только ребра с положительной пропускной способностью, то поток не может быть увеличен (кстати, доказательство этого утверждения не так просто).
17.03.2015
Новые материалы
Кластеризация: более глубокий взгляд
Кластеризация — это метод обучения без учителя, в котором мы пытаемся найти группы в наборе данных на основе некоторых известных или неизвестных свойств, которые могут существовать. Независимо от..
Как написать эффективное резюме
Предложения по дизайну и макету, чтобы представить себя профессионально
Вам не позвонили на собеседование после того, как вы несколько раз подали заявку на работу своей мечты? У вас может..
Частный метод Python: улучшение инкапсуляции и безопасности
Введение
Python — универсальный и мощный язык программирования, известный своей простотой и удобством использования. Одной из ключевых особенностей, отличающих Python от других языков, является..
Как я автоматизирую тестирование с помощью Jest
Шутка для победы, когда дело касается автоматизации тестирования
Одной очень важной частью разработки программного обеспечения является автоматизация тестирования, поскольку она создает..
Работа с векторными символическими архитектурами, часть 4 (искусственный интеллект)
Hyperseed: неконтролируемое обучение с векторными символическими архитектурами (arXiv)
Автор: Евгений Осипов , Сачин Кахавала , Диланта Хапутантри , Тимал Кемпития , Дасвин Де Сильва ,..
Понимание расстояния Вассерштейна: мощная метрика в машинном обучении
В обширной области машинного обучения часто возникает необходимость сравнивать и измерять различия между распределениями вероятностей. Традиционные метрики расстояния, такие как евклидово..
Обеспечение масштабируемости LLM: облачный анализ с помощью AWS Fargate и Copilot
В динамичной области искусственного интеллекта все большее распространение получают модели больших языков (LLM). Они жизненно важны для различных приложений, таких как интеллектуальные..
sвt, если все ребра имеют пропускную способность1. 17.03.2015