矩陣中的最短路徑與作弊路徑的障礙

首先，這是一個assingment，我不是在尋找直接的答案，而是最好的解決方案，因爲你可能會認爲它的複雜性。矩陣中的最短路徑與作弊路徑的障礙

這是已知的矩陣（開始和結束）中的2個點之間的最短路徑問題，同時在路上有障礙物。向上，向下，向左和向右移動可接受。讓我們說，當我移動我攜帶某物和每個運動的成本是2。矩陣中有幾個點（讓我們將它們命名爲B點），我可以將這個點放在一個B點並從另一個B點撿起它。在B點傾銷的成本是1，而從B點挑選的成本又是1。每當我沒有這個動作時，我現在的移動成本是1。我認爲解決方案是將矩陣轉換爲樹並應用BFS。然而，這沒有B分。

每當我考慮到B點的複雜性就會出現最壞的情況N^2。下面是一個例子：

S - - - 
- - - - 
B - - B 
- - O E

S =啓動，E =結束，B = B點下降某物，O =障礙物所以我開始帶S向下移動至B點（2 * 2 = 4分）離開B點（1分）右移（2 * 1 = 2分），拿起（1分），下移2分=共10分。

我認爲是建立與節點樹中的每個點B，然而，這將產生幾乎（V-1）*（V-1）個邊的非常密集的循環圖，其發生在N^2個邊界只是algortithm創建圖表。即如上述的最壞的情況下：

S b b b 
b b b b 
b b b b 
b b b E

我認爲另一種選擇是，第一計算withouth的乙點的最短路徑。然後在每次迭代處進行迭代：首先在S上具有bfs，並且最接近B 在E上具有BFS並且最接近B 然後查看是否存在B最靠近S和B最靠近E的路徑。如果有，那麼我會看到路徑是否小於有障礙的常規最短路徑。如果那是更大的那麼沒有最短的路徑（沒有貪婪的測試）。如果在2個B點之間沒有路徑，請嘗試第二個靠近S並再試一次。如果再次沒有路徑，第二個距離E最近並且離S最近。但是，我不能在最糟糕的情況下計算這一個中的複雜性，再加上沒有對此進行評估的貪婪測試。任何有關計算複雜性或甚至指出最佳複雜性解決方案的幫助（不是解決方案，而只是複雜性）將不勝感激

來源

2017-04-11 Akismpa

可能有更好的事實是，你的圖形是一個網格，但沒有使用它，你至少可以在O（n^2 * log（n））中得到一個解，如果n是正方形的邊，所以O（V log V）如果V〜n^2是頂點數。該解決方案的一個提示：您可以使用更大的圖，其中一個節點是原始問題的完整狀態，因此一對（position，haveObject）... – gdelab

您的解決方案比最糟糕的情況更糟糕：如果你在任何地方都有Bs，你會嘗試每一對B點，你不想爲它們中的每一個計算最短路徑，並且從開始（例如Floyd-Warshall）一起計算所有它們也會太長 – gdelab

重要的是要注意，不止一次地掉落和拾取物品是件好事。例如。看看這個：'S-b-b-b-b-E'，你會在第一個B中直接跳到最後一個B，在第二個B中拿起並在第三個中再次下降是沒有意義的。但是最接近S和E的b不一定是最好的。 – maraca

您的矩陣是圖的表示。沒有作弊路徑，實現一個不錯的BFS是很容易的。實施作弊路徑並不重要。只需添加與第一個「層」相同的矩陣即可。底層是'carry'，頂層是'沒有攜帶'。您只能在給定成本的B點移動到另一層。這是與第三維相同的BFS。

每層有n^2個節點和（n-1）^ 2個邊，另外還有連接層的最大n^2個邊。那是O（n^2）。

來源

2017-04-11 21:49:02 stefan

只是澄清一下，使用dijkstra（ElogV）版本的總複雜度是 – Akismpa

您可以創建一個節點標記爲（N，w）的新圖，其中N是原始圖中的節點（因此是矩陣中的一個位置），w = 0或1表示您是攜帶一個重量。在這個圖中添加所有可能的邊很容易

這個新圖的大小爲2 * V，而不是V^2（邊的數量約爲4 * V +數（B））。

然後，您可以使用最短路徑算法，例如Dijkstra算法：在您的情況下爲O（V log（V））的複雜度O（E + V log（V））。

來源

2017-04-12 07:25:40 gdelab

我的輸入是N（V個節點），而不是V個具有V-1個邊的節點，所以總的複雜度在最差的情況下也是V^2，其中每個點都是B點只是爲了創建圖。 – Akismpa

沒有。即使在最糟糕的情況下，典型的節點也有一條邊向右，一條向下，一條向左，一條向上，另一條向另一個節點以相同（x，y）值但w不同值。它們每個都被計數兩次，總共產生2 * V節點和5 * V邊緣（忽略邊界和障礙物的影響） – gdelab

是的你是對的，我誤解了你的解決方案 – Akismpa

矩陣中的最短路徑與作弊路徑的障礙

回答

相關問題