極小值

極小值

的問題是找到最小的值（重量每邊的是等於1）的路徑到具有起始的自由選擇每個其他節點無向圖中的節點。數據是以鄰接關係的形式存在的。節點的編號從0到最大。

所以在圖形上方正確的解決方案是3，因爲在這種情況下，所有其他節點的路徑最長爲3儘量選擇節點號2或4

我的解決辦法：

遍歷每個節點，並找到下一個節點的路徑開銷，這些值中最大的是我們的結果它使用findRoad實現，逐級搜索遞歸搜索以查找連接。
Acc保持當前迭代的值等於此頂點必須經過的最長路徑
如果acc大於先前的finded值（min），我們停止迭代此節點，因爲此節點不會給我們更好的結果
算法結束最後一個節點上的迭代結束

算法後正常工作hovever很慢，我想一個解決方案來改善它，但它只是減緩了算法進一步下跌：

在遞歸調用findRoad

更換，始終是邊緣過濾列表的完整列表，第一個參數（不包括已籤的）

代碼：

val a: List[(Int,Int)] //list of all edges 
val c: Set[(Int,Int)] //set of all edges 
val max //maximum index of node 

//main loop that manages iterations and limits their number 
def loop(it: Int, it2: Int, acc: Int,min: Int): Int = { 
    if(it > max) min 
    else if(it2 > max) if(min<acc)loop(it+1,0,0,min) 
    else loop(it+1,0,0,acc) 
    else if(acc >= min) loop(it+1,0,0,min) 
    else if(it == it2) loop(it,it2+1,acc,min) 
    else { 
     val z = findRoad(b,List(it),it2,1,min) 
     if(z > acc) loop(it,it2+1,z,min) 
     else loop(it,it2+1,acc,min) 
    } 
} 
//finding shortest path from node s to node e 
def findRoad(a: List[(Int,Int)], s: List[Int], e: Int, lev: Int,min: Int): Int = { 
    if(lev > min) Int.MaxValue 
    else if(s.exists(s => (a.exists(p => p == (s,e) || p == (e,s))))) lev 
    else findRoad(a,connectEdges(s,Set()),e,lev+1,min) 
} 
//finding all predecessor and successors 
def connectEdges(a: List[Int], acc: Set[Int]): List[Int] = { 
    if(a.isEmpty) acc.toList 
    else connectEdges(a.tail, acc++c.collect{ 
     case (b,c) if(b == a.head) => c 
     case (b,c) if(c == a.head) => b 
    }) 
}

是整體思路有缺陷或某些應該避免scala操作（如過濾，收集，將集合轉換爲集合）？

也許我應該使用像Floyd-Warshall算法一樣的所有對最短路徑算法？

來源

2015-08-13 majesiu

使用BFS的數量。由於邊緣成本爲1，它將爲您提供從頂點u到O(V+E)時間內所有其他頂點的最短路徑。現在從u獲取所有頂點v的最大距離[u,v]。可以稱這d。最後，您需要給出最小值爲d的頂點。總體運行時間爲O((V+E)*V)。

算法：

min = infinity 
result = -1 // which vertex yields minimum result 
for all vertices u in V: 
    dist = [|V|] // array of size |V| initialized to 0 
    fill dist using BFS starting from u 
    max = max(dist) 
    if max < min: 
     min = max 
     result = u 
return result

來源

2015-08-15 04:26:32 xashru

我想你可以從每個頂點運行BFS，並且對於每個頂點記住使用BFS走過的最長路徑的長度。你的結果是其中的最小值。這將是O（n²）。

您也可以找到每對用弗洛伊德 - Warshall算法頂點的最短路徑，然後爲每個頂點v找到頂點ü使DIST [V] [U]最大。在每個頂點的所有這些值中，最小的一個就是您的答案。由於Floyd-Warshall，它會是O（n³）。

N - 頂點

來源

2015-08-13 15:51:57 Badf

回答

相關問題