Bài toán 3 thầy tu và 3 con quỷ năm 2024

Biết rằng thuyền chỉ trở được tối đa 2 người [Cả thầy tu và quỷ]. Nếu số quỷ trên bờ nhiều hơn số thầy tu trên bờ, thầy tu đó sẽ bị ăn thịt.

Giờ thì bắt đầu nào! Game khá dễ nhưng vẫn rất mong nhận được những comment đáp án từ các bạn!

Bài 3: NGƯỜI LÁI THUYỀN THÔNG MINHTrên một dòng sông, có một người lái thuyền phải chở một con sói, một con dê và một chiếc bắp cải sang sông. Khó một nỗi là thuyền của bác nhỏ nên mỗi chuyến chỉ chở được một con sói, hoặc một con dê, hoặc một bắp cải. Nhưng nếu chó sói đứng cạnh dê thì chó sói sẽ ăn thịt dê, mà dê đứng cạnh bắp cải thì dê sẽ ăn bắp cải.Làm thế nào bay giờ? Bác lái thuyền suy nghĩ một lúc rồi bác reo lên: "Ta đã có cách." Và rồi bác đã hoàn thành công việc thật xuất sắc.

Trí tuệ nhân tạo Tên đề tài: Viết chương trình mô phỏng bài toán qua sông [có thể có giao diện đồ họa]: Tại bến sông nọ có 3 thầy tu và 3 con quỷ muốn qua sông. Biết rằng tại một thời điểm thuyền chỉ chở tối đa được 2 khách. Nếu bất cứ ở trên bờ nào, bên này hoặc bên kia thì số con quỷ phải bé hơn hoặc bằng số thầy tu, ngược lại quỷ sẽ ăn thịt thầy tu.

GIÁO VIÊN HƯỚNG DẪN: ĐOÀN THỊ THANH HẰNG

NHÓM SINH VIÊN THỰC HIỆN: NGÔ ANH TUẤN

ĐÀO HUY NHẬT MINH

PHẠM HỒNG VÂN

ĐỖ TUẤN HÙNG

LỚP: 71DCTT

HÀ NỘI 2-

1

* Nhiệm vụ phân công của thành viên:.............................................................

STT

Họ tên thành viên

Chức năng Ghi chú

1

Ngô Anh Tuấn

Xây dựng word + Tìm hiểu về thuật toán Best-first Search + code demo

Nhóm Trưởng

2

Đào Huy Nhật Minh

Tìm hiểu về thuật toán + Tổng quan về AI Thành viên

3

Phạm Hồng Vân

Tìm hiểu về thuật toán + Tổng quan về AI Thành viên

4

Đỗ Tuấn Hùng

Tìm hiểu về thuật toán + Tổng quan về AI Thành viên

Trưởng nhóm Ngô Anh Tuấn

MỤC LỤC............................................................................................................

MỤC LỤC

LỜI MỞ ĐẦU......................................................................................................

• NHẬN XÉT CỦA GIÁO VIÊN HƯỚNG DẪN............................................................
• * Nhiệm vụ phân công của thành viên:.............................................................
• MỤC LỤC............................................................................................................
• LỜI MỞ ĐẦU......................................................................................................
• MỤC TIÊU, PHƯƠNG PHÁP, NHIỆM VỤ VÀ Ý NGHĨA ĐỀ TÀI.............
• CHƯƠNG 1. TỔNG QUAN VỀ TRÍ TUỆ NHÂN TẠO..............................................
• 1. Trí tuệ nhân tạo hoạt động như thế nào?....................................................
• 1. Mục đích của AI?...........................................................................................
• CHƯƠNG 2. Demo bài toán và thuật toán qua sông..................................................
• KẾT LUẬN.................................................................................................................
• TÀI LIỆU THAM KHẢO...........................................................................................

MỤC TIÊU, PHƯƠNG PHÁP, NHIỆM VỤ VÀ Ý NGHĨA ĐỀ TÀI.............

Mục tiêu:

Phương pháp nghiên cứu:

• Tìm về phương thức hoạt động và ứng dụng về AI.

Nhiệm vụ của đề tài:

• Nghiên cứu về Trí tuệ nhân tạo bằng bài toán qua sông.
• Áp dụng thuật toán Best-fisrt Search để giải mã bài toán

Ý nghĩa của đề tài:

• Hiểu được thuật toán
• Ứng dụng của thuật toán vào đời sống

CHƯƠNG 1. TỔNG QUAN VỀ TRÍ TUỆ NHÂN TẠO..............................................

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

Trí tuệ nhân tạo hay trí thông minh nhân tạo [Artificial intelligence – viết

tắt là AI] là một ngành thuộc lĩnh vực khoa học máy tính [Computer science]. Là

trí tuệ do con người lập trình tạo nên với mục tiêu giúp máy tính có thể tự động

hóa các hành vi thông minh như con người.

Trí tuệ nhân tạo khác với việc lập trình logic trong các ngôn ngữ lập trình là

