[理工] [ds][algo] [核對]-成大99-資工所
一.Data Structures
1.
(a) -20
(b) 6
2.
我選abc
(a)我比較傾向把d視為常數
(c)考慮到undirected,應該是T
(d)錯的理由是考慮可能存在loop
3.
(a) yes
pseudo code不會寫.....強烈徵求
(b) 不會
二.Algorithms
4.Θ(nlgn)
5.用Dag-shortest-path
(先用DFS算出各個node的finishing time 做拓僕排序
再依據這個order對每個相鄰的node做relax)
6.例證法
q ---------------- > r
^ <---------------- ^
| | | |
| | | |
| | | |
| | | |
| | | |
v v
<---------------
s --------------> t
從圖上知道q到t的最長path是q-r-t
但q-r並不是q到r的最長path (應該是q-s-t-r)
而r-t也不是r到t的最長path (應該是r-q-s-t)
所以不具有optimal structure
7.用Bellman-ford檢驗
有錯請指認 謝謝~
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 111.255.9.225
推
02/15 22:27, , 1F
02/15 22:27, 1F
→
02/15 22:27, , 2F
02/15 22:27, 2F
→
02/19 16:05, , 3F
02/19 16:05, 3F
→
02/19 16:05, , 4F
02/19 16:05, 4F
→
02/19 16:05, , 5F
02/19 16:05, 5F
→
02/19 16:05, , 6F
02/19 16:05, 6F
→
02/19 16:05, , 7F
02/19 16:05, 7F
→
02/19 16:05, , 8F
02/19 16:05, 8F
推
02/19 16:13, , 9F
02/19 16:13, 9F
討論串 (同標題文章)