生成路徑在圖紅寶石

Question

我有12個節點的無向​​圖，我產生一個這樣的數組：

arr = [[3, 12], [8, 12], [0, 3], [0, 5], [0, 10], [7, 9], [5, 5], [4, 9], [5, 12], [0, 1]] 

其代表的曲線邊緣。

我想通過圖找到最長的路徑，例如每個邊最多使用一次。對於給定的例子會是這樣的：

arr = [[1, 0], [0, 5], [5, 5], [5, 12], [12, 3], [3, 0], [0, 10]] 

我通過搜索歐拉路徑上看到許多源解決方案，這個問題，但用其它編程語言。我將如何在Ruby中繼續使用它？

Answer 1

歐拉路徑訪問每邊緣恰好一次，所以我猜你不需要這個。我可以提供的是這樣的：

def find_path(arr, first_chain = nil, path = [], available = arr.dup) 
    edge_idx = available.index do |first, _| 
    first_chain.nil? || first == first_chain 
    end 
    unless edge_idx 
    return path 
    end 
    edge = available.delete_at(edge_idx) 
    path << edge 
    find_path(arr, edge.last, path, available) 
end 

arr = [[0, 5], [3, 0], [5, 5], [1, 0], [0, 10], [5, 12], [12, 3]] 

find_path arr 
# => [[0, 5], [5, 5], [5, 12], [12, 3], [3, 0], [0, 10]] 

find_path arr, 1 
# => [[1, 0], [0, 5], [5, 5], [5, 12], [12, 3], [3, 0], [0, 10]] 

該算法找到一些路徑開始的第一個元素，或給予任何其他整數。這是不保證它使用的所有元素，或者說，它甚至可能最長的，但它是一個路徑...

---

對於非定向的圖形，你需要考慮的是，邊緣可能恰恰相反：

def find_path(arr, first_chain = nil, path = [], available = arr.dup) 
    edge_idx = available.index do |edge| 
    first_chain.nil? || edge.include?(first_chain) 
    end 
    unless edge_idx 
    return path 
    end 
    edge = available.delete_at(edge_idx) 
    edge = edge.reverse if first_chain && edge.first != first_chain 
    path << edge 
    find_path(arr, edge.last, path, available) 
end 

find_path arr 
# => [[0, 5], [5, 5], [5, 12], [12, 3], [3, 0], [0, 1]] 

find_path arr, 1 
# => [[1, 0], [0, 5], [5, 5], [5, 12], [12, 3], [3, 0], [0, 10]] 

---

要找到最長路徑，你需要建立所有可能的路徑，並選擇最長：

def find_longest_path(arr, first_chain = nil, available = arr.dup) 
    paths = available.each_index.select do |edge_idx| 
    first_chain.nil? || available[edge_idx].include?(first_chain) 
    end.map do |edge_idx| 
    edge = available[edge_idx] 
    edge = edge.reverse if first_chain && edge.first != first_chain 
    [edge, *find_longest_path(arr, edge.last, 
         available[0...edge_idx] + available[edge_idx+1..-1])] 
    end 
    # a hack to find longest in all reverse paths 
    if first_chain.nil? && arr == available 
    paths << find_longest_path(arr, nil, arr.map(&:reverse)) 
    end 
    paths.max_by { |path| path.length } 
end 

arr = [[3, 12], [8, 12], [0, 3], [0, 5], [0, 10], [7, 9], [5, 5], [4, 9], [5, 12], [0, 1]] 

find_longest_path arr 
# => [[10, 0], [0, 3], [3, 12], [12, 5], [5, 5], [5, 0], [0, 1]] 

find_longest_path arr, 1 
# => [[1, 0], [0, 3], [3, 12], [12, 5], [5, 5], [5, 0], [0, 10]] 

這段代碼做了什麼？
而不是採取第一邊緣，可以在我們的路徑中使用，此算法需要所有邊緣，可以在我們的路徑中使用。

對於每個這樣的邊緣，它建立一個新的路徑，其中：

1. 開始與所選擇的邊緣
2. 從available陣列
3. 繼續與最長路徑去除邊緣購自開始邊緣的外頂點（遞歸）

這建立了所有的列表po可行路徑。從這個方法返回最長（最大長度）。

三個線I標記爲# hack是因爲當first_chain是nil算法找到開始反向邊緣任何非最長路徑。爲了支持顛倒的邊緣，我運行了兩次 - 第二次顛倒了所有的邊緣。

這是不是執行一個已知的算法，但一個簡單的蠻力執行，可能不是最有效，最簡單或最美好的，但它應該把你放在正確的方向。您可能會發現更多關於在ruby中使用圖形的信息here

Answer 2

像這樣的事情可能會爲你工作，雖然有可能是更好的方法

def generate_array 
    a = [] 
    b2 = nil 
    10.times do 
    b1,b2 = [b2 || rand(12),rand(12)] 
    a << [b1,b2] 
    end 
    a 
end 
generate_array 
#=> [[0, 4], [4, 4], [4, 11], [11, 4], [4, 8], [8, 11], [11, 4], [4, 2], [2, 6], [6, 0]] 

也只是基於你給出的輸出rand(12)因爲上限使用0指數，因此設置將永遠不會返回12記要返回人數最多的是11