船上數字的最短路徑

我在做家庭作業（C++）時遇到了麻煩。我並不是要求完整的解決方案，但向正確的方向傾斜可能會有所幫助。 :)船上數字的最短路徑

我在該板上有一個NxN板（最大N = 100）和一個1x2的數字（立方體）。立方體一側塗成紅色，另一側塗成藍色。爲立方體默認位置留在板的上側角，藍色的一面朝上：

B B . . 
. . . . 
. . . . 
. . . .

（4×4例子中，B代表藍色）

有可能是在黑板上的寶石（障礙物）。 移到我可以用我的身材令：

旋轉它90/180/270度順時針
可以前後翻頁的左/右/上/下邊緣的立方體，改變它的'向上顏色 ''

有關示例，使用權利上的默認位置翻轉：

. . R R 
. . . . 
. . . . 
. . . .

，然後使用旋轉90：

. . R . 
. . R . 
. . . . 
. . . .

，然後使用翻轉左：

. B . . 
. B . . 
. . . . 
. . . .

當然，旋轉或翻轉時，你不能降落在石碑上。因此，問題是 - 對於任何給定的電路板配置（圖形位置和石頭位置）編寫一個程序，該程序將使默認位置（藍色方向向上！）使用最少的移動次數並返回1如果可能或返回0如果這是不可能的。

我覺得這個問題很有趣，但我不得不承認我對它有些困惑。特別是藍色的一面/紅色的一面。我無法真正弄清楚如何「翻譯」我可以用通常最短路徑算法的語言來使用這些移動（並且我從未使用過任何這些算法）。所以，我會很感激你的每一條建議！ :)

來源

2012-05-27 ante.ceperic

紅色/藍色的東西只是增加了一個反轉旋轉方向的成本。即您的成本函數需要採用方向參數添加返回非對稱成本圖。 – starbolin

實際上它比這更復雜，因爲翻轉實際上是以無法實現旋轉的方式將立方體從其初始位置移開。並不總是可能在路徑的盡頭翻轉。 –

關鍵是推導一個成本函數以達到每個可能的相鄰位置。搜索'成本空間'需要處理達到給定位置的'如何'。 – starbolin

在處理這類問題時，首先要做的是找到問題的狀態的表示。在這種情況下，你需要：

兩個整數，它代表了數字
一個布爾值的左上位置，這代表了圖形的顏色（紅/藍）
一個boolean值，它代表數字的方向（水平/垂直）

如果您熟悉位掩碼，則應該只使用32位整數來完成此操作（x位置爲8位，y位置爲8位，其餘的部分）。通過這種方式，您不需要實施比較運算符。 OR 你定義一個簡單的結構（稱之爲state）與這3個信息，並在此嚴格的排序比較（這只是需要把state在std::set。

在此之後，就可以解決這個問題。使用BFS

要做到這一點，你需要：

的std::map<state,state>來存儲你已經在重點參觀了位置，位置你在來值（如果您可以使用C++ 11，並使用位掩碼來存儲您的狀態，則將其替換爲map和unordered_map）
A std::queue<state>其中推送並彈出要處理的狀態。
一些代碼，用於確定從給定的狀態可達到的每個可能的狀態（即，實現了所有可能的行動，走板尺寸的照顧）

僞代碼：

map<state,state> visited; 
    queue<state> to_be_processed; 

    visited.insert(initial_state,initial_state); //you are not coming from anywhere 
    to_be_processed.push (initial_state); 

    while(!to_be_processed.empty()) { 

       state cur = to_be_processed.pop(); 
       if (cur == end_state) //you are done 
       { 
        //to get the path from initial_state to end_state you have just to walk visited in the inverse order. 
        return 1; 
       } 
       for (i = every possible state reachable from cur) { 
        if (visited.count(i) != 0) continue; //already visited 
        to_be_processed.push(i); 
        visited.insert(i,cur); //i has been visited, and you reached i from cur 
       } 

    } 
    return 0; //if you get here, no way

的障礙物的存在使剛剛這個問題更難以代碼，但沒有概念上的不同。

請注意，在這種情況下BFS的工作原理是因爲您從一個州到另一個州所付的費用總是相同的。

來源

2012-05-28 02:02:50 sbabbi

首先，由於您被要求找到確切的最佳路徑，我會去Dijksta's algorithm。

對於這個算法，你將需要：

這給未來可能的移動功能。
一個函數，告訴你一個職位是否已經訪問過。
一個函數，告訴你每個路徑的總成本。
當然一個函數，它告訴你，當你達到最終位置

給定一個初始位置，你的立方體能夠完全達到7個新職位。很容易挑選哪些是可能的。

G是簡單的，你已經取得了迄今爲止+ 1爲下一步的行動:)

我會用一個哈希表來跟蹤訪問位置的移動次數。（這可能是編寫最困難的函數），但你現在不需要過多考慮。一個簡單的向量和逐項比較就可以做到。代碼運行後，您可以對其進行優化。

最後，您需要檢查立方體是否處於其初始位置藍色方向向上。

來源

2012-05-27 23:26:15

您可以將每個可能的1x2塊和顏色（紅色或藍色）組合解釋爲頂點並移動爲邊。如果可以通過一次移動就可以達到某個特定的1x2塊和顏色組合（頂點），那麼這兩個組合之間就會有一個連接（邊緣）。然後，您必須在給定配置和結果圖中的「主頁」配置之間找到最短路徑（可能是廣度優先搜索，因爲無論您執行何種操作，移動的成本都相同）。

如果您想進一步學習，您可以使用圖表遍歷期間使用啓發式算法的高級圖譜搜索算法（啓發式算法是假設黑板上沒有障礙物到達目的地所需的最小移動量）。例如，您可以使用A* algorithm。

來源

2012-05-27 23:41:32 Helstein

構建這樣的圖形需要很長的時間。從初始位置開始，您可以構建只包含可實現位置的圖形，一旦達到最終位置，請執行回溯操作，或使用上述的BFS或DFS。但這就是Dijkstra的全部內容。 Ofc，如果在一張地圖上有多個查詢，那麼預先計算這個圖是一個非常聰明的解決方案。 –

是的，你是對的，但我沒有提到該圖應該在搜索之前建立。由於這是一項家庭作業，我不想在實施過程中提供太多細節。另外，我不認爲你需要Dijkstra來解決這個問題，因爲你沒有使用加權圖（BFS應該足夠了）。 – Helstein

船上數字的最短路徑

回答

相關問題