Giới thiệu

24 bài họcPythonXem thuật toán chạy từng bước

Trí tuệ nhân tạo

Học tư duy giải bài toán bằng AI: nhận diện bản chất bài toán, chọn phương pháp phù hợp, đánh giá lời giải. Thuật toán tìm kiếm chạy từng bước trên đồ thị, học máy đi kèm code Python minh họa.

Bắt đầu học →

bài học

phần

thuật toán chạy từng bước

Python

code minh họa

Phần này dạy trí tuệ nhân tạo theo tinh thần sách tương tác: lý thuyết ngắn gọn, thuật toán chạy từng bước, và code Python minh họa cho phần học máy. Mục tiêu không phải học thuộc công cụ, mà là tư duy giải bài toán bằng AI. Nội dung bám theo giáo trình Trí tuệ nhân tạo cho sinh viên năm ba ngành công nghệ thông tin, chia thành bốn phần.

Thử ngay: xem thuật toán tìm đường chạy từng bước

Trước khi vào bài, hãy thử một thuật toán thật. Bấm ▶ Chạy để xem tìm kiếm theo bề rộng lan từ nút S tới đích T, hàng đợi phồng lên co lại sau mỗi bước. Đây chính là kiểu công cụ tương tác bạn sẽ gặp ở toàn bộ phần tìm kiếm.

BFS trên đồ thị nhỏ: hàng đợi FIFO, lan theo tầng

1from collections import deque
2
3def bfs(do_thi, bat_dau, dich):
4    bien = deque([bat_dau])
5    da_tham = {bat_dau}
6    while bien:
7        nut = bien.popleft()
8        for ke in do_thi[nut]:
9            if ke not in da_tham:
10                if ke == dich:
11                    return "tim thay"
12                da_tham.add(ke)
13                bien.append(ke)
14    return None

Hàng đợi (FIFO)

Đã thăm (explored)

(rỗng)

Khởi tạo: đưa nút xuất phát S vào hàng đợi FIFO và ghi S vào tập da_tham để sau này không nạp lại. Hàng đợi là [S]. Ô "Đã thăm" bên dưới chỉ liệt kê các nút đã được lấy ra mở rộng, nên lúc này còn trống.

1/6

đang mở rộng trong biên đã thăm đường đi