Mục Lục
Lời Mở Đầu............................................................................................................. 3
I.

Phân Tích Bài Tốn........................................................................................... 4

II.

Khái Niệm Không Gian Trạng Thái....................................................................5
1.

Đặt vấn đề.................................................................................................... 5

2.

Mô tả trạng thái............................................................................................ 5

3.

Tốn tử chuyển trạng thái............................................................................. 5

4.

Khơng gian trạng thái của bài tốn...............................................................6

5.

Biểu diễn khơng gian trạng thái dưới dạng đồ thị.........................................7

III. Thuật Toán Và Biểu Diễn Trạng Thái Của Bài Tốn............................................7
1.

Thuật Tốn Tìm Kiếm Mù Blind Search..........................................................7

2.

Mơ Tả Trạng Thái Của Bài Tốn.....................................................................9

IV.

Chương trình giải quyết bài tốn................................................................10


Lời Mở Đầu
“Trí tuệ nhân tạo (Artificial Intelligence – AI) là gì? Từ xa
xưa, lồi người ln mơ ước có những cỗ máy hỗ trợ con người
làm tất cả mọi thứ theo ý mình. Để được như vậy, những cổ
máy đó phải có được tri thức như tri thức của con người, từ
những điều đơn giản nhất, đến những điều phức tạp nhất. Cuối
thế kỷ 19, đầu thế kỷ 20, những nhà khoa học như Leonardo De
Vinci, Blaise Pascal, Albert Einstein, Isaac Newton, Galileo
Galilei, Alan Turing… đã bắt đầu nghiên cứu ra các phương
pháp, cách thức, cỗ máy… giúp loài người thực hiện giấc mơ đó.
Cho đến thời điểm hiện tại, những thành tựu nghiên cứu từ các
nhà khoa học trong các lĩnh vực như tốn học, khoa học máy
tính, vật lý, hóa học, sinh học, … đã được ứng dụng rất nhiều
trong xã hội loài người.
AI được ứng dụng trong rất nhiều hoạt động và lĩnh vực
khác nhau. Đối với hoạt động nghiên cứu cơ bản trong các lĩnh
vực toán học, vật lý lượng tử, sinh học di truyền, hóa học phân
tích, AI giúp giải phương trình vi phân, đạo hàm riêng, tính tốn

mơ phỏng q trình tương tác ở mức lượng tử, mô phỏng tái tạo
thành công lỗ hổng đen, tối ưu hóa Gen, xác định các marker
cho điều chỉnh Gen, thiết kế thuốc trên Gen, xác định cấu trúc
hóa học, đề xuất các kết hợp… Đối với hoạt động nghiên cứu
ứng dụng, với các thành tựu trong các lĩnh vực như xã hội, quân
sự, kinh tế, giao thông, y tế… AI đã hỗ trợ bác sỹ chẩn đốn
bệnh, phân tích hình ảnh y khoa, dự báo dịch bệnh, xem xét tác
động chính sách…


I.
Phân Tích Bài Tốn
1. Mục Đích bài Tốn.
Đề 6: Trị chơi đoán số
Cậu bé nghĩ ra 1 số (Gọi là S) gồm bỗn chữ số (không nhất
thiết khác nhau) trong sáu chữ số từu 1 đến 6. Để tìm số đó
máy lần lượt đưa ra các số dự đốn (gọi là M), mỗi số gồm 4 chữ
số không nhất thiết khác nhau. Với mỗi lần dự đoán, máy nhận
được 2 câu trả lời của cậ bé cho 2 câu hỏi sau.
+ Có bao nhiêu chữ số trong M là chữ số trong S nhưng vị trí
xuất hiện của mỗi chữ số đó là sai?
+ Có bao nhiêu chữ số trong M là chữ số trong S và đồng
thời vị trí xuất hiện của mỗi chữ số đều đúng?
Yêu cầu: Hãy hiện lên màn hình các số máy dự đốn và
nói mỗi số đó nhận 2 câu trả lời từ bàn phím của cậu bé cho đến
khi được số đúng như cậu bé nghĩ. (Số lần dự đốn khơng q 6
lần).
Ví dụ:
Cậu bé nghĩ ra 1 số (Gọi là S) gồm bỗn chữ số : 5436 (số
Máy cần tìm)