ở việc ứng dụng các hệ thống học máy [machine learning] để mô phỏng trí tuệ

của con người trong các xử lý mà con người làm tốt hơn máy tính.

AI được thực hiện bằng cách nghiên cứu cách suy nghĩ của con người, cách

con người học hỏi, quyết định và làm việc trong khi giải quyết một vấn đề nào

đó, và sử dụng những kết quả nghiên cứu này như một nền tảng để phát triển các

phần mềm và hệ thống thông minh, từ đó áp dụng vào các mục đích khác nhau

trong cuộc sống. Nói một cách dễ hiểu thì AI là việc sử dụng, phân tích các dữ

liệu đầu vào nhằm đưa ra sự dự đoán rồi đi đến quyết định cuối cùng.

Tuy rằng trí thông minh nhân tạo có nghĩa rộng như là trí thông minh trong

các tác phẩm khoa học viễn tưởng, nó là một trong những ngành trọng yếu

của tin học. Trí thông minh nhân tạo liên quan đến cách cư xử, sự học hỏi và khả

năng thích ứng thông minh của máy móc.

Loại 3: Lý thuyết trí tuệ nhân tạo Công nghệ AI này có thể học hỏi cũng như tự suy nghĩ, sau đó áp dụng

những gì học được để thực hiện một việc cụ thể. Hiện nay, công nghệ AI này

vẫn chưa trở thành một phương án khả thi.

Loại 4: Tự nhận thức

Công nghệ AI này có khả năng tự nhận thức về bản thân, có ý thức và hành

xử như con người. Thậm chí, chúng còn có thể bộc lộ cảm xúc cũng như hiểu

được những cảm xúc của con người. Đây được xem là bước phát triển cao nhất

của công nghệ AI và đến thời điểm hiện tại, công nghệ này vẫn chưa khả thi.

3. Trí tuệ nhân tạo hoạt động như thế nào?....................................................

Trên thực tế, AI được hoàn thiện bằng việc nghiên cứu cách mà não bộ của con người suy nghĩ, học hỏi, ra quyết định và làm việc. Các kỹ sư AI sẽ sử dụng thuật toán và các ngôn ngữ lập trình Trí tuệ nhân tạo để tạo ra các mô hình mẫu dựa trên lịch sử dữ liệu của người dùng.

Các mô hình mẫu này sau đó sẽ bắt đầu đưa ra dự đoán về các tr ạng thái trong tương lai như việc trò chuyện hay thực hiện các nhiệm vụ ngẫu nhiên. Bằng cách này, một chatbot được cung cấp các ví dụ về các cuộc trò chuyện văn bản có thể học và tạo ra các cuộc trao đổi sống động như thật. Đó là những cách sử dụng phổ biến và quen thuộc với hầu hết tất cả mọi người, ngoài ra AI còn có thể làm được nhiều hơn thế nữa.

lai, những chiếc xe có thể kết nối với nhau thông qua Wifi để đưa ra những lộ

trình vận tải tốt nhất.

Trong sản xuất Trí tuệ nhân tạo được ứng dụng để xây dựng những quy trình sản xuất tối

ưu hơn. Công nghệ AI có khả năng phân tích cao, làm cơ sở định hướng cho

việc ra quyết định trong sản xuất.

Trong y tế

Ứng dụng tiêu biểu của trí tuệ nhân tạo trong lĩnh vực y tế là máy bay thiết

bị bay không người lái được sử dụng trong những trường hợp cứu hộ khẩn cấ p.

Thiết bị bay không người lái có tốc độ nhanh hơn xe chuyên dụng đến 40% và

vô cùng thích hợp để sử dụng ở những nơi có địa hình hiểm trở.

Trong giáo dục

Sự ra đời của trí tuệ nhân tạo giúp tạo ra những thay đổi lớn trong lĩnh vực

giáo dục. Các hoạt động giáo dục như chấm điểm hay dạy kèm học sinh có thể

được tự động hóa nhờ công nghệ AI. Nhiều trò chơi, phần mềm giáo dục ra đời

đáp ứng nhu cầu cụ thể của từng học sinh, giúp học sinh cải thiện tình hình học

tập theo tốc độ riêng của mình.

Trí tuệ nhân tạo còn có thể chỉ ra những vấn đề mà các khóa học cần phải

cải thiện. Chẳng hạn như khi nhiều học sinh được phát hiện là gửi đáp án sai cho

bài tập, hệ thống sẽ thông báo cho giáo viên đồng thời gửi thông điệp đến học

sinh để chỉnh sửa đáp án phù hợp. Công nghệ AI còn có khả năng theo dõi sự

tiến bộ của học sinh và thông báo đến giáo viên khi phát hiện ra vấn đề đối với

kết quả học tập của học sinh.

CHƯƠNG 2. Demo bài toán và thuật toán qua sông..................................................

