需要一些幫助來理解有關最大化圖連通性的這個問題

我在想如果有人能幫我理解這個問題。我準備了一個小圖，因爲它更容易直觀地解釋它。需要一些幫助來理解有關最大化圖連通性的這個問題

alt text http://img179.imageshack.us/img179/4315/pon.jpg

問題我試圖解決：

1.構建依賴圖 鑑於曲線圖的連接，並確定一個節點如何依賴於其他，順序的度量依賴關係。舉例來說，我能不能把一些規則說

節點3依賴於節點4
節點2取決於節點3
節點3取決於節點5

但由於最終的規則不是「有價值的」（同樣基於相同的指標），我不會將規則添加到我的系統中。

2.執行請求命令 一旦我構建了依賴關係圖，請按照最大化最終連接順序執行列表。我不確定這是否是一個真正的問題，但我總覺得在這種情況下可能存在多個訂單，因此需要選擇最佳訂單。

首先，我想知道我是否正確構建了問題，是否應該知道任何角落案例。其次，我可以看到一個密切相關的算法嗎？目前，我正在考慮類似Feedback Arc Set或Secretary Problem，但我現在有點困惑。有什麼建議麼？ PS：我自己對這個問題有點困惑，所以請不要爲此對我火上澆油。如果需要澄清，我會嘗試更新問題。

來源

2010-05-10 Legend

看起來您正試圖確定您發送給具有依賴關係（或「部分排序」）的節點之間的請求的順序。

如果你谷歌的「部分順序依賴關係圖」，你得到一個鏈接到here，這應該給你足夠的信息，找出一個好的解決方案。

通常情況下，您希望按照節點在其依賴關係之後來排序節點; AKA拓撲排序。

來源

2010-05-10 21:27:13 MSN

感謝您的意見。我想我正在尋找一種拓撲排序。唯一的下一步就是想出一個從我擁有的圖形中構建DAG的好方法。再次感謝。 – Legend 2010-05-11 23:47:38

我對你的排序約束與你所描繪的圖形有點混淆：沒有什麼能匹配。也就是說，這聽起來像你有軟排序約束（A應該在B之前，但不一定），違反約束的成本。 An optimal algorithm for scheduling that is NP-hard，但我敢打賭你可以使用偏向大重量邊緣的DFS獲得相當不錯的時間表，然後刪除所有後邊緣。

來源

2010-05-10 23:28:38

感謝您的輸入。對此感到抱歉。我在我的問題中提到了這一點。我仍然處於形成這個問題的階段，所以請原諒我的混亂:) – Legend 2010-05-11 23:46:54

如果事先知道每個節點的依賴關係，則可以輕鬆構建圖層。

這很有趣，但我在組織時遇到了同樣的問題......我的應用程序:)的不同模塊的編譯

的想法很簡單：

def buildLayers(nodes): 
    layers = [] 
    n = nodes[:] # copy the list 
    while not len(n) == 0: 
    layer = _buildRec(layers, n) 

    if len(layer) == 0: raise RuntimeError('Cyclic Dependency') 

    for l in layer: n.remove(l) 
    layers.append(layer) 
    return layers 

def _buildRec(layers, nodes): 
    """Build the next layer by selecting nodes whose dependencies 
    already appear in `layers` 
    """ 
    result = [] 
    for n in nodes: 
    if n.dependencies in flatten(layers): result.append(n) # not truly python 
    return result

然後你就可以彈出層一次一個，每一次你就可以發送請求並行地到該層的每個節點。

如果您保留一組已經選擇的節點，並且依賴關係也被表示爲一組，則檢查效率更高。其他實現將使用事件的傳播，以避免所有這些嵌套循環......在最壞的情況下

通知你爲O（n ），但我只有三十幾個組件和有沒有那麼相關：對

來源

2010-05-11 17:55:59

感謝您的時間。我想我們兩個都在兩個不同的領域解決同樣的問題:)我的問題還有一個約束：我還沒有決定一個合適的度量，但尚未決定一個節點如何依賴另一個。 – Legend 2010-05-11 23:48:57

需要一些幫助來理解有關最大化圖連通性的這個問題

回答

相關問題