作者查詢 / springman
作者 springman 在 PTT [ Prob_Solve ] 看板的留言(推文), 共89則
限定看板:Prob_Solve
看板排序:
全部Stock19716Gossiping10255Christianity1835ChangHua1760car1752nCoV20191329Lifeismoney1322HatePolitics1305EZsoft786NBA734MobileComm708Tennis705Browsers586VoIP554LaTeX544Disabled511Office454Google433AfterPhD428biker384IME381Broad_Band350Jeremy_Lin296IA293Windows241JesusLove206Instant_Mess150DYU148C_and_CPP147Free_box146Linux143study133AntiVirus130swim115Federer96Math96Badminton95Android93ONE_PIECE89Prob_Solve89Tech_Job88Teacher71Education61Golf50sky44Nets41PhD40Law-Service39ask-why37Programming37NetRumor32FITNESS31Fix-Network24iOS24MLB20Blog19Brethren19StockPicket17teaching16RegExp14AVEncode13Chiayi13AudioPlayer12Hornets11ask10DV10Kaohsiung10Lakers10BigPeitou9BigShiLin9ChungLi9Gov_owned9Hawks9Hsinchu9Keelung9Web_Design9WomenTalk9WorldCup9Ecophilia8Editor8Ajax7Bunco7Japan_Travel6java6JinYong6DSLR5Football5Knicks5GossipPicket4home-sale4joke4L_TalkandCha4LAW4Miaoli4specialman4Test4TW-F-Tennis4CD-R3Insurance3movie3NSwitch3Option3Rockets3SYSOP3tabletennis3UTAH-JAZZ3Wizards3Baseball2Celtics2ChicagoBulls2Facebook2Finance2MenTalk2NTUT_Talk2PHP2Siam-Star2Storage_Zone2Ang_Lee1Conan1Database1Donate-Blood1FCU_COOP1FCU_Talk1gay1HsinTien1Hualien1hwai1I-Lan1MAC1Mavericks1MdnCNhistory1money1MuscleBeach1Nadal1Nangang1NCU_Talk1PACERS1PingTung1Python1Salary1Tainan1TamShui1TW-history1TW-M-Tennis1WorkinChina1WorldCupGG1YoungArtist1<< 收起看板(147)
1F推:這好像是 NP-complete 的問題吧01/07 20:44
6F推:只是好像可以將 subset-sum 的問題 reduce 成這個問題01/08 18:59
7F→:若沒想錯的話,應該是 NP-complete 沒錯01/08 19:00
1F推:假設 n = 2^k,則 (lg n)! = k!,而 n^3 = 2^{3k}12/31 16:46
2F→:k! 當然比 2^{3k} 大,都取 lg 的話12/31 16:46
3F→:lg k! = k lg k,而 lg(2^{3k}) = 3k12/31 16:47
1F推:BFS 可以直接在 directed graph 上做,不必轉12/22 19:52
2F→:將長度為 i 的 edge 轉成 i 條 edges 可能就可以12/22 19:52
3F→:是 multistage graph 不是 multigraph ...12/22 19:54
4F→:看起來 shortest path 與 longest path 的做法類似12/22 19:54
5F→:有長度為負數的邊時應該也可以,因為沒有 cycle12/22 19:55
9F推:因為每條邊的長度最多是 5,所以將長度為 i 的邊12/23 05:32
10F→:轉成 i 條邊之後,邊數最多是 5|E| 條12/23 05:32
11F→:代入 BFS 一樣是 O(V+E) 的時間內可以做完12/23 05:33
4F推:不是biconnected的圖形似乎也可能是strongly connected12/23 05:36
5F→:我想用 DFS 找 cycles 應該真的做得到,只是要想清楚12/23 05:37
10F推:若 T 是 MBST 的話,其他 spanning tree 的最大邊都不會12/20 04:35
11F→:比 T 的最大邊小。12/20 04:35
1F推:k 是最後找到 v 的位置吧,a[k] = v,對嗎?12/11 03:16
19F推:這讓我想到大一時在寫八皇后的問題,怎麼都想不出來11/11 20:33
20F→:後來有人提到用遞迴,將所有情形都找出來11/11 20:33
21F→:然後每一種檢查是否符合條件11/11 20:33
22F→:原以為只能這麼做,結果後來看到一位天才的同學11/11 20:34
23F→:用八層迴圈一樣很快就跑出來,真的很天才。11/11 20:34
15F推:找到 shortest path 之後,刪掉 shortest path 的一邊09/18 14:59
16F→:再找 shortest path,有可能就是 second shortest path09/18 14:59
17F→:shortest path 上每條邊刪掉一次、找 shortest path09/18 14:59
18F→:照理說應該有答案,只是萬一所得到的答案都跟原來一樣長09/18 15:00
19F→:怎麼辦呢?sorry,可能是我沒想清楚。09/18 15:00
21F推:每條邊的長度若都是正的的話09/19 08:42
22F→:可以先寫一個不限制simple path的shortest path的演算法09/19 08:43
23F→:然後找起點的每個鄰居到終點的 shortest path09/19 08:44
24F→:再加上前面的做法,好像會包含 second shortest path09/19 08:45
25F→:不過不太確定...09/19 08:45
26F→:最近好像都只在想 heuristic 的方法,沒有好的證明...09/19 08:46