Mọi lộ trình

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

Dẫn dắt xe thăm hiểm Sao Hỏa bằng các thuật toán đứng sau mọi ứng dụng bản đồ và trò chơi: đồ thị như dữ liệu, BFS, DFS, Dijkstra và A* viết từ đầu, mê cung được khắc và giải, và một bảng điều khiển xe tự vạch đường né đá trên Raspberry Pi.

Raspberry Pi 4 Model BMiễn phí7 bài học6 h4 chương2.766 XPLập trình · Nâng cao+250 XP

Đã hoàn thành 0 trên 7

Bạn sẽ làm được gì

3 dự án, làm từng bước một

7 bài học trong 4 chương, khoảng 6 giờ trên Raspberry Pi 4 Model B được mô phỏng. Miễn phí, ngay trong trình duyệt, mỗi bước đều được trình mô phỏng kiểm tra.

Dự án chương 2

Tìm kiếm theo chiều sâu (DFS)

Tìm kiếm theo chiều sâu, dùng đệ quy và dùng ngăn xếp: thứ tự nó đi sâu, trạm nào bị bão bụi cắt đứt, vì sao đường đầu tiên nó tìm thấy trên bản đồ không phải đường ngắn nhất, và giới hạn đệ quy mà một cánh đồng lớn sẽ gặp phải.

Mở trong trình mô phỏng
Dự án chương 3

Tìm kiếm A*

Dijkstra có thêm cảm giác hướng đi: một hàm heuristic, khoảng cách Manhattan, độ ưu tiên f = g + h, cùng một đường tốt nhất nhưng cần ít ô hơn hẳn, một đồng bằng rộng nơi mức tiết kiệm rất lớn, và cái giá phải trả khi heuristic quá tự tin.

Mở trong trình mô phỏng
Dự án chương 4

Trùm: robot giải mê cung

Bảng điều khiển của Rover 7: một mê cung, A* lập kế hoạch theo lệnh, đèn báo trạng thái cho việc lập kế hoạch, đường đi và bị vây kín, lệnh lái kèm quay đầu, đá được nhập trực tiếp buộc phải lập kế hoạch lại, và một hành trình lái tới đích.

Mở trong trình mô phỏng
Bản đồ

Từng chương một

Mỗi bài học mở ra khi bài trước hoàn thành, và mỗi chương kết thúc bằng một dự án.

Chương 1

Đồ thị

Trạm, đường đi và bản đồ địa hình dạng dữ liệu để chương trình tìm kiếm.

  1. Mở288 XP

    Đồ thị dạng dữ liệu

    Bản đồ đường đi của xe thăm dò Sao Hỏa dạng một đồ thị: các trạm và đường đi trong một dict danh sách, bậc của đỉnh và trạm đông nhất, một bộ kiểm tra tìm ra đường một chiều, đếm cạnh, và một bản đồ địa hình biến thành đồ thị các ô.

    0/6 bước

4 câu hỏi, được chấm ngay khi bạn trả lời.
Chương 2

Tìm

Rộng trước và sâu trước: vòng lan tỏa, cách đi sâu, và công dụng của từng cách.

  1. Đã khóa288 XP

    Tìm kiếm theo chiều rộng (BFS)

    Tìm kiếm theo chiều rộng với deque: thứ tự nó thăm các trạm, khoảng cách tính theo số bước nhảy, cha để dựng lại đường đi, cùng một hàm chạy trên lưới của xe thăm dò, đường đi được vẽ lên bản đồ, và đèn đỏ khi một hòn đá vây kín đích.

    0/6 bước

  2. Dự ánĐã khóa576 XP

    Tìm kiếm theo chiều sâu (DFS)

    Tìm kiếm theo chiều sâu, dùng đệ quy và dùng ngăn xếp: thứ tự nó đi sâu, trạm nào bị bão bụi cắt đứt, vì sao đường đầu tiên nó tìm thấy trên bản đồ không phải đường ngắn nhất, và giới hạn đệ quy mà một cánh đồng lớn sẽ gặp phải.

    0/6 bước

4 câu hỏi, được chấm ngay khi bạn trả lời.
Chương 3

Chi phí và phỏng đoán

