Ford-Fulkerson algorithm

[@krystlecarrington5485]

объсняете алгосы лучше всех на ютубе, всегда радуюсь, если гуглю алгоритм и вижу Ваш разбор

[@memoryLayer]

Да это жестко. Это видео осиливал больше двух часов)) Постепенно переслушивая и перематывая + делал своё задание паралельно. Спасибо большое

[@romantsarev1145]

Отлично! Главное, что два часа ушли не впустую!

[@nadyamoscow2461]

Счастливчик! Я, вообще, в день по 4 минуты видео "перевариваю", и трачу на эти минуты по часу. Тупо конспектирую, понимая через раз. Причем, параллельно учу Си и Питон. Так вот, языки мне даются слету, включая написание кодов и решение задач. Причем, подозреваю, что если мне те же задачи начнут объяснять в форме алгоритмов, я и их не пойму. Просто, видимо, алгоритмы , как форма передачи информации - вообще, не мое. Хотя практика показывает, что мозг, если его долго заставлять понимать то, чего он понимать не хочет, в итоге сдается и "открывается".

[@memoryLayer]

@@nadyamoscow2461 Вот это связка C and Python)) Вопрос зачем?)) Дам подсказку: нельзя учить несколько языков одновременно , дальше основ это никуда не зайдёт (я говорю про уверенный. Advanced level) . В любом случае успехов в обучении))

[@nadyamoscow2461]

@@memoryLayer Спасибо! И поздравляю с достигнутым Advanced level ! Я не совсем одновременно. Меня, в принципе, интересует С, затем С++ и, возможно, в будущем, при необходимости, Java. Они базово аналогичны и вытекают один из другого с некоторыми изменениями. А Python просто попался на пути. Я одновременно и не учу: Си пока отложен. Вернусь, когда освою ООП на Питоне. Кстати, даже после азов Си, Питон кажется неприлично упрощенным. С другой стороны, логика - везде логика. Когда вернусь к Си, полученные знания в Питоне не помешают. Для меня это хобби, так что на меня не давит необходимость скорее на работу устроиться или типа того - могу учиться в удовольствие, пробовать и выбрать, что больше понравится. Я просто предпочитаю как следует разобраться, из чего именно выбираю. А алгоритмы - они при любом синтаксисе алгоритмы. Без них же никуда, чтоб они провалились... Нельзя же строить дом без фундамента

[@YtSearchLifeStyle]

@@nadyamoscow2461 ммм... Ну и как спустя год?))))

[@ArksRussian]

Спасибо большое, добрый человек! После вашего видео алгоритм в голове лёг как следует. По какой-то причине, для этого алгоритма большинство описаний в интернете не вводят используемые термины и упускают часть формул. Ваше описание - приятное исключение.

[@xclamaation]

Огромное спасибо Вам за такое подробное объяснение!

[@romantsarev1145]

Пожалуйста!

[@blessedponica8030]

Огромное спасибо, с вашей подачей материал очень хорошо усваивается!

[@romantsarev1145]

Рад, что материал приносит пользу.

[@fatvvsfatvvs5642]

Вау, лучшее объяснение алгоритма Форда Фалкерсона! Наконец-то я понял этот алгоритм!

[@romantsarev1145]

Спасибо за отзыв! Рад, что Вам пригодилось и понравилось.

[@Tatiana-zs3dc]

Прекрасное предельно ясное объяснение ! Спасибо вам огромное !

[@romantsarev1145]

Пожалуйста. Рад, что понравилось.

[@ВладиславВолодимирови]

5:45, почему 2 узел не входит в множество для третьего узла? Т.е. как видно, что пропускная способность == 0?

[@romantsarev1145]

Да, на ребре 2-3 стоит метка 40/0. Это значит, что из узла 2 мы можем двигаться в узел 3 (пропускная способность равна 40), а из узла 3 в узел 2 - не можем (пропускная способность равна 0). А раз из узла 3 в узел 2 попасть мы не может, то 2 не входит в множество S3.

[@ВладиславВолодимирови]

Roman Tsarev точно, не обратил внимание на направление. Спасибо большое)

[@romantsarev1145]

Владислав Владимирович Пожалуйста

[@ElleandriaAsakura]

тогда что происходит на 11:50?

[@romantsarev1145]

