作者hcsoso (索索)
看板Prob_Solve
標題Re: [問題] 可停留的路線安排程式
時間Sun Dec 18 15:38:33 2016
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://webptt.com/m.aspx?n=bbs/Prob_Solve/M.1482046720.A.0FE.html
1F：→ outofyou: 看不出來值1值2的關係，一個有限制d(v)，一個沒有。 12/18 22:46
抱歉寫得不夠清楚; 改了一下描述不知道有沒有好一些?
2F：推 DJWS: 如果不停留路徑長的像？形狀 要怎麼用BFS找出來? 12/18 22:52
3F：推 aaaaajack: 我覺得有問題 最短路徑不保證是最佳路徑 假設整張數值 12/19 00:49
4F：→ aaaaajack: 差不多僅有一些值異常小的格子 最佳解必然會繞過這些格 12/19 00:49
5F：→ aaaaajack: 子 12/19 00:49
6F：→ aaaaajack: 至於何為最佳路徑，在不清楚終點為何的情況下無法保證 12/19 00:53
的確, 你們是對的, 我錯誤的假設了最佳路徑的性質 (文中性質二是錯的).
※ 編輯: hcsoso (50.179.159.193), 12/19/2016 06:29:43