Hiện lên màn hình :
- Số máy dự đốn : 1234
- Máy Nhận được 2 câu trả lời:
Đúng số - Đúng vị trí : 1
Đúng số - Sai vị trí : 1
- Số máy dự đoán : 2156
- Máy Nhận được 2 câu trả lời:
Đúng số - Đúng vị trí : 1
Đúng số - Sai vị trí : 1
- Số máy dự đốn : 1416
- Máy Nhận được 2 câu trả lời:
Đúng số - Đúng vị trí : 2
Đúng số - Sai vị trí : 0
- Số máy dự đốn : 5436
- Máy Nhận được 2 câu trả lời:
Đúng số - Đúng vị trí : 4


Đúng số - Sai vị trí : 0
- Thơng báo máy chọn đúng số (Đúng số - Đúng vị trí : 4)
II. Khái Niệm Không Gian Trạng Thái
1. Đặt vấn đề
Khi giải quyết bài tốn bằng phương pháp tìm kiếm, trước
hết ta phải xác định khơng gian tìm kiếm bao gồm tất cả các
đối tượng trên đó thực hiện việc tìm kiếm.
Một phương pháp biểu diễn vấn đề phù hợp là sử dụng các
khái niệm trạng thái (state) và toán tử (operator).
Phương pháp giải quyết vấn đề dựa trên khái niệm trạng
thái và toán tử được gọi là cách tiếp cận giải quyết vấn đề nhờ
không gian trạng thái.

2. Mô tả trạng thái
Giải bài tốn trong khơng gian trạng thái, trước hết phải xác
định dạng mô tả trạng thái bài toán sao cho bài toán trở nên
đơn giản hơn, phù hợp bản chất vật lý của bài tốn (Có thể sử
dụng các xâu ký hiệu, véctơ, mảng hai chiều, cây, danh sách).
Mỗi trạng thái chính là mỗi hình trạng của bài tốn, các tình
trạng ban đầu và tình trạng cuối của bài toán gọi là trạng thái
đầu và trạng thái cuối.
3. Toán tử chuyển trạng thái.
Toán tử chuyển trạng thái thực chất là các phép biến đổi
đưa từ trạng thái này sang trạng thái khác. Có hai cách dùng để
biểu diễn các toán tử:
Biểu diễn như một hàm xác định trên tập các trạng
thái và nhận giá trị cũng trong tập này.
Biểu diễn dưới dạng các quy tắc sản xuất S? A có
nghĩa là nếu có trạng thái S thì có thể đưa đến trạng thái A.
Ví dụ . Bài toán đong nước
Các thao tác sử dụng để chuyển trạng thái này sang trạng
thái khác gồm:


Đổ đầy một bình, đổ hết nước trong một bình ra ngồi, đổ
nước từ bình này sang bình khác. Như vậy, nếu trạng thái đang
xét là (x,y) thì các trạng thái kế tiếp có thể chuyển đến sẽ là:
(m,y)
(x,n)
(0,y)
(x,0)
(x,y)
(0, x+ y) nếu x+y < = n

