Описание тега hungarian-algorithm

Описание тега Вопросы с тегом
The Hungarian algorithm is a combinatorial optimization algorithm that solves the assignment problem, that of finding a maximum weight matching in a bipartite graph, in polynomial time.
2 ответа

Нахождение максимальной суммы счастья

У меня есть проблема, чтобы решить, и не вижу оптимального решения:/ Проблема заключается в: У меня есть n рабочих и k рабочих мест. Каждая работа должна выполняться указанным количеством работников, и у каждого работника есть свой уровень счастья д…
14 мар '15 в 14:49
1 ответ

Венгерский алгоритм для неквадратной матрицы

Я пытаюсь реализовать венгерский алгоритм. Все хорошо, за исключением случаев, когда матрица не квадратная. Все методы, которые я искал, говорят, что я должен сделать это квадратным путем добавления фиктивных строк / столбцов и заполнения фиктивной …
07 июл '18 в 12:52
3 ответа

Венгерский алгоритм с взаимными парами?

Я пытаюсь использовать следующую реализацию венгерского алгоритма: http://community.topcoder.com/tc?module=Static&d1;=tutorials&d2;=hungarianAlgorithm. Я хотел бы изменить этот алгоритм, чтобы я мог связать набор с самим собой. То есть, если "a" наз…
13 дек '14 в 03:21
1 ответ

Как нарисовать матрицу задач?

У меня есть задача с проблемой назначения. У нас есть один суперкомпьютер и n компьютеры и я хочу выполнить n задачи на них. Суперкомпьютер может рассчитывать только одну задачу в любое время, суперкомпьютер имеет отдельный компьютер. Компьютер полу…
08 июн '14 в 16:51
0 ответов

Алгоритм Christofides для ориентированного графа

Можно ли реализовать алгоритм Christofides для ориентированного графа? Предположим, у вас есть неориентированный граф, в котором каждая вершина имеет ребра в обоих направлениях относительно друг друга в графе (не в себе). Но веса ребер не обязательн…
11 июн '14 в 21:10
1 ответ

Венгерский алгоритм - метод Wikipedia для этого примера не работает

Я пытаюсь реализовать венгерский алгоритм в C. У меня есть матрица: 35 0 0 0 0 30 0 5 55 5 0 10 0 45 30 45 И я дошел до стадии, когда мне нужно найти минимальное количество строк, чтобы покрыть все нули (выполняя как можно больше назначений). Очевид…
18 окт '17 в 05:51
3 ответа

Как найти минимальное количество строк, необходимое для покрытия всех нулей в двумерном массиве?

Я пытаюсь сделать достойную реализацию венгерского алгоритма, однако я застрял в том, как найти минимальное количество строк, которые покрывают все нули в массиве Также мне нужно знать эти строки, чтобы сделать некоторые вычисления позже вот объясне…
09 апр '12 в 13:55
2 ответа

Венгерский алгоритм - произвольный выбор

Я рассмотрел несколько объяснений венгерского алгоритма для решения проблемы назначения, и подавляющее большинство из них покрывают очень упрощенные случаи. Самое понятное объяснение, которое я нашел, - это видео на YouTube. Я могу написать алгоритм…
08 авг '16 в 19:22
1 ответ

Оптимальные пары самых дальних точек

У меня есть четный набор точек в 2D. Мне нужен алгоритм, который может сделать пары таких точек, чтобы общая сумма расстояния между парами была максимальной. Я думаю, что динамическое программирование, жадный подход не сработает. Могу ли я использов…
23 июл '13 в 15:32
1 ответ

Венгерский алгоритм

Я нашел реализацию венгерского алгоритма, но у меня есть вопрос о значении "звездный ноль" и "загрунтованный ноль". Я думаю, что это используется для обозначения отмеченного нуля, но я не уверен. Это правильно? Это код: http://ccp.uchicago.edu/kheta…
24 апр '14 в 19:44
3 ответа

Учитывая 2 массива и оба имеют одинаковое количество элементов, построить все хешированные карты и вернуть

Например, два массива: var names = ['Tom','Jerry','Sam']; var hobbies = ['Eat','Sleep','Laugh']; Есть ли функция, которая может построить два массива в виде карт: {'Tome':'Eat','Jerry':'Sleep','Sam':'Laugh'} {'Tome':'Sleep','Jerry':'Eat','Sam':'Laug…
29 май '14 в 09:07
1 ответ

Венгерский алгоритм тупик

Я слежу за учебником на Youtube индийского парня о венгерской проблеме. Я складываю в точке, где он решает, какие строки и столбцы будут выбраны для следующего шага. В его примере нет проблемы, с которой я сталкиваюсь. Вот таблица моего примера: 2 1…
07 июн '16 в 18:47
1 ответ

Прямоугольная матрица Мункреса на основе столбцов взаимоисключающего выделения

Здесь я предоставляю Минимальный Полный Проверяемый Пример моей проблемы: Рассматривается прямоугольная матрица размером 3 X 17: строки = [10,6,9]. где столбцы являются шаблонами, каждый из которых связан со значением example file: "patterns_list" &…
08 июн '15 в 11:44
1 ответ

PL/SQL-реализация венгерского / кун-мункрского алгоритма

Где PL/SQL-реализация алгоритма Венгрии / Кун-Мункре? Похоже, я не могу найти в Интернете ничего.
16 мар '15 в 19:57
0 ответов

Связь данных / слияние нескольких объектов от нескольких (ненадежных) датчиков

Я хочу связать неизвестное количество объектов с неизвестным количеством наблюдений (может быть больше или меньше, чем количество объектов). Каждый пустой цветной круг является предсказанием местоположения объекта. В то время как каждая заполненная…
19 мар '18 в 15:01
1 ответ

Покрытие нулей минимальными строками по венгерскому методу

Я пытаюсь выполнить шаги по покрытию нулей минимальным количеством строк в венгерском методе следующим образом: Отметьте все неназначенные строки. Если отмеченная строка имеет нули, отметьте соответствующий столбец. В отмеченном столбце, если есть н…
19 июл '13 в 12:59
1 ответ

Венгерский алгоритм, соответствующий одному набору

Я ищу вариант венгерского алгоритма (я думаю), который соединит N людей с собой, исключая самопары и обратные пары, где N четно. Например, учитывая N0 - N6 и матрицу C затрат для каждой пары, как я могу получить набор из 3 пар с наименьшей стоимость…
21 мар '14 в 16:24
1 ответ

EMA-венгерский алгоритм не работает

Я хотел оформить заказ на эту венгерскую систему приложений. Я импортировал этот проект в NetBeans, но он выдает ошибку, так как error: cannot find symbol public class HungarianApp extends SingleFrameApplication { symbol: class SingleFrameApplicatio…
21 ноя '13 в 16:15
1 ответ

print_matrix библиотеки munkres python генерирует исключение для матрицы, содержащей нули

Lowest cost through this matrix: Traceback (most recent call last): File "muncre.py", line 8, in <module> print_matrix(matrix, msg='Lowest cost through this matrix:') File "/usr/lib/python2.7/dist-packages/munkres.py", line 730, in print_matri…
05 июн '15 в 11:30
1 ответ

Создайте группы из двух человек из списка людей с рейтингом

Я получил список людей и рейтинг того, насколько хороша эта комбинация. Мне нужно максимально увеличить рейтинг. Я уже посмотрел на венгерский алгоритм, но он решает немного другую проблему. Как вы можете решить такую ​​проблему?
25 янв '14 в 22:09