[DIS] Theo tôi thì...

[hiensmart]

Theo tôi thì mod của box này nên đề ra những thuật toán cũng như những bài toán điển hình để mọi người cùng tham gia chứ tôi thấy box này đìu hiu wá
Tôi mở hàng trước:
Chắc các bạn ai cũng biết thuật toán tìm đg ngắn nhất
Có 1 bài toán khá lý thú:
Tìm đường đi ngắn nhất từ TP 1-> TP n trong khoản tiền cho trước
Inp: số thành phố, số tiền cho trước, số đg, từng con đg (TP bắt đâu, TP tới, Chi phí, Độ dài)

[ntrhieu]

Bạn phải cho giới hạn chứ. Chẳng hạn số thành phố? Có thể có thuật toán tốt hơn, nhưng nếu Số thành phố x Max (cost của 1 cạnh của đồ thị) vừa đử nhỏ (chẳng hạn 10^6) thì có thuật toán hiệu quả để chạy: Lưu một hàng đợi gồm các đỉnh, d và chi phí đến đỉnh dấy, và độ dài đến định đấy. Cùng 1 chi phí thì chỉ cần lưu lại độ dài bé nhất. Hàng đợi được sắp xếp theo chi phí tăng dần. Thuật toán tương tự bài "Roads" thi CEOI (bạn search trên internet se thấy).

[hiensmart]

BẠn có thể xem đề kỹ hơn bên bài "đường đi ngắn nhất,help me" hay "đường đi ngắn nhất" gì đó của sboyht để biết cụ thể hơn về đề

[haison3000]

Bài này dùng quy hoach động giải va cũng khá cơ bản.

[monkeyvu]

Bài này có khá nhiều thuật toán để giải đó,nhưng tùy bài mình sẽ sử dụng những thuật toán khác nhau.Mà hông biết có ai có cách nào mà hay hay không hen?Như bạn ntrhieu đã nói đó,nếu dữ liệu vào quá lớn thì.....bó tay á.

[TriLite]

mấy bác à, ba cái algorithm về graph thì trong sách ấy, khi cần thì lấy ra ứng dụng. Làm bài trong trường không kịp nữa, thời gian đâu làm bài đố