Trí tuệ nhân tạo

Trí tuệ nhân tạo
Trí tuệ nhân tạo

TRƯỜNG ĐẠI HỌC CÔNG NGHIỆP HÀ NỘI

KHOA CÔNG NGHỆ THÔNG TIN

===== o0o =====

BÀI TẬP LỚN MÔN: TRÍ TUỆ NHÂN TẠO

Đề tài: Ứng dụng thuật toán tìm kiếm vào bài toán rót

nước

Giáo viên hướng dẫn: Giảng viên. Lê Thị Thủy Lớp : IT6043. Nhóm: 7 Thành viên nhóm: Nguyễn Trung Đạt – 2021602947 Hoàng Kim Cường – 2021601915 Trần Ngọc Quang – 2021605058

Hà Nội – 8/2023.

LỜI MỞ ĐẦU

Để hoàn thành bản báo cáo này, chúng em đã nhận được rất nhiều sự hướng

dẫn từ phía các thầy các cô trong khoa. Sự giảng dạy chu đáo, tận tình và sự giúp đỡ

nhiệt tình từ các thầy các cô đã giúp chúng em hiểu ra nhiều vấn đề và hoàn thành

bản báo cáo này tốt nhất.

Chúng em tỏ lòng biết ơn sâu sắc với cô Lê Thị Thuỷ, người cô đã tận tình

hướng dẫn và giúp đỡ, chỉ bảo nhóm em trong suốt quá trình nghiên cứu đề tài và

hoàn thành báo cáo này..

Sau khoảng thời gian cô Lê Thị Thủy đưa ra đề tài, chúng em đã rất nỗ lực và

cố gắng trong việc tìm hiểu về đề tài. Các bạn trong nhóm cùng các cộng sự đã rất

chăm chỉ cũng như giúp đỡ lẫn nhau để cho ra một báo cáo hoàn hảo nhất đến thời

điểm hiện tại. Một lần nữa nhóm em xin cảm ơn giảng viên Lê Thị Thủy, các bạn

trong lớp và tập thể nhóm làm việc đã cùng nhau hoàn thành tốt được bản báo cáo

này.

Chúng em xin chân thành cảm ơn!

CHƯƠNG I : KHÔNG GIAN TRẠNG THÁI VÀ CÁC THUẬT

TOÁN TÌM KIẾM MÙ

1 Không gian trạng thái

Không gian trạng thái là tập hợp tất cả các trạng thái của bài toán ứng với một

cấu trúc biểu diễn nào đó. Một không gian trạng thái (state space) là 1 bộ [N, A, S,

GD] trong đó:

N (node) là các nút hay các trạng thái của đồ thị.

A (arc) là tập cung (hay các liên kết) giữa các nút.

S (solution) là một tập chứa các trạng thái đích của bài toán ( S c N ^ S !0)

Các trạng thái trong GD (Goal Description) được mô tả theo một trong hai đặc

tính:

  • Đặc tính có thể đo lường được các trạng thái gặp trong quá trình tìm kiếm.

VD: Tic-tac-toe, 8-puzzle,…

  • Đặc tính của đường đi hình thành trong quá trình tìm kiếm. VD: TSP

Đường đi của lời giải (solution path) là một con đường đi qua đồ thị này từ một

nút thuộc S đến một nút thuộc GD.

1 Các thuật toán tìm kiếm mù

1.2 Thuật toán tìm kiếm theo chiều sâu (Depth First Search)

a, Tư tưởng của chiến lược tìm kiếm theo chiều sâu

Từ đỉnh xuất phát duyệt một đỉnh kề. Các đỉnh của đồ thị được duyệt theo các nhánh đến nút lá. Nếu chưa tìm thấy đỉnh TG thì quay lui tới một đỉnh nào đó để sang nhánh khác.

Việc tìm kiếm kết thúc khi tìm thấy đỉnh TG hoặc đã hết các đỉnh. b, Thuật toán tìm kiếm theo chiều sâu.

Lưu trữ: Sử dụng hai danh sách DONG và MO trong đó:

DONG: Chứa các đỉnh đã xét, hoạt động theo kiểu FIFO (hàng đợi). MO: chứa các đỉnh đang xét , hoạt động theo kiểu LIFO (ngăn xếp).

  1. MO = Ø; MO = MO  {T0}

  2. while (MO != Ø)

