作者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/cn.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