Nano Hash - криптовалюты, майнинг, программирование

Алгоритм Каргера с весами

Предположим, что нам дан неориентированный невзвешенный граф G=(V,E) и некоторая функция стоимости c:E→R>0, присваивающая каждому ребру e∈E положительную стоимость c(e). Цель состоит в том, чтобы вычислить минимальный разрез G с минимальной стоимостью (т. Е. Минимальный разрез стоимости среди разрезов, состоящих из наименьшего количества ребер). Приведите алгоритм, который с высокой вероятностью находит такое минимальное сокращение затрат за полиномиальное время. Каково время работы вашего алгоритма? Подсказка: алгоритм Каргера

Подход I: выполните Karger n ^ c раз (все еще полиномиальный, повышает показатель степени n от c) и сравните полученные минимальные сокращения. с с>=1

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

или даже сочетание того и другого?

random graph algorithm graph-algorithm kargers-algorithm
17.08.2019

Ответы:


1

Подход I ничего не добавляет к алгоритму Каргера. Из введения к этой статье: количество раз минимальное сечение может быть найдено с высокой вероятностью." Другими словами, Подход I уже является частью алгоритма.

Подход II технически не нужен (алгоритм Каргера в любом случае в конечном итоге найдет минимальное сечение) и может активно нарушать алгоритм. Например, рассмотрим граф, который можно разрезать, удалив одно конкретное ребро, но в противном случае для разрезания требуется два или более ребра (числа обозначают стоимость ребра):

введите здесь описание изображения

Если это конкретное ребро имеет самую высокую стоимость (999 в этом примере), то повышение вероятности выбора этого ребра для сокращения уменьшает вероятность нахождения (минимальной стоимости) минимального разреза. На самом деле, это снижает вероятность нахождения (любой стоимости) минимального сокращения.

Так что все, что вам нужно сделать, это запустить стандартный алгоритм. На каждой итерации вам нужно проверить, имеет ли вновь найденный разрез меньше ребер, чем текущий лучший разрез. Если это так, то вновь найденный разрез является лучшим (пока что). Если вновь найденный разрез имеет то же количество ребер, что и текущий лучший разрез, сравните затраты, чтобы определить, какой из них лучше.

17.08.2019
Новые материалы
Кластеризация: более глубокий взгляд
Кластеризация — это метод обучения без учителя, в котором мы пытаемся найти группы в наборе данных на основе некоторых известных или неизвестных свойств, которые могут существовать. Независимо от..
Как написать эффективное резюме
Предложения по дизайну и макету, чтобы представить себя профессионально Вам не позвонили на собеседование после того, как вы несколько раз подали заявку на работу своей мечты? У вас может..
Частный метод Python: улучшение инкапсуляции и безопасности
Введение Python — универсальный и мощный язык программирования, известный своей простотой и удобством использования. Одной из ключевых особенностей, отличающих Python от других языков, является..
Как я автоматизирую тестирование с помощью Jest
Шутка для победы, когда дело касается автоматизации тестирования Одной очень важной частью разработки программного обеспечения является автоматизация тестирования, поскольку она создает..
Работа с векторными символическими архитектурами, часть 4 (искусственный интеллект)
Hyperseed: неконтролируемое обучение с векторными символическими архитектурами (arXiv) Автор: Евгений Осипов , Сачин Кахавала , Диланта Хапутантри , Тимал Кемпития , Дасвин Де Сильва ,..
Понимание расстояния Вассерштейна: мощная метрика в машинном обучении
В обширной области машинного обучения часто возникает необходимость сравнивать и измерять различия между распределениями вероятностей. Традиционные метрики расстояния, такие как евклидово..
Обеспечение масштабируемости LLM: облачный анализ с помощью AWS Fargate и Copilot
В динамичной области искусственного интеллекта все большее распространение получают модели больших языков (LLM). Они жизненно важны для различных приложений, таких как интеллектуальные..