Алгоритм Прима

[@mrsoomo]

Спасибо ВАМ, очень помогли.

[@romantsarev1145]

Пожалуйста!

[@badmasha_life]

Доброго времени суток, спасибо за видео) Добавьте (если будет возможность) про алгоритм Борувки) Было бы полезно.

[@IVT-rt1yr]

Начало : 1:45 Конец : 4:08

[@ekaterinak9924]

Спасибо!)

[@3a9lll69]

Це відео допомогло мені зробити реферат по цій темі, дякую за добрий контент

[@romantsarev1145]

Пожалуйста. Рад, что помогло.

[@goltvian]

Спасибо, все предельно понятно))

[@romantsarev1145]

Пожалуйста

[@Поларис-щ5р]

а что делать, если в матрице Р в одном столбце несколько значений разных, а в каком то столбце вообще нет значений кроме 0(на протяжении алгоритма в матрицах значения в этом столбце не менялись)?Как восстанавливать путь тогда?

[@romantsarev1145]

Что за матрица Р? 🤔

[@Поларис-щ5р]

@@romantsarev1145 не под тем видео коммент оставил. Я про видео о алгоритме флойда.

[@romantsarev1145]

@@Поларис-щ5р Вы тогда там оставьте коммент, я туда отвечу

[@avverevkin]

А каково практическое применение этого метода? С алгоритмом Дейкстры и Флойда понятно, там мы кратчайший (самый дешевый) путь ищем, а тут? В примере 1-4=5, а, 1-3-4=6, но на первом шаге мы отбросили ребро 1-4 потому что 1-3 дешевле.

[@romantsarev1145]

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

[@avverevkin]

@@romantsarev1145 Да, точно, задачи логистики. Задачи разные, согласен

[@roman.chudov]

А как мы перешли от 6-4 к 3-2? До этого мы шли по инцидентным вершинам к текущей, но 4 и 2 не инцидентны. Перепрыгнули как-то. И еще ничего не говорится о циклах.

[@romantsarev1145]

Множество U - вот ответ на оба Ваших вопроса. "...мы должны на каждом шаге выбирать ребро минимальной стоимости, которое связывает одну вершину из множества U и вершину, которая в множество U пока не входит" (2:01). Вот так мы и перешли от 6-4 (в этом момент во множество U входили вершины 1, 3, 4, 6) к 3-2 (2 в множество U не входило), и минимальный вес ребра из всех рассматриваемых был равен 5 (то самое ребро 3-2). Зачем мне что-то говорить о циклах? Если Вы работаете как описано в видео, то есть с использованием множества U, то циклы не возникнут никогда.

[@HIRUTSU]

нужно рассматривать все ребра, инцидентные вершинам, включенных в дерево и выбирать среди них минимальное. так как 6-4 было минимально с весом 2, а потом из всех мин ребер было 3-2 с весом 5

[@mrsoomo]

5-6 это не ребро с весом 0?

[@romantsarev1145]

Там 6 должно быть.

[@ПАИ152]

Спасибо! Все понятно, вот толь-ко между 5 и 6 нету стоимости ребра

[@romantsarev1145]

Пожалуйста. Да, стоимость ребра слетела при подготовке видео. Надеюсь, это несильно сбивает с толку. Стоимость ребра (5, 6) равна 6.

[@Очевидец-н7с]

@@romantsarev1145 надеетесь что это сильно сбивает с толку?

[@romantsarev1145]

@@Очевидец-н7с )

[@ivanhuzikov]

спасибо

[@romantsarev1145]

Пожалуйста

[@w1nchester551]

Как бы вы действовали если бы ребро (1,4) имело бы стоимость 2, а ребро (6,4) 3?

[@romantsarev1145]

Тогда дерево бы строилось так: (1,3), (1,4), (4, 6)...

[@w1nchester551]

@@romantsarev1145 Спасибо, дошло. Не сразу понял, что нужно рассматривать все ребра, инцидентные вершинам, включенных в дерево и выбирать среди них минимальное.

[@maxim_bashkirovmusic7304]

Остовное дерево ударение на первое О

[@romantsarev1145]

Да, знаю. Когда погружался в тему только литература была доступна. Как там поймешь, где ударение... Надо бы переписать видео, да руки не доходят.

[@maxim_bashkirovmusic7304]

Roman Tsarev главное видео хорошее)) А вообще проверить можно Остов - Остовное

[@Sanya_paket]

Спасибо, вроде понятно. Осталось переварить и написать на java

[@romantsarev1145]

Пожалуйста

[@SergTyuboss]

О'стов, а не осто'в

[@romantsarev1145]

Да

[@SergTyuboss]

А вообще лучше говорить минимальное стягивающее дерево, ну его этот остов-скелет🙂

[@positivenozy6065]

Неверно, должно быть v-1 рёбер в минимальном оставном дереве

[@romantsarev1145]

Что "неверно"? Да, ребер в ОДМС v-1, т.е. на единицу меньше числа вершин. Так и вышло. Вершин шесть, ребер пять, сумма их весов минимальная из всех возможных. Или "неверное" это резюме какого-то вашего внутреннего диалога? 🤔

[@Русь-Родина]

Дизлайк за рекламу, барыга.

[@romantsarev1145]

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

[@Русь-Родина]

@@romantsarev1145 Я оплачиваю просмотр рекламы своим трафиком, фирмы платят за размещение рекламы. Тебе ютуб платит не за видео, а за рекламу, точнее за количество ее просмотров. Нет никаких гарантий, что твое видео не бред. Ютуб ничего полезного не предлагает кроме бреда. Так что дизлайк я поставил в любом случае правильно.

[@romantsarev1145]

@@Русь-Родина я так и написал, что мне за тебя рекламодатели платят через KZbin. Своим Интернет трафиком ты мне ничего не оплачиваешь. За бред во всем KZbin я отвечать не буду. А вот мое видео хорошее, что уж ты наговариваешь то?! Мне не веришь, комментарии почитай. Отрицательные выпиливаю только в случае оскорблений. В дизлайке по причине вынужденного просмотра рекламы не вижу ничего правильного. То есть ты жадничаешь заплатить 250 рублей за премиум, чтобы смотреть видео на KZbin вообще без рекламы. Выбираешь смотреть с рекламой, она тебя раздражает, а ты ставишь мне дизлайк при нормальном контенте. Я это правильным не считаю.

[@Русь-Родина]

@@romantsarev1145 меня же вынуждают свой программный код раскрывать бесплатно, хотя я знаю, что он давно уже украден. Поэтому и интереса к нему нет никакого. Почему я должен к другим после такого отношения относиться иначе? Трудись на благо человечества бесплатно. Станешь сильно популярным тебя забанят. Не продавайся за грош.