(x+y -n,n) nếu x+y > n
(x+ y,0) nếu x+y < = m
(m, x+y-m) nếu x+y > m
4. Khơng gian trạng thái của bài tốn.
Khơng gian trạng thái là tập tất cả các trạng thái có thể có
và tập các tốn tử của bài tốn.
Khơng gian trạng thái là một bộ bốn, Ký hiệu: K= (T, S, G,
F). Trong đó,
T: tập tất cả các trạng thái có thể có của bài tốn
S: trạng thái đầu
G: tập các trạng thái đích
F: tập các tốn tử
Ví dụ 1. Khơng gian trạng thái của bài tốn đong nước là bộ
bốn T, S, G, F xác đinh như sau:
T = { (x,y) / 0 <= x <= m; 0 <= y <= n }
S = (0,0)
G = { (x,k) hoặc (k,y) / 0 <= x <= m; 0 <=
y <= n}
F = Tập các thao tác đong đầy, đổ ra hoặc
đổ sang bình khác thực hiện trên một bình.
5. Biểu diễn không gian trạng thái dưới dạng đồ thị
Các khái niệm
Đồ thị G = (V,E) trong đó V:tập đỉnh, E: tập cung (EV*V)
Chú ý
G là đồ thị vơ hướng thì (i, j) là một cạnh cũng như là
(j, i) (tức là:(i, j)I E thì (j,i)I E)


-


Nếu G là đồ thị có hướng thì cung (i, j) hồn tồn

khác với cung (j, i).
III. Thuật Tốn Và Biểu Diễn Trạng Thái Của Bài Tốn
1. Thuật Tốn Tìm Kiếm Mù Blind Search
Khái niêm: Một tìm kiếm mù (hay cịn gọi là tìm kiếm khơng
hiểu rõ ) là một tìm kiếm mà khơng có thơng tin về phạm vi của
nó. Điều duy nhất mà tìm kiếm mù có thể làm là phân biệt
trạng thái không mục tiêu với trạng thái mục tiêu.
Hãy xem xét bản đồ đơn giản sau của Romania
Giả sử bạn hiện đang ở Arad và chúng tôi muốn đến

Bucharest. Nếu chúng ta tạo ra một cây tìm kiếm, cấp 1 sẽ có
ba trạng thái; Zerind, Sibiu và Timisoara. Một tìm kiếm mù sẽ
khơng có ưu tiên về việc nó sẽ khám phá nút nào trước (sau này
chúng ta sẽ thấy rằng chúng ta có thể phát triển các chiến lược
tìm kiếm kết hợp một số thơng tin tình báo).
Bạn có thể thắc mắc tại sao chúng ta nên sử dụng tìm kiếm
mù, khi chúng ta có thể sử dụng tìm kiếm với một số trí thơng
minh được tích hợp sẵn. Câu trả lời đơn giản là có thể khơng có


bất kỳ thơng tin nào mà chúng tơi có thể sử dụng. Chúng tơi có
thể chỉ đang tìm kiếm một câu trả lời và sẽ không biết rằng
chúng tôi đã tìm thấy nó cho đến khi chúng tơi nhìn thấy nó.
Nhưng cũng rất hữu ích khi nghiên cứu những tìm kiếm
khơng được thơng tin này vì chúng tạo cơ sở cho một số tìm
kiếm thơng minh mà chúng ta sẽ xem xét sau này.
Các tìm kiếm mù mà chúng ta sắp xem xét chỉ khác nhau
về thứ tự mà chúng ta mở rộng các nút, nhưng như chúng ta sẽ

thấy, điều này có thể có tác động đáng kể đến việc tìm kiếm
hoạt động tốt như thế nào.
2. Mơ Tả Trạng Thái Của Bài Tốn
Mỗi trạng thái chính là mỗi hình trạng của bài tốn, các tình
trạng ban đầu và tình trạng cuối của bài tốn gọi là trạng thái
đầu và trạng thái cuối.
Ví dụ 1: (Trị chơi đốn số - Bulls and Cows)
- Gọi x là số chữ số trong M là chữ số trong S và đồng thời vị
trí xuất hiện của mỗi chữ số đều đúng.
- Gọi y là số số trong M là chữ số trong S nhưng vị trí xuất
hiện của mỗi chữ số đó là sai.
Như vậy bộ có thứ tự (x | y) có thể xem là trạng thái của bài
tốn. Với cách mô tả như vậy, các trạng thái đặc biệt của bài
tốn sẽ là:
* Xét trường hợp: Các số khơng trùng nhau
+ T là tập các đỉnh như hình dưới
+ S Trạng thái ban đầu là (x | y) với x + y ≥ 2 và (x | y) ≠ (3
| 1)
+ G Trạng thái cuối là (4 | 0)
+ F: Random
abcd
1 2 3 4 5 6 ≠ (0,0) (1,0) (0,1) (3,1)
mnpq
1364