Đường rẻ nhất với Dijkstra, rồi A* với cảm giác hướng đi.

  1. Đã khóa250 XP

    Dijkstra

    Khi đường đi có chi phí, ít đường nhất không có nghĩa là nhanh nhất: thời gian lái làm trọng số cạnh, heapq làm hàng đợi ưu tiên, thuật toán Dijkstra trên các trạm rồi trên địa hình có cát mềm, và đếm số ô nó phải xem xét.

    0/5 bước

  2. Dự ánĐã khóa500 XP

    Tìm kiếm A*

    Dijkstra có thêm cảm giác hướng đi: một hàm heuristic, khoảng cách Manhattan, độ ưu tiên f = g + h, cùng một đường tốt nhất nhưng cần ít ô hơn hẳn, một đồng bằng rộng nơi mức tiết kiệm rất lớn, và cái giá phải trả khi heuristic quá tự tin.

    0/5 bước

5 câu hỏi, được chấm ngay khi bạn trả lời.
Chương 4

Mê cung và trùm cuối

Tạo và giải mê cung, rồi đưa Rover 7 chạy xuyên qua một mê cung.

  1. Đã khóa288 XP

    Mê cung

    Tạo mê cung bằng DFS ngẫu nhiên, chứng minh mê cung hoàn hảo bằng cách đếm lối đi, giải bằng BFS, vẽ lời giải, đếm ngõ cụt, và đổi seed để mỗi lần có một mê cung mới.

    0/6 bước

  2. Dự ánĐã khóa576 XP

    Trùm: robot giải mê cung

    Bảng điều khiển của Rover 7: một mê cung, A* lập kế hoạch theo lệnh, đèn báo trạng thái cho việc lập kế hoạch, đường đi và bị vây kín, lệnh lái kèm quay đầu, đá được nhập trực tiếp buộc phải lập kế hoạch lại, và một hành trình lái tới đích.

    0/6 bước

4 câu hỏi, được chấm ngay khi bạn trả lời.
Chứng chỉ

Chứng chỉ khi bạn hoàn thành

Hoàn thành mọi bài học và vượt qua mọi bài kiểm tra cuối chương, Mokxi sẽ cấp chứng chỉ ghi tên bạn, được xác minh trên trang riêng của nó.

Số chứng chỉ:MXC0-URSE-0001

Chứng chỉ Hoàn thành

Chứng nhận rằng

Tên Của Bạn

đã hoàn thành tốt khóa học

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

Bao gồm Đồ thị, Tìm kiếm, Chi phí và phỏng đoán, và Mê cung và trùm cuối.

7 bài học · khoảng 6 giờ học

DaneDane, Nhà sáng lập, MokxiCấp ngày 17 tháng 11, 2026
Xác minh chứng chỉ nàymokxi.com/cert/MXC0URSE0001
Chứng chỉ

Nhận chứng chỉ của bạn

  • Tên bạn và một mã số duy nhấtIn trên chứng chỉ khổ ngang thuộc về bạn.
  • Được Mokxi xác minhMã QR và trang công khai để ai cũng có thể kiểm tra.
  • Thêm vào LinkedInMột cú nhấp điền sẵn biểu mẫu chứng chỉ trên LinkedIn.
  • Tải về PDFIn ra hoặc đính kèm vào CV hay hồ sơ xin việc.

Hoàn thành khóa học để nhận chứng chỉ có thể xác minh, ghi tên bạn, kèm mã QR và liên kết cho LinkedIn. Chứng chỉ đi kèm gói Pro, và 7 ngày dùng thử miễn phí.

Nội dung khóa học

Mọi bài học trong khóa

Tất cả 7 bài học, theo thứ tự, kèm nội dung mỗi bài. Bất kỳ bài nào cũng mở ngay trong trình soạn code.

Chương 1

Đồ thị

  1. Đồ thị dạng dữ liệuBản đồ đường đi của xe thăm dò Sao Hỏa dạng một đồ thị: các trạm và đường đi trong một dict danh sách, bậc của đỉnh và trạm đông nhất, một bộ kiểm tra tìm ra đường một chiều, đếm cạnh, và một bản đồ địa hình biến thành đồ thị các ô.
Chương 2

