Описание тега push-relabel
0
ответов
Каковы ограничения алгоритма MPM и алгоритма Push-relbel для максимального потока?
Я кодирую это и должен знать об ограничениях для этих двух разных алгоритмов: 1) Емкости должны быть целыми или нет? 2) График должен быть ациклическим или нет? Кто-нибудь может дать намек? Спасибо
23 сен '13 в 02:19
0
ответов
Реализация алгоритма Relabel-to-Front правильна
Я пытаюсь реализовать реализацию алгоритма Relabel-To-Front для моего проекта, и сейчас происходит то, что алгоритм работает нормально, но, несмотря на то, что он получает правильный максимальный поток, он не получает правильного среза. Так что я ду…
29 апр '18 в 00:51
0
ответов
Алгоритм толкания
Я сделал MATLAB-версию кода FIFO push-relbel (точно так же, как тот, что в Википедии, и попробовал его. Функция разряда точно так же, как Википедия. Он отлично работает для небольших графиков (например, количество узлов = 7). Однако, когда я увеличи…
25 янв '13 в 21:36
0
ответов
CUDA реализован PUSH RELABEL решает общий граф?
Я пытался найти какой-то код с открытым исходным кодом, который использует метод Goldberg push and relbel или preflow-push, preflow-relaybel для решения срезов графа для ОБЩЕГО графа. Я знаю, что CUDA имеет пример кода 2D npp GrabCut, и я также знаю…
01 фев '13 в 01:05
1
ответ
Реализация алгоритма push-relbel
Я изучал алгоритм push-relbel с сайта topcoder: http://community.topcoder.com/tc?module=Static&d1;=tutorials&d2;=maxflowPushRelabel Я думаю, что с реализацией что-то не так. Как узел может оттолкнуть избыточный поток к узлу, когда он насыщен. Наприм…
18 окт '13 в 21:31
1
ответ
Как я могу прочитать данные из файла в библиотеке Boost
Я использую библиотеку Boost, чтобы найти максимальный поток (push relbel), и есть файл read_dimacs.hpp для чтения данных, но stdin. проблема в том, что мой файл данных слишком большой, и я хочу прочитать файл данных напрямую из файла. Может ли кто-…
01 фев '15 в 10:51
1
ответ
Двухэтапная эвристика
Я не понимаю, как реализовать эвристику гэпа с помощью push relbel. Вики описал это так: "В эвристике перебрасывания промежутков мы поддерживаем массив A размером n, содержащий в A[i] количество узлов для каждой метки (до n). Если найдена метка d, т…
28 янв '13 в 20:45
1
ответ
Как преобразовать сеть предварительного потока с избыточным потоком в сеть потока
Я реализовал первую фазу алгоритма ретрансляции push-меток с наивысшей меткой для максимального потока, но я не смог найти никаких ресурсов о том, как реализовать второй этап, то есть преобразовать push-сеть с предварительным потоком в действительну…
14 ноя '14 в 07:42
1
ответ
Как создать график и вызвать алгоритм с этим кодом
Я пытался понять этот код; это реализация алгоритма push-relbel в C++: // Adjacency list implementation of FIFO push relabel maximum flow // with the gap relabeling heuristic. This implementation is // significantly faster than straight Ford-Fulkers…
13 авг '14 в 14:13
0
ответов
Внедрение алгоритма максимального потока / минимального сокращения push-relbel с O(n^2 * sqrt(m)) сложностью по времени
Я читал об алгоритме push-relbel max flow/min cut с временной сложностью O(n^2 * sqrt(m)), но мне не удалось найти реализацию этого алгоритма или реализовать его самостоятельно. Надеюсь, вы можете реализовать это или иметь некоторые ресурсы, которые…
28 апр '18 в 14:36
1
ответ
В алгоритмах Push Relabel для максимального потока, почему нет пути от источника s к стоку t?
Мне сложно понять следующую лемму из CLRS: Пусть G - сеть потоков, s и t - узлы источника и приемника, f - предварительный поток из s в t, а h - функция высоты на G. Тогда в остаточном графе Gf нет пути увеличения от s до t., Почему это?
04 фев '12 в 10:19
0
ответов
Начальный поток для алгоритма push-relabel max flow в BGL
У меня есть сеть потоков и начальный возможный поток (назовем поток f0). Теперь я хотел бы найти максимальный потокfmax, так что для каждого ребра fmax(E) >= f0(E). То есть каждое ребро должно иметь поток, по крайней мере, равный начальному поток…
09 ноя '19 в 18:52
1
ответ
Алгоритмы увеличения максимального потока не компилируются. ошибка: формирование ссылки на void
Boost предоставляет три различных алгоритма для поиска максимального потока в ориентированных графах: boykov_kolmogorov, edmonds_karp и push_relabel. Все они имеют версии параметров с именем и без имени. Наборы параметров, которые они используют, та…
08 ноя '20 в 05:05
0
ответов
Алгоритм push Relabel - максимальный расход без учета лишнего веса
Мне было поручено поработать над алгоритмом Push-Relabel, чтобы найти максимальный поток от S к T. Однако загвоздка в том, что мне нужно найти более быструю реализацию, учитывая тот факт, что мне все равно, есть ли избыток поток на любом узле, если …
24 апр '21 в 23:36