Trang chủCông nghệ thông tinThuật toán

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

Bài toán tìm đường đi giữa các phòng với Thuật toán tìm kiếm theo chiều rộng và chiều sâu

Chúng ta có một robot vận chuyển hàng hóa và mong muốn robot này tự hoạt động mà không cần sự điều khiển của con người. Nhiệm vụ của robot sẽ chuyển hàng từ phòng này sang phòng khác. Vậy thì làm thế nào để robot xác định được lộ trình di chuyển của mình?! Chúng ta sẽ cùng tìm hiểu thuật toán tìm kiếm theo chiều rộng và ứng dụng thuật toán này để giải quyết bài toán đã được đặt ra.

Giả sử chúng ta có một nhà kho được bố trí như hình vẽ sau:


Hình 1: Sơ đồ nhà kho

Chúng ta cần tìm ra lộ trình của robot đi trong nhà kho trên.

I. Thuật toán tìm kiếm theo chiều rộng

Thuật toán tìm kiếm theo chiều rộng là một thuật toán duyệt hoặc tìm kiếm một phần tử trên một cấu trúc dữ liệu dạng cây hay một đồ thị, có chiến lược tìm kiếm mù (tìm kiếm không có định hướng). Nó sẽ ưu tiên theo chiều ngang, nghĩa là duyệt từ trái qua phải hết rồi mới duyệt tiếp xuống dưới cho từng phần tử.

Thuật toán sử dụng một cấu trúc dữ liệu hàng đợi để lưu trữ thông tin trung gian thu được trong quá trình tìm kiếm:

  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.

II. Thực hiện với Thuật toán tìm kiếm theo chiều rộng

Bây giờ thì chúng ta sẽ thực hiện việc xác định lộ trình di chuyển của robot bằng thuật toán tìm kiếm theo chiều rộng qua từng bước thực hiện cụ thể.

Giả sử robot đang ở phía ngoài nhà kho (0) và cần di chuyển đến phòng số (2). Chúng ta sẽ tạo ra một bảng theo dõi các số liệu như sau:

Bước 1: Phòng hiện tại của robot là (0). Và phòng trước đó của nó cũng chính là phòng (0). Và phòng hiện tại cũng chưa phải là phòng mà robot cần đến. Ta tiến hành cập nhật các dữ liệu trên vào bảng theo dõi.

Do robot chưa đến nơi, ta sẽ tìm kiếm xem từ phòng hiện tại thì robot sẽ có thể đi đến những phòng nào tiếp theo. Từ Hình 1, ta thấy rằng robot từ phòng (0) có thể đi đến phòng (1). Do phòng (1) chưa được xét (chưa có dữ liệu lưu trữ) nên ta sẽ tiến hành thêm dữ liệu vào một hàng mới trong bảng theo dõi và tiến hành khảo sát tiếp.

Bước 2: Do ta sử dụng giải thuật tìm kiếm theo chiều rộng nên ta sẽ chọn dữ liệu từ dòng tiếp theo để xét, đó chính là dòng 2, lúc này phòng hiện tại sẽ là phòng (1). Và phòng này cũng chưa là phòng mà robot cần đến.

Do robot chưa đến nơi, ta sẽ tìm kiếm xem từ phòng hiện tại thì robot sẽ có thể đi đến những phòng nào tiếp theo. Từ Hình 1, ta thấy rằng robot từ phòng (1) có thể đi đến phòng (0) và phòng (3). Do phòng (0) đã xét nên ta sẽ bỏ qua, còn phòng (3) chưa được xét nên ta sẽ tiến hành thêm dữ liệu vào một hàng mới trong bảng theo dõi và tiến hành khảo sát tiếp.

Bước 3: Ta xét dòng số 3, lúc này phòng hiện tại sẽ là phòng (3). Và phòng này cũng không phải là phòng mà robot cần đến.

Do robot chưa đến nơi, ta sẽ tìm kiếm xem từ phòng hiện tại thì robot sẽ có thể đi đến những phòng nào tiếp theo. Từ Hình 1, ta thấy rằng robot từ phòng (3) có thể đi đến phòng (1), (2) và phòng (4). Do phòng (1) đã xét nên ta sẽ bỏ qua, còn phòng (2) và (4) chưa được xét nên ta sẽ tiến hành thêm dữ liệu vào bảng theo dõi và tiến hành khảo sát tiếp.

Bước 4: Ta xét dòng số 4, lúc này phòng hiện tại sẽ là phòng (2). Và phòng này là phòng mà robot cần đến nên chương trình dừng.

