推 yupog2003: 45題那個searching可能在說depth first search? 12/29 20:22
→ yupog2003: 這樣就可以用暴力法測試n!種可能符不符合要求了 12/29 20:22
→ yupog2003: 其實我也覺得這樣講好牽強，可是我也想不到為什麼 12/29 20:23
→ yupog2003: search可以拿來解這個問題 12/29 20:23
推 yupog2003: 54題，如果Problem I無解，代表G中的cycle至少存在一個 12/29 20:31
→ yupog2003: 邊的weight是2+ne，也就是有一條weight為1的邊被weight 12/29 20:32
→ yupog2003: 為2+ne的邊取代了，此時distance就是n-1+2+ne=1+n+ne 12/29 20:33
→ yupog2003: 所以這個臨界點就是1+n+ne，必須要<1+n+ne才會有解 12/29 20:35
→ yupog2003: 相反的>=1+n+ne就無解了，也就是>n+ne=n(1+e) 12/29 20:36
→ yupog2003: 就是C選項說的那個，D選項我覺得把n(1+e/2)改成n(1+e) 12/29 20:37
→ yupog2003: 就會對了，很不嚴謹，但我當初的想法是這樣 12/29 20:37
→ yupog2003: 我是先把G想成一個complete graph，有weight為1和2+ne 12/29 20:41
→ yupog2003: 兩種邊，裡面有好多種邊數為n的cycle，然後下去想這樣 12/29 20:41
→ gary19941208: 了解了，感謝你！看有沒有其他大大可以解釋search 12/29 22:52
→ gary19941208: 了 12/29 22:52