作者DJWS (...)
看板Prob_Solve
標題Re: [問題] 可停留的路線安排程式
時間Wed Dec 14 08:46:26 2016
※ 引述《jakeasa123 (啊斑斑)》之銘言：
: 先前在Python板發了篇文，也獲得了一些提示，但看了好幾天也試做了幾個版本，還是沒能達到目標，於是來此詢問。
: Python板原文：https://webptt.com/m.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/m.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