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

看板 [ Prob_Solve ]

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

共 6 篇文章

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

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

首頁

尾頁

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

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

內容預覽:

哈哈，原來是NP-Complete問題，難怪特別難想。 :). 是我太孤陋寡聞了，真是不好意思。. 既然有關鍵字了，我就可以自己上網查點資料了。. 謝謝你啦！. 另外再請教一個問題，. 如果這個圖是位在二維平面上，且cost都滿足距離的定義，. 當距離分別為 Euclidean distance 和

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:

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

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

內容預覽:

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

(還有362個字)

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 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.

首頁

尾頁