Áp dụng thuật toán quay lui vét cạn giải quyết bài toán mã đi tuần (Code C++, C#)

Tìm hiểu cách giải bài toán Mã đi tuần kinh điển bằng thuật toán quay lui vét cạn. Báo cáo chi tiết kèm code minh họa C++ và C# Winform.

• Tác giả: Trần Đăng Quang
• Người hướng dẫn: Phạm Đức Hồng
• Trường học: Trường Đại học Điện lực
• Chuyên ngành: Nhập môn Trí tuệ nhân tạo
• Đề tài: Áp dụng thuật toán quay lui vét cạn giải quyết bài toán Mã đi tuần
• Loại tài liệu: Báo cáo chuyên đề học phần
• Năm xuất bản: 2020
• Địa điểm: Hà Nội

Tóm tắt

I. Giới Thiệu Về Bài Toán Mã Đi Tuần

Bài toán mã đi tuần là một trong những bài toán cổ điển và thú vị nhất trong lĩnh vực thuật toán quay lui vét cạn. Đây là bài toán mà trong đó quân mã được đặt trên một ô của bàn cờ trống và phải di chuyển theo quy tắc cờ vua để có thể đi qua mỗi ô trên bàn cờ đúng một lần duy nhất. Bài toán này không chỉ là một thách thức toán học thuần túy mà còn là ứng dụng thực tế trong lĩnh vực trí tuệ nhân tạo và tối ưu hóa thuật toán. Với sự phát triển của công nghệ máy tính, việc giải quyết bài toán mã đi tuần trở nên khả thi hơn bao giờ hết. Nhiều nhà toán học và lập trình viên đã dành thời gian nghiên cứu để tìm ra các phương pháp hiệu quả giải quyết bài toán này, đặc biệt là thông qua thuật toán quay lui.

1.1. Định Nghĩa Bài Toán Mã Đi Tuần

Mã đi tuần (Knight's Tour) là một dãy các nước đi của quân mã trên bàn cờ sao cho mã ghé thăm mỗi ô đúng một lần. Quân mã di chuyển theo quy tắc cờ vua: hai ô theo chiều ngang hoặc dọc và một ô vuông góc. Bài toán yêu cầu tìm một lộ trình hoàn chỉnh mà mã có thể đi qua toàn bộ bàn cờ. Trên bàn cờ 8x8 tiêu chuẩn, bài toán này có hàng triệu giải pháp khác nhau, tạo nên sự hấp dẫn đối với các nhà nghiên cứu.

1.2. Xuất Xứ Và Lịch Sử Bài Toán

Bài toán mã đi tuần có nguồn gốc từ thế kỷ 12, lần đầu tiên được ghi chép ở Ấn Độ cổ đại. Sau đó, nó trở thành bài toán nổi tiếng ở Châu Âu vào thế kỷ 18. Nhiều nhà toán học nổi tiếng như Euler đã nghiên cứu và đóng góp vào giải quyết bài toán này. Việc ứng dụng thuật toán quay lui để giải bài toán mã đi tuần đã mở ra một hướng đi mới trong khoa học máy tính hiện đại.

II. Thuật Toán Quay Lui Vét Cạn Là Gì

Thuật toán quay lui vét cạn (Backtracking Algorithm) là một kỹ thuật tìm kiếm toàn diện, xây dựng từng bước các giải pháp tiềm năng và quay lại khi phát hiện con đường không dẫn đến lời giải. Đây là phương pháp cơ bản nhưng cực kỳ hiệu quả trong trí tuệ nhân tạo và lập trình tổ hợp. Nguyên lý của quay lui là nếu một phương pháp không dẫn đến kết quả, thuật toán sẽ quay trở lại bước trước và thử các lựa chọn khác. Kỹ thuật này được ứng dụng rộng rãi trong việc giải các bài toán như bài toán n quân hậu, bài toán tô màu đồ thị, và đặc biệt là bài toán mã đi tuần.

2.1. Nguyên Lý Hoạt Động Của Quay Lui

Thuật toán quay lui hoạt động bằng cách xây dựng một cây tìm kiếm nơi mỗi nút đại diện cho một trạng thái. Từ mỗi nút, thuật toán thử tất cả các nước đi có thể từ vị trí hiện tại. Nếu một nước đi dẫn đến đường cul-de-sac (không thể tiếp tục), thuật toán sẽ quay lại nút cha và thử nước đi khác. Quá trình này lặp lại cho đến khi tìm được giải pháp hoàn chỉnh hoặc xác nhận không có giải pháp.

2.2. Ưu Điểm Và Hạn Chế

Ưu điểm của quay lui là đơn giản, dễ hiểu và đảm bảo tìm được giải pháp nếu nó tồn tại. Hạn chế chính là độ phức tạp tính toán cao, đặc biệt với các bài toán kích thước lớn. Với bàn cờ 8x8, bài toán mã đi tuần yêu cầu khám phá một không gian tìm kiếm khổng lồ, nhưng với các tối ưu hóa, nó vẫn có thể giải quyết trong thời gian hợp lý.

III. Thiết Kế Thuật Toán Giải Bài Toán Mã Đi Tuần

Để giải quyết bài toán mã đi tuần bằng thuật toán quay lui, chúng ta cần thiết kế một hệ thống thông minh nhằm khám phá tất cả các nước đi có thể từ mỗi vị trí. Đầu tiên, chúng ta tạo một ma trận bàn cờ để lưu trữ thứ tự các nước đi. Sau đó, chúng ta định nghĩa các nước đi hợp lệ của quân mã - tám hướng di chuyển tiêu chuẩn (2 ngang 1 dọc hoặc 1 ngang 2 dọc). Hàm đệ quy sẽ thử mỗi nước đi từ vị trí hiện tại, và nếu tất cả các ô được ghé thăm, chúng ta đã tìm được giải pháp hoàn chỉnh. Cơ chế quay lui đảm bảo rằng nếu một đường không dẫn đến lời giải, thuật toán sẽ quay trở lại và thử phương pháp khác.

3.1. Cấu Trúc Dữ Liệu Cần Thiết

Để cài đặt bài toán mã đi tuần, chúng ta cần một ma trận 2 chiều đại diện cho bàn cờ, nơi mỗi phần tử lưu trữ số thứ tự nước đi. Chúng ta cũng cần một mảng hướng chứa 8 cặp tọa độ biểu diễn các nước đi hợp lệ của quân mã. Cuối cùng, chúng ta cần biến đếm để theo dõi số lượng ô đã ghé thăm và hàm kiểm tra để xác minh một nước đi có hợp lệ không.

3.2. Hàm Đệ Quy Và Quay Lui

Hàm đệ quy chính nhận vị trí hiện tại và số nước đi hiện tại làm tham số. Hàm sẽ thử lần lượt tất cả 8 hướng từ vị trí hiện tại. Nếu một nước đi hợp lệ và ô chưa được ghé thăm, chúng ta đánh dấu ô đó và gọi đệ quy. Nếu đệ quy thành công, chúng ta trả về true. Nếu không, chúng ta quay lại bỏ dấu ô (backtracking) và thử hướng tiếp theo.

IV. Cài Đặt Và Kết Quả Thực Nghiệm

Bài toán mã đi tuần đã được cài đặt thành công bằng C++ và C# Winform, cho phép người dùng nhập kích thước bàn cờ và chọn vị trí bắt đầu của quân mã. Chương trình hiểnuống thị các nước đi của mã dưới dạng số thứ tự, giúp dễ dàng theo dõi lộ trình đầy đủ. Kết quả thử nghiệm cho thấy thuật toán hoạt động hiệu quả trên bàn cờ 8x8 tiêu chuẩn, tìm được giải pháp hoàn chỉnh trong thời gian chấp nhận được. Giao diện trực quan cho phép người dùng quan sát quá trình di chuyển của quân mã từng bước, từ đó hiểu rõ hơn cách thức hoạt động của thuật toán quay lui.

4.1. Cài Đặt Với C

Phiên bản C++ sử dụng một mảng 2 chiều để biểu diễn bàn cờ và hàm đệ quy để thực hiện quay lui. Chương trình nhập vào kích thước bàn cờ và tọa độ bắt đầu, sau đó in ra lời giải dưới dạng ma trận. Kết quả cho thấy thời gian chạy rất nhanh ngay cả với bàn cờ 8x8, chứng minh hiệu quả của thuật toán.

4.2. Giao Diện C Winform Và Kết Quả

Phiên bản C# Winform cung cấp giao diện đồ họa trực quan, cho phép nhập kích thước bàn cờ, chọn vị trí bắt đầu, và xem quá trình thực thi của thuật toán. Giao diện hiển thị từng nước đi của quân mã, giúp người dùng hiểu rõ cách thuật toán quay lui giải quyết bài toán một cách b体tắc và hiệu quả.

Trích đoạn nội dung tài liệu

CHƯƠNG 1: GIỚI THIỆU VỀ AI VÀ THUẬT TOÁN QUAY LUI VÉT CẠN 1. GIỚI THIỆU VỀ TRÍ TUỆ NHÂN TẠO 1. Trí tuệ nhân tạo là gì ? Để hiểu trí tuệ nhân tạo (artificial intelligence) là gì chúng ta bắt đầu với khái niệm sự bay nhân tạo (flying machines), tức là cái máy bay. Đã từ lâu, loài người mong muốn làm ra một cái máy mà có thể di chuyển được trên không trung mà không phụ thuộc vào địa hình ở dưới mặt đất, hay nói cách khác là máy có thể bay được.

Không có gì ngạc nhiên khi những ý tưởng đầu tiên làm máy bay là từ nghiên cứu cách con chim bay. Những chiếc máy biết bay được thiết kế theo nguyên lý “vỗ cánh” như con chim chỉ có thể bay được quãng đường rất ngắn và lịch sử hàng không thực sự sang một trang mới kể từ anh em nhà Wright thiết kế máy bay dựa trên các nguyên lý của khí động lực học (aerodynamics). Các máy bay hiện nay, như đã thấy, có sức trở rất lớn và bay được quãng đường có thể vòng quanh thế giới. Nó không nhất thiết phải có nguyên lý bay của con chim nhưng vẫn bay được như chim (dáng vẻ), và còn tốt hơn chim.

Quay lại câu hỏi Trí tuệ nhân tạo là gì. Trí tuệ nhân tạo là trí thông minh của máy do con người tạo ra. Ngay từ khi chiếc máy tính điện tử đầu tiên ra đời, các nhà khoa học máy tính đã hướng đến phát hiển hệ thống máy tính (gồm cả phần cứng và phần mềm) sao cho nó có khả năng thông minh như loài người. Mặc dù cho đến nay, theo quan niệm của người viết, ước mơ này vẫn còn xa mới thành hiện thực, tuy vậy những thành tựu đạt được cũng không hề nhỏ: chúng ta đã làm được các hệ thống (phần mềm chơi cờ vua chạy trên siêu máy tinh GeneBlue) có thể thắng được vua cờ thế giới; chúng ta đã làm được các phần mềm có thể chứng minh được các bài toán hình học; v.

Hay nói cách khác, trong một số lĩnh vực, máy tính có thể thực hiện tốt hơn hoặc tương đương con người (tất nhiên không phải tất cả các lĩnh vực). Đó chính là các hệ thống thông minh. Có nhiều cách tiếp cận để làm ra trí thông minh của máy (hay là trí tuệ nhân tạo), chẳng hạn là nghiên cứu cách bộ não người sản sinh ra trí thông minh của loài người nhưthế nào rồi ta bắt chước nguyên lý đó, nhưng cũng có những cách khác sử dụng nguyên lý hoàn toàn khác với cách sản sinh ra trí thông minh của loài người mà vẫn làm ra cái máy thông minh như hoặc hơn người; cũng giống như máy bay hiện nay bay tốt hơn con chim do nó có cơ chế bay không phải là giống như cơ chế bay của con chim. 8 Như vậy, trí tuệ nhân tạo ở đây là nói đến khả năng của máy khi thực hiện các công việc mà con người thường phải xử lý; và khi dáng vẻ ứng xử hoặc kết quả thực hiện của máy là tốt hơn hoặc tương đương với con người thì ta gọi đó là máy thông minh hay máy đó có trí thông minh.

Hay nói cách khác, đánh giá sự thông minh của máy không phải dựa trên nguyên lý nó thực hiện nhiệm vụ đó có giống cách con người thực hiện hay không mà dựa trên kết quả hoặc dáng vẻ ứng xử bên ngoài của nó có giống với kết quả hoặc dáng vẻ ứng xử của con người hay không. Các nhiệm vụ của con người thường xuyên phải thực hiện là: giải bài toán (tìm kiếm, chứng minh, lập luận), học, giao tiếp, thể hiện cảm xúc, thích nghi với môi trường xung quanh, v., và dựa trên kết quả thực hiện các nhiệm vụ đó để kết luận rằng một ai đó có là thông minh hay không. Môn học Trí tuệ nhân tạo nhằm cung cấp các phương pháp luận để làm ra hệ thống có khả năng thực hiện các nhiệm vụ đó: giải toán, học, giao tiếp, v. bất kể cách nó làm có như con người hay không mà là kết quả đạt được hoặc dáng vẻ bên ngoài như con người.

Trong môn học này, chúng ta sẽ tìm hiểu các phương pháp để làm cho máy tính biết cách giải bài toán, biết cách lập luận, biết cách học, v. Lịch sử Vào năm 1943, Warren McCulioch và Walter Pitts bắt đầu thực hiện nghiên cứu ba cơ sở lý thuyết cơ bản: triết học cơ bản và chức năng của các noron thần kinh; phân tích các mệnh đề logic; và lý thuyết dự đoán của Turing. Các tác giả đã nghiên cứu đề xuât mô hình noron nhân tạo, mỗi noron đặc trưng bởi hai trạng thái “bật”, “tắt” và phát hiện mạng noron có khả năng học. Thuật ngữ “Trí tuệ nhân tạo” (Artificial Intelligence - AI) được thiết lập bởi John McCarthy tại Hội thảo đầu tiên về chủ đề này vào mùa hè năm 1956.

Đồng thời, ông cũng đề xuất ngôn ngữ lập trình Lisp – một trong những ngôn ngữ lập trình hàm tiêu biểu, được sử dụng trong lĩnh vực AI. Sau đó, Alan Turing đưa ra "Turing test" như là một phương pháp kiểm chứng hành vi thông minh. Thập kỷ 60, 70 Joel Moses viết chương trình Macsyma - chương trình toán học sử dụng cơ sở tri thức đầu tiên thành công. Marvin Minsky và Seymour Papert đưa ra các chứng minh đầu tiên về giới hạn của các mạng nơ-ron đơn giản.

Ngôn ngữ lập trình logic Prolog ra đời và được phát triển bởi Alain Colmerauer. Ted Shortliffe xây dựng thành công một số hệ chuyên gia đầu tiên trợ giúp chẩn đoán trong y học, các hệ thống này sử dụng ngôn ngữ luật để biểu diễn tri thức và suy 9 diễn. Vào đầu những năm 1980, những nghiên cứu thành công liên quan đến AI như các hệ chuyên gia (expert systems) – một dạng của chương trình AI mô phỏng tri thức và các kỹ năng phân tích của một hoặc nhiều chuyên gia con người. Vào những năm 1990 và đầu thế kỷ 21, AI đã đạt được những thành tựu to lớn nhất, AI được áp dụng trong logic, khai phá dữ liệu, chẩn đoán y học và nhiều lĩnh vực ứng dụng khác trong công nghiệp.

Sự thành công dựa vào nhiều yếu tố: tăng khả năng tính toán của máy tính, tập trung giải quyết các bài toán con cụ thể, xây dựng các mối quan hệ giữa AI và các lĩnh vực khác giải quyết các bài toán tương tự, và một sự chuyển giao mới của các nhà nghiên cứu cho các phương pháp toán học vững chắc và chuẩn khoa học chính xác. Lĩnh vực của AI  Lập luận, suy diễn tự động: Khái niệm lập luận (reasoning), và suy diễn (reference) được sử dụng rất phổ biến trong lĩnh vực AI. Lập luận là suy diễn logic, dùng để chỉ một tiến trình rút ra kết luận (tri thức mới) từ những giả thiết đã cho (được biểu diễn dưới dạng cơ sở tri thức). Như vậy, để thực hiện lập luận người ta cần có các phương pháp lưu trữ cơ sở tri thức và các thủ tục lập luận trên cơ sở tri thức đó.

 Biểu diễn tri thức: Muốn máy tính có thể lưu trữ và xử lý tri thức thì cần có các phương pháp biểu diễn tri thức. Các phương pháp biểu diễn tri thức ở đây bao gồm các ngôn ngữ biểu diễn và các kỹ thuật xử lý tri thức. Một ngôn ngữ biểu diễn tri thức được đánh giá là “tốt” nếu nó có tính biểu đạt cao và các tính hiệu quả của thuật toán lập luận trên ngôn ngữ đó. Tính biểu đạt của ngôn ngữ thể hiện khả năng biểu diễn một phạm vi rộng lớn các thông tin trong một miền ứng dụng.

Tính hiệu quả của các thuật toán lập luận thể hiện chi phí về thời gian và không gian dành cho việc lập luận. Tuy nhiên, hai yếu tố này dường như đối nghịch nhau, tức là nếu ngôn ngữ có tínhbiểu đạt cao thì thuật toán lập luận trên đó sẽ có độ phức tạp lớn (tính hiệu quả thấp)và ngược lại (ngôn ngữ đơn giản, có tính biểu đạt thấp thì thuật toán lập luận trên đó sẽ có hiệu quả cao). Do đó, một thách thức lớn trong lĩnh vực AI là xây dựng các ngôn ngữ biểu diễn tri thức mà có thể cân bằng hai yếu tố này, tức là ngôn ngữ có tínhbiểu đạt đủ tốt (tùy theo từng ứng dụng) và có thể lập luận hiệu quả. 10  Lập kế hoạch: khả năng suy ra các mục đích cần đạt được đối với các nhiệm vụ đưa ra, và xác định dãy các hành động cần thực hiện để đạt được mục đích đó.

 Học máy: là một lĩnh vực nghiên cứu của AI đang được phát triển mạnh mẽ và có nhiều ứng dụng trong các lĩnh vực khác nhau như khai phá dữ liệu, khám phá tri thức,…  Xử lý ngôn ngữ tự nhiên: là một nhánh của AI, tập trung vào các ứng dụng trên ngôn ngữ của con người. Các ứng dụng trong nhận dạng tiếng nói, nhận dạng chữ viết, dịch tự động, tìm kiếm thông tin,…  Hệ chuyên gia: cung cấp các hệ thống có khả năng suy luận để đưa ra những kết luận. Các hệ chuyên gia có khả năng xử lý lượng thông tin lớn và cung cấp các kết luận dựa trên những thông tin đó. Có rất nhiều hệ chuyên gia nổi tiếng như các hệ chuyên gia y học MYCIN, đoán nhận cấu trúc phân tử từ công thức hóa học DENDRAL, …  Robotics  … 1.

GIỚI THIỆU VỀ KỸ THUẬT QUAY LUI Thuật toán quay lui vét cạn (Backtracking) là một kĩ thuật thiết kế giải thuật dựa trên đệ quy. Ý tưởng của quay lui là tìm lời giải từng bước, mỗi bước chọn một trong số các lựa chọn khả dĩ và đệ quy. Người đầu tiên đề ra thuật ngữ này (backtrack) là nhà toán học người Mỹ D. Lehmer vào những năm 1950.

Tư tưởng Nét đặc trưng của phương pháp quay lui là các bước hướng tới lời giải cuối cùng của bài toán đều được làm thử. Tại mỗi bước, nếu có một lựa chọn được chấp nhận thì ghi lại lựa chọn này và tiến hành các bước thử tiếp theo. 11 Còn ngược lại không có lựa chọn nào thích hợp thì làm lại bước trước, xóa bỏ sự ghi nhận và quay về chu trình thử các lựa chọn còn lại. Hành động trên được gọi là quay lui, thuật toán thể hiện phương pháp này gọi là quay lui.

Điểm quan trọng của thuật toán là phải ghi nhớ tại mỗi bước đi qua để tránh trùng lặp khi quay lui. Các thông tin này được lưu trữ trong một ngăn xếp, nên thuật toán thể hiện ý thiết kế một cách đệ quy. Heuristic Người ta thường sử dụng một số phương pháp heuristic để tăng tốc cho quá trình quay lui.