Trang chủTrí tuệ nhân tạo

Trang chủ

Từ điển Tri thức

Tin tức

Bài viết chọn lọc

Chương trình đào tạo

Lập trình Arduino

Trí tuệ nhân tạo

Chuyên mục

STEAM

Câu chuyện cuộc sống

Công nghệ thông tin

Tiện ích

Đồng hồ bấm giờ

Tìm kiếm dữ liệu

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

Giải thuật tìm kiếm theo chiều rộng (Breadth First Search – viết tắt là BFS) duyệt qua một đồ thị theo chiều rộng và sử dụng hàng đợi (queue) để ghi nhớ đỉnh liền kề để bắt đầu việc tìm kiếm khi không gặp được đỉnh liền kề trong bất kỳ vòng lặp nào.

Mô tả thuật toán:

  1. Chèn đỉnh gốc vào hàng đợi (đang hướng tới).
  2. Lấy ra đỉnh đầu tiên trong hàng đợi và quan sát nó:
    • Nếu đỉnh này chính là đỉnh đích, dừng quá trình tìm kiếm và trả về kết quả.
    • Nếu không phải thì chèn tất cả các đỉnh kề với đỉnh vừa thăm nhưng chưa được quan sát trước đó vào hàng đợi.
  3. Nếu hàng đợi là rỗng, thì tất cả các đỉnh có thể đến được đều đã được quan sát – dừng việc tìm kiếm và trả về "không thấy".
  4. Nếu hàng đợi không rỗng thì quay về bước 2.

Để hiểu rõ hơn về thuật toán tìm kiếm theo chiều rộng, chúng ta sẽ xét bài toán Tháp Hà Nội.

Dạng thường gặp nhất của trò chơi này gồm một bộ các đĩa kích thước khác nhau, có lỗ ở giữa, nằm xuyên trên ba cái cọc. Bài toán đố bắt đầu bằng cách sắp xếp các đĩa theo trật tự kích thước vào một cọc sao cho đĩa nhỏ nhất nằm trên cùng, tức là tạo ra một dạng hình nón. Yêu cầu của trò chơi là di chuyển toàn bộ số đĩa sang một cọc khác, tuân theo các quy tắc sau:

  1. Chỉ có 3 cột để di chuyển.
  2. Một lần chỉ được di chuyển một đĩa (không được di chuyển đĩa nằm giữa).
  3. Một đĩa chỉ có thể được đặt lên một đĩa lớn hơn (không nhất thiết hai đĩa này phải có kích thước liền kề, tức là đĩa nhỏ nhất có thể nằm trên đĩa lớn nhất).

< Trí tuệ nhân tạo là gì?
Trí tuệ nhân tạo

Trí tuệ nhân tạo là gì?

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

Quảng cáo

Trang chủ | Giới thiệu về Xuân Tuyến Network