Re: [問題] 可停留的路線安排程式

看板Prob_Solve作者hcsoso (索索)時間7年前 (2016/12/18 15:38)推噓2(2推 0噓 4→)

留言6則, 3人參與討論串5/5 (看更多)

Dec 18, 2016 修文: 此篇算法是錯的, 底下性質二的證明不正確. 認真回一篇好了. 這題只需要一次 BFS 計算每個位置下列兩個值即可. 令 d(v) 為起點至該點圖上的距離. 當說到 "在某位置停留" 時指的是在該位置重複獲利 (即使用了 self-loop). 一. 不在任何位置停留下起點到該點 v 走過 d(v) 步最佳獲利二. 從起點到該點經過 N 天 (N 為題目所給天數) 最佳獲利值一可簡單 DP 完成, 或是一併在計算值 (2) 之 BFS 時計算. 值二不難看出等價於二'. 從起點不在任何位置停留, 經過 d(v) 步抵達該點 v 後停留至 N 天之最佳獲利 (我們只需證明以下性質: 最佳獲利途徑必為起點 d(v) 步直達終點後停留原地獲利. 性質一. 最佳路徑上終點必有最大獲利. 證明. 假設不然, 則路徑上有一位置 w 獲利為最大(必然大過終點). 則由起點出發延最佳路徑抵達 w 後停留至 N 天必獲利更多, 矛盾. ▓ 性質二. 最佳路徑必為圖上從起點至終點最短路徑, 不經停留, 留在終點獲利. 證明. 由性質一可知越早抵達終點越佳; 若最佳路徑不為最短路徑, 則使用最短路徑抵達終點後停留必可獲利更多, 矛盾. Dec 18, 2016 修文: 此證明忽略了最短路徑上獲利可能很低, 因此是錯誤的. ) 值二'利用值一常數時間即可計算. 此圖每個位置只有最多八個鄰居, 所有位置值一可在線性時間計算完成. (事實上最短路徑方向的關係, 只有最多三個鄰居有影響.) 而執行 BFS N 步後 (若所要求天數少 BFS 深度可提早終止), 將值二最大的位置與值輸出即可. 連路徑都需要的話在 DP 時記錄前一個位置即可. 整個演算法可在線性時間完成. 不難看出這個演算法可推廣到任意圖, 而執行時間仍然為線性. (當然, 這時圖的邊數也會被算在內.) -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 50.179.159.193 ※ 文章網址: https://www.ptt.cc/bbs/Prob_Solve/M.1482046720.A.0FE.html

→

outofyou

12/18 22:46, , 1^F

12/18 22:46, 1^F

抱歉寫得不夠清楚; 改了一下描述不知道有沒有好一些?

推

DJWS

12/18 22:52, , 2^F

12/18 22:52, 2^F

推

aaaaajack

12/19 00:49, , 3^F