The Ford-Fulkerson method or Ford-Fulkerson algorithm allows to solve the maximum flow problem. It was published by L. R. Ford, Jr. and D. R. Fulkerson in 1956.
Спасибо большое, добрый человек! После вашего видео алгоритм в голове лёг как следует. По какой-то причине, для этого алгоритма большинство описаний в интернете не вводят используемые термины и упускают часть формул. Ваше описание - приятное исключение.
Счастливчик! Я, вообще, в день по 4 минуты видео "перевариваю", и трачу на эти минуты по часу. Тупо конспектирую, понимая через раз. Причем, параллельно учу Си и Питон. Так вот, языки мне даются слету, включая написание кодов и решение задач. Причем, подозреваю, что если мне те же задачи начнут объяснять в форме алгоритмов, я и их не пойму. Просто, видимо, алгоритмы , как форма передачи информации - вообще, не мое. Хотя практика показывает, что мозг, если его долго заставлять понимать то, чего он понимать не хочет, в итоге сдается и "открывается".
@@nadyamoscow2461 Вот это связка C and Python)) Вопрос зачем?)) Дам подсказку: нельзя учить несколько языков одновременно , дальше основ это никуда не зайдёт (я говорю про уверенный. Advanced level) . В любом случае успехов в обучении))
@@memoryLayer Спасибо! И поздравляю с достигнутым Advanced level ! Я не совсем одновременно. Меня, в принципе, интересует С, затем С++ и, возможно, в будущем, при необходимости, Java. Они базово аналогичны и вытекают один из другого с некоторыми изменениями. А Python просто попался на пути. Я одновременно и не учу: Си пока отложен. Вернусь, когда освою ООП на Питоне. Кстати, даже после азов Си, Питон кажется неприлично упрощенным. С другой стороны, логика - везде логика. Когда вернусь к Си, полученные знания в Питоне не помешают. Для меня это хобби, так что на меня не давит необходимость скорее на работу устроиться или типа того - могу учиться в удовольствие, пробовать и выбрать, что больше понравится. Я просто предпочитаю как следует разобраться, из чего именно выбираю. А алгоритмы - они при любом синтаксисе алгоритмы. Без них же никуда, чтоб они провалились... Нельзя же строить дом без фундамента
Нет. Пропускную способность вычитаем в направлении потока. Раз поток проходит от 3 узла к 2, то получаем (30+10)/(10-10 - это от 3 к 2) = 40/0, а не 20/20.
Допущена ошибка в таблице на 20:54. У ребра (3;4) должно быть (10;0) - (0;10) = (10;-10). Да, на выходе получается одно и тоже, но это выражение может запутать. Руководился лишь вашей логикой, предоставленной в данном видеоролике. Если я где-то ошибся, то пожалуйста, исправьте меня. Спасибо за хорошее видео и предоставленный материал.
Да, на ребре 2-3 стоит метка 40/0. Это значит, что из узла 2 мы можем двигаться в узел 3 (пропускная способность равна 40), а из узла 3 в узел 2 - не можем (пропускная способность равна 0). А раз из узла 3 в узел 2 попасть мы не может, то 2 не входит в множество S3.
さまAsakura Переходим к шагу 3: поскольку вес ребра из второго узла в пятый (30) меньше веса ребра из второго узла в третий (40), то переходим в узел 3; помечаем третий узел меткой [40, 2]; полагаем i=3; переходим к шагу 2.
Почему на первом шаге мы не перешли от узла 4 к узлу 2, ведь для него пропускная способность (= 40 > 20), больше чем к узлу 5? А так ваши видео очень приятно и понятно слушать)
@@ronro1 Это вопрос ко второму Шагу 2 на первой итерации (5:32)? Цитирую с 5:51 "Второй узел не входит [во множество узлов с потенциальными кандидатами S], поскольку остаточная пропускная способность ребра от узла 3 к узлу 2 равна нулю". Все в видео верно.
@@romantsarev1145, на самом же деле пропускная способность все таки равна 40. Потому что подпись под узлом 2 = (40, 0), а у всех других вершин (20, 0) или же (10, 0)
На каждой итерации (при прохождении от истока к стоку) мы пытаемся "пропихнуть" максимальный поток. Это те самые 20, 10, 10... На каждой последующей итерации мы учитываем то, что уже выбрали. Заканчиваем итерации, когда уже не можем ничего "пропихнуть". И суммируем те самые частные максимальные потоки всех предыдущих итераций.
@@impetrov Хороший вопрос. Идея в следующем, раз из узла 1 в узел 3 на этой итерации проходит поток в 20, то он "ослабляет" исходную пропускную способность 30 до 10. Одновременно с этим появляется потенциал для движения потока из 3 в 1 в размере 20, если он придет на следующих итерациях.
@@romantsarev1145 я вот не понимаю, почему этот потенциал возникает? если там нет потока, то понятно, потенциально можно от 3-1 направить. Но почему потенциал возникает именно тогда, когда появляется из 1 в 3 не могу понять.
Если же Вам нужна развернутая консультация, лучше будет обратиться к фрилинсерам на studlance(goo.gl/xpccZj) или studwork(goo.gl/rBHSfi), где за символическую плату Вас проконсультируют, а то и предоставят полное решение с подробными пояснениями. Можете также воспользоваться услугами на workzilla(goo.gl/4hN4HF), на этой площадке предоставляются услуги широкого профиля, в том числе, и решение различных задач.
Автор, как это решать??? Смотрел 25 минут, в конце понял что смотрел не то :facepalm: Потом еще 25 минут рисовал, то что ниже. Помоги, а, плиз. После пропускания потока в транспортной сети (см. рисунок) насыщенными оказались дуги: U = (s, 1), (s, 5), (5, 6), (3, t), (6, 3). (1) >>>10>>>> ( 3) ^ v ^ ^ v 12 8 22 10 11 ^ v ^ ^ v s >14> (5 ) >10> (6) >10> ( t) v ^ ^ v ^ 18 11 12 4 17 v ^ ^ v ^ (2 ) > 9> (4) Определите, возможно ли увеличить поток в данной сети.
не переписывай, все норм есть люди которые видят это в первый раз и это замечательно что ты повторяешь по 20 раз одно и тоже, остальные могут читать книги написанные старыми программистами которые кодят на бинарном коде.
