Thuật toán tìm đường của Google Map
Show
Bạn có thể tìm kiếm tất cả mọi thứ, như bưu điện, gian hàng chụp ảnh, trạm xe buýt hoặc tên đường, bằng cách sử dụng Google Maps. Bạn sẽ nhận được kết quả tìm kiếm tốt hơn khi đăng nhập vào Google Maps. Khi đăng nhập, bạn có thể nhanh chóng tìm thấy những địa điểm bạn đã tìm kiếm trước đó và tìm kiếm các địa chỉ liên hệ của mình theo tên. Xem toàn bộ bản đồĐể xem toàn bộ bản đồ và ẩn bảng điều khiển bên, hãy nhấp vào biểu tượng Mũi tên ở bên phải của bảng điều khiển. Lọc kết quả tìm kiếm trên Google Maps
Mẹo tìm kiếmSau đây là một số ví dụ về các tìm kiếm trên Google Maps:
Nhận thêm thông tin về địa điểmĐể nhận thêm thông tin về một địa điểm, hãy thực hiện theo một trong các cách sau:
Bạn sẽ thấy thông tin về địa điểm, như địa chỉ, giờ làm việc, số điện thoại, trang web và xếp hạng hoặc bài đánh giá. Mẹo: Bạn có thể sử dụng 3D Touch trên iPhone 6s trở lên để tìm trang web của một địa điểm, lưu địa điểm, tìm đường đi và chia sẻ địa điểm. Để bật 3D Touch, hãy chuyển đến ứng dụng Cài đặt Xem các đề xuất tìm kiếm cho địa điểm
Cách Maps hiển thị kết quả địa phươngCác địa điểm chung trên bản đồKết quả địa phương xuất hiện cho những người tìm kiếm cho doanh nghiệp và địa điểm gần vị trí của họ. Kết quả được hiển thị ở nhiều nơi khác nhau trên Maps và Tìm kiếm. Ví dụ: bạn có thể sẽ thấy kết quả địa phương nếu tìm kiếm "nhà hàng Ý" từ thiết bị di động. Google sẽ cố gắng hiển thị cho bạn loại nhà hàng lân cận mà bạn muốn ghé thăm. Kết quả địa phương bị ảnh hưởng bởi một số yếu tố, những yếu tố chủ yếu là mức độ liên quan, khoảng cách và sự nổi bật. Những yếu tố này được kết hợp để giúp tìm thấy kết quả phù hợp nhất cho tìm kiếm của bạn. Ví dụ: các thuật toán của Google có thể quyết định rằng một doanh nghiệp ở xa vị trí của bạn có nhiều khả năng cung cấp những gì bạn đang tìm kiếm hơn so với một doanh nghiệp ở gần bạn hơn và vì vậy, xếp hạng doanh nghiệp ở xa đó cao hơn trong kết quả địa phương. Lưu ý: Kết quả trong Google Maps không bị ảnh hưởng bởi thanh toán từ các công ty khác. Nội dung trả phí trong Google Maps được gắn nhãn. Tìm hiểu thêm về kết quả tìm kiếm địa phương trong Google. Địa điểm có liên quan đến bạnMột số địa điểm được cá nhân hóa mà bạn thấy trên Google Maps chỉ có thể hiển thị cho bạn. Nếu đang sử dụng Google+, bạn cũng có thể thấy các địa điểm được những người trong vòng kết nối của bạn đề xuất hoặc chia sẻ. Dưới đây là một số ví dụ về nguồn gốc của thông tin này:
Các địa điểm được cá nhân hóa mà bạn nhìn thấy có thể có từ:
Nếu bạn không muốn thấy đề xuất tìm kiếm trong Google Maps, hãy tắt Hoạt động web và ứng dụng của bạn. Các sản phẩm khác của Google
Các địa điểm được cá nhân hóa mà bạn nhìn thấy có thể có từ:
Nếu bạn không muốn thấy đề xuất tìm kiếm trong Google Maps, hãy cập nhật tùy chọn của bạn trong các sản phẩm khác của Google.
Thông tin này có hữu ích không? Chúng tôi có thể cải thiện trang này bằng cách nào?
Hồi đó tôi thi tin học trẻ không chuyên, năm trước đó tôi đã được giải nhất tỉnh và giải 3 toàn quốc gì đó về làm phần mềm. Giải tin học trẻ không chuyên thường có 2 hệ thống giải, 1 dành cho thi lập trình và 1 dành cho phần mềm. Tôi chọn thi phần mềm vì 2 lý do Ít cạnh tranh và thời gian chuẩn bị dài — khôn thế chứ lị. Với phần mềm bản đồ này, tôi đã nghĩ đến việc đạt tiếp giải năm nay. Lúc đó, tôi sẽ nói với ban giám khảo rằng, tại sao tôi đặt tên phần mềm là Vimap ? Vì ban đầu, nó là bản đồ thành phố Vinh, lớn hơn nữa nó sẽ là bản đồ Việt Nam, lớn hơn nữa nữa nó sẽ là bản đồ của Viễn — tên tui :P Tiếc là cái giây phút đó chỉ có trong tưởng tượng của chàng trai 18 tuổi thôi. Tưởng tượng chán rồi bắt tay vào làm thôi. Đầu tiên là phải vẽ bản đồ. Tôi ra nhà sách, mua 1 tấm bản đồ của thành phố về. Bản đồ giấy nên to dễ sợ. Tôi mang ra tiệm scan để scan lên máy tính, người ta phải scan nhiều lần, mỗi lần 1 góc rồi tôi copy về. Về nhà hì hụi dùng photoshop để ghép nó lại với nhau, dùng Pen vẽ lại từng con đường, từng góc phố. Tô màu xám-vàng giống như google map. Hồi đó chưa biết đồ họa vector nên làm bitmap thôi. Để làm tính năng zoom-in zoom-out, tôi tự phóng to, thu nhỏ bản đồ rồi lưu ra các file khác nhau. Vì bản đồ nó rất to nên không thể lưu 1 file ảnh được, lưu vậy lúc người dùng load được cái ảnh chắc mất nguyên năm. Cái này đương nhiên học tập Google map, tôi thấy nó load ảnh theo từng ô vuông. Từ cái bản đồ to, tôi chia nhỏ thành nhiều ô vuông khác nhau, mỗi ô vuông là 1 file. May là Photoshop nó có tính năng này, chứ ko thì mệt chết bà. Có bản đồ xong, tôi viết các tính năng kéo thả để di chuyển bản đồ, zoom.. Tất cả viết bằng HTML, JS, CSS. Phần này chỉ có to tay thôi chứ không cần suy nghĩ nhiều. Phần khó nhất là phần tìm đường. Người dùng chọn 2 điểm trên bản đồ, giờ làm sao để tìm đường đi ngắn nhất giữa 2 điểm đó — đây cũng là phần tôi tự hào nhất. Hồi đó tôi thích tin nhưng thi chuyên Tin không đậu, may là còn đậu chuyên Lý. Do không theo chuyên Tin nên mấy cái thuật toán tôi đều tự học, chủ yếu là đọc tài liệu trên mạng hoặc lên mấy diễn đàn như ddth.com để hỏi. Các thuật toán tìm đường thì trong sách Toán rời rạc có, cũng ngâm cứu chán chê mà chưa chọn được cách nào ưng ý để áp dụng vào thực tế. Trong thời gian nghiên cứu thuật toán tìm đường, tôi chuyển sang việc nhập liệu trước.
Hồi đó dùng MySql để lưu trữ. x1,y1 là tọa độ điểm 1, các điểm cách nhau bằng dấu gạch đứng | và lưu hết các điểm vào trong 1 trường. Các bạn đừng chửi ngu nhé vì 12 năm trước thì cũng chỉ đến thế là cùng thôi :D Quay lại bài toán tìm đường, tôi quyết định chọn thuật toán A*. Hồi đó chỉ tìm hiểu thuật toán này qua Wikipedia. Ngâm cứu mãi rồi bắt tay vào viết, nhưng thực ra viết xong rồi cũng ko biết mình hiểu có đúng thuật toán hay không :D Để hiểu A* thì các bạn phải đọc về thuật toán tìm Dijkstra trước, xong rồi đọc tiếp các thuật toán tối ưu dùng hàm heuristic. Cơ bản các bạn có thể hiểu như này, trường hợp tệ nhất của mọi thuật toán tìm kiếm là Vét cạn — tức là thử tất cả các trường hợp có thể. Trong tìm đường thì Vét cạn là thử tất cả các cung đường có thể đi, sau đó chọn ra đường ngắn nhất. Để giảm số lượng cung đường cần thử, người ta đưa vào các hàm đánh giá heuristic. Giả sử ta đang ở ngã 3 đường, giờ chọn rẽ phải hay rẽ trái ? Hàm heuristic sẽ dựa vào các thông số đã biết để đưa ra quyết định là rẽ bên nào sẽ có khả năng về đích sớm hơn. Tôi lúc đó hiểu A* một cách hình tượng như thế này : Bạn đang cần tìm đường đến đài truyền hình của thành phố. Tuy bạn đang ở xa nhưng bạn vẫn nhìn thấy tháp truyền hình. Bạn vừa di chuyển vừa nhìn ngọn tháp để đưa ra phán đoán. Bạn sẽ chọn ngã rẽ nào đưa bạn đến gần ngọn tháp hơn. Cách hiểu này rất hợp lý trong thực tế và cũng phù hợp với việc tìm đường đi trên bản đồ thành phố. Áp dụng cụ thể như sau. Giả sử bạn xuất phát ở điểm A(x1,y1) Điểm này nối với điểm B(x2,y2) và điểm C(x3,y3). Điểm đích là điểm D(x4, y4). Bạn sẽ chọn điểm nào để rẽ ? Đầu tiên chúng ta tính khoảng cách AB và AC là đường đi trên thực tế, sau đó tính khoảng cách BD và CD ( đây là khoảng cách đường chim bay — chứ trên thực tế chưa chắc B và D được nối với nhau trực tiếp ). Kế tiếp chúng ta so sánh, nếu AB+BD < AC+CD thì điểm B sẽ tiềm năng hơn điểm C — do đưa chúng ta đến gần điểm đích hơn, và do đó chúng ta bổ sung điểm B vào đường đi.
Tư tưởng là vậy nhưng để cài đặt thuật toán chạy thành công thì cũng phải mất kha khá thời gian. Và với một người không chuyên thì nó là một điều đáng tự hào. Tôi đã hoàn thành bản đồ thành phố với các chức năng cơ bản là kéo thả, phóng to thu nhỏ, tìm tên đường và tìm đường đi giữa 2 điểm. Mặc dù vậy, sản phẩm này chỉ đạt giải 2 cuộc thi Tin học trẻ không chuyên cấp Tỉnh và không được tham gia cuộc thi toàn quốc. Nhưng không vì thế mà tôi dừng lại, tôi và một số bạn đã liên hệ với tỉnh đoàn Nghệ An để đưa bản đồ này vào phục vụ cho mùa thi. Lúc đấy đã đặt domain là vinhmuathi.net. Hồi đấy Vinh là một điểm thi tập trung, nên các thí sinh từ các tỉnh lân cận đổ về Vinh để thi. Chúng tôi đưa danh sách nhà trọ và các điểm thi lên bản đồ để phục vụ các bạn ở xa. Mặc dù năm đó chúng tôi cũng đi thi :P May mà đỗ. Lúc mới làm xong, tôi có đăng lên ddth, giờ vẫn còn xem lại được ở đây https://www.ddth.com/showthread.php/174454-B%E1%BA%A3n-%C4%91%E1%BB%93-TP-Vinh-tr%E1%BB%B1c-tuy%E1%BA%BFn?s=aeb9916ba7f4b9ecbe98997c3cf668c7 . Nhờ bài đăng này mà tôi được các anh ở Naiscorp (socbay) tài trợ hosting, từ đó làm quen được với các anh nên sau này đi đại học được nâng đỡ nhiều. Cũng nhờ thời gian thực tập-làm việc ở Naiscorp nên tôi mới được trải qua nhiều thứ như bây giờ. Tiếc là vào năm nhất đại học, tôi đổi máy tính qua lại, rồi do bất cẩn mà tôi làm mất toàn bộ mã nguồn Vimap. Giờ tiếc quá, cũng không còn cái ảnh screenshot nào. Nên bài này phải ngồi viết chay như này, sợ sau này cũng quên mất. Nghĩ lại thì hồi cấp 3 là thời gian được làm theo sở thích của mình nhiều nhất. Bạn có thể theo đuổi nhiều ngày nhiều tháng vì đam mê mà không hề có áp lực gì. Vậy nên các bạn cấp 3 hãy tận hưởng nhé ./
Cùng một tác giả
8 3
Livestream đã và đang là chuyện hằng ngày hằng giờ trên các mạng xã hội. Những bài viết livestream được ưu tiên hiển thị nhiều hơn so với những bài...
8 3
Đây là kinh nghiệm của mình gần đây, khi server bị hack và mình vất vả chống đỡ. Bài ghi lại cách cấu hình server CentOS cho bảo mật hơn. Cấu hìn...
4 0
Sau 1 thời gian làm ReactJS cho website gostream.co thì nhu cầu tất yếu tiếp theo là làm app. Mặc dù GoStream đã có app cả ios và android nhưng app... Bài viết liên quan
18 8
Đây là một câu hỏi thường gặp trong những buổi phỏng vấn ứng viên Java, và cũng có không ít bạn vì câu hỏi này mà gặp trắc trở, hôm nay chúng ta sẽ...
0 0
https://grokonez.com/kotlin/kotlinconvertmapsortedmap Kotlin convert Map to SortedMap In the tutorial, JavaSampleApproach will show you how to co... |