Bài học và trò chơi học tập

Đồ thị và tìm đường

Điều khiển một xe thăm dò Sao Hỏa bằng các thuật toán đứng sau mọi ứng dụng bản đồ và trò chơi: BFS, DFS, Dijkstra và A*, viết từ đầu bằng Python trên Raspberry Pi.

Khóa học

Đồ thị và tìm đường là một khóa Coding nâng cao gồm bảy bài học. Mỗi bài chạy trên cùng một mạch: một Raspberry Pi 4 với mô-đun đèn giao thông (đỏ ở GPIO17, vàng ở GPIO27, xanh lá ở GPIO22), đóng vai đèn trạng thái của xe thăm dò. Bản đồ và lộ trình được in ra Serial Monitor, và mỗi bước được kiểm tra theo những gì Pi in ra hoặc đèn nào sáng.

  1. Đồ thị dưới dạng dữ liệu: các trạm và con đường của căn cứ Base Jezero thành một dict chứa danh sách, bậc và trạm đông nhất, một bộ kiểm tra tìm ra đường một chiều, bổ đề bắt tay, và một bản đồ địa hình chuyển thành đồ thị các ô.
  2. BFS: một hàng đợi khám phá theo từng vành, khoảng cách tính theo số bước, các cha để dựng lại lộ trình, một hàm route dùng cho cả trạm và lưới, lộ trình vẽ trên bản đồ, và đèn đỏ khi một vụ sạt lở đá vây kín đích đến.
  3. DFS: đệ quy và một ngăn xếp tường minh, các trạm bị một cơn bão bụi cắt đứt, lộ trình đầu tiên dài 32 bước trong khi BFS tìm được 24, và giới hạn đệ quy mà một khu vực 30 x 30 vấp phải.
  4. Dijkstra: thời gian di chuyển làm trọng số cạnh, heapq làm hàng đợi ưu tiên, lộ trình 30 phút lại đi nhiều hơn một con đường so với lộ trình 40 phút, và cát mềm trên bản đồ địa hình.
  5. A: độ ưu tiên f = g + h, khoảng cách Manhattan và heuristic khả tín, cùng một lộ trình từ 25 ô thay vì 42, một đồng bằng 600 ô nơi A mở rộng 54 ô so với 570 ô của Dijkstra, và lộ trình tệ hơn mà phỏng đoán quá tự tin chọn ra.
  6. Mê cung: một DFS ngẫu nhiên đục ra một mê cung hoàn hảo (39 lối đi cho 40 ô), BFS giải nó, lời giải được vẽ, các ngõ cụt được đếm, và một seed mới tạo ra một mê cung mới.
  7. Trùm cuối: robot giải mê cung: hồi kết.

Danh mục còn liệt kê một ESP32-C3 và một khung hai bánh. Khóa học này chỉ xây trên Pi, với chuyển động của xe thể hiện qua các lệnh lái được in ra, nên mọi bước đều có thể kiểm tra ngay trong trình duyệt.

Hồi kết

Rover 7's console reads commands typed in the Serial Monitor. Its canyon is the maze from lesson 6 with six extra walls knocked out, because a real canyon has loops. solve plans with A*, amber lamp on while it searches, then green, and prints the route as drive commands: R F L F F F F R F L F R F L F F R F for the 11 cell route, worked out from the change in compass heading at each cell. rock 4 9 drops a boulder on the route and the next solve finds a 13 cell way around. rock 8 15 blocks the goal's only way in, and the red lamp says so. drive plans and plays the commands out, one move at a time, until "arrived at the goal. Science time."

Engine của Pi làm khác ở chỗ nào

Pi chạy MicroPython 1.29, không phải CPython. Trong khóa học này điều đó thể hiện ở vài chỗ:

  • heapq có heappush, heappop và heapify, đúng những gì Dijkstra và A* cần; collections.deque cũng có sẵn cho BFS.
  • Một dict không giữ thứ tự khóa được đưa vào, nên các bảng duyệt qua sorted(...). Danh sách giữ nguyên thứ tự, nên các danh sách láng giềng vẫn an toàn.
  • Đệ quy dừng lại gần 800 khung với RuntimeError: pystack exhausted. Giới hạn của CPython là 1,000 và lỗi của nó là RecursionError. Bài DFS cố tình chạm tường rồi khắc phục bằng một ngăn xếp.
  • random.seed(2026) cho cùng một mê cung ở mỗi lần chạy trên engine này. CPython lấy số ngẫu nhiên từ một bộ sinh khác, nên cùng seed ở đó có thể đục ra một mê cung khác nhưng cũng hoàn hảo không kém.
  • input() đọc một dòng gõ vào Serial Monitor.