さまAsakura Переходим к шагу 3: поскольку вес ребра из второго узла в пятый (30) меньше веса ребра из второго узла в третий (40), то переходим в узел 3; помечаем третий узел меткой [40, 2]; полагаем i=3; переходим к шагу 2.

[@meunyaolya3076]

спасибо большое! актуально как никогда!!!

[@romantsarev1145]

Пожалуйста!

[@АртемЯрошенко-г8ц]

Большое спасибо автору видео! Все предельно ясно объяснил.

[@romantsarev1145]

Пожалуйста

[@valentynkhaman7688]

На 18:06 пропусканая способность между узлами 2-3 разве не 20/20 должна стать ?

[@romantsarev1145]

Нет. Пропускную способность вычитаем в направлении потока. Раз поток проходит от 3 узла к 2, то получаем (30+10)/(10-10 - это от 3 к 2) = 40/0, а не 20/20.

[@anbotip]

Спасибо автору за видео. Пытался понять данный алгоритм из теории - не получилось. А после видео всё стало на свои места.

[@dargfox_]

Допущена ошибка в таблице на 20:54. У ребра (3;4) должно быть (10;0) - (0;10) = (10;-10). Да, на выходе получается одно и тоже, но это выражение может запутать. Руководился лишь вашей логикой, предоставленной в данном видеоролике. Если я где-то ошибся, то пожалуйста, исправьте меня. Спасибо за хорошее видео и предоставленный материал.

[@romantsarev1145]

Действительно, вы правы. В таблице опечатка. (На рисунках все правильно).

[@torrodincov6497]

Хорошо, очень хорошо, что вы есть

[@МухамеджановТимур-м6е]

Спасибо большое !!

[@romantsarev1145]

Пожалуйста!

[@professional2094]

Спасибо за видео! А почему ни слова про обратные ребра? В рассматриваемом примере мы гоним поток только по прямым ребрам.

[@antichrist509]

Здравствуйте, а что нам показывает максимальный поток в сети? Для чего нам его искать?

[@romantsarev1145]

Как например узнать, сколько нефти можно за единицу времени перегнать через существующий трубопровод? С помощью этого (или аналогичного) алгоритма.

[@antichrist509]

Roman Tsarev спасибо

[@impetrov]

Если по ребру 1-3 проходит поток 20, то почему пропускная способность ребра 3-1 стала 20??

[@romantsarev1145]

На каком этапе?

[@impetrov]

@@romantsarev1145 вот тут: 10:00

[@romantsarev1145]

@@impetrov Хороший вопрос. Идея в следующем, раз из узла 1 в узел 3 на этой итерации проходит поток в 20, то он "ослабляет" исходную пропускную способность 30 до 10. Одновременно с этим появляется потенциал для движения потока из 3 в 1 в размере 20, если он придет на следующих итерациях.

[@impetrov]

@@romantsarev1145 я вот не понимаю, почему этот потенциал возникает? если там нет потока, то понятно, потенциально можно от 3-1 направить. Но почему потенциал возникает именно тогда, когда появляется из 1 в 3 не могу понять.

[@clankyhippo9133]

Сперва испугался, что нет стрелочек, а потом понял

[@SosokYlitky]

Спасибо за видео.

[@romantsarev1145]

Пожалуйста

[@ВалерийШитов-х1ю]

Просто лайк

[@gintoke8888]

А что делать если вес дуги не 20/0 а просто 2 или 5?

[@romantsarev1145]

Это значит, что вес дуги просто 2/0 или 5/0. В самом начале про это рассказывается.

[@vadymca8420]

Так и не понял почему в конце максимум будет 20+10+10+10+10=60...

[@romantsarev1145]

На каждой итерации (при прохождении от истока к стоку) мы пытаемся "пропихнуть" максимальный поток. Это те самые 20, 10, 10... На каждой последующей итерации мы учитываем то, что уже выбрали. Заканчиваем итерации, когда уже не можем ничего "пропихнуть". И суммируем те самые частные максимальные потоки всех предыдущих итераций.

[@vadymca8420]

@@romantsarev1145 💙💛

[@vveivi]

Где можно взять перезентацию?

[@romantsarev1145]

Сделайте скриншоты

[@vveivi]

@@romantsarev1145 Мне нужно взять Ваш отличный исходник и дополнить пару моментов

[@romantsarev1145]

@@vveivi Без проблем. 10 000 руб. на карту и исходник Ваш.

[@woaalong]

Для орграфа алгоритм такой же?

[@romantsarev1145]