{ n = get(MO) // lấy đỉnh đầu trong danh sach MO if (n==TG) // nếu n là trạng thái kết thúc return TRUE // tìm kiếm thành công, dừng DONG = DONG  {n} //đánh dấu n đã được xét for các đỉnh kề v của n if (v chưa đc xét) //v chưa ở trong DONG MO = MO  {v} //đưa v vào đầu DS MO father(v)=n// lưu lại vết đường đi từ n đến v } c, Ví dụ thuật toán theo chiều sâu Cho đồ thị như hình vẽ sau:

See also  2024 DeMarini Voodoo One BBCOR Baseball Bat: WBD2461010

A

B C

N

D

O

J

M P

X

G H

Y

L

U V I

R S

while (MO != Ø) { n = get(MO) // lấy đỉnh đầu trong danh sach MO if (n==TG) // nếu n là trạng thái kết thúc return TRUE // tìm kiếm thành công, dừng DONG = DONG ∪ {n} //đánh dấu n đã được xét for các đỉnh kề v của n if (v chưa đc xét) //v chưa ở trong DONG MO = MO ∪ {v} //đưa v vào cuối DS MO father(v)=n// lưu lại vết đường đi từ n đến v } Chúng ta có một số nhận xét sau đây về thuật toán tìm kiếm theo chiều rộng: Trong tìm kiếm theo chiều rộng, trạng thái nào được sinh ra trước sẽ được phát

triển trước, do đó danh sách MỞ được xử lý như hàng đợi. Trong bước 2, ta cần kiểm tra xem n có là trạng thái kết thúc hay không. Nói chung các trạng thái kết thúc được

xác định bởi một số điều kiện nào đó, khi đó ta cần kiểm tra xem n có thỏa mãn các điều kiện đó hay không.

Nếu bài toán có nghiệm (tồn tại đường đi từ trạng thái ban đầu tới trạng thái đích), thì thuật toán tìm kiếm theo chiều rộng sẽ tìm ra nghiệm, đồng thời đường đi

tìm được sẽ là ngắn nhất. Trong trường hợp bài toán vô nghiệm và không gian trạng thái hữu hạn, thuật toán sẽ dừng và cho thông báo vô nghiệm.

Đánh giá tìm kiếm theo chiều rộng: Bây giờ ta đánh giá thời gian và bộ nhớ mà tìm kiếm theo chiều rộng đòi hỏi.

Giả sử, mỗi trạng thái khi được phát triển sẽ sinh ra b trạng thái kề. Ta sẽ gọi b là nhân tố nhánh. Giả sử rằng, nghiệm của bài toán là đường đi có độ dài d. Bởi nhiều

nghiệm có thể được tìm ra tại một đỉnh bất kỳ ở mức d của cây tìm kiếm, do đó số đỉnh cần xem xét để tìm ra nghiệm là:

1 + b + b 2 +… + bd-1 + k Trong đó k có thể là 1, 2, …, bd. Do đó số lớn nhất các đỉnh cần xem xét là: 1 + b + b 2 +… + bd- . Như vậy, độ phức tạp thời gian của thuật toán tìm kiếm theo chiều rộng là

O(bd). Độ phức tạp không gian cũng là O(bd), bởi vì ta cần lưu vào danh sách MỞ tất cả các đỉnh của cây tìm kiếm ở mức d, số các đỉnh này là bd

C, Ví dụ thuật toán tìm kiếm theo chiều rộng: Cho đồ thị như hình vẽ sau:

Đỉnh đầu T 0 =A, TG= {N}.Tìm đường đi p từ To đến TG bằng phương pháp tìm kiếm theo chiều rộng?

n B(n) MO DONG

A

A B, C, D B, C, D A

B M, N C, D, M, N A,B

C L D, M, N, L A,B,C

D O, P M, N, L, O, P A,B,C,D

M X, Y N, L, O, P, X, Y

A,B,C,D,M

N là đích dừng

Xây dựng đường đi có hành trình: p = A -> B -> N. Nhận xét:

  • Nếu trong đồ thị tồn tại đường đi từ T0 đến 1 đỉnh TG -> Goal thì hàm BFS sẽ dừng lại và cho đường đi p có độ dài ngắn nhất.

A

B C

N

D

O

J

M P

X

G H

Y

L

U V I

R S

n ← getNew (OPEN) if (n = TG) then return path T 0 → TG else { for each m ∈ A(n) do if(m ≠ OPEN + CLOSE) then { tính h(m), g(m) f(m) = g(m) +h(m) cha(m) = n OPEN = OPEN ∪ {m}

See also  Top phim về trí tuệ nhân tạo đáng xem nhất

}

else {

g(m) = min{g(m), gnew(m)

CLOSE= CLOSE ∪ {n}

}

}

return False; }

C, Ví dụ thuật toán AT

Cho đồ thị (hình 3). Đỉnh xuất phát A và Goal = {D, H}

n A(n) OPEN CLOSE

A(0)

A B, C, E B(2),C(4), F(6) A

B C(4), F(6) A, B

C D, E D(12),E(6),F(6) A, B, C

E D(12), F(6) A, B, C, E

F G, H G(11),H(7),D(12) A, B, C, E, F

H →là đích → dừng

Hình : Duyệt đồ thị theo AT

Thuật giải AT kết thúc khi gặp HGoal và tìm được đường đi p=A->F->H có

chi phí C(p)=7.

Kết quả: Nếu trong đồ thị G tồn tại đường đi p: T0 → TG Goal thì thủ tục AT sẽ

dừng và cho kết quả đường đi có độ dài ngắn nhất.

Nhận xét:

  • Nếu C(a)=1  aE thì AT trở thành BFS

  • Nếu thay điều kiện g(n)->min bằng điều kiện d(n)->max, trong đó d(n) là độ

sâu hiện tại của n thì AT trở thành DFS.

1.3 Thuật giải AKT

a, Định nghĩa:

Với thuật giải AT trong quá trình TK chỉ xét đến các đỉnh và giá của chúng.

  • Việc tìm đỉnh triển vọng phụ thuộc vào hàm g(n) là thông tin quá khứ.

  • Giải thuật này không phù hợp với các bài toán có độ phức tạp hàm mũ (do

phải xét trên số lượng lớn các đỉnh).

while (MO! = ⊘){ n = getnew (MO) if (n==TG) return TRUE; else { for (m ∈ B(n)) { g(m)=g(n)+Cost(m,n); Tính h(m), f(m)=g(m)+h(m); MO=MO ∪ {m}; } } return FALSE; } C, Ví dụ thuật toán AKT

Chọn hàm f(n) = g(n) + h(n)

Trong đó: h(n) thông tin liên quan đến số đĩa ở cọc 3

g(n) là số lần chuyển đĩa từ T0 đến trạng thái n.

 Nếu cọc 3 chưa có đĩa nào thì h = 2

 Nếu cọc 3 có 1 đĩa nhỏ thì h = 3

 Nếu cọc 3 có 1 đĩa to thì h = 1

 Nếu cọc 3 có 2 đĩa và đĩa nhỏ ở trên đĩa to thì h = 0

1.3 Thuật giải A*

a, khái niệm

A* là một phiên bản đặc biệt của AKT áp dụng cho trường hợp đồ thị. Thuật

toán này tìm một đường đi từ một nút khởi đầu tới một nút đích cho trước (hoặc tới

một nút thỏa mãn một điều kiện đích). Thuật toán này sử dụng một "đánh giá

heuristic" để xếp loại từng nút theo ước lượng về tuyến đường tốt nhất đi qua nút đó.

Thuật toán này duyệt các nút theo thứ tự của đánh giá heuristic này.

Ý tưởng trực quan

Xét bài toán tìm đường – bài toán mà A* thường được dùng để giải. A* xây

dựng tăng dần tất cả các tuyến đường từ điểm xuất phát cho tới khi nó tìm thấy một

  • Danh sách TT kế tiếp của Ti: các TT Tk sao cho Cost(T0- >Tk) thông qua Ti

đạt min.

void Asao(){ MO = {T0}, DONG=, g(T0)=0, Tính h(T0), f(T0)=g(T0)+h(T0); while (MO!=){ n=getnew(MO)//lấy đỉnh n sao cho f(n) đạt min. if (n==TG) return TRUE; else{ for (mB(n)) { if (m(MODONG)){ Tính h(m), g(m), f(m)=g(m)+h(m); Cha(m)=n; MO=MO{m}; }else{ g(m) = min{gold(m),gnew(m)}; Cập nhật lại MO;

} } } DONG = DONG{n}; } return FALSE; } c, Các tính chất

