2013年4月27日 星期六

Dijkstra's algorithm 及其他


1. Breadth-first Search ((BFS)) 加強版,原本的 queue 要改成 priority queue ((也就是 heap,heap 有分 min heap 或 max heap))


2. 問題的關鍵都是「如何抽象化成數學模型」,哪些是點 ((狀態,哪些 factors 該計入狀態?)),哪些是邊 ((有向或是無向,數字權重代表的意義是甚麼?))


3. 如果 N 不大,可以考慮用 Floyd-Warshall Algorithm,使用前思考一下為什麼使用這個演算法?這是對的演算法嗎?如何保證答案就是演算法算出來的答案?


4. DFS 與 BFS 是否可以互相取代?

沒有留言:

張貼留言