作者DJWS (...)
看板Prob_Solve
标题Re: [问题] 可停留的路线安排程式
时间Wed Dec 14 08:46:26 2016
※ 引述《jakeasa123 (啊斑斑)》之铭言：
: 先前在Python板发了篇文，也获得了一些提示，但看了好几天也试做了几个版本，还是没能达到目标，於是来此询问。
: Python板原文：https://webptt.com/cn.aspx?n=bbs/Python/M.1480482142.A.713.html
1. 养不教，父之过。教不严，师之惰。
不必同情老师和同学。他们都有问题。
2. 原文的推文都在状况外。
3. 你的问题可以粗略分成程式问题、算法问题。
4. 程式问题就是语文问题，另含一点点数学问题。
程式语言变化少，只有for if array recursion，通常都有前例可循，其实不难。
由於你没有提供程式码，这里假设你没有程式方面的问题。
5. 算法问题就是数学问题。
数学问题最困难的地方，就是变化太多、往往没有前例可循。
比方说，在几何图形上画一条补助线，问题豁然开朗，根本莫名其妙。
即便背熟算法课本，遇到新的算法问题，通常还是解不开，不必自责。
6. 这一题的特色是：
(1) 分阶段：分成一天一天，每天做一件事。
(2) 有因果：今天的位置，决定了明天的位置（在九宫格内）。
(3) 可累积：今天的收益，以後列入总收益。
通常这种题型，可以用dynamic programming解决。
盘面拷贝数份，叠起来，变成三维。
一天换一个盘面，往上方走去。
程式码有：一个二维阵列（盘面），两个二维阵列（dp表格），四层回圈（填表格）
7. 为什麽我会知道那些特色呢？
书读多了、问题看多了，依照经验归纳出来的。
这些特色在不同地方有不同称呼：
例如算法课本里面的词汇是「optimal substructure」
例如竞赛选手所用的词汇是「无後效性」「状态转移」
那些特色已经形成了SOP了吗？
就我所知没有。只能自己看着办。
. 为什麽我能联想到dp呢？
因为我曾经遇过类似题目，运气好。
8. 数学问题不只一种解法，这个问题也不只一种解法。
如果你想掌握各种解法：
(1) 靠别人：找一个懂的人，跟他交朋友。往後若有需要，靠交情、花钱请他帮忙。
(2) 靠自己：读懂各类算法课程、书籍、论文，情况许可就再念个phd。
9. 获得了「掌握各种解法」的实力之後，有什麽用呢？
我看过的有：为兴趣、为面试、为逞英雄、为练脑力、为消遣。
每个人状况不一样，我没有办法评论。
10. 你们老师同学，也许都想到了这个份上。
可能他们已经获得了「掌握各种解法」的实力。
可能他们不想获得这种实力，因为没用处、因为关注其他实力、因为太弱、...。
因此他们各方评估後，决定简单教、随便学就好。
与其说他们都有问题，不如说他们都有心思。
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 220.137.3.36
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Prob_Solve/M.1481676390.A.610.html
※ 编辑: DJWS (220.137.3.36), 12/14/2016 09:00:19
1F：推 Gaogaigar: 推心得 12/14 10:05
2F：推 jakeasa123: 感谢你的细心回应 12/14 17:56
3F：推 s89162504: 高级酸XD 12/14 18:01
4F：推 cutekid: 推喔(Y) 12/14 18:16
5F：推 FRAXIS: 这问题有没有可能用 BFS 解决？ 12/15 07:06
6F：推 FRAXIS: 如果最佳解有 self loop 应该是在最後一点 12/15 07:09
7F：→ FRAXIS: 而如果没有 self-loop 的话 应该可以忽略 cycle 12/15 07:10
8F：→ FRAXIS: 不知道对不对 12/15 07:10
9F：→ DJWS: 这个问题有一个性质: 正解按照地理座标排序仍是正解 12/15 08:10
10F：→ DJWS: 因为它的起点在中央，所以地理座标设定成中间小、外围大 12/15 08:10
11F：→ DJWS: 也许这个性质可以用来节省时间 不过我还没想出来 12/15 08:11
好像讲错了 当我没说 XD
12F：→ DJWS: 还有就是，因为可以一直停留，根据贪心的原则，问题变成了: 12/15 08:25
13F：→ DJWS: 天数足够的话，赶快跑去附近的最大值，然後躺着赚 12/15 08:26
^^^^(修正)远方
14F：→ DJWS: 天数不足的话，就留在起点附近的最大值，也是躺着赚 12/15 08:26
15F：→ DJWS: 当盘面只有一维的话 应该是可以线性时间解出来 12/15 08:29
16F：→ DJWS: 二维我就不清楚 交给ACM IOI选手想吧 他们脑筋比较好 12/15 08:30
※ 编辑: DJWS (118.167.32.224), 12/15/2016 08:39:30
17F：→ outofyou: 这题可以设一个停止填表的中断点，就是已填表格数(天数) 12/15 11:21
18F：→ outofyou: ^^^对不起，好像不能确定，是我乱讲 12/15 11:34
19F：→ outofyou: 可以确定的是有最大值的那一格的累积值也已最大的时候。 12/17 12:01
20F：推 aaaaajack: 枚举终点 把weight改成终点值-原值做最短路径 可以做到 12/18 00:36
21F：→ aaaaajack: O(n^4 log n)不受天数影响 不过我不知道怎麽做到更快 12/18 00:36
22F：推 hcsoso: 我想楼上的 n 指的是矩阵的边长? 题目中 n 为天数. 12/18 14:45
23F：→ hcsoso: 不论如何, 这题不难做到线性时间, 一次 BFS 加上证明一些 12/18 14:46
24F：→ hcsoso: 最佳解的性质就行了. 12/18 14:46
25F：推 hcsoso: 噢, 漏了一步, 得先做一次 DP 计算不停留的最大利益. 12/18 14:59
26F：→ aaaaajack: 是边长没错 没注意原题的n是天数 12/19 00:51
27F：推 hcsoso: 请教 aaaaajack 的算法若碰到负圈怎麽办? 有负边的图中 12/19 06:57
28F：→ hcsoso: 最短路径 (simple path) 应是 NP-hard? 12/19 06:58
29F：→ hcsoso: 啊, 可以先将所有负的位置移除, 最佳路径不使用他们 12/19 06:59
30F：→ DJWS: 楼上又在乱讲 负值形成"口 回"这类形状 路径势必要穿过去 12/19 07:02
31F：→ DJWS: 不能删除负值 也没办法"一齐加上足够大数值"解决这种情况 12/19 07:04
32F：→ DJWS: 况且根据原po给的盘面来看 应该是没有负值... 12/19 07:05
33F：推 hcsoso: 不是盘面上的负值, 而是 a 大算法中 终点值减原值可能为负 12/19 07:07
34F：→ hcsoso: D 大提到的情形不会发生在最佳路径上 12/19 07:09
35F：→ DJWS: 这样是我误会了 对不起 12/19 07:23
36F：推 aaaaajack: 负值直接忽略 ，证得终点必为最大值 否则改停在最大值 12/19 07:49
37F：→ aaaaajack: *路径上最大值 12/19 07:49
38F：推 hcsoso: a大的算法可能有另外的问题。固定终点後也许有另一条获 12/19 07:57
39F：→ hcsoso: 利较少的但较短的路径，在天数较少时也许才是最佳解。得 12/19 07:57
40F：→ hcsoso: 计算 k 步内最短路径才行？ 12/19 07:57
41F：推 hcsoso: 最糟的情形多一个 n^2 项。也许用动态最短路径资料结构 12/19 08:02
42F：→ hcsoso: 可以快一点，不过有点恶心… 12/19 08:02
43F：→ DJWS: 根据贪心原则，至多算n^2天，DP至多O(n^4)，不必搞那麽复杂 12/19 08:25
44F：推 hcsoso: Good point. 12/19 08:42
45F：→ aaaaajack: 你可能没看懂我意思 终点值-原值算的就是「亏多少」 12/19 09:40
46F：→ aaaaajack: 确实算n^2天即可 我本来是打算找找看有没有单调性可以 12/19 09:41
47F：→ aaaaajack: 利用 但情况似乎比我想的复杂 12/19 09:42
48F：→ aaaaajack: 总之就是 已知最後要去哪里赚 就挑亏最少的路径过去 12/19 09:50
49F：→ aaaaajack: 天数只影响要挑哪个终点 12/19 09:52
50F：推 hcsoso: 请问如何依照天数决定终点呢？假设我们固定一终点，按终 12/19 10:27
51F：→ hcsoso: 点值调整各位置值为亏损，并将忽略负值位置。若这时最佳 12/19 10:27
52F：→ hcsoso: 路径亏损10并花费10步，而有另一路径前往同一终点亏损10 12/19 10:27
53F：→ hcsoso: 0但花3步。当天数为三时如果只跑 Dijkstra 该点因最短路 12/19 10:27
54F：→ hcsoso: 径花费10步因此不会被选取，除非演算法纪录对每个点每个 12/19 10:27
55F：→ hcsoso: 天数的最短亏损路径，但这就需要 k-Dijkstra 了。不知我 12/19 10:27
56F：→ hcsoso: 是否误解了？ 12/19 10:27
57F：推 aaaaajack: 抱歉，你说的没错，确实有问题 12/19 10:37
58F：推 aaaaajack: 我误解你原先天数的疑虑是optimality 12/19 10:41
59F：→ aaaaajack: 但事实上feasibility就爆了Orz 12/19 10:42
60F：→ DJWS: 想要单调性的话...的确是有啦! 12/19 17:06
61F：→ DJWS: 盘面是一维的时候 类似於longest increasing subsequence 12/19 17:08
62F：→ DJWS: 每个地点都有一个适合的天数区间 12/19 17:08
63F：→ DJWS: 每当(地点座标,地点收益)变大、天数区间也随之变大 12/19 17:10
64F：→ DJWS: 预先计算每个地点的天数区间 之後可以暴搜/二分搜找答案 12/19 17:12
65F：→ DJWS: 盘面是二维的话 我就不清楚了 12/19 17:14
66F：→ aaaaajack: 一维路就只有一条 还不如直接枚举 Orz 12/19 19:19
67F：→ DJWS: 二维的路也就那麽几条 不如直接dp? 12/20 05:30
68F：→ aaaaajack: 囧 二维simple path有无穷多条啊 12/20 09:15
69F：→ aaaaajack: 说错 指数多条 12/20 09:16
70F：→ aaaaajack: 现在问题不就是一维轻松线性 二维只能平方吗 12/20 09:21
71F：→ DJWS: 根据贪心原则，直达区域极值最赚，至多算n天，DP至多O(n^3) 12/20 22:02
72F：→ DJWS: 如果再引入单调性 我觉得是有机会再降一些啦 12/20 22:05
73F：→ DJWS: 修正一下，不是n天，是2n天 12/20 22:05
74F：→ aaaaajack: 至多算n天就不对了 12/20 22:06
75F：→ aaaaajack: 就像hcsoso那篇做法的问题 直达不会是最赚的 12/20 22:07
76F：→ aaaaajack: 你可以设一些weight极小的格子强迫蛇行 达到n^2/2左右 12/20 22:07
77F：→ aaaaajack: 天数还是太难处理 或许DP O(n^4)真的是最佳解 12/20 22:56