Các nhà khoa học máy tính khám phá ra con đường dài nhất để đi thuyền vòng quanh thế giới mà không cần cập bến

Một chủ đề trên Reddit từ năm trước cuối cùng cũng được giải quyết. Đó là tìm ra đường thẳng dài nhất để đi vòng quanh thế giới mà không cần phải chạm đất. Tất nhiên, nhìn lướt qua những hình ảnh dưới đây, chúng ta có thể thấy rõ ràng những đường chỉ dẫn này không phải là đường thẳng.

Nhưng bạn hãy nhớ lại rằng cung tròn chính là biểu diễn của đường thẳng trên bề mặt hình cầu của Trái. Nghĩa là khi bạn trải chúng ra trên mặt phẳng thì những đường cung tròn này sẽ thành đường thẳng.

Rohan Chabukswar từ Trung tâm Nghiên cứu Công nghệ Hoa Kỳ ở Ireland và Kushal Mukherjee từ IBM Research ở Ấn Độ đã phát triển một thuật toán có thể tính toán đường dài nhất trên biển hoặc đất liền. Bộ đôi vừa trình bày kết quả nghiên cứu của họ.

Thuật toán sử dụng một kỹ thuật gọi là branch và bound. Nó hoạt động bằng cách xem xét tất cả các giải pháp tiềm năng trên một sơ đồ giống như các nhánh trên một cái cây. Thuật toán sau đó kiểm tra tính khả thi của từng nhánh trên sơ đồ. Về cơ bản nó xem xét các giải pháp có thể có trong một nhánh và cố gắng tìm một tập hợp con gần hơn với giá trị tối ưu.

Nếu nhánh không gần với giải pháp tối ưu, nó sẽ bị bỏ qua hoàn toàn. Hai nhà nghiên cứu nói rằng thuật toán của họ trả về con đường trên biển dài nhất trong khoảng 10 phút tính toán. Con đường dài nhất trên đất liền mất khoảng 45 phút để tính toán. Cả 2 quãng đường này đều được các thuật toán thực hiện trên một máy tính xách tay thông thường.

Điều thú vị là đường thủy “hầu như” giống với con đường mà người ta tìm thấy vào năm 2012 dựa trên bản đồ. Con đường dưới nước mà các nhà nghiên cứu xếp hạng dài 32,089.7 km. Trong khi đó, con đường bộ dài nhất chạy qua 15 quốc gia và kéo dài 11,241.1km.

Tham khảo: Bgr