討論串(共6篇) - [問題] 一個圖論的問題 - 看板Prob_Solve

看板 [ Prob_Solve ]

討論串[問題] 一個圖論的問題

共 6 篇文章

排序：最舊先 | 最新先 | 留言數 | 推文總分

內容預覽：開啟 | 關閉 | 只限未讀

首頁

尾頁

Re: [問題] 一個圖論的問題

推噓1(1推 )留言1則，0人參與作者tkcn (小安)時間17年前 (2007/12/22 19:59)資訊

內容預覽:

找出所有被選定的點之間的最短路徑，. 便可建出一個虛擬的 graph，而且是 complete graph，. 找出 MST 再從虛擬的 edge 中找回對應的最短路徑。. 實際寫演算法的話，. 可以不用真的去產生那虛擬的 graph，. 只要將原先的 MST 搭配 all-pairs shorte

Re: [問題] 一個圖論的問題

推噓0(0推 )留言0則，0人參與作者DJWS (...)時間17年前 (2007/12/23 12:54)資訊

內容預覽:

你誤會題意了。舉個例子：. edge cost. 1 <--> 2 2. 1 <--> 3 2. 1 <--> 4 1. 2 <--> 3 3. 然後讓 2 3 4 這三個節點相連通，所需要的最少 cost 應為 5。. --. ※ 發信站: 批踢踢實業坊(ptt.cc). ◆ From: 140.

Re: [問題] 一個圖論的問題

推噓0(0推 )留言0則，0人參與作者xu3jp68 (信箱爆炸..XD)時間17年前 (2007/12/23 17:48)資訊

內容預覽:

假設你要找2,3,4之間最小成本，所以找所有路徑當中跟2,3,4有關的，. 選成本最小的一條，這邊是1 <--> 4，所以你現在收集了1跟4的點，. 然後在搜尋有跟1,4當中有關的最小成本，這邊是1 <--> 2 or 1 <--> 3. 假設你選1 <--> 2，所以你現在手上有1,2,4三個點，

(還有21個字)

Re: [問題] 一個圖論的問題

推噓0(0推 )留言0則，0人參與作者DJWS (...)時間17年前 (2007/12/23 20:12)資訊

內容預覽:

謝謝你的回覆。 :). 如你所說，這個問題是給定一個圖，並選定一些節點，. 然後才要將這些節點兩兩都相連通。. 我對你提供的方法還有一些疑問。. 當選擇「成本最小的一條路徑」時，. 這是指最短路徑嗎？. 另外，如果「成本最小的一條路徑」不只一條時，. 該選擇哪一條路徑呢？. 我再舉個例子：. edg

(還有362個字)

Re: [問題] 一個圖論的問題

推噓0(0推 )留言0則，0人參與作者tkcn (小安)時間17年前 (2007/12/24 01:13)資訊

內容預覽:

http://en.wikipedia.org/wiki/K-minimum_spanning_tree. This problem is known to be NP-complete.. 看來只能用 heuristic 囉. --. ※ 發信站: 批踢踢實業坊(ptt.cc). ◆ From:

首頁

尾頁