Нахождение коротких и толстых путей

Мотивация: в стандартных алгоритмах увеличения потока по траектории внутренний цикл требует поиска путей от источника к стоку в ориентированном взвешенном графике. Теоретически, общеизвестно, что для того, чтобы алгоритм даже завершился, когда существуют иррациональные ребристые емкости, нам нужно наложить ограничения на пути, которые мы находим. Алгоритм Эдмондса-Карпа, например, говорит нам, чтобы найти кратчайшие пути.

Опытным путем было замечено, что мы могли бы также хотеть найти толстые (есть ли лучший термин для этого?) Пути. Например, при использовании масштабирования емкости мы находим кратчайшие пути, которые могут нести как минимум объема потока. Нет ограничений на длину пути. Когда мы больше не можем найти какие-либо пути, мы уменьшаем и повторяем. $\epsilon$ $\epsilon$

Я заинтересован в оптимизации выбора путей расширения для очень специфического применения max-flow, и я хочу исследовать этот компромисс между короткими и толстыми путями. (Примечание: мне не обязательно всегда решать проблему. Меня больше всего интересует нахождение наибольшей нижней границы потока за кратчайшее время стенок.)

Вопрос: существует ли стандартный способ интерполяции между подходом кратчайшего пути и подходом масштабирования емкости? То есть, существует ли алгоритм для поиска путей, которые бывают как короткими, так и толстыми, где в идеале какой-то параметр будет контролировать, какую длину пути мы готовы обменять на жирность? В крайнем случае я хотел бы иметь возможность восстанавливать кратчайшие пути на одном конце и пути в стиле масштабирования емкости на другом.

ds.algorithms graph-theory graph-algorithms dan_x
источник

Обратите внимание, что если вы попытаетесь оптимизировать как краткость, так и упитанность одновременно, вы вводите области многокритериальной оптимизации, что в большинстве случаев означает NP-твердость.

Рафаэль

ϵ

$\epsilon$

@Daniel Apon - псевдокод для масштабирования емкости представлен на странице 31 этих слайдов: cs.princeton.edu/~wayne/kleinberg.../07maxflow.pdf

dan_x

@Raphael - Обратите внимание, что я ищу одну цель, например, линейную комбинацию длины и упитанности. Это все еще считается многокритериальной оптимизацией?

dan_x

ϵ

$\epsilon$

В духе вашего комментария о «довольно хорошо, но не обязательно оптимально», я представляю следующую идею абсолютно без гарантии оптимальности!

Для полноты ниже приведен псевдокод, на который вы ссылались (примечание: связанный алгоритм предполагает, что значения границ являются целыми числами от 1 до C, а значения потока и остаточной емкости являются целыми):

Scaling-Max-Flow (G, s, t, C) {
   foreach e ∈ E f (e) ← 0
   Δ ← наименьшая степень 2 больше или равна C
   G_f ← остаточный график

   в то время как (Δ ≥ 1) {
      G_f (Δ) ← Δ-остаточный график
      while (существует дополнительный путь P в G_f (Δ)) {
         f ← увеличение (f, C, P)
         обновить G_f (Δ)
      }
      Δ ← Δ / 2
   }
   возврат f
}

$\epsilon$ $\epsilon = \Delta$ $\epsilon$

$0 \le \rho \le 1$ $\rho$

$\epsilon$ $\rho$

$\epsilon \leftarrow (\rho)\epsilon + (1-\rho)$

$\rho = 0$ $\rho = 1$ $0 < \rho < 1$ $\epsilon$ $\le 1$

Даниэль Апон
источник

Спасибо за идею - это приближается к тому, что я имел в виду. Мое единственное беспокойство заключается в том, что это просто другой «график распада» для масштабирования емкости, верно?

dan_x

По мере того, как вы распадаетесь более агрессивно, вы получаете более короткие пути, а когда вы распадаетесь менее агрессивно, вы получаете более толстые пути. Я имел в виду, что каждый путь получит оценку, основанную на том, насколько он толстый и насколько коротким, а затем алгоритм найдет все пути с оценкой, превышающей некоторый порог.

dan_x

Но если нет стандартного способа сделать это, я могу сесть и подумать над тем, чтобы получить алгоритм, который делает то, что я хочу.

dan_x

Нахождение коротких и толстых путей

Ответы: