ИШ
Различные падежи, производные существительные, не найдешь ведь
Size: a a a
2020 May 21
AK
Различные падежи, производные существительные, не найдешь ведь
А также синонимы, иносказания и прочее-прочее-прочее
IC
Здравствуйте
а как объяснить вот этот перекос, на котором обращают внимание в курсе?
а как объяснить вот этот перекос, на котором обращают внимание в курсе?
IC
OT
кто нибудь знает аналог cumsum в pandas для строк ?
AK
#C3W1 Алгоритм Крускала на 2:31. Это же не алгоритм Крускала, нет? Это Алгоритм Прима. https://www.coursera.org/learn/unsupervised-learning/lecture/7NBYV/grafovyie-mietody-klastierizatsii
AK
AK
Ошибаюсь/нет?
AG
сейчас посмотрю)
AG
пока скажу, что мин остов ищется и тем и тем методом, но Крускал более популярен, потому что пишется легко
AG
и работает быстро, если заюзать RMQ
AG
там сортируются ребра по возрастанию и добавляются по увеличению веса
AG
пропускаются ребра, из-за которых могут образовываться циклы
AG
Прим по другому работает
AG
ты перепутал немного, у Приму добавляется не минимальное допустимое, а минимальное смежное с текущим деревом
AG
Прим именно строить на каждом шаге дерево, а на стадии Крускала может быть лес, а на последней получится строго дерево
AG
вообще по опыту олимпиадных задач Прима никогда не писал) только Крускала
AK
Описание Прима с вики:
«Сначала берётся произвольная вершина и находится ребро, инцидентное данной вершине и обладающее наименьшей стоимостью. Найденное ребро и соединяемые им две вершины образуют дерево. Затем, рассматриваются рёбра графа, один конец которых — уже принадлежащая дереву вершина, а другой — нет; из этих рёбер выбирается ребро наименьшей стоимости. Выбираемое на каждом шаге ребро присоединяется к дереву. Рост дерева происходит до тех пор, пока не будут исчерпаны все вершины исходного графа.»
«Сначала берётся произвольная вершина и находится ребро, инцидентное данной вершине и обладающее наименьшей стоимостью. Найденное ребро и соединяемые им две вершины образуют дерево. Затем, рассматриваются рёбра графа, один конец которых — уже принадлежащая дереву вершина, а другой — нет; из этих рёбер выбирается ребро наименьшей стоимости. Выбираемое на каждом шаге ребро присоединяется к дереву. Рост дерева происходит до тех пор, пока не будут исчерпаны все вершины исходного графа.»
AK
Описание из лекции:
"Изначально множество уже найденных ребер будет пустым. Затем на первом шаге мы добавим ребро с минимальным весом. Мы рассматриваем случай взвешенного графа, потому что наша задача — получить именно минимальное остовное дерево, то есть дерево, для которого суммарный вес ребер будет минимальным, и в то же время это будет остовное дерево. На каждом шаге мы добавляем ребро, одна из вершин которого уже принадлежит множеству выбранных вершин, а другая еще не принадлежит. И при этом среди всех таких ребер вес у добавляемого ребра должен быть самым маленьким. В тот момент, когда у нас задействованы все вершины графа, мы получаем остовное дерево, и оказывается, можно доказать, что это будет минимальное остовное дерево.»
"Изначально множество уже найденных ребер будет пустым. Затем на первом шаге мы добавим ребро с минимальным весом. Мы рассматриваем случай взвешенного графа, потому что наша задача — получить именно минимальное остовное дерево, то есть дерево, для которого суммарный вес ребер будет минимальным, и в то же время это будет остовное дерево. На каждом шаге мы добавляем ребро, одна из вершин которого уже принадлежит множеству выбранных вершин, а другая еще не принадлежит. И при этом среди всех таких ребер вес у добавляемого ребра должен быть самым маленьким. В тот момент, когда у нас задействованы все вершины графа, мы получаем остовное дерево, и оказывается, можно доказать, что это будет минимальное остовное дерево.»