对齐问题：如何找到两组点之间的最小总距离？

Question

给定两个集合，假设 N 和 M 分别有 n 和 m 个点（每个点用 x 和 y 坐标描述），我如何找到 min(n,m) 点的最佳对齐，以便我最小化对齐点的欧氏距离之和？

我试图避免比较 N 和 M 点的每种可能组合的蛮力方法。

我仔细阅读了它和 Assignment problem，看来我可以将其定义为线性规划来解决它。但是，我不确定如何编写程序（例如在 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] ]

有人可以指点一下吗？

Answer 1

如果我没有正确理解你想要完成的事情，假设你有一些要点

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

和其他一些要点

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

您想在第一组和第二组的元素之间建立对，以便该组中点数最少的每个点都与另一个组中的唯一点相匹配。使用上面的示例输入，我们期望结果：

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

here 有一个 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，然后 returns 具有键 :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}

扩展答案：其他 objective 函数

上述解决方案最小化了原问题中所述的 objective 函数："minimise the sum of euclidean distances"

然而，这可能并不总能带来预期的结果，例如在

的特殊情况下

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

有两个可能的解决方案具有相同的最小化距离。为了更喜欢精确匹配的那个，我们必须调整 objective 函数 。我们将 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)))

在这里，只要存在完全匹配，我们就简单地 return 一个较大的负距离，以强烈倾向于该分配。

对齐问题：如何找到两组点之间的最小总距离？

Alignment problem: how do I find the minimum overall distance between two sets of points?

clojure

alignment