查找下面近日在採訪中質疑計劃

我們假設你有，以下笛卡爾座標系（象限I）的網格。

o - x - x - x - o 
| | | | | 
x - x - x - o - x 
| | | | | 
x - o - o - x - x 

where, o => person at intersection and x => no person at intersection 

class Point { 
int x; 
int y; 
boolean hasPerson; 
} 


Point findNearestPointWhereAllPeopleCanMeet(Point[] people) { 

}

實施，其中給予人的位置（點）名單的程序，找到一個位置（點），使得最接近點都給點。

你會如何解決這個問題？

1）方法是k-d樹，但你知道任何其他解決方案嗎？

來源

2011-12-20 Bmis13

如果「所有給定點的最近點」意味着距離的最小和，請查看http://en.wikipedia.org/wiki/Geometric_median – MBo

如果問題要求最小化Manhattan distance（即人們只能平行於座標軸行走），那麼問題就會變得很微不足道。首先，選擇座標是獨立的問題，並且選擇座標是x座標和和座標。

然後，對於每個座標，只需找到沿該軸的人的位置的中值。對於許多人的配置，可以有多個點將所有人的步行距離的總和最小化。（只要考慮2個人在x和相同的y座標上相隔2個以上的區塊;任何兩個人之間的相交將需要兩個人完全相同的步行）。

如果問題要求最小化歐幾里得距離，那麼目標是找到2變量L1中位數。這是一個標準問題，但它遠非微不足道。（例如，請參閱here。）有一個獨特的答案。鑑於這是一個面試問題，我懷疑這不適用。

來源

2011-12-20 08:33:39

之前要學習KD樹這些都是來到我的腦海裏的一些想法：

迭代的每一點你的矩陣，圖表，或不管它是
分配給每個點（X，Y ）代表從Point到任何人的MAX_distance的值。（參見下面一澄清示例）
採取任何具有最低MAX_DISTANCE

E.G.的點的給定的點（0,0）：

對於（1,0）的距離爲：1
對於（2,0）的距離爲：2
對於（0,2）的距離是：2
對於（3,1）的距離爲：4
對於（4,2）的距離爲：6

的MAX_DISTANCE爲（0,0）6中給出的輸入最低的MAX_distance應該是3，並且有許多像這樣的值的點（2,1）f或實例。

應該有辦法讓這個算法更有效率..也許用kd trees：p或者像其他調整一樣，比如檢查總人數，他們的相對位置/距離，任何迭代的MAX_distance值等。

來源

2011-12-20 06:33:30 Gevorg

這可能會給你一個比正確答案更多的近似值。但也許你可以嘗試某種聚類（見醫學圖像處理）

如果你的項目的所有點到Y軸：

3* 
4* 
3*

然後投射到X軸：

2* 2* 2* 2* 2*

圖例：3 *表示座標軸上的3個人

現在找到也使用權重的中位數（weight @location =有多少人在第在軸上的位置）

如果您找到兩個座標軸的中位數，那麼您可以將會議點數作爲（medianX，medianY）。

如果您在計算一個座標軸上的中位數時，還可以通過計算另一個座標軸的中位數來確保距離最小化，您可以得到正確的最近點。後一種情況比較困難。

來源

2011-12-20 19:21:25 Adrian

查找下面近日在採訪中質疑計劃

回答

相關問題