Bước 5: Khi robot đã đến nơi, chúng ta căn cứ vào bảng theo dõi để xác định lộ trình đi.

  • Ta tạo ra một bảng lưu trữ đường đi. Và lúc này, bảng có giá trị là [2].
  • Tại dòng số 4, ta có được dữ liệu của phòng trước đó là (3), ta ghi giá trị này vào đầu của bảng lưu trữ đường đi, ta được [3, 2].
  • Ta tra trong bảng theo dõi, ta thấy phòng (3) được lưu ở dòng số 3, tại dòng này ta thu được giá trị phòng trước đó là (1), ta lưu giá trị này vào đầu của bảng lưu trữ đường đi, ta được [1, 3, 2].
  • Ta tra trong bảng theo dõi, ta thấy phòng (1) được lưu ở dòng số 2, tại dòng này ta thu được giá trị phòng trước đó là (0), ta lưu giá trị này vào đầu của bảng lưu trữ đường đi, ta được [0, 1, 3, 2].
  • Ta tra trong bảng theo dõi, thấy phòng (0) được lưu ở dòng số 1, như vậy đây là điểm xuất phát. Việc tìm kiếm đường đi chấm dứt.

Như vậy lộ trình di chuyển của robot sẽ là: 0 → 1 → 3 → 2.


Hình 2: Lộ trình của robot khi đi từ phòng (0) đến phòng (2) thực hiện bởi Thuật toán tìm kiếm theo chiều rộng


Hình 3: Đồ thị tìm kiếm của Thuật toán tìm kiếm theo chiều rộng

III. Chương trình thực hiện bằng ngôn ngữ lập trình Python với Thuật toán tìm kiếm theo chiều sâu

Chúng ta sử dụng ngôn ngữ lập trình Python để xây dựng một chương trình xác định lộ trình bất kỳ của robot:

IV. Thuật toán tìm kiếm theo chiều sâu

Thuật toán tìm kiếm theo chiều sâu cũng là một thuật toán duyệt hoặc tìm kiếm một phần tử trên một cấu trúc dữ liệu dạng cây hay một đồ thị, có chiến lược tìm kiếm mù (tìm kiếm không có định hướng). Thuật toán khởi đầu tại gốc (hoặc chọn một đỉnh nào đó coi như gốc) và phát triển xa nhất có thể theo mỗi nhánh. Quá trình tìm kiếm được phát triển tới đỉnh con đầu tiên của nút đang tìm kiếm cho tới khi gặp được đỉnh cần tìm hoặc tới một nút không có con. Khi đó giải thuật quay lui về đỉnh vừa mới tìm kiếm ở bước trước. Trong dạng không đệ quy, tất cả các đỉnh chờ được phát triển được bổ sung vào một ngăn xếp.

Ý tưởng của thuật toán:

  1. Tìm kiếm theo chiều sâu cũng giống như khám phá mê cung với một cuộn chỉ và một thùng sơn đỏ để đánh dấu, tránh bị lạc. Trong đó mỗi đỉnh s trong đồ thị tượng trưng cho một cửa trong mê cung.
  2. Ta bắt đầu từ đỉnh s, buộc đầu cuộn chỉ vào s và đánh đấu đỉnh này "đã thăm". Sau đó ta đánh dấu s là đỉnh hiện hành u.
  3. Bây giờ, nếu ta đi theo cạnh (u, v) bất kỳ.
  4. Nếu cạnh (u, v) dẫn chúng ta đến đỉnh "đã thăm" v, ta quay trở về u.
  5. Nếu đỉnh v là đỉnh mới, ta di chuyển đến v và lăn cuộn chỉ theo. Đánh dấu v là "đã thăm". Đặt v thành đỉnh hiện hành và lặp lại các bước.
  6. Cuối cùng, ta có thể đi đến một đỉnh mà tại đó tất cả các cạnh kề với nó đều dẫn chúng ta đến các đỉnh "đã thăm". Khi đó, ta sẽ quay lui bằng cách cuộn ngược cuộn chỉ và quay lại cho đến khi trở lại một đỉnh kề với một cạnh còn chưa được khám phá. Lại tiếp tục quy trình khám phá như trên.
  7. Khi chúng ta trở về s và không còn cạnh nào kề với nó chưa bị khám phá là lúc thuật toán dừng.

< Thuật toán Sắp xếp Nổi bọt với Ngôn ngữ lập trình Python Sử dụng webcam để phát hiện khuôn mặt với Python và thư viện OpenCV >
Các bài viết mới nhất cùng chuyên mục

Sử dụng webcam để phát hiện khuôn mặt với Python và thư viện OpenCV

Bài toán tìm đường đi giữa các phòng với Thuật toán tìm kiếm theo chiều rộng và chiều sâu

Thuật toán Sắp xếp Nổi bọt với Ngôn ngữ lập trình Python

Các bài viết cùng chuyên mục

Thuật toán Sắp xếp Nổi bọt với Ngôn ngữ lập trình Python

Quảng cáo

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