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.
- Đồ 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 ô.
- 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
routedù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. - 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.
- Dijkstra: thời gian di chuyển làm trọng số cạnh,
heapqlà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. - 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.
- 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.
- 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ỗ:
heapqcóheappush,heappopvàheapify, đúng những gì Dijkstra và A* cần;collections.dequecũ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.