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

作者: DJWS (...)   2016-12-14 08:46:26
※ 引述《jakeasa123 (啊斑斑)》之銘言:
:   先前在Python板發了篇文,也獲得了一些提示,但看了好幾天也試做了幾個版本,還是沒能達到目標,於是來此詢問。
:   Python板原文:https://www.ptt.cc/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. 你們老師同學,也許都想到了這個份上。
可能他們已經獲得了「掌握各種解法」的實力。
  可能他們不想獲得這種實力,因為沒用處、因為關注其他實力、因為太弱、...。
  因此他們各方評估後,決定簡單教、隨便學就好。
  與其說他們都有問題,不如說他們都有心思。
作者: Gaogaigar   2016-12-14 10:05:00
推心得
作者: jakeasa123 (啊斑斑)   2016-12-14 17:56:00
感謝你的細心回應
作者: s89162504 (阿本)   2016-12-14 18:01:00
高級酸XD
作者: cutekid (可愛小孩子)   2016-12-14 18:16:00
推喔(Y)
作者: FRAXIS (喔喔)   2016-12-15 07:06:00
這問題有沒有可能用 BFS 解決?如果最佳解有 self loop 應該是在最後一點而如果沒有 self-loop 的話 應該可以忽略 cycle不知道對不對
作者: DJWS (...)   2016-12-15 08:10:00
這個問題有一個性質: 正解按照地理座標排序仍是正解因為它的起點在中央,所以地理座標設定成中間小、外圍大也許這個性質可以用來節省時間 不過我還沒想出來還有就是,因為可以一直停留,根據貪心的原則,問題變成了:天數足夠的話,趕快跑去附近的最大值,然後躺著賺天數不足的話,就留在起點附近的最大值,也是躺著賺當盤面只有一維的話 應該是可以線性時間解出來二維我就不清楚 交給ACM IOI選手想吧 他們腦筋比較好
作者: outofyou   2016-12-15 11:21:00
這題可以設一個停止填表的中斷點,就是已填表格數(天數)^^^對不起,好像不能確定,是我亂講
作者: aaaaajack (丁丁是個人才)   2016-12-18 00:36:00
枚舉終點 把weight改成終點值-原值做最短路徑 可以做到O(n^4 log n)不受天數影響 不過我不知道怎麼做到更快
作者: hcsoso (索索)   2016-12-18 14:45:00
我想樓上的 n 指的是矩陣的邊長? 題目中 n 為天數.不論如何, 這題不難做到線性時間, 一次 BFS 加上證明一些最佳解的性質就行了.噢, 漏了一步, 得先做一次 DP 計算不停留的最大利益.
作者: aaaaajack (丁丁是個人才)   2016-12-19 00:51:00
是邊長沒錯 沒注意原題的n是天數
作者: hcsoso (索索)   2016-12-19 06:57:00
請教 aaaaajack 的算法若碰到負圈怎麼辦? 有負邊的圖中最短路徑 (simple path) 應是 NP-hard?啊, 可以先將所有負的位置移除, 最佳路徑不使用他們
作者: DJWS (...)   2016-12-19 07:02:00
樓上又在亂講 負值形成"口 回"這類形狀 路徑勢必要穿過去不能刪除負值 也沒辦法"一齊加上足夠大數值"解決這種情況況且根據原po給的盤面來看 應該是沒有負值...
作者: hcsoso (索索)   2016-12-19 07:07:00
不是盤面上的負值, 而是 a 大算法中 終點值減原值可能為負D 大提到的情形不會發生在最佳路徑上
作者: DJWS (...)   2016-12-19 07:23:00
這樣是我誤會了 對不起
作者: aaaaajack (丁丁是個人才)   2016-12-19 07:49:00
負值直接忽略 ,證得終點必為最大值 否則改停在最大值*路徑上最大值
作者: hcsoso (索索)   2016-12-19 07:57:00
a大的算法可能有另外的問題。固定終點後也許有另一條獲利較少的但較短的路徑,在天數較少時也許才是最佳解。得計算 k 步內最短路徑才行?最糟的情形多一個 n^2 項。也許用動態最短路徑資料結構可以快一點,不過有點噁心…
作者: DJWS (...)   2016-12-19 08:25:00
根據貪心原則,至多算n^2天,DP至多O(n^4),不必搞那麼複雜
作者: hcsoso (索索)   2016-12-19 08:42:00
Good point.
作者: aaaaajack (丁丁是個人才)   2016-12-19 09:40:00
你可能沒看懂我意思 終點值-原值算的就是「虧多少」確實算n^2天即可 我本來是打算找找看有沒有單調性可以利用 但情況似乎比我想的複雜總之就是 已知最後要去哪裡賺 就挑虧最少的路徑過去天數只影響要挑哪個終點
作者: hcsoso (索索)   2016-12-19 10:27:00
請問如何依照天數決定終點呢?假設我們固定一終點,按終點值調整各位置值為虧損,並將忽略負值位置。若這時最佳路徑虧損10並花費10步,而有另一路徑前往同一終點虧損100但花3步。當天數為三時如果只跑 Dijkstra 該點因最短路徑花費10步因此不會被選取,除非演算法紀錄對每個點每個天數的最短虧損路徑,但這就需要 k-Dijkstra 了。不知我是否誤解了?
作者: aaaaajack (丁丁是個人才)   2016-12-19 10:37:00
抱歉,你說的沒錯,確實有問題我誤解你原先天數的疑慮是optimality但事實上feasibility就爆了Orz
作者: DJWS (...)   2016-12-19 17:06:00
想要單調性的話...的確是有啦!盤面是一維的時候 類似於longest increasing subsequence每個地點都有一個適合的天數區間每當(地點座標,地點收益)變大、天數區間也隨之變大預先計算每個地點的天數區間 之後可以暴搜/二分搜找答案盤面是二維的話 我就不清楚了
作者: aaaaajack (丁丁是個人才)   2016-12-19 19:19:00
一維路就只有一條 還不如直接枚舉 Orz
作者: DJWS (...)   2016-12-20 05:30:00
二維的路也就那麼幾條 不如直接dp?
作者: aaaaajack (丁丁是個人才)   2016-12-20 09:15:00
囧 二維simple path有無窮多條啊說錯 指數多條現在問題不就是一維輕鬆線性 二維只能平方嗎
作者: DJWS (...)   2016-12-20 22:02:00
根據貪心原則,直達區域極值最賺,至多算n天,DP至多O(n^3)如果再引入單調性 我覺得是有機會再降一些啦修正一下,不是n天,是2n天
作者: aaaaajack (丁丁是個人才)   2016-12-20 22:06:00
至多算n天就不對了就像hcsoso那篇做法的問題 直達不會是最賺的你可以設一些weight極小的格子強迫蛇行 達到n^2/2左右天數還是太難處理 或許DP O(n^4)真的是最佳解

Links booklink

Contact Us: admin [ a t ] ucptt.com