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)
@@impetrov Хороший вопрос. Идея в следующем, раз из узла 1 в узел 3 на этой итерации проходит поток в 20, то он "ослабляет" исходную пропускную способность 30 до 10. Одновременно с этим появляется потенциал для движения потока из 3 в 1 в размере 20, если он придет на следующих итерациях.
@@romantsarev1145 я вот не понимаю, почему этот потенциал возникает? если там нет потока, то понятно, потенциально можно от 3-1 направить. Но почему потенциал возникает именно тогда, когда появляется из 1 в 3 не могу понять.
На каждой итерации (при прохождении от истока к стоку) мы пытаемся "пропихнуть" максимальный поток. Это те самые 20, 10, 10... На каждой последующей итерации мы учитываем то, что уже выбрали. Заканчиваем итерации, когда уже не можем ничего "пропихнуть". И суммируем те самые частные максимальные потоки всех предыдущих итераций.
Если же Вам нужна развернутая консультация, лучше будет обратиться к фрилинсерам на 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 раз одно и тоже, остальные могут читать книги написанные старыми программистами которые кодят на бинарном коде.
объсняете алгосы лучше всех на ютубе, всегда радуюсь, если гуглю алгоритм и вижу Ваш разбор
Да это жестко. Это видео осиливал больше двух часов)) Постепенно переслушивая и перематывая + делал своё задание паралельно. Спасибо большое
Отлично! Главное, что два часа ушли не впустую!
Счастливчик! Я, вообще, в день по 4 минуты видео "перевариваю", и трачу на эти минуты по часу. Тупо конспектирую, понимая через раз. Причем, параллельно учу Си и Питон. Так вот, языки мне даются слету, включая написание кодов и решение задач. Причем, подозреваю, что если мне те же задачи начнут объяснять в форме алгоритмов, я и их не пойму. Просто, видимо, алгоритмы , как форма передачи информации - вообще, не мое.
Хотя практика показывает, что мозг, если его долго заставлять понимать то, чего он понимать не хочет, в итоге сдается и "открывается".
@@nadyamoscow2461 Вот это связка C and Python)) Вопрос зачем?)) Дам подсказку: нельзя учить несколько языков одновременно , дальше основ это никуда не зайдёт (я говорю про уверенный. Advanced level) . В любом случае успехов в обучении))
@@memoryLayer Спасибо! И поздравляю с достигнутым Advanced level !
Я не совсем одновременно. Меня, в принципе, интересует С, затем С++ и, возможно, в будущем, при необходимости, Java. Они базово аналогичны и вытекают один из другого с некоторыми изменениями. А Python просто попался на пути. Я одновременно и не учу: Си пока отложен. Вернусь, когда освою ООП на Питоне. Кстати, даже после азов Си, Питон кажется неприлично упрощенным. С другой стороны, логика - везде логика. Когда вернусь к Си, полученные знания в Питоне не помешают. Для меня это хобби, так что на меня не давит необходимость скорее на работу устроиться или типа того - могу учиться в удовольствие, пробовать и выбрать, что больше понравится. Я просто предпочитаю как следует разобраться, из чего именно выбираю. А алгоритмы - они при любом синтаксисе алгоритмы. Без них же никуда, чтоб они провалились... Нельзя же строить дом без фундамента
@@nadyamoscow2461 ммм... Ну и как спустя год?))))
Огромное спасибо, с вашей подачей материал очень хорошо усваивается!
Рад, что материал приносит пользу.
Спасибо большое, добрый человек!
После вашего видео алгоритм в голове лёг как следует. По какой-то причине, для этого алгоритма большинство описаний в интернете не вводят используемые термины и упускают часть формул. Ваше описание - приятное исключение.
Прекрасное предельно ясное объяснение ! Спасибо вам огромное !
Пожалуйста. Рад, что понравилось.
Большое спасибо автору видео! Все предельно ясно объяснил.
Пожалуйста
Огромное спасибо Вам за такое подробное объяснение!
Пожалуйста!
Хорошо, очень хорошо, что вы есть
Спасибо автору за видео. Пытался понять данный алгоритм из теории - не получилось. А после видео всё стало на свои места.
Вау, лучшее объяснение алгоритма Форда Фалкерсона! Наконец-то я понял этот алгоритм!
Спасибо за отзыв! Рад, что Вам пригодилось и понравилось.
спасибо большое! актуально как никогда!!!
Пожалуйста!
Спасибо за видео! А почему ни слова про обратные ребра? В рассматриваемом примере мы гоним поток только по прямым ребрам.
Спасибо большое !!
Пожалуйста!
Спасибо за видео.
Пожалуйста
На 18:06 пропусканая способность между узлами 2-3 разве не 20/20 должна стать ?
Нет. Пропускную способность вычитаем в направлении потока. Раз поток проходит от 3 узла к 2, то получаем (30+10)/(10-10 - это от 3 к 2) = 40/0, а не 20/20.
Допущена ошибка в таблице на 20:54. У ребра (3;4) должно быть (10;0) - (0;10) = (10;-10). Да, на выходе получается одно и тоже, но это выражение может запутать. Руководился лишь вашей логикой, предоставленной в данном видеоролике. Если я где-то ошибся, то пожалуйста, исправьте меня. Спасибо за хорошее видео и предоставленный материал.
Действительно, вы правы. В таблице опечатка. (На рисунках все правильно).
Просто лайк
Спасибо!
Пожалуйста
5:45, почему 2 узел не входит в множество для третьего узла? Т.е. как видно, что пропускная способность == 0?
Да, на ребре 2-3 стоит метка 40/0. Это значит, что из узла 2 мы можем двигаться в узел 3 (пропускная способность равна 40), а из узла 3 в узел 2 - не можем (пропускная способность равна 0). А раз из узла 3 в узел 2 попасть мы не может, то 2 не входит в множество S3.
Roman Tsarev точно, не обратил внимание на направление. Спасибо большое)
Владислав Владимирович Пожалуйста
тогда что происходит на 11:50?
さまAsakura Переходим к шагу 3: поскольку вес ребра из второго узла в пятый (30) меньше веса ребра из второго узла в третий (40), то переходим в узел 3; помечаем третий узел меткой [40, 2]; полагаем i=3; переходим к шагу 2.
Сперва испугался, что нет стрелочек, а потом понял
Почему на первом шаге мы не перешли от узла 4 к узлу 2, ведь для него пропускная способность (= 40 > 20), больше чем к узлу 5? А так ваши видео очень приятно и понятно слушать)
Спасибо. Что же касается узла 4, то ребра, соединяющего его с узлом 2, вообще нет.
потому что
@@romantsarev1145 скорее всего он имел в виду от узла 3 к узлу 2, там действительно вы не учитываете этот переход
@@ronro1 Это вопрос ко второму Шагу 2 на первой итерации (5:32)? Цитирую с 5:51 "Второй узел не входит [во множество узлов с потенциальными кандидатами S], поскольку остаточная пропускная способность ребра от узла 3 к узлу 2 равна нулю". Все в видео верно.
@@romantsarev1145, на самом же деле пропускная способность все таки равна 40. Потому что подпись под узлом 2 = (40, 0), а у всех других вершин (20, 0) или же (10, 0)
Здравствуйте, а что нам показывает максимальный поток в сети? Для чего нам его искать?
Как например узнать, сколько нефти можно за единицу времени перегнать через существующий трубопровод? С помощью этого (или аналогичного) алгоритма.
Roman Tsarev спасибо
Идеальное объяснение, спасибо огромное
Все круто , но купите пожалуйста хороший микрофон для записи , минус уши
Легче величину потока считать на ребрах в стоке или истоке. Не совсем понял логику 20 + 10 + 10 + 10 + 10. За видео спасибо, освежил память)
если вы за 3 года все таки поняли логику, не могли бы вкратце объяснить?
А что делать если вес дуги не 20/0 а просто 2 или 5?
Это значит, что вес дуги просто 2/0 или 5/0. В самом начале про это рассказывается.
Если по ребру 1-3 проходит поток 20, то почему пропускная способность ребра 3-1 стала 20??
На каком этапе?
@@romantsarev1145 вот тут: 10:00
@@impetrov Хороший вопрос. Идея в следующем, раз из узла 1 в узел 3 на этой итерации проходит поток в 20, то он "ослабляет" исходную пропускную способность 30 до 10. Одновременно с этим появляется потенциал для движения потока из 3 в 1 в размере 20, если он придет на следующих итерациях.
@@romantsarev1145 я вот не понимаю, почему этот потенциал возникает? если там нет потока, то понятно, потенциально можно от 3-1 направить. Но почему потенциал возникает именно тогда, когда появляется из 1 в 3 не могу понять.
а так же делать если у тебя направленная сеть ?
Да
@@romantsarev1145 спасибо за ответ
@@romantsarev1145 ах да и Еше точно так или есть изменения (ну насчёт сток и истока понятно)
Точно так
@@romantsarev1145 вес правильно спасибо большое(нормальное объяснение не мог найти ну точнее были но для маленьких сетей)наконец то дискретную сдам
Где можно взять перезентацию?
Сделайте скриншоты
@@romantsarev1145 Мне нужно взять Ваш отличный исходник и дополнить пару моментов
@@vveivi Без проблем. 10 000 руб. на карту и исходник Ваш.
Для орграфа алгоритм такой же?
Да.
Так и не понял почему в конце максимум будет 20+10+10+10+10=60...
На каждой итерации (при прохождении от истока к стоку) мы пытаемся "пропихнуть" максимальный поток. Это те самые 20, 10, 10... На каждой последующей итерации мы учитываем то, что уже выбрали. Заканчиваем итерации, когда уже не можем ничего "пропихнуть". И суммируем те самые частные максимальные потоки всех предыдущих итераций.
@@romantsarev1145 💙💛
Завтра зачет по этой жепе, классно что можно тупо посмотреть видос и не читать буковы
Главное, чтобы мимо не пролетело )
Как вас найти ?
+Roman Tsarev можно с вами про консультироваться ?
Вы можете задать Ваш вопрос в комментариях.
Если же Вам нужна развернутая консультация, лучше будет обратиться к фрилинсерам на 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 раз одно и тоже, остальные могут читать книги написанные старыми программистами которые кодят на бинарном коде.