Алгоритъм за съпоставяне на набори от точки

Имам два набора от точки A и B, докато точките могат да бъдат 2D или 3D. И двата комплекта имат еднакъв размер n, който е доста нисък (5 - 20).

Бих искал да знам колко добре се съгласуват тези комплекти. Тоест, в идеалния случай бих намерил двойки между точките, така че сумата от всички евклидови двойки разстояния d(A,B) да е минимална. Така

d(A,B) = \sum_{i=1}^n ||A_i - B_i||_2

Крайният резултат се използва за сравнение с други набори от точки. Така например:

  • A = (1,1), (1,2), (1,3)
  • B = (1,1), (2,2), (1,3)

ще ми даде d(A,B) = 1.

  • C = (1,1), (2,1), (3,1)
  • D = (2,1), (2,2), (3,1)

ще ми даде d(C,D) = 1.414.

Някакви добри идеи?


algorithm geometry dynamic-programming mathematical-optimization
person ypnos    schedule 20.01.2015    source източник
comment
Как постигате d(C,D) = 2? Какво междуточково разстояние използвате? Проверете cs.smith.edu/~orourke/TOPP/P6.html   -  person Yves Daoust    schedule 20.01.2015
comment
Съжалявам, че беше грешка. Бих използвал евклидово разстояние.   -  person ypnos    schedule 20.01.2015
comment
Формулата, която използвате за изчисляване на d(a,b), изобщо не е очевидна. Моля, пояснете.   -  person RBarryYoung    schedule 20.01.2015
comment
Вашата връзка ме отведе до тази статия, съдържаща компактно описание на алгоритъма: Sayan Bhattacharya. Проучване на алгоритмите за евклидово съпоставяне. db.cs.duke.edu/courses/cps234/fall08/ проекти/sayan_proj.pdf   -  person ypnos    schedule 20.01.2015
comment
Скрит зад кулисите тук е проблем с графиката (двустранно съвпадение с минимална цена): en.wikipedia.org/wiki /Hungarian_algorithm   -  person Rerito    schedule 21.01.2015

Отговори (1)


arrow_upward
4
arrow_downward

Можете например да моделирате проблема си като проблем с присвояването (връзка към Wikipedia ), където дефинирате цената C_ij за присвояване на точка A_i (от набор A) на точка B_j (от набор B), за да бъде равна на разстоянието между тях. След това този проблем с присвояването може да бъде решен с помощта на унгарския алгоритъм (връзка към Wikipedia).

person Fanfan    schedule 20.01.2015
comment
Вашият отговор вече е много полезен. Алгоритъмът е O(n^3). Би било чудесно, ако има по-бърз алгоритъм за моя случай. - person ypnos; 21.01.2015
comment
Разбрах, че Earth Mover's Distance, който споменах във въпроса си, също използва унгарския алгоритъм. Той обаче използва оптимизации (напр. фактът, че разходите произтичат от показател). Така че изглежда най-добрият избор за мен. - person ypnos; 21.01.2015