PDA

View Full Version : Finding shortest path?



jiSh@n
03-01-2004, 00:27
Nếu như đồ thị có số đỉnh, cạnh rất lớn (khỏang vài ngàn -> vài chục ngàn) thì ngoài cách dùng danh sách liên kết ra có còn cách nào lưu trữ hiệu quả ko? Có thuật toán nào để tìm đường đi ngắn nhất giữa 2 đỉnh hiệu quả hơn Dijkstra ko? Tui nghe nói A* cũng tương tự Dijkstra, ko biết có phải vậy ko?

msn
03-01-2004, 14:03
Với đồ thị như vậy có lẽ hiệu quả nhất là Dijkstra heap. Còn A* thì chỉ dùng trong đồ thị thực tế ví dụ như ma trận vuông hay đồ thị hình học còn với đồ thị lí thuyết thì không dùng được A* đâu.

jiSh@n
03-01-2004, 23:31
Dijkstra heap là seo vậy? có khác gì với Dijkstra ko?

CrazyBabe
04-01-2004, 00:47
Dùng dynamic listing chắc là hiệu quả nhất nếu có áp dụng truy xuất bằng băm.
A* khác hẳn với Dijkstra, khi nó thực thi trường hợp xấu nhất sẽ ngang bằng Dijkstra.
Muốn nhanh thì dùng RA*
Muốn chính xác 100% mà nhanh thì dùng D*
Mấy thuật toán này có tên rồi, search một cú là ra, hỏi nhiều làm gì ?

jiSh@n
04-01-2004, 01:14
hic, có điều tên nó kèm dấu * là ký tự đại diện, search bằng Google nó cho ra một đống A..., chẳng biết đâu mà lần.

yuna_admirer
04-01-2004, 06:18
Còn thuật toán ra sao thì bà con học hành ĐH chắc biết hết rồi.

ITbaby
04-01-2004, 07:39
Oe oe ! Em chưa có học đại học vậy làm sao em biết đây các anh chị ui ! Cho em cái link di oe oe oe..........

CrazyBabe
05-01-2004, 00:43
Ối dời ơi....
Má ơi....
Em yêu ơi....
Có mỗi tìm kiếm mà cũng...
Làm ơn cho thêm một số thông tin kiểu như path finding shortest, fastest zô...
Simple exam:
http://www.policyalmanac.org/games/aStarTutorial.htm
http://www.intrafoundation.com/pathfinder2d.asp

CrazyBabe
05-01-2004, 00:44
À wên, còn một site cũng hay fết, đấy là www.aiguru.com, vô đó tìm mấy cái path find ngon lém.

jiSh@n
05-01-2004, 18:58
Thank CrazyBabe nhiều nhé.