independent-set

    1熱度

    1回答

    讓我說我有一個男人和女人的名單。每個男人(x)對每個女人進行評估,每個女人(y)評估每個男人的評分,評分爲0-9。 例如 X1:{Y1:0,Y2:5,Y3:9} X2:{Y1:1,Y 2:0,Y3:9} X3:{Y1:5,Y2 :5,Y3:8} Y1:{X1:3,X2:3,X3:5} Y2:{X1:8,X2:2,X 3:2} Y3 :{x1:9,x2:5,x3:9} 我正在尋找一種算法,將所有x

    3熱度

    1回答

    假設我們有一個類似於鏈表(或有向無環圖)的圖。一個獨立的集合由不與集合中的任何其他節點共享邊的節點組成。如果每個節點都是加權的,我們如何計算獨立節點集的最大可能值?我知道我們必須使用動態編程,所以我有一點線索,但我希望有人能解釋他們將如何處理它。謝謝!

    0熱度

    1回答

    我開發了一種算法,該算法基於距離約束找到圖的最小獨立支配集。 (我用Python和NetworkX生成圖表,並獲得對) 該算法採用蠻力方法: 找到所有可能的對邊的 檢查哪些節點滿足距離約束 查找所有可能的獨立支配組 比較找到的獨立支配組並找到最小支配組 對於少數節點它不會有所作爲,但是對於大量的程序來說非常慢。 有沒有什麼方法可以讓我們使用不同的方法更快運行? 謝謝

    4熱度

    1回答

    所以我練一些編程的面試問題,以及跨越這個sample pdf其中建議「瞭解如何使用口罩,以獨立於機器的方式來創建他們」絆倒。但它並沒有闡明機器相關和機器獨立掩模之間的區別。 我通常只是弄清楚,提供我想要的面膜,例如,如果我只希望最後4位,我會做的整數 int y = x & 15; 我不明白爲什麼這會是機依賴,如果是。 那麼,什麼是創造一個面具是獨立於機器的例子?什麼是創建機器相關的掩碼的例子

    0熱度

    1回答

    我讀過可以在多項式時間內找到完美圖的最大獨立集。 是否有任何多項式時間算法可以找到完美圖的所有獨立集的列表?

    0熱度

    1回答

    對於matroid電路的唯一性,請參考此注意: http://math.mit.edu/~goemans/18433S13/matroid-notes.pdf。在定理4.1的證明中,最後2個句子「由於S也是獨立的,我們必須有| X | = | S |並且由於e∈C1-f,我們必須有X = S + e - f∈I但這意味着C2⊆S + e - f = X,這是C2以來的一個矛盾。「有人可以解釋爲什麼

    4熱度

    2回答

    給定二部圖。每個頂點都有一些整數值 - 權重。 是否可以在多項式時間內在此圖中找到最大加權independent vertex set? 如果存在這樣的解決方案,這個問題的算法是什麼?

    0熱度

    1回答

    線路,分支和獨立路徑覆蓋有什麼區別? 給出以下情形,路徑將如何顯示? 圖片爲下面的鏈接上控制流圖 - >http://testerstories.com/files/Path.Test.011.png 步驟尋找爲每一個真實路徑被太多讚賞。 謝謝:)

    0熱度

    1回答

    我正在學習如何使用分支和reduce方法找出最大獨立集問題的時間複雜度。以下是從教科書中複製的計算。 在這裏,我無法找出紅色框標註線如何來自它的前行。 在上一行中,爲什麼我在求和部分內沒有下標?背後的原因是什麼?

    0熱度

    2回答

    我創建了一個測試圖來嘗試創建一個獨立集。我知道獨立集是一組沒有連接的頂點,但我不知道如何在合金4.2中實現這一點。下面是我有: abstract sig Vertex { e: set Vertex -- e is the edge relation } -- the test graph has vertices A, B, C, D, E, F one sig A, B, C,