Cũng như tìm kiếm theo chiều rộng (breadth-first search), A* là thuật toán đầy

đủ (complete) theo nghĩa rằng nó sẽ luôn luôn tìm thấy một lời giải nếu bài toán có

lời giải.

Nếu hàm heuristic h có tính chất thu nạp được (admissible), nghĩa là nó không

bao giờ đánh giá cao hơn chi phí nhỏ nhất thực sự của việc đi tới đích, thì bản thân

See also  Đề cương nhập môn trí tuệ nhân tạo

A* có tính chất thu nạp được (hay tối ưu) nếu sử dụng một tập đóng. Nếu không sử

dụng tập đóng thì hàm h phải có tính chất đơn điệu (hay nhất quán) thì A* mới có

tính chất tối ưu. Nghĩa là nó không bao giờ đánh giá chi phí đi từ một nút tới một nút

kề nó cao hơn chi phí thực. Phát biểu một cách hình thức, với mọi nút x,y trong

đó y là nút tiếp theo của x:

h(x) ≤ g(y) – g(x) + h(y)

A* còn có tính chất hiệu quả một cách tối ưu (optimally efficient) với mọi hàm

heuristic , có nghĩa là không có thuật toán nào cũng sử dụng hàm heuristic đó mà chỉ

phải mở rộng ít nút hơn A*, trừ khi có một số lời giải chưa đầy đủ mà tại đó dự đoán