1. Bài toán: Viết chương trình mô phỏng bài toán qua sông [có thể có giao diện đồ họa]. Bài toán phát biểu như sau: Tại bến sông nọ có 3 thầy tu và 3 con quỷ muốn qua sông. Biết rằng tại một thời điểm thuyền chỉ chở tối đa được 2 khách. Nếu bất cứ ở trên bờ nào, bên này hoặc bên kia thì số con quỷ phải bé hơn hoặc bằng số thầy tu, ngược lại quỷ sẽ ăn thịt thầy tu. Hãy viết chương trình giải quyết bài toán trên.

2. Thuật toán Best-fisrt Search: [Greedy search]

Thuật toán tìm kiếm đầu tiên tốt nhất tham lam luôn chọn đường dẫn xuất hiện tốt nhất tại thời điểm đó. Nó là sự kết hợp của thuật toán tìm kiếm theo chiều sâu và tìm kiếm theo chiều rộng. Nó sử dụng hàm heuristic và tìm kiếm. Tìm kiếm ưu tiên nhất cho phép chúng tôi tận dụng lợi thế của cả hai thuật toán. Với sự trợ giúp của tìm kiếm ưu tiên nhất, ở mỗi bước, chúng ta có thể chọn nút hứa hẹn nhất. Trong thuật toán tìm kiếm đầu tiên tốt nhất, chúng tôi mở rộng nút gần nhất với nút mục tiêu và chi phí gần nhất được ước tính bằng hàm heuristic, tức là f [n] = g [n].

• Were, h [n] = chi phí ước tính từ nút n đến mục tiêu.
• Thuật toán đầu tiên tốt nhất được thực hiện bởi hàng đợi ưu tiên.
• Thuật toán tìm kiếm đầu tiên tốt nhất:  Bước 1: Đặt nút bắt đầu vào danh sách MỞ.  Bước 2: Nếu danh sách MỞ trống, Dừng và quay lại thất bại.  Bước 3: Xóa nút n khỏi danh sách MỞ có giá trị thấp nhất là h [n] và đặt nó vào danh sách ĐÃ ĐÓNG.  Bước 4: Mở rộng nút n và tạo ra các phần tử kế thừa của nút n.  Bước 5: Kiểm tra từng nút kế thừa của nút n và tìm xem có nút nào là nút mục tiêu hay không. Nếu bất kỳ nút kế thừa nào là nút mục tiêu, sau đó trả về thành công và kết thúc tìm kiếm, nếu không, hãy chuyển sang Bước 6.  Bước 6: Đối với mỗi nút kế nhiệm, thuật toán sẽ kiểm tra hàm đánh giá f [n], sau đó kiểm tra xem nút đã nằm trong danh sách MỞ hoặc ĐÓNG CỬA hay chưa. Nếu nút chưa có trong cả hai danh sách, hãy thêm nó vào danh sách MỞ.  Bước 7: Quay lại Bước 2. Thuận lợi:  Tìm kiếm đầu tiên tốt nhất có thể chuyển đổi giữa BFS và DFS bằng cách đạt được những lợi thế của cả hai thuật toán.  Thuật toán này hiệu quả hơn thuật toán BFS và DFS. Nhược điểm:

 Nó có thể hoạt động như một tìm kiếm theo chiều sâu không có hướng dẫn trong trường hợp xấu nhất.  Nó có thể bị mắc kẹt trong một vòng lặp như DFS.  Thuật toán này không tối ưu. Ví dụ: Tại mỗi lần lặp, mỗi nút được mở rộng bằng cách sử dụng hàm đánh giá f [n] = h [n], được cho trong bảng dưới đây.

Trong ví dụ tìm kiếm này, em đang sử dụng hai danh sách là danh sách “open and close”. Sau đây là các bước lặp để duyệt qua ví dụ trên:

• Ví dụ 3: Đồ thị ví dụ cách hoạt động Best First Search

Cho đồ thị như hình trên, nút gốc là A, duyệt và tìm đường đi tốt nhất đến B. Cây dưới đây mô tả các bước duyệt đồ thị:

Đầu tiên phát triển đỉnh A sinh ra các đỉnh kề là C, D và E. Trong ba đỉnh này, đỉnh D có giá trị hàm đánh giá nhỏ nhất, nó được chọn để phát triển và sinh ra F, I. Trong số các đỉnh chưa được phát triển C, E, F, I thì đỉnh E có giá trị đánh giá nhỏ nhất, nó được chọn để phát triển và sinh ra các đỉnh G, K. Trong số các

đỉnh chưa được phát triển thì G tốt nhất, phát triển G sinh ra B, H. Đến đây ta đã đạt tới trạng thái kết thúc. Trong thủ tục này, chúng ta sử dụng danh sách L để lưu các trạng thái chờ phát triển, danh sách được sắp theo thứ tự tăng dần của hàm đánh giá sao cho trạng thái có giá trị hàm đánh giá nhỏ nhất ở đầu danh sách.