日誌2020-08-11 05:12

最近在程設版看到一個問題

問題如圖


我們來看看留言裡面有什麼答案


|V| = 500 * 500 = 25萬個點，這樣真的可以用Floyd–Warshall？


這個問題的連通狀態是一直在改變的，與現實應用連結，可以想到封包怎麼送的問題


所以下面留言的Bellman–Ford和Dijkstra都有機會

2

2

LINE 分享

相關創作

從別人家的糞扣(code)了解學習演算法(algorithm)是有用的

好會ㄛ

忘記玩梗ㄌ

留言

• 2020-08-11 08:08樂小呈：
  500 * 500 的網格用Dijkstra效能會爆吧[e21]

  2020-08-11 10:52♙♲⚙＼~O_O~／⚙♲♙：可能會 可能不會
  
  25萬個點*每個點4條岔路=100萬
  log2(25萬) ≒ 18
  1800萬*某個我也不知道多少的係數
  
  在C/C++
  int s=0; for(int x=100000000;x--;) s=(s+x)&0x3FFFFFFF;
  1億才會感覺到卡(大約0.2秒)
  
  在javascript
  s=0; for(let x=10000000;x--;) s+=x;
  1千萬就會卡(大約0.5秒)

  2020-08-11 11:04♙♲⚙＼~O_O~／⚙♲♙：我更正 一定爆 多做幾件事情就超過了 QQ

• 2020-08-11 08:15樂小呈：
  但好像比較好的做法就是Dijkstra了[e21]

  2020-08-11 10:26♙♲⚙＼~O_O~／⚙♲♙：我的話應該是 用bfs以目標位置當起點硬上吧(25萬個點*每個點4條岔路=100萬,應該可以吧(?))
  然後發現要加什麼東西都很難加 因為效能需求直接吃滿0.1秒 接著就想怎麼用A*剪枝
  最後覺得整個寫太醜 直接把尋路變成智障型(greedy) 走不過去就放棄這樣

  2020-08-11 10:33♙♲⚙＼~O_O~／⚙♲♙：啊 不行 他的邊權重不一樣 那要把queue改成priority queue
  恩...Dijkstra \OvO/

• 送出