Tôi luôn bị hấp dẫn bởi Định tuyến bản đồ, nhưng tôi chưa bao giờ tìm thấy bất kỳ hướng dẫn cấp giới thiệu tốt (hoặc thậm chí nâng cao!) Nào trên đó. Có ai có bất kỳ gợi ý, gợi ý, vv?Bản đồ Định tuyến, a la Google Maps?
Cập nhật: Tôi chủ yếu tìm kiếm con trỏ về cách hệ thống bản đồ được triển khai (cấu trúc dữ liệu, thuật toán, v.v.).
Hãy xem open street map project để xem cách điều này đang được giải quyết trong một dự án phần mềm thực sự miễn phí chỉ sử dụng dữ liệu do người dùng cung cấp và cấp phép và có wiki containing stuff you might find interesting.
Một vài năm trở lại những người liên quan đến nơi khá dễ dàng đi và trả lời rất nhiều câu hỏi tôi đã có vì vậy tôi thấy không có lý do tại sao họ vẫn không phải là một bó tốt đẹp.
Thay vì API học tập để mỗi nhà cung cấp dịch vụ bản đồ (như Gmaps, Ymaps api) của nó tốt để tìm hiểu Mapstraction
"Mapstraction là một thư viện cung cấp một API phổ biến đối với nhiều API mapping javascript"
tôi sẽ đề nghị bạn truy cập URL và tìm hiểu một API chung. Có số lượng tốt của How-Tos quá.
Bằng cách định tuyến bản đồ, bạn có nghĩa là tìm đường đi ngắn nhất dọc theo mạng lưới đường phố?
Thuật toán đường dẫn ngắn nhất Dijkstra được biết đến nhiều nhất. Wikipedia không phải là phần giới thiệu xấu: http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm
Có một ứng dụng Java ở đây, nơi bạn có thể thấy nó hoạt động: http://www.dgp.toronto.edu/people/JamesStewart/270/9798s/Laffra/DijkstraApplet.html và Google bạn dẫn bạn đến mã nguồn chỉ bằng bất kỳ ngôn ngữ nào.
Bất kỳ triển khai thực tế nào để tạo tuyến đường lái xe sẽ bao gồm khá nhiều dữ liệu trên mạng đường phố mô tả chi phí liên kết với các liên kết và nút đi qua — hệ thống phân cấp mạng đường, tốc độ trung bình, ưu tiên giao lộ, liên kết tín hiệu giao thông, lượt bị cấm v.v ... .
tôi chưa tìm thấy một hướng dẫn tốt về định tuyến nhưng có rất nhiều mã để đọc:
có những ứng dụng định tuyến GPL sử dụng dữ liệu OpenStreetMap, ví dụ: Gosmore hoạt động trên Windows (+ di động) và Linux. Có một số ứng dụng thú vị sử dụng cùng một dữ liệu, nhưng gosmore có một số ứng dụng thú vị e.g. interface with websites.
Vấn đề lớn nhất với định tuyến là dữ liệu xấu và bạn không bao giờ có đủ dữ liệu tốt. Vì vậy, nếu bạn muốn thử nó giữ cho bài kiểm tra của bạn rất địa phương để bạn có thể kiểm soát dữ liệu tốt hơn.
Barry Brumitt, một trong những kỹ sư của bản đồ Google tính năng phát hiện tuyến đường, đã viết một bài về chủ đề này mà bạn có thể quan tâm:
The road to better path-finding 11/06/2007 03:47:00 PM
A * thực sự là gần gũi hơn với các thuật toán lập bản đồ sản xuất. Nó đòi hỏi một chút thăm dò ít hơn so với thuật toán ban đầu của Dijikstra.
Thực ra, D * đã sửa đổi là những gì thường được sử dụng theo như tôi biết. – mmcdole
Từ quan điểm khái niệm, hãy tưởng tượng thả đá vào ao và xem gợn sóng. Các tuyến đường sẽ đại diện cho các ao và đá vị trí bắt đầu của bạn.
Tất nhiên, thuật toán sẽ phải tìm kiếm một số tỷ lệ n^2 đường dẫn khi khoảng cách n tăng. Bạn sẽ đưa bạn vị trí bắt đầu và kiểm tra tất cả các đường dẫn có sẵn từ thời điểm đó. Sau đó đệ quy gọi cho các điểm ở cuối của những đường dẫn và như vậy.
Bạn có thể tăng hiệu suất, bằng cách không kiểm tra lại đường dẫn, bằng cách không kiểm tra lại các tuyến tại một thời điểm nếu nó đã được bao phủ và bằng cách từ bỏ các đường dẫn mất quá nhiều thời gian.
Một cách khác là sử dụng phương pháp tiếp cận ant pheromone, nơi kiến bò thu thập ngẫu nhiên từ điểm bắt đầu và để lại một đường nhỏ, tạo nên nhiều kiến vượt qua một đường nhất định. Nếu bạn gửi (đủ) kiến từ cả điểm bắt đầu và điểm kết thúc thì cuối cùng con đường có mùi hương mạnh nhất sẽ là ngắn nhất. Điều này là do con đường ngắn nhất sẽ được truy cập nhiều lần hơn trong một khoảng thời gian nhất định, vì kiến kiến đi bộ với tốc độ đồng đều.
EDIT @ Spikie
Là một giải thích thêm về cách để thực hiện các thuật toán ao - cấu trúc dữ liệu tiềm năng cần được đánh dấu:
Bạn sẽ cần phải lưu trữ các bản đồ như một mạng lưới. Đây chỉ đơn giản là một tập hợp các số nodes và edges giữa chúng. Tập hợp số nodes cấu thành một số route. Một cạnh nối hai nút (có thể là cùng một nút) và có một số cost được kết hợp như distance hoặc time để di chuyển qua cạnh. Một cạnh có thể là hai chiều hoặc đơn hướng. Có lẽ đơn giản nhất để chỉ có các hướng đơn hướng và tăng gấp đôi cho việc di chuyển hai chiều giữa các nút (tức là một cạnh từ A đến B và một cạnh khác từ B đến A).
Bằng cách ví dụ, hãy tưởng tượng ba ga đường sắt được sắp xếp theo tam giác đều hướng lên trên. Ngoài ra còn có thêm ba trạm mỗi nửa chừng giữa chúng. Các cạnh tham gia tất cả các trạm liền kề với nhau, sơ đồ cuối cùng sẽ có một tam giác ngược nằm bên trong tam giác lớn hơn.
Các nút nhãn bắt đầu từ dưới cùng bên trái, chuyển từ trái sang phải và lên, như A, B, C, D, E, F (F ở trên cùng).
Giả sử các cạnh có thể được di chuyển theo một trong hai hướng. Mỗi cạnh có chi phí 1 km.
Ok, vì vậy, chúng tôi muốn định tuyến từ dưới cùng bên trái A đến ga trên cùng F. Có nhiều tuyến đường có thể, bao gồm cả các tuyến đường tăng gấp đôi trở lại, ví dụ: ABCEBDEF.
Chúng tôi có thông báo là NextNode, chấp nhận node và cost và tự gọi cho mỗi nút mà nút này có thể chuyển đến.
Rõ ràng nếu chúng ta để thói quen này chạy nó cuối cùng sẽ khám phá tất cả các tuyến đường, bao gồm những tuyến có khả năng có chiều dài vô hạn (ví dụ ABABABAB, v.v.). Chúng tôi ngừng điều này xảy ra bằng cách kiểm tra lại số cost. Bất cứ khi nào chúng tôi ghé thăm một nút chưa được truy cập trước đó, chúng tôi đặt cả chi phí và nút mà chúng tôi đến từ nút đó. Nếu một nút đã được truy cập trước khi chúng tôi kiểm tra so với chi phí hiện tại và nếu chúng tôi rẻ hơn thì chúng tôi cập nhật nút và tiếp tục (đệ quy). Nếu chúng ta đắt hơn, thì chúng ta bỏ qua nút. Nếu tất cả các nút bị bỏ qua thì chúng ta thoát khỏi thường trình.
Nếu chúng tôi nhấn nút mục tiêu của mình thì chúng tôi cũng thoát khỏi quy trình.
Bằng cách này, tất cả các tuyến đường khả thi đều được chọn, nhưng chủ yếu là những tuyến có chi phí thấp nhất. Đến cuối quá trình, mỗi nút sẽ có chi phí thấp nhất để nhận được nút đó, bao gồm nút đích của chúng tôi.
Để nhận được tuyến đường, chúng tôi làm việc ngược từ nút mục tiêu của chúng tôi. Vì chúng tôi đã lưu trữ nút chúng tôi đến từ cùng với chi phí, chúng tôi chỉ cần lùi lại xây dựng tuyến đường. Ví dụ, chúng ta sẽ kết thúc với một cái gì đó như:
Node A - (Tổng) Chi phí 0 - Từ Node Không
Node B - Chi phí 1 - Từ Node Một
Node C - Chi phí 2 - Từ Node B
Nút D - Chi phí 1 - Từ Nút A
Nút E - Chi phí 2 - Từ Nút D/Chi phí 2 - Từ Nút B (đây là trường hợp ngoại lệ với chi phí bằng nhau)
Nút F - Chi phí 2 - Từ Nút D
Vì vậy, tuyến đường ngắn nhất là ADF.
@ jonathan, xin vui lòng cho bạn biết chi tiết của đá trong thuật toán ao và làm thế nào tôi có thể áp dụng nó trên bản đồ.hãy nói rằng tôi đang ở một điểm và tôi muốn tìm kiếm xung quanh trong gợn trước khi chuyển sang gợn bên ngoài tiếp theo. và anh chàng tôi biết và 2 năm sau cuộc trò chuyện – Spikie
Một suy nghĩ khác xảy ra với tôi về chi phí của mỗi lần truyền tải, nhưng sẽ tăng thời gian và sức mạnh xử lý cần thiết để tính toán.
Ví dụ: Có 3 cách tôi có thể thực hiện (nơi tôi sống) để đi từ điểm A đến điểm B, theo GoogleMaps. Các đơn vị Garmin cung cấp một trong 3 đường dẫn này trong tính toán tuyến đường Quickest. Sau khi đi qua từng tuyến đường này nhiều lần và trung bình (rõ ràng sẽ có lỗi tùy thuộc vào thời gian trong ngày, lượng caffein vv), tôi cảm thấy các thuật toán có thể tính đến số lượng đường cong trên đường cho mức độ chính xác cao , ví dụđường thẳng 1 dặm sẽ nhanh hơn đường 1 dặm với đường cong sắc nét trong đó. Không phải là đề xuất thực tế nhưng chắc chắn là một gợi ý tôi sử dụng để cải thiện kết quả của tuyến đường đi làm hàng ngày.
Từ kinh nghiệm làm việc trong lĩnh vực này, A * thực hiện công việc rất tốt. Đó là (như đã đề cập ở trên) nhanh hơn thuật toán của Dijkstra, nhưng vẫn đủ đơn giản cho một lập trình viên thông thường có thẩm quyền để thực hiện và hiểu.
Xây dựng mạng tuyến đường là phần khó nhất nhưng có thể chia nhỏ thành một loạt các bước đơn giản: nhận tất cả các con đường; sắp xếp các điểm thành trật tự; tạo các nhóm điểm giống nhau trên các đường khác nhau thành các nút giao nhau (nút); thêm vòng cung theo cả hai hướng nơi các nút kết nối (hoặc theo một hướng duy nhất cho đường một chiều).
Thuật toán A * là well documented on Wikipedia. Vị trí chính để tối ưu hóa là việc chọn nút tốt nhất từ danh sách mở, mà bạn cần một hàng đợi ưu tiên hiệu suất cao. Nếu bạn đang sử dụng C++, bạn có thể sử dụng bộ điều hợp STL priority_queue.
Tùy chỉnh thuật toán để định tuyến qua các phần khác nhau của mạng (ví dụ: người đi bộ, xe hơi, phương tiện công cộng, v.v.) có tốc độ, khoảng cách ưu tiên hoặc các tiêu chí khác khá dễ dàng. Bạn làm điều đó bằng cách viết các bộ lọc để kiểm soát phân đoạn tuyến nào có sẵn, khi xây dựng mạng và trọng số nào được gán cho từng phân đoạn.
Bản đồ thường quá lớn để cho phép các thuật toán đường dẫn ngắn nhất chuẩn, bạn sẽ phải xây dựng một số chẩn đoán để chọn biểu đồ con. Hơn nữa, bạn có thể sử dụng các phương pháp tiếp cận heuristic hoàn toàn khác nhau (ví dụ: đường cao tốc đầu tiên, ..) để tìm tuyến đường. –