chính xác chi phí của đường đi tối ưu.

d, Ví dụ

Trạng thái ban đầu T0 = A, trạng thái đoch Goal = {B}, các số ghi cạnh các

cung là độ dài đường đi, các số cạnh các đỉnh là giá trị của hàm h

Đồ thị áp dụng cho A*

Ban đầu OPEN = {A, g(A) = 0, f(A) = 14}

Phát triển đỉnh A sinh ra các đỉnh con C, D, E và F. Tính giá trị của hàm f tại

các đỉnh này ta có:

OPEN = {

g(C) = 9, f(C) = 9 + 15 = 24, cha(C) = A, g(D) = 7,

f(D) = 7 +6 = 13, cha(D) = A,

g(E) = 13, f(E) = 13 + 8 = 21, cha(E) = A, g(F) = 20,

g(I) = 19, f(I) = 19 + 4 = 23, cha(I) = E

}

CLOSE = {A, g(A) = 0, f(A) = 14,

D, g(D) = 7, f(D) = 7 + 6 = 13, cha(D) = A E, g(E) = 11, f(E) = 11 + 8 = 19,

cha(E) = D

}

Chọn đỉnh K để phát triển. Các đỉnh tiếp của K là B. OPEN = {g(C) = 9, f(C) =

9 + 15 = 24, cha(C) = A,

g(F) = 20, f(F) = 20 +7 = 27, cha(F) = A

g(H) = 15, f(H) = 15 + 10 = 25, cha(H) = D

g(I) = 19, f(I) = 19 + 2 = 23, cha(I) = E,

g(B) = 23, f(B) = 23 + 0 = 23, cha(B) = K,

} CLOSE= {

A, g(A) = 0, f(A) = 14, D, g(D) = 7, f(D) = 7 + 6 = 13, cha(D) = A, E, g(E) = 11, f(E) = 11 + 8 = 19, cha(E) = D,

g(K) = 17, f(K) = 17 + 2 = 19, cha(K) = E

}

Trong tập OPEN có f(B) = f(I) nên chọn ngẫu nhiên một trong hai đỉnh này.

Giả sử chọn đỉnh B để phát triển.

Do B ∈ Goal nên quá trình tìm kiếm kết thúc. Để đưa ra đường đi ta try ngược

lại trong tập CLOSE. Khi đó đường đi tìm được có chi phí c(p)= 23 và trình tự các

đỉnh.

Nhận xét:

p: A  D  E  K  B

Đường đi tìm được có thể không phải là tốt nhất.

Nếu h(n) = 0 trong mọi trường hợp thì A* trở thành AT.

Bảng so sánh 2 thuật toán DFS và DFS.

BFS DFS Thứ tự các đỉnh khi duyệt đồ thị

Các đỉnh được duyệt theo từng mức

Các đỉnh được duyệt theo từng nhánh Độ dài đường đi p từ T 0 đến TG

Ngắc nhất Có thể không ngắn nhất

Tính hiệu quả – Chiến lược có hiệu quả khi lời giải nằm ở mức thấp (gần gốc cây)

  • Thuận lợi khi tìm kiếm nhiều lời giải

  • Chiến lược có hiệu quả khi lời giải nằm gần hướng đi được chọn theo phương án

  • Thuận lợi khi tìm kiếm 1 lời giải Sử dụng bộ nhớ Lưu trữ toàn bộ KGTT Lưu trữ các TT đang xét Trường hợp tốt nhất Vét cạn toàn bộ Phương án chọn đường đi chính xác có lời giải trực tiếp Trường hợp xấu nhất Vét cạn Vét cạn

Comments are closed.
Ky Phu,Nho Quan,Ninh Binh, Viet Nam Country
+84.229 6333 111

BOOKING TEE TIME

[formidable id=8 title=true description=true]
Trang An Golf and Resort