Венгерский алгоритм(Hungarian Algorithm)

[mrgloom_]

порекомендуйте какую нибудь библиотеку по этому алгоритму, которая легка в использовании, желательно которую сами использовали или у которой есть примеры по использованию.
еще говорят не у всех библиотек на деле $O(N^3)$

я не уверен но помоему это так же называется bipartite graph matching(паросочетания в двудольном графе).

нужно это для сопоставления точек типа такого.

[longstreet]

mrgloom_ в сообщении #612986 писал(а):

еще говорят не у всех библиотек на деле $O(N^3)$

$O(N^3)$ это в модифицированном алгоритме, а в классическом $O(N^4)$.

[Zealint]

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

Вам нужен алгоритм алгоритм Cost Scaling с двойным проталкиванием предпотока, который и пишется короче Венгерского и в десяток раз быстрее работает при n порядка пары тысяч.

А если Вам нужны именно паросочетания, а не назначения, то есть много простых алгоритмов с субкубическим временем.

-- Пт авг 31, 2012 17:03:16 --

Забыл добавить, библиотек по этому поводу не знаю, такие алгоритмы всегда пишу своими руками.

[mrgloom_]

http://stackoverflow.com/questions/5505 ... th-minimum

тут вот еще рассмотрены какие то приближённые решения.

[mrgloom_]

Цитата:

А если Вам нужны именно паросочетания, а не назначения

я не уверен , мне нужны пары точек, которые бы минимизировали некоторую метрику.
вообще для каждой точки вычисляется некий дескриптор (shape context) и потом для каждой пары точек составляется матрица (cost matrix).
Возможно стоит еще попробовать решить задачу в постановке минимизации евклидова расстояние между точками.

попробовал ваш алгоритм-победитель вроде работает, продолжу тестирование, только непонятно можно ли поставить задачу для не квадратной матрицы? (т.е. сейчас я просто дополняю фиктивными элементами до квадратной)

[Zealint]

mrgloom_ в сообщении #614125 писал(а):

только непонятно можно ли поставить задачу для не квадратной матрицы? (т.е. сейчас я просто дополняю фиктивными элементами до квадратной)

Я бы наверное ответил, если бы понял суть задачи. Но пока строгого описания я не вижу. Я пока понял, что для каждой пары точек составляется матрица. Но даже то, как она выглядит здесь неясно. Картинки вообще ни о чём не говорят.

-- Пн сен 03, 2012 15:48:21 --

mrgloom_ писал(а):

и потом для каждой пары точек составляется матрица

И вообще, если матрица строится для каждой пары точек, то сколько матриц-то?

[mrgloom_]

если кратко, то тут слайд 6
http://www.cs.utexas.edu/~grauman/cours ... AEKLEE.pdf
матрица одна, я не правильно выразился.

[Zealint]

Ну, если я правильно понял, нужно отыскать максимальное по мощности паросочетание в двудольном графе с минимальной суммой рёбер. Это и есть задача о назначениях. Если граф имеет разное число долей (матрица не квадратная), то алгоритм можно модифицировать, если знать принцип его работы. В моей статье есть все необходимые ссылки. Не знаю, чем я тут ещё могу помочь. Можно и дополнять до квадрата; в любом случае надо смотреть, изучать, исследовать... Может быть у вас матрица всегда имеет такой вид, что жадный алгоритм будет давать удовлетворительное решение.

[mrgloom_]

я не понял cost scaling работает аналогично\идентично Hungarian Algorithm, только быстрее?
возможно ли поставить задачу для double в матрице?(т.е. не нарушит ли это алгоритм?)

может у вас есть еще мысли как решить мою задачу- получить пары точек или что примерно тоже самое получить трансформацию между двумя сетами точек?

еще мне кажется, что если решать задачу как минимизацию евклидова расстояния результат получится примерно как у ICP(Iterative Closest Point) http://en.wikipedia.org/wiki/Iterative_closest_point

[Zealint]

mrgloom_ в сообщении #614618 писал(а):

я не понял cost scaling работает аналогично\идентично Hungarian Algorithm, только быстрее?
возможно ли поставить задачу для double в матрице?(т.е. не нарушит ли это алгоритм?)

Нет, это совершенно разные алгоритмы. Подставить double нельзя так как алгоритм основан на поиске приближённого решения с точностью до степеней двойки. Сначала масштаб цен (cost) большой, затем уменьшается вдвое (scaling), потом ещё раз и так, пока не станет равным 1. На последней итерации найденное решение является оптимальным с точностью до $1=2^0$, поэтому оно на самом деле оптимально только для целых чисел. Хотя с дробными может просто повести.

Если нужно, чтобы с дробными тоже работал, нужно умножить все числа на 10 в подходящей степени, чтобы они стали целыми. Потом ответ поделить на то же самое.

Цитата:

может у вас есть еще мысли как решить мою задачу- получить пары точек или что примерно тоже самое получить трансформацию между двумя сетами точек?

Вообще нету ни мыслей, ни желания что-то делать без глубокого анализа задачи. А глубокий анализ я делаю только для своих задач.