cách tìm kiếm áp dụng trong thành phố mà các chương trình hay áp dụng là từ những đường nhỏ, ngõ nhỏ đi ra đường lớn ngõ lớn.
Trong phần ảnh ví dụ của mình vẫn chưa thực sự rõ ràng lắm nhưng cũng tạm đủ hỉêu, giả sử ta đi từ A đến B. Nếu tìm đường ngắn nhất chắc chắn nó sẽ chỉ theo đường Đê La Thành -> Khâm Thiên, nhưng ngừời đi thường đi theo đường Kim Mã -> Nguyễn Thái Học -> Lê Duẩn
Như vậy, Nếu giữ nguyên thuật toán cho cả thành phố chương trình sẽ chạy tốn nhiều tài nguyên và thời gian. Chính vì thế mà ta phải phân loại đường, giả sử phân làm 2 loại: đường 2 chiều nhỏ (như Đê La Thành) và đường 2 làn đường lớn(như Kim Mã). Vậy thuật toán sẽ được chạy làm 3 lần, lần thứ nhất chỉ áp dụng cho đường lớn, lần thứ 2 áp dụng cho điểm xuất phát tới đường lớn và lần cuối cùng từ đường lớn tới điểm đích.
Số loại đường phân loại tuỳ thuộc vào từng bản đồ cụ thể, ví dụ Hà nội thì theo mình phân ra làm 2 loại là OK, khi nào chạy ngon ta sẽ update lên nhiều loại hơn, càng nhiều loại thì độ chính xác phù hợp với con người càng cao.
Việc phân loại này vừa giảm được points mà kết quả lại sát với thực tế hơn.
Hơn nữa khi chạy Dijk thì 2 lần 100 points luôn luôn nhanh hơn rất nhiều so với chạy 1 lần 200 points. Cái này chắc bác cũng dễ hiểu
Làm dữ liệu cũng ko khó, nửa ngày là OK, HN chỉ có vài trăm con đường thôi, mua 1 tấm bản đồ về là biết đường nào to đường nào nhỏ.
Trong phần ảnh ví dụ của mình vẫn chưa thực sự rõ ràng lắm nhưng cũng tạm đủ hỉêu, giả sử ta đi từ A đến B. Nếu tìm đường ngắn nhất chắc chắn nó sẽ chỉ theo đường Đê La Thành -> Khâm Thiên, nhưng ngừời đi thường đi theo đường Kim Mã -> Nguyễn Thái Học -> Lê Duẩn
Như vậy, Nếu giữ nguyên thuật toán cho cả thành phố chương trình sẽ chạy tốn nhiều tài nguyên và thời gian. Chính vì thế mà ta phải phân loại đường, giả sử phân làm 2 loại: đường 2 chiều nhỏ (như Đê La Thành) và đường 2 làn đường lớn(như Kim Mã). Vậy thuật toán sẽ được chạy làm 3 lần, lần thứ nhất chỉ áp dụng cho đường lớn, lần thứ 2 áp dụng cho điểm xuất phát tới đường lớn và lần cuối cùng từ đường lớn tới điểm đích.
Số loại đường phân loại tuỳ thuộc vào từng bản đồ cụ thể, ví dụ Hà nội thì theo mình phân ra làm 2 loại là OK, khi nào chạy ngon ta sẽ update lên nhiều loại hơn, càng nhiều loại thì độ chính xác phù hợp với con người càng cao.
Việc phân loại này vừa giảm được points mà kết quả lại sát với thực tế hơn.
Hơn nữa khi chạy Dijk thì 2 lần 100 points luôn luôn nhanh hơn rất nhiều so với chạy 1 lần 200 points. Cái này chắc bác cũng dễ hiểu
Làm dữ liệu cũng ko khó, nửa ngày là OK, HN chỉ có vài trăm con đường thôi, mua 1 tấm bản đồ về là biết đường nào to đường nào nhỏ.
Attachments
-
aaaaa.JPG