IV.

Chương trình giải quyết bài tốn


package btlon;

import java.util.HashSet;
import java.util.Iterator;
import java.util.Scanner;
import java.util.Set;

public class BanC {
public static void main(String[] args) {
Set<String> possibleNums = generatePossibleNums();
int steps = 0;
System.out.println("Bulls and cows là một trò chơi giải mã trong đó
bạn nghĩ đến số có 4 chữ số và người khác cố gắng đốn nó");
System.out.println("Bulls: Số đúng và đúng vị trí \nCows: Số đúng
nhưng sai vị trí \n");


System.out.println("=================================
================================\n");
System.out.println("Xin chào! Tơi là máy tính!\nBây giờ tơi sẽ nghĩ 1
con số...");
Scanner reader = new Scanner(System.in);
while (true) {
steps++;
Iterator<String> iter = possibleNums.iterator();
String AIguess = iter.next();
System.out.println("---***---");
System.out.println("Số tơi đốn là: " + AIguess);
System.out.print("Số số đúng và đúng vị trí(Bulls): ");
int numberOfBulls = reader.nextInt();

System.out.print("Số số đúng nhưng sai vị trí(Cows): ");
int numberOfCows = reader.nextInt();
removeWrongNums(new BcCount(numberOfBulls, numberOfCows),
AIguess, possibleNums);
if (numberOfBulls == 4) {
System.out.println("Tơi đã đốn với " + steps + " lần đoán");
break;
}
}
reader.close();
}

public static BcCount calcBullandCowCount(String guess, String
candidate) {
BcCount bcCount = new BcCount(0, 0);
for (int i = 0; i < candidate.length(); i++) {
if (guess.charAt(i) == candidate.charAt(i)) {
bcCount.bullCount++;


} else if (guess.contains(String.valueOf(candidate.charAt(i)))) {
bcCount.cowCount++;
}
}
return bcCount;
}

public static Set<String> generatePossibleNums() {
Set<String> set = new HashSet<String>();
for (int i = 1023; i <= 9876; i++) {

set.add(String.valueOf(i));
}
Iterator<String> iter = set.iterator();
while (iter.hasNext()) {
String str = iter.next();
Set<Character> digits = new HashSet<>();
for (char c : str.toCharArray()) {
if (digits.contains(c)) {
iter.remove();
break;
}
digits.add(c);
}
}
return set;
}

public static void removeWrongNums(BcCount guessBcCount, String
guess,
Set<String> possibleNums) {
Iterator<String> iter = possibleNums.iterator();


while (iter.hasNext()) {
String str = iter.next();
if (calcBullandCowCount(guess, str).equals(guessBcCount) ==
false) {
iter.remove();
}
}

}

}

Tổng kết
Thuật tốn Tìm kiếm mù được vận dụng để giải quyết bài toán
hệ thống dây điện đã cho thấy trong thực tế các thuật toán rất
cấp thiết và quan trọng trong hiện tại và tương lai. Sử dụng các
thuật toán để xử lý các vấn đề cách tối ưu nhất. Qua bài toán về
hệ thống dây điện này đã cho chúng em hiểu rất nhiều về mơn
học trí tuệ nhân tạo và vận dụng vào cuộc sống hàng ngày để
sử lý một vấn đề nào đó. Và đặc biệt là chúng em được tiếp thu
mọi kiến thức được truyền đạt từ cơ Đồn Thị Thanh Hằng rất
hay và bổ ích. Chúng em đã biết được cách tự lập thu thập
nhiều thơng tin bổ ích từ nhiều nguồn để hồn thành bài tập lớn
này. Từ đó học được nhiều bài học ý nghĩa.