8

ポイントの X、Y 座標を含む 2 つのリストがあります。リスト 1 には、リスト 2 よりも多くのポイントが含まれています。

タスクは、全体のユークリッド距離が最小になるように点のペアを見つけることです。

私は作業コードを持っていますが、これが最善の方法であるかどうかはわかりません。リストはそれぞれ約2000要素であるため、結果（最小値を見つけるためのより良いアルゴリズム）または速度のために改善できるヒントを取得したいと思います.

サンプル ベクトルのラウンドは、同じ距離のポイントも取得するために実装されています。「rdist」関数を使用すると、すべての距離が「距離」で生成されます。マトリックスの最小値よりも、2 つのポイントをリンクするために使用されます ("dist_min")。これらの 2 点のすべての距離は NA に置き換えられ、リスト 2 のすべての点がリスト 1 の点を持つまで、次の最小値を検索することによってループが続行されます。最後に、視覚化のためのプロットを追加しました。

require(fields)

set.seed(1)
x1y1.data <- matrix(round(runif(200*2),2), ncol = 2)   # generate 1st set of points 
x2y2.data <- matrix(round(runif(100*2),2), ncol = 2)   # generate 2nd set of points

distances <- rdist(x1y1.data, x2y2.data)
dist_min <- matrix(data=NA,nrow=ncol(distances),ncol=7)   # prepare resulting vector with 7 columns

for(i in 1:ncol(distances)) 
{
    inds <- which(distances == min(distances,na.rm = TRUE), arr.ind=TRUE)

    dist_min[i,1] <- inds[1,1]              # row of point(use 1st element of inds if points have same distance)
    dist_min[i,2] <- inds[1,2]              # column of point (use 1st element of inds if points have same distance)
    dist_min[i,3] <- distances[inds[1,1],inds[1,2]] # distance of point
    dist_min[i,4] <- x1y1.data[inds[1,1],1]     # X1 ccordinate of 1st point
    dist_min[i,5] <- x1y1.data[inds[1,1],2]     # Y1 coordinate of 1st point
    dist_min[i,6] <- x2y2.data[inds[1,2],1]     # X2 coordinate of 2nd point
    dist_min[i,7] <- x2y2.data[inds[1,2],2]     # Y2 coordinate of 2nd point

    distances[inds[1,1],] <- NA # remove row (fill with NA), where minimum was found
    distances[,inds[1,2]] <- NA # remove column (fill with NA), where minimum was found
}

# plot 1st set of points
# print mean distance as measure for optimization
plot(x1y1.data,col="blue",main="mean of min_distances",sub=mean(dist_min[,3],na.rm=TRUE))       
points(x2y2.data,col="red")                         # plot 2nd set of points
segments(dist_min[,4],dist_min[,5],dist_min[,6],dist_min[,7])   # connect pairwise according found minimal distance

最小距離で出力

4

1 に答える 1

11

これは、代入問題として知られる組み合わせ最適化の基本的な問題です。割り当て問題を解決する 1 つのアプローチは、R パッケージの手がかりに実装されているハンガリー語のアルゴリズムです。

require(clue)
sol <- solve_LSAP(t(distances))

単純なソリューションよりも優れていることを確認できます。

mean(dist_min[,3])
# [1] 0.05696033
mean(sqrt(
  (x2y2.data[,1] - x1y1.data[sol, 1])^2 +  
    (x2y2.data[,2] - x1y1.data[sol, 2])^2))
#[1] 0.05194625

そして、あなたの質問と同様のプロットを作成できます。

plot(x1y1.data,col="blue")       
points(x2y2.data,col="red")
segments(x2y2.data[,1], x2y2.data[,2], x1y1.data[sol, 1], x1y1.data[sol, 2])

ここに画像の説明を入力

于 2012-12-20T00:47:31.833 に答える