[理工] 交大100資演

看板Grad-ProbAsk作者時間9年前 (2016/12/29 19:49), 編輯推噓2(2推 0噓 13→)
留言15則, 2人參與, 最新討論串1/1
請問45題b選項說用searching可以解是怎麼解，(答案為C) http://i.imgur.com/TuqzD6y.jpg
54題d選項的n(1+e/2)是什麼意思，一直想不通...(答案為D) http://i.imgur.com/hlf4959.jpg
謝謝～～ -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.112.25.105 ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1483012147.A.525.html
推
12/29 20:22, , 1F
45題那個searching可能在說depth first search?
12/29 20:22, 1F
→
12/29 20:22, , 2F
這樣就可以用暴力法測試n!種可能符不符合要求了
12/29 20:22, 2F
→
12/29 20:23, , 3F
其實我也覺得這樣講好牽強，可是我也想不到為什麼
12/29 20:23, 3F
→
12/29 20:23, , 4F
search可以拿來解這個問題
12/29 20:23, 4F
推
12/29 20:31, , 5F
54題，如果Problem I無解，代表G中的cycle至少存在一個
12/29 20:31, 5F
→
12/29 20:32, , 6F
邊的weight是2+ne，也就是有一條weight為1的邊被weight
12/29 20:32, 6F
→
12/29 20:33, , 7F
為2+ne的邊取代了，此時distance就是n-1+2+ne=1+n+ne
12/29 20:33, 7F
→
12/29 20:35, , 8F
所以這個臨界點就是1+n+ne，必須要<1+n+ne才會有解
12/29 20:35, 8F
→
12/29 20:36, , 9F
相反的>=1+n+ne就無解了，也就是>n+ne=n(1+e)
12/29 20:36, 9F
→
12/29 20:37, , 10F
就是C選項說的那個，D選項我覺得把n(1+e/2)改成n(1+e)
12/29 20:37, 10F
→
12/29 20:37, , 11F
就會對了，很不嚴謹，但我當初的想法是這樣
12/29 20:37, 11F
→
12/29 20:41, , 12F
我是先把G想成一個complete graph，有weight為1和2+ne
12/29 20:41, 12F
→
12/29 20:41, , 13F
兩種邊，裡面有好多種邊數為n的cycle，然後下去想這樣
12/29 20:41, 13F
→
12/29 22:52, , 14F
了解了，感謝你！看有沒有其他大大可以解釋search
12/29 22:52, 14F
→
12/29 22:52, , 15F
了
12/29 22:52, 15F
‣ 更多 gary19941208 的文章
文章代碼(AID): #1OPFWpKb (Grad-ProbAsk)