Алгоритм вне неисправной является алгоритм , который вычисляет решение проблемы потока минимальной стоимости в сети потока . Он был опубликован в 1961 г. Д. Р. Фулкерсоном [1] и описывается здесь. [2]Аналог стационарного потока в сети узлов и дуг может описывать множество процессов. Примеры включают в себя транспортные системы и действия по назначению персонала. У дуг обычно есть параметры стоимости и мощности. Постоянно возникающая проблема заключается в попытке определить маршрут с минимальной стоимостью между двумя точками в сети с ограниченным доступом. Идея алгоритма состоит в том, чтобы идентифицировать дуги вне килтера и модифицировать сеть потоков до тех пор, пока все дуги не станут килтерами и не будет достигнут поток с минимальной стоимостью. Алгоритм может использоваться для минимизации общей стоимости ограниченного потока в ориентированной сети.
Алгоритм
Для начала алгоритм берет один цикл и набор номеров узлов. Затем он выполняет поиск дуги с нарушением резкости. Если ничего не найдено, алгоритм завершен. Если поток необходимо увеличить или уменьшить, чтобы привести дугу в разрез, алгоритм будет искать путь, который соответственно увеличивает или уменьшает поток. Если не найдены пути для улучшения системы, значит, нет приемлемого потока. Это делается до тех пор, пока все дуги не станут равными, и на этом алгоритм будет завершен.
Предположим, что сеть имеет n узлов и m ориентированных дуг. Мы пишем если дуга имеет начальный узел и конечный узел . Позволять быть потоком по дуге (из узла к узлу ). Определять а также быть нижней и верхней границами пропускной способности потока в дуге . Емкости могут быть конечными или бесконечными на некоторых или всех дугах либо для нижней, либо для верхней границы. Проблема, которую необходимо решить, - это минимизировать: при условии:
для каждого (1)
, а также:
для каждого (2)
Если данный поток x удовлетворяет (1), то поток сохраняется в каждом узле, и мы называем этот поток циркуляцией. Если поток x удовлетворяет (2), мы говорим, что он допустим.
Сложность
Время выполнения:
- Алгоритм завершается в итерации
- Преобладающее вычисление - вычисление кратчайшего пути
- Общее время выполнения:
Рекомендации
- ↑ DR Fulkerson (март 1961 г.). "Необычный метод решения задач с минимальными затратами". Журнал Общества промышленной и прикладной математики . 9 (1): 18–27. JSTOR 2099013 .
- ^ Дурбин, EP; Кроенке, Д.М. (декабрь 1967 г.). Неуверенный алгоритм: букварь - Меморандум RM-5472-PR (PDF) . Санта-Моника, Калифорния, США: Rand Corporation . Проверено 16 января 2018 .
Внешние ссылки
- Algoritmo Out-of-Kilter на YouTube (на испанском языке)
- ^ Кембриджский университет (июль 2012 г.). «Алгоритм вне килтера» (PDF) . www.maths.cam.ac.uk .