Да.

[@АртурЦай-ы9щ]

Зачем удалил Нину Львовну?

[@romantsarev1145]

Погорячился

[@МаксимМалинин-п8з]

Почему на первом шаге мы не перешли от узла 4 к узлу 2, ведь для него пропускная способность (= 40 > 20), больше чем к узлу 5? А так ваши видео очень приятно и понятно слушать)

[@romantsarev1145]

Спасибо. Что же касается узла 4, то ребра, соединяющего его с узлом 2, вообще нет.

[@ИванДружинин-б5ф]

потому что

[@ronro1]

@@romantsarev1145 скорее всего он имел в виду от узла 3 к узлу 2, там действительно вы не учитываете этот переход

[@romantsarev1145]

@@ronro1 Это вопрос ко второму Шагу 2 на первой итерации (5:32)? Цитирую с 5:51 "Второй узел не входит [во множество узлов с потенциальными кандидатами S], поскольку остаточная пропускная способность ребра от узла 3 к узлу 2 равна нулю". Все в видео верно.

[@Ratmir_Akhm]

@@romantsarev1145, на самом же деле пропускная способность все таки равна 40. Потому что подпись под узлом 2 = (40, 0), а у всех других вершин (20, 0) или же (10, 0)

[@yehornedbalo2969]

Спасибо!

[@romantsarev1145]

Пожалуйста

[@lonewhiteraven3440]

а так же делать если у тебя направленная сеть ?

[@romantsarev1145]

Да

[@lonewhiteraven3440]

@@romantsarev1145 спасибо за ответ

[@lonewhiteraven3440]

@@romantsarev1145 ах да и Еше точно так или есть изменения (ну насчёт сток и истока понятно)

[@romantsarev1145]

Точно так

[@lonewhiteraven3440]

@@romantsarev1145 вес правильно спасибо большое(нормальное объяснение не мог найти ну точнее были но для маленьких сетей)наконец то дискретную сдам

[@SomeGuy-q1d]

Легче величину потока считать на ребрах в стоке или истоке. Не совсем понял логику 20 + 10 + 10 + 10 + 10. За видео спасибо, освежил память)

[@Ratmir_Akhm]

если вы за 3 года все таки поняли логику, не могли бы вкратце объяснить?

[@mrlime9437]

Идеальное объяснение, спасибо огромное

[@kaisaryerdenbekov1588]

Автор, как это решать??? Смотрел 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) Определите, возможно ли увеличить поток в данной сети.

[@romantsarev1145]

Лучше пересмотрите еще раз видео и разберитесь с алгоритмом. Это будет гораздо лучше, чем я за Вас решу.

[@johnsimpson2827]

Все круто , но купите пожалуйста хороший микрофон для записи , минус уши

[@FyWin]

Как вас найти ?

[@FyWin]

+Roman Tsarev можно с вами про консультироваться ?

[@romantsarev1145]

Вы можете задать Ваш вопрос в комментариях.

[@romantsarev1145]

Если же Вам нужна развернутая консультация, лучше будет обратиться к фрилинсерам на studlance(goo.gl/xpccZj) или studwork(goo.gl/rBHSfi), где за символическую плату Вас проконсультируют, а то и предоставят полное решение с подробными пояснениями. Можете также воспользоваться услугами на workzilla(goo.gl/4hN4HF), на этой площадке предоставляются услуги широкого профиля, в том числе, и решение различных задач.

[@kostiantynpilavov3980]

по графу

[@ХочуСдохнуть-у1я]

Завтра зачет по этой жепе, классно что можно тупо посмотреть видос и не читать буковы

[@romantsarev1145]

Главное, чтобы мимо не пролетело )

[@TheBestTvarynka]

Чувак, спасибо :)!

[@Буревестник-р2п]

Спасибо большое

[@romantsarev1145]

Пожалуйста, Михаил.

[@2007vintik]

снимаю шляпу, спасибо

[@ПрикладнаяИнформатика-э1ф]

Полезно, но слишком затянуто По двадцать раз одно и то же повторять смысла не вижу, всё же не совсем идиоты по ту сторону экрана сидят)

[@romantsarev1145]

Переписать? )

[@expanzo]

не переписывай, все норм есть люди которые видят это в первый раз и это замечательно что ты повторяешь по 20 раз одно и тоже, остальные могут читать книги написанные старыми программистами которые кодят на бинарном коде.