比方說，我有3種不同顏色塊的房間，標記爲A，B和C： 
最近塊，每種顏色的一個，但在不同的行
我的目標是找到三個最靠近Lolo的塊使得我有一個A，一個B和一個C.另外，每個塊和Lolo本身必須位於不同的行上： 
例如，可以使用行1上的塊，因爲洛洛在那一排上： 
如果我們選擇上述洛洛的塊，從0行沒有其他塊可用於： 
在這個例子中，正確的答案是這些塊： 
我可以很容易地找到最近的3到洛洛的路上;然而，我很難應用額外的約束（每個字母之一，而不是在同一行）。這感覺就像旅行商問題的變化。
什麼是解決這些塊的有效方法？ （即使在正確的方向點將不勝感激！）謝謝！
貪婪的解決方案：
下面塊的所有采摘應該做這樣它符合該行的限制。
bestDistanceSoFar/3進一步，否則重複從1爲此我建議爲每種顏色分類列表。
我相信這是最佳的，但爲什麼它會需要一些思考。
預處理：
您可以從洛洛進一步清除所有塊的同一行洛洛的，正如你所說，而且所有塊比同排在同類型的另一塊，這是不在這種情況下很多，但仍然如此。
附加說明：
假設你只有3種顏色，蠻力的運行時間將是爲O（n ），這是比少了很多O（n！）或O（2 n）。
明顯優化蠻力是所有的顏色分離，這將導致爲O（n ÑÑ）的運行時間，其中n 我是量第i個顏色塊。
似乎可以通過使用2D k-d樹來改進此算法，並使用它找到每個顏色/字母的最近鄰居。似乎應該將算法限制爲O（N log N），可能具有較高的係數（從構建多個kd樹並移除多個點）。 – Nuclearman
謝謝！事實證明，單獨的預處理技術已經消除了足夠的塊，我現有的強力解決方案變得足夠快。 – iccir
@Nuclearman我認爲kd-tree可能會讓事情變得更復雜。按照距洛洛的歐式距離排序的列表應該足夠了。 – Dukeling
我認爲你應該使用DFS
你在接下來的方式建立G：
你建立你可以深入3運行DFS圖表後，選擇最低成本路徑直接兒子。
這會給你最低的距離。
還有其他限制嗎？它需要運行多快？
爲它提到的預處理技術（我們最終使用）選擇了其他答案，但是對此進行了改進。謝謝！ – iccir
我可以通過取3個塊的每個子集來蠻力，計算到Lolo的加法距離，按距離上升對其進行排序，然後測試每個子集的附加約束。當然，必須有一個更優雅的方式:) – iccir
「A」必須比「C」更接近Lolo嗎？或者是否有限制塊的親密排序？ IE，「A」必須最接近，然後是「B」，然後是「C」？ –
「A」可以比「C」更遠離Lolo。 – iccir