Đang chuẩn bị nút TẢI XUỐNG, xin hãy chờ
Tải xuống
đặt vấn đề Trong một số tr-ờng hợp sử dụng bản đồ để tra cứu đ-ờng đi tới điểm nào đó th-ờng xuất hiện câu hỏi làm thế nào để xác định đ-ờng đi đến đó là ngắn nhất? Trong phạm vi hẹp hoặc mạng l-ới giao thông đơn giản ít đ-ờng đi thì có thể tìm ngay đ-ợc câu trả lời. Hầu hết các tr-ờng hợp còn lại là khó khăn. | KỸ ThUẬT TỈM ĐƯỜNG ĐI NGẮN NhÂT TRÊN BẢN ĐỔ KS. Lưu VĂN GIANG Trung tâm biên tập và công nghệ cao Nhà xuất bản Bản đồ Tóm tắt Bài báo nói về kỹ thuật tìm đường đi có độ dài ngắn nhất cũa hai điểm bất kỳ trên bẳn đồ và đề xuất một sô ứng dụng kỹ thuật này trong thực tế. Summary In this paper we consider the details of the routing algorith the shortest path on the graph and some applications from the result in the practice. I. ĐẶT VẤN ĐỂ Trong một số trường hợp sử dụng bản đồ để tra cứu đường đi tới điểm nào đó thường xuất hiện câu hỏi làm thế nào để xác định đường đi đến đó là ngắn nhấ t Trong phạm vi hẹp hoặc mạng lưới giao thông đơn giản ít đường đi thì có thể tìm ngay được câu trả lời. Hầu hế t các trường hợp còn lại là khó khăn. Vấn đề đặt ra là cần xây dựng cơ sở kỹ thuật tìm đường đi ngắn nhấ t giữa hai điểm xác định trên bản đồ trong thời gian nhỏ nhấ t đáp ứng ngay yêu cầu sử dụng. II. cơ sở CỦA KỸ ThUẬT TỈM ĐƯỜNG ĐI NGẮN NhÂT TRÊN BẢN ĐỔ Phát biểu bài toán Cho hai điểm bấ t kì trên bản đồ. Hãy chỉ ra đường đi có độ dài ngắn nhấ t giữa hai điểm đó trên cơ sở hệ thố ng giao thông của bản đồ. 1. Cơ sỏ toán học giải bài toán Cơ sở toán học của vấn đề này thực ra đã được toán học giải quyết từ rất lâu. Có rất nhiều phương pháp khác nhau trong bài này giới thiệu kỹ thuật tìm đường đi ngắn nhất dựa trên lý thuyết toán đồ thị. Phương pháp này có nhiều ưu điểm hơn khi áp dụng trong các bản đồ số bởi vì các bản đồ số dạng véc tơ đều xây dựng trên cơ sở lý thuyết đồ thị. Cho đồ thị G V E có trọng số không âm là các c V là tập đỉnh E là tập cạnh C u v là ma trận trọng số u v e V xem hình vẽ 1 Tất cả các thuật toán tìm đường đi ngắn nhất trên đổ thị đều dựa trên một tính chất Mọi đường con của đường đi ngắn nhấ t cũng là đường đi ngắn nhấ t . Giả sử tìm đường đi ngắn nhấ t từ đỉnh s tới đỉnh t s t e V người ta luôn tìm được đỉnh v trước t sao cho khoảng cách từ s đến t sẽ bằng d s t d s v c v t . Đỉnh v sẽ là trước t ngắn nhất Mọi đoạn sẽ từng bước kiế n thiết một cây .
