Нестандартный алгоритм - Out-of-kilter algorithm

В нестандартный алгоритм является алгоритм который вычисляет решение проблема минимальных затрат в проточная сеть. Он был опубликован в 1961 г. Д. Р. Фулкерсон  ^[1] и описан здесь.^[2] Аналог установившегося потока в сети узлов и дуг может описывать множество процессов. Примеры включают в себя транспортные системы и действия по назначению персонала. Дуги обычно имеют параметры стоимости и мощности. Постоянно возникающая проблема заключается в попытке определить маршрут с минимальной стоимостью между двумя точками в сети с ограниченными возможностями. Идея алгоритма состоит в том, чтобы идентифицировать дуги вне килтера и модифицировать сеть потоков до тех пор, пока все дуги не станут килтерами и не будет достигнут поток с минимальной стоимостью. Алгоритм можно использовать для минимизации общей стоимости ограниченного потока в ориентированной сети.

Алгоритм

Для начала алгоритм берет один цикл и набор номеров узлов. Затем выполняется поиск дуги с нарушением правил. Если ничего не найдено, алгоритм завершен. Если поток необходимо увеличить или уменьшить, чтобы привести дугу в разрез, алгоритм будет искать путь, который соответственно увеличивает или уменьшает поток. Если не найдены пути для улучшения системы, значит, нет приемлемого потока. Это делается до тех пор, пока все дуги не станут равными, и на этом алгоритм будет завершен.

Предположим, что сеть имеет n узлов и m ориентированных дуг. Мы пишем ${ displaystyle j ~ (я, я ^ {1})}$ если дуга ${ displaystyle j}$ имеет начальный узел ${ displaystyle i}$ и конечный узел ${ displaystyle i ^ {1}}$. Позволять ${ Displaystyle х (j)}$ быть потоком по дуге ${ displaystyle j}$ (из узла ${ displaystyle i}$ узел ${ displaystyle i ^ {1}}$). Определить ${ displaystyle c ^ {-} (j)}$ и ${ displaystyle c ^ {+} (j)}$ быть нижней и верхней границами пропускной способности потока в дуге ${ displaystyle j}$. Емкости могут быть конечными или бесконечными на некоторых или всех дугах либо для нижней, либо для верхней границы. Проблема, которую необходимо решить, - это минимизировать: ${ Displaystyle сумма _ {J = 1} ^ {m} d (j) x (j)}$ при условии:

${ displaystyle sum _ {j: j ~ (i, i ^ {1})} x (j) - sum _ {j: j ~ (i ^ {1}, i)} x (j) = 0 }$ для каждого ${ displaystyle i = 1, ...., n}$ (1)

, и:

${ Displaystyle с ^ {-} (j) leq x (j) leq c ^ {+} (j)}$ для каждого ${ displaystyle j = 1, ...., n}$ (2)

Если данный поток x удовлетворяет (1), то поток сохраняется в каждом узле, и мы называем этот поток циркуляцией. Если поток x удовлетворяет (2), мы говорим, что он допустим.

Сложность

Время выполнения:

• Алгоритм завершается в ${ Displaystyle О (мЕ)}$ итерации
• Преобладающее вычисление - вычисление кратчайшего пути
• Общее время выполнения: ${ Displaystyle О (м ^ {2} U + mUn log (п))}$

использованная литература

^[1]

внешние ссылки

• Algoritmo Out-of-Kilter на YouTube (на испанском)