Hexagon計劃中的最短路徑？

在最新的IEEE Xtreme競賽中，我試圖解決的一個問題是，Hexagon計劃中的最短路徑？

輸入兩點p1（x1，y1），p2（x2，y2）必須找到p1的最短路徑長度到P2，

例如，如果P1（1,1），P2（4,4），那麼最短路徑的9個邊緣lenght，

enter image description here

我不喜歡的東西深度優先搜索，如果兩點之間的距離很小，並且對於點（1,1）需要很長時間（10,10），

並且最大點（12,12）的點數有限制。

我的方法是將上述圖片轉換爲所有權重爲1的無向圖，然後找到最短路徑。

這裏是我的功能找到最短路徑：

int minCost; 
vector<int> path; 
multimap<int,int> Connections; 
typedef multimap<int,int>::iterator mmit; 

void shortestPath(int cs){ 
    if(cs > minCost) 
     return; 
    if(path.back() == Target){ 
     if(cs < minCost) 
      minCost = cs; 
     return; 
    } 

    pair<mmit,mmit> it = Connections.equal_range(path.back()); 
    mmit mit = it.first; 

    for(; mit != it.second ; ++mit){ 
     if(isVisited(mit->second)) 
      continue; 
     markVisited(mit->second); 
     path.push_back(mit->second); 
     shortestPath(cs+1); 
     markUnvisited(mit->second); 
     path.pop_back(); 
    } 
}

有什麼方法比這個更快？我可以使用dijkstra來獲取這張無向圖嗎？

來源

2012-11-11 Rami Jarrar

也許使用廣度優先搜索？ – irrelephant

使用深度優先搜索似乎是最糟糕的想法！看起來廣度優先搜索是要走的路（這應該相當於最好的搜索，因爲所有步驟的大小都是相同的）。鑑於從源頭到目標的方向是已知的，你也可以排除任何向錯誤方向移動的東西。 –

aha，我會嘗試bfs，但是如何知道目標的方向？ –

使用Dijkstra或任何類型的基於圖形的搜索似乎在這裏總是矯枉過正。在每個頂點，您只需選擇使您更接近目標的下一個頂點。

所以你從（1,1）的中心開始。您需要選擇起始頂點。顯然這是東南部的一個。

從那裏，你有三種選擇：向西移動，向東北移動或向東南移動。這實際上是每個第二個頂點的選擇。你選擇讓你更接近的方向（即，與目標對準最小的角度）。

事實上，你可以用一種很嚇人的方式表示所有的頂點座標。請注意，它們大致位於六邊形座標之間的一半處。所以你可以說第一個頂點在(1.5,1.33)。

你在第一座標可能的行動是方向：

west  = (0, -0.67) 
north-east = (-0.5, 0.33) 
south-east = (0.5, 0.33)

我們稱之爲奇運動。現在，連動你有這些選擇：

east  = (0, 0.67) 
north-west = (-0.5, -0.33) 
south-west = (0.5, -0.33)

因此，所有你需要做的是，對每個可能的方向，測試新的距離（直線距離 - 即畢達哥拉斯）到目標。選擇三個選項中距離最短的新頂點。顯然你不必計算實際的距離 - 距離平方很好。

我敢肯定，你可以計算出最初和最後的動作。

最後一點，顯然我使用的是不精確的雙重算術。你可以將你所有的方向（當然你的六邊形座標）縮放6並使用整數。

來源

2012-11-11 23:13:01 paddy

你能爲此提供一些代碼或僞代碼嗎？ –

這個問題在我看來只不過是曼哈頓距離的一個特殊版本而已。你不能基於修改後的座標明確計算解決方案嗎？ – ypnos

不，我無法理解修改後的座標！ –

Hexagon計劃中的最短路徑？

回答

相關問題