Google Maps: Tìm Đường Ngắn Nhất Trong 4 Giây

Source: Facebook

Nội Dung

Google Maps tìm ra đường đi ngắn nhất cho bạn trong 4 giây. Nhưng nếu tính thủ công, bạn cần 10^200 năm, con số mà không có bất cứ con người nào hình dung ra được.

Quy Mô Của Vấn Đề

• Mạng lưới đường bộ Bắc Mỹ có hơn 64 triệu giao lộ
• Số tuyến đường có thể đi từ New York đến San Francisco: ước tính khoảng 10^220 tuyến
• Dù bạn kiểm tra một tỷ tuyến mỗi giây, vẫn cần hơn 10^200 năm để thử hết

Giải Pháp Thuật Toán

OSPF được xây dựng dựa trên thuật toán của Dijkstra:

“Vẽ đường thẳng nối 2 điểm, sau đó xác định các nút trên đường gần điểm đó nhất rồi nối các nút đó lại với nhau.”

Nhưng để 1 người tìm đường đi ngắn nhất, họ có thể chỉ mất vài tháng thôi… 😄