Tìm

  1. Tìm kiếm theo chiều rộng (BFS)Tìm kiếm theo chiều rộng với deque: thứ tự nó thăm các trạm, khoảng cách tính theo số bước nhảy, cha để dựng lại đường đi, cùng một hàm chạy trên lưới của xe thăm dò, đường đi được vẽ lên bản đồ, và đèn đỏ khi một hòn đá vây kín đích.
  2. Tìm kiếm theo chiều sâu (DFS)Tìm kiếm theo chiều sâu, dùng đệ quy và dùng ngăn xếp: thứ tự nó đi sâu, trạm nào bị bão bụi cắt đứt, vì sao đường đầu tiên nó tìm thấy trên bản đồ không phải đường ngắn nhất, và giới hạn đệ quy mà một cánh đồng lớn sẽ gặp phải.
Chương 3

Chi phí và phỏng đoán

  1. DijkstraKhi đường đi có chi phí, ít đường nhất không có nghĩa là nhanh nhất: thời gian lái làm trọng số cạnh, heapq làm hàng đợi ưu tiên, thuật toán Dijkstra trên các trạm rồi trên địa hình có cát mềm, và đếm số ô nó phải xem xét.
  2. Tìm kiếm A*Dijkstra có thêm cảm giác hướng đi: một hàm heuristic, khoảng cách Manhattan, độ ưu tiên f = g + h, cùng một đường tốt nhất nhưng cần ít ô hơn hẳn, một đồng bằng rộng nơi mức tiết kiệm rất lớn, và cái giá phải trả khi heuristic quá tự tin.
Chương 4

Mê cung và trùm cuối

  1. Mê cungTạo mê cung bằng DFS ngẫu nhiên, chứng minh mê cung hoàn hảo bằng cách đếm lối đi, giải bằng BFS, vẽ lời giải, đếm ngõ cụt, và đổi seed để mỗi lần có một mê cung mới.
  2. Trùm: robot giải mê cungBảng điều khiển của Rover 7: một mê cung, A* lập kế hoạch theo lệnh, đèn báo trạng thái cho việc lập kế hoạch, đường đi và bị vây kín, lệnh lái kèm quay đầu, đá được nhập trực tiếp buộc phải lập kế hoạch lại, và một hành trình lái tới đích.
Bộ kit

Cùng lắp trên bàn thực hành của bạn

Mỗi bài học đều chạy trong trình mô phỏng, không cần mua gì. Khi bạn muốn làm thật, các bộ kit này có sẵn linh kiện.

Đã có kit rồi?

Tìm kit của bạn

Chọn bộ kit khởi đầu bạn đang có và chạy mọi bài học trong sách hướng dẫn với cùng linh kiện trên cùng các chân.

Xem tất cả các kit
Câu hỏi

Giới thiệu về Đồ thị và tìm đường

Đồ thị và tìm đường có miễn phí không?

Có. Cả 7 bài học của Đồ thị và tìm đường đều miễn phí và chạy ngay trong trình duyệt, không cần cài gì và không phải mua linh kiện nào trước khi bắt đầu.

Tôi có cần một Raspberry Pi 4 Model B thật không?

Không. Mỗi bài học chạy trên một Raspberry Pi 4 Model B được mô phỏng với các linh kiện trên khung vẽ, và trình mô phỏng kiểm tra từng bước khi bạn làm. Khi bạn muốn lắp thật, cách nối dây và code giống hệt sẽ chạy được trên bo mạch thật.

Đồ thị và tìm đường mất bao lâu?

Khoảng 6 giờ: 7 bài học trong 4 chương, mỗi bài gồm vài bước ngắn. Tiến độ của bạn được lưu lại, nên bạn có thể dừng ở bất kỳ bài học nào và tiếp tục từ chỗ đã dừng.

Mình sẽ làm được gì?

Mỗi chương kết thúc bằng một dự án tổng hợp: Tìm kiếm theo chiều sâu (DFS), Tìm kiếm A* và Trùm: robot giải mê cung.

Bắt đầu từ đâu?

Bắt đầu bằng "Đồ thị dạng dữ liệu", và mỗi bài học xây dựng trên bài trước đó. Mới học mạch điện tử? Cơ bản về điện tử học là khóa học bắt đầu từ con số không.