Проблема совмещения: как найти минимальное общее расстояние между двумя наборами точек? - PullRequest
Новая
       8

Проблема совмещения: как найти минимальное общее расстояние между двумя наборами точек?

0 голосов
/ 06 мая 2020

Учитывая два набора, скажем, N и M с количеством точек n и m соответственно (каждый описывается координатами x и y), как мне найти лучшее выравнивание точек min (n, m), чтобы минимизировать сумму евклидовых расстояний выровненных точек?

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

Я читал об этом и Задача присваивания , и кажется, что я могу определить ее как линейную программу для ее решения. Однако я не уверен, как я смогу написать программу (например, на Clojure) для решения этой проблемы. Это наиболее оптимальный способ?

Edit3: добавлен новый пример: хотя предоставленное решение для @Rulle, похоже, работает для приведенного выше примера, оно не работает для следующего: 

(def sample-set-a #{[0.575 0.675] [0.575 0.575]}) 

(def sample-set-b #{[0.575 0.675] [0.575 9.575]})

Что должно дать

[ [0.575 0.675] [0.575 0.675], [0.575 0.575][0.575 9.575] ]

Несмотря на то, что есть два возможных решения с одинаковым весом:

[ [0.575 0.575] [0.575 0.675], [0.575 0.675] [0.575 9.575] ]

Кто-нибудь может посоветовать ?

1 Ответ

1 голос
/ 06 мая 2020

Если я правильно понял, что вы пытаетесь выполнить sh, предположим, что у вас есть несколько точек 

(def sample-set-a #{[0 0] [1 0] [2 0] [0 1]})

и некоторые другие точки 

(def sample-set-b #{[1.1 -0.2] [0.01 0.99]})

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

#{[[1 0] [1.1 -0.2]] [[0 1] [0.01 0.99]]}

Для этого есть библиотека Clojure . Вы можете добавить зависимость [munkres "0.5.0"] в свой project.clj файл, а затем просто использовать эту библиотеку. Вот реализация вашей проблемы с использованием этой библиотеки: 

(ns assignment-problem.core
  (:require [munkres]))

(defn sqr [x]
  (* x x))

(defn dist [[x0 x1] [y0 y1]]
  (Math/sqrt (+ (sqr (- x0 y0))
                (sqr (- x1 y1)))))

(defn solve-euclidean-assignment [a b]
  (if (< (count b) (count a))
    (update (solve-euclidean-assignment b a) :assignments (partial mapv (comp vec reverse))) 
    (let [a (vec a)
          b (vec b)
          cost-matrix (for [x a]
                        (for [y b]
                          (dist x y)))]
      (munkres/minimize-weight cost-matrix a b))))

Функция solve-euclidean-assignment вызывается с двумя наборами точек, а затем возвращает карту с ключами :assignments и :weight, где :assignments содержит пары. Вот пример его вызова: 

(def sample-set-a #{[0 0] [1 0] [2 0] [0 1]})
(def sample-set-b #{[1.1 -0.2] [0.01 0.99]})
(solve-euclidean-assignment sample-set-a sample-set-b)
;; => {:assignments [[[1 0] [1.1 -0.2]] [[0 1] [0.01 0.99]]], :weight 0.23774893337370998}

РАСШИРЕННЫЙ ОТВЕТ: другие целевые функции

Приведенное выше решение минимизирует целевую функцию, как указано в исходной задаче: «минимизировать сумму евклидовых расстояний»

Однако это не всегда может привести к желаемому результату, например, в частном случае 

(def sample-set-a #{[0.575 0.675] [0.575 0.575]}) 
(def sample-set-b #{[0.575 0.675] [0.575 9.575]})

есть два возможных решения с таким же минимизированным расстоянием. Чтобы выбрать вариант с точным соответствием, мы должны настроить целевую функцию . Мы переименовываем dist в euclidean-dist, а затем возводим его в степень. Дробная степень меньше 1 будет иметь тенденцию отдавать предпочтение решениям с точным соответствием: 

(defn euclidean-dist [[x0 x1] [y0 y1]]
  (Math/sqrt (+ (sqr (- x0 y0))
                (sqr (- x1 y1)))))

(defn dist [a b]
  (let [e 0.5] ;; <-- A value less than 1 means we prefer exact matches. 
               ;; Raising to ½ is the same as computing the square root.
    (Math/pow (euclidean-dist a b) e)))

Вот еще один кандидат на функцию dist, который может быть легче понять: 

(defn dist [a b]
  (let [d (euclidean-dist a b)]
    (if (zero? d)
      -100
      d)))

Здесь мы просто возвращаем большое отрицательное расстояние всякий раз, когда есть точное совпадение, чтобы явно предпочесть это присвоение.

...