Алгоритм Прима
HTML-код
- Опубликовано: 17 апр 2017
- Алгоритм построения остовного дерева минимальной стоимости. Впервые предложен чешским математиком Войцехом Ярником в 1930 году. Позже, в 1957 году, независимо от Ярника разработан Робертом Примом, именно, за ним и закрепилось название этого алгоритма построения минимального остовного дерева.
Спасибо ВАМ, очень помогли.
Пожалуйста!
Доброго времени суток, спасибо за видео) Добавьте (если будет возможность) про алгоритм Борувки) Было бы полезно.
Спасибо, все предельно понятно))
Пожалуйста
спасибо
Пожалуйста
Начало : 1:45
Конец : 4:08
Спасибо!)
Спасибо! Все понятно, вот толь-ко между 5 и 6 нету стоимости ребра
Пожалуйста. Да, стоимость ребра слетела при подготовке видео. Надеюсь, это несильно сбивает с толку. Стоимость ребра (5, 6) равна 6.
@@romantsarev1145 надеетесь что это сильно сбивает с толку?
@@user-hk2hf4fb2s )
Спасибо, вроде понятно. Осталось переварить и написать на java
Пожалуйста
Це відео допомогло мені зробити реферат по цій темі, дякую за добрий контент
Пожалуйста. Рад, что помогло.
а что делать, если в матрице Р в одном столбце несколько значений разных, а в каком то столбце вообще нет значений кроме 0(на протяжении алгоритма в матрицах значения в этом столбце не менялись)?Как восстанавливать путь тогда?
Что за матрица Р? 🤔
@@romantsarev1145 не под тем видео коммент оставил. Я про видео о алгоритме флойда.
@@user-ro1jv6gn3n Вы тогда там оставьте коммент, я туда отвечу
А каково практическое применение этого метода? С алгоритмом Дейкстры и Флойда понятно, там мы кратчайший (самый дешевый) путь ищем, а тут? В примере 1-4=5, а, 1-3-4=6, но на первом шаге мы отбросили ребро 1-4 потому что 1-3 дешевле.
Решили, например, сетки кинуть между шестью компами. Расстоянием между ними известно. Нужно соединить так, чтобы как можно меньше кабеля потратить.
А при чем тут кратчайший путь вообще не понятно. Постановка задачи одна, а рассуждения о решении совершенно другой задачи. Так Вы минимальный по стоимости остов хотите найти или кратчайший путь? Это разные задачи.
@@romantsarev1145 Да, точно, задачи логистики.
Задачи разные, согласен
А как мы перешли от 6-4 к 3-2? До этого мы шли по инцидентным вершинам к текущей, но 4 и 2 не инцидентны. Перепрыгнули как-то. И еще ничего не говорится о циклах.
Множество U - вот ответ на оба Ваших вопроса. "...мы должны на каждом шаге выбирать ребро минимальной стоимости, которое связывает одну вершину из множества U и вершину, которая в множество U пока не входит" (2:01). Вот так мы и перешли от 6-4 (в этом момент во множество U входили вершины 1, 3, 4, 6) к 3-2 (2 в множество U не входило), и минимальный вес ребра из всех рассматриваемых был равен 5 (то самое ребро 3-2).
Зачем мне что-то говорить о циклах? Если Вы работаете как описано в видео, то есть с использованием множества U, то циклы не возникнут никогда.
нужно рассматривать все ребра, инцидентные вершинам, включенных в дерево и выбирать среди них минимальное. так как 6-4 было минимально с весом 2, а потом из всех мин ребер было 3-2 с весом 5
Остовное дерево ударение на первое О
Да, знаю. Когда погружался в тему только литература была доступна. Как там поймешь, где ударение... Надо бы переписать видео, да руки не доходят.
Roman Tsarev главное видео хорошее))
А вообще проверить можно Остов - Остовное
5-6 это не ребро с весом 0?
Там 6 должно быть.
Как бы вы действовали если бы ребро (1,4) имело бы стоимость 2, а ребро (6,4) 3?
Тогда дерево бы строилось так: (1,3), (1,4), (4, 6)...
@@romantsarev1145 Спасибо, дошло. Не сразу понял, что нужно рассматривать все ребра, инцидентные вершинам, включенных в дерево и выбирать среди них минимальное.
О'стов, а не осто'в
Да
А вообще лучше говорить минимальное стягивающее дерево, ну его этот остов-скелет🙂
Дизлайк за рекламу, барыга.
Тут дело такое. Я считаю, что любая работа должна быть оплачена. В том числе моя. Ты же понимаешь, что я проделал некоторую работу, чтобы ты мог посмотреть это видео. Ну, так вот, видео то ты посмотрел, а денег мне не прислал. Зато за тебя заплатила та компания, чью рекламу тебе показали. Таким образом баланс сохранился. Но ты, по ходу, это не догоняешь. Так что дизлайк тебе ответкой.
@@romantsarev1145 Я оплачиваю просмотр рекламы своим трафиком, фирмы платят за размещение рекламы. Тебе ютуб платит не за видео, а за рекламу, точнее за количество ее просмотров. Нет никаких гарантий, что твое видео не бред. Ютуб ничего полезного не предлагает кроме бреда. Так что дизлайк я поставил в любом случае правильно.
@@Русь-Родина я так и написал, что мне за тебя рекламодатели платят через RUclips. Своим Интернет трафиком ты мне ничего не оплачиваешь. За бред во всем RUclips я отвечать не буду. А вот мое видео хорошее, что уж ты наговариваешь то?! Мне не веришь, комментарии почитай. Отрицательные выпиливаю только в случае оскорблений.
В дизлайке по причине вынужденного просмотра рекламы не вижу ничего правильного. То есть ты жадничаешь заплатить 250 рублей за премиум, чтобы смотреть видео на RUclips вообще без рекламы. Выбираешь смотреть с рекламой, она тебя раздражает, а ты ставишь мне дизлайк при нормальном контенте. Я это правильным не считаю.
@@romantsarev1145 меня же вынуждают свой программный код раскрывать бесплатно, хотя я знаю, что он давно уже украден. Поэтому и интереса к нему нет никакого. Почему я должен к другим после такого отношения относиться иначе? Трудись на благо человечества бесплатно. Станешь сильно популярным тебя забанят. Не продавайся за грош.