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

[hcsoso (索索)]

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: 看不出來值1值2的關係，一個有限制d(v)，一個沒有。
抱歉寫得不夠清楚; 改了一下描述不知道有沒有好一些?

推 DJWS: 如果不停留路徑長的像？形狀  要怎麼用BFS找出來?
推 aaaaajack: 我覺得有問題 最短路徑不保證是最佳路徑 假設整張數值
→ aaaaajack: 差不多僅有一些值異常小的格子 最佳解必然會繞過這些格
→ aaaaajack: 子
→ aaaaajack: 至於何為最佳路徑，在不清楚終點為何的情況下無法保證
的確, 你們是對的, 我錯誤的假設了最佳路徑的性質 (文中性質二是錯的).
※ 編輯: hcsoso (50.179.159.193), 12/19/2016 06:29:43