Trang chủ / Trí Tuệ Nhân Tạo

Nhập môn trí tuệ nhân tạo - 27




C(7),


F(C) =A

F(K) =A

K(4)

F(3)

F(3)

F(3), D(6), C(7)

F(F) =K

F(3)

B(0), H(4)

B(0), H(4)

B(0), H(4) D(6),

C(7)

F(B) =F

F(H) =F

B(0) t





Kết luận: tìm kiếm thành công

Đường đi B FKA

Có thể bạn quan tâm!

Xem toàn bộ 272 trang tài liệu này.

Nhập môn trí tuệ nhân tạo - 27

2. Sử dụng thuật toán Sâu lặp để tìm đường đi từ đỉnh uo=A đến đỉnh B với độ sâu d=1 theo thứ tự tăng dần của trọng số các đỉnh.

Khởi tạo:

uo=A, T={B} d=1


u

Kề u

L

Father (F)



A(12, 0)


A(12, 0)

K(4, 1), D(6, 1), C(7, 1)

C(7, 1), D(6, 1),

K(4, 1)

F(K) =A

F(D) =A

F(C) =A

C(7, 1)

G(6, 2)

G(6, 2), D(6, 1), K(4, 1)

F(G) =C

G(6, 2) loại


D(6, 1), K(4, 1)


D(6, 1)

E(4, 2), G(6, 2)

G(6, 2), E(4, 2), K(4, 1)

F(E) =D

F(G) =D

G(6, 2) E(4,

2) loại


K(4, 1)


K(4, 1)

F(3, 2)

F(3, 2)


F(3, 2) loại



Kết luận: tìm kiếm thất bại


Bài 2.13.

1. Sử dụng thuật toán tốt nhất-đầu tiên để tìm đường đi từ đỉnh uo=A đến đỉnh G. Khởi tạo:

uo=A, T={G}


u

Kề u

L

Father (F)



A(12)



A(12)

B(8), C(3), K(5)

C(3), K(5), B(8)

F(B) =A

F(C) =A

F(K) =A

C(3)

D(4), E(7)

D(4), K(5), E(7), B(8)

F(D) =C

F(E) =C

D(4)

G(0)

G(0), K(5), E(7), B(8)

F(G) =D

G(0) T

dừng



Kết luận: tìm kiếm thành công

Đường đi G DCA

2. Sử dụng thuật toán sâu lặp để tìm đường đi từ đỉnh uo=A đến đỉnh G với độ sâu d=1. Khởi tạo:

uo=A, T={G}


u

Kề u

L

Father (F)



A(12, 0)


A(12, 0)

B(8, 1), C(3, 1), K(5, 1)

B(8, 1), K(5, 1), C(3, 1)

F(B) =A

F(C) =A

F(K) =A

B(8, 1)

D(4, 2), C(3, 2), E(7, 2)

E(7, 2), D(4, 2), C(3, 2),

K(5, 1), C(3, 1)

F(D) =B

F(C) =B

F(E) =B

E(7, 2), D(4,

2),

C(3, 2)

loại

K(5, 1), C(3, 1)


K(5, 1)

C(3, 2), H(4, 2)

H(4, 2), C(3, 2), C(3, 1)


H(4, 2), C(3,

2)

loại

C(3, 1)


C(3, 1)

D(4, 2), E(7, 2)

E(7, 2), D(4, 2)


E(7, 2), D(4,

2)

loại


Kết luận: tìm kiếm thất bại


uo=A, T={B}

Bài 2.14.


Khởi tạo:

Kề u

L

Father (F)



A(0, 15)


A(0, 15)

C(2, 10), G(8, 13),

D(3, 9), E(9, 14)

D(3, 9), C(2, 10), G(8, 13),

E(9, 14)

F(D) =A

F(C) =A

F(G) =A

F(E) =A

D(3, 9)

G(6, 11), H(16, 20),

E(8, 13)

C(2, 10), G(6, 11), E(8, 13),

H(16, 20)

F(G) =D

F(E) =D

F(H) =D

C(2, 10)

G(9, 14) loại

G(6, 11), E(8, 13), H(16, 20)


G(6, 11)

H(17, 21) loại

K(10, 14)

E(8, 13), K(10, 14), H(16,

20)

F(K) =G

E(8, 13)

H(12, 16), F(24, 29)

K(10, 14), H(12, 16), F(24,

29)

F(H) =E

F(F) =E

K(10, 14)

B(22, 22)

H(12, 16), B(22, 22), F(24,

29)


H(12, 16)

B(18, 18)

B(18, 18), F(24, 29)

F(B) =H

B(18, 18)

T

dừng



Kết luận: đường đi ngắn nhất là 18, BHEDA

u


Bài 2.15.

Khởi tạo: cost=+ uo=A, T={F}

u

Kề u

L1

L

Father (F)

A(0, 17)



A(0, 17)


A(0, 17)

C(2, 10), G(6,

11),

K(9, 13)

C(2, 10), G(6,

11),

K(9, 13)

C(2, 10), G(6,

11),

K(9, 13)

F(C) =A

F(G) =A

F(K) =A

C(2, 10)

D(5, 11)

D(5, 11)

D(5, 11),

F(D) =C


G(9, 14) loại


G(6, 11),





K(9, 13)


D(5, 11)

E(15, 20),

H(8, 12),

H(8, 12),

F(H) =D

H(8, 12)

E(15, 20)

E(15, 20),

G(6, 11),

K(9, 13)

F(E) =D

H(8, 12)

B(10, 16)

B(10, 16)

B(10, 16),

F(B) =H


F(20, 20)

F(20, 20)

F(20, 20),

F(F) =H




E(15, 20),





G(6, 11),





K(9, 13)


B(10, 16)

F(18, 18)

F(18, 18)

F(18, 18),

F(F) =B




E(15, 20),





G(6, 11),





K(9, 13)


F(18, 18)

cost>18


E(15, 20),


T

cost=18

G(6, 11),



K(9, 13)

E(15, 20)

loại


G(6, 11),

K(9, 13)


G(6, 11)

D(9, 15) loại

H(17, 21) loại

K(10, 14) loại


K(9, 13)


K(9, 13)

H(18, 22) loại

B(21, 27) loại



Kết luận: đường đi ngắn nhất là 18, FBHDCA


Bài 2.16.

Khởi tạo: cost=+ uo=A, T={B}

u

Kề u

L1

L

Father (F)

A(0, 12)



A(0, 12)


A(0, 12)

C(2, 10), D(3,

D(3, 9),

D(3, 9),

F(C) =A


9),

E(4, 9), C(2,

E(4, 9), C(2,

F(D) =A


E(4, 9)

10)

10)

F(E) =A

G(6, 11), E(8,

13)

G(6, 11), E(8,

13)

G(6, 11), E(4,

9), C(2, 10)

F(G) =D

G(6, 11)

K(10, 14),

H(17, 21)

K(10, 14),

H(17, 21)

K(10, 14),

H(17, 21), E(4,

9), C(2, 10)

F(K) =G

F(H) =G

K(10, 14)

H(19, 23),

B(22, 22)

B(22, 22),

H(19, 23)

B(22, 22),

H(17, 21), E(4,

9), C(2, 10)

F(B) =K

B(22, 22)

T

cost>22

cost=22


H(17, 21), E(4,

9), C(2, 10)


H(17, 21)

B(23, 23) loại

do 23>cost


E(4, 9), C(2,

10)


E(4, 9)

H(8, 12), F(20,

25) loại

H(8, 12)

H(8, 12), C(2,

10)

F(H) =E

H(8, 12)

B(14, 14)

B(14, 14)

B(14, 14), C(2,

10)

F(B) =H

B(14, 14)

T

cost>14

cost=14


C(2, 10)


C(2, 10)

G(5, 10)

G(5, 10)

G(5, 10)

F(G) =C

G(5, 10)

K(9, 13),

H(16, 20) loại

K(9, 13)

K(9, 13)


K(9, 13)

H(18, 22) loại

B(21, 21) loại




L=

Kết thúc





Kết luận: đường đi ngắn nhất là 14, BHEA

D(3, 9)


Bài 2.17.

Khởi tạo: uo=A, T={B}

u

Kề u

L

Father (F)



A(0, 12)


A(0, 12)

C(7, 15), D(3, 9)

D(3, 9), C(7, 15)

F(D) =A

F(C) =A

G(6, 11), E(8, 13)

G(6, 11), E(8, 13), C(7,

15)

F(G) =D

F(E) =D

G(6, 11)

K(10, 15), H(17, 21)

E(8, 13), C(7, 15),

K(10, 15), H(17, 21)

F(K) =G

F(H) =G

E(8, 13)

H(15, 19), F(16, 21)

C(7, 15),

K(10, 15),

H(15, 19), F(16, 21)

F(H) =E

F(F) =E

C(7, 15)

G(13, 18)

K(10, 15),

G(13, 18),

H(15, 19), F(16, 21)

F(G) =C

K(10, 15)

B(18, 18)

B(18, 18),

G(13, 18),

H(15, 19), F(16, 21)

F(B) =K

B(18, 18)

T

dừng



Kết luận: đường đi ngắn nhất là 18, BKGDA

D(3, 9)


Bài 2.18.

Khởi tạo cost=+ uo=A, T={B}

u

Kề u

L1

L

Father (F)




A(0, 12)


A(0, 12)

C(5, 13),

D(2, 8)

D(2, 8),

C(5, 13)

D(2, 8),

C(5, 13)

F(D) =A

F(C) =A

D(2, 8)

G(5, 10),

E(4, 9),

E(4, 9),

F(E) =D


E(4, 9)

G(5, 10)

G(5, 10), C(5, 13)

F(G) =D

E(4, 9)

H(11, 14),

F(10, 14),

F(10, 14),

F(F) =E


F(10, 14)

H(11, 14)

H(11, 14), G(5, 10),

F(H) =E


A(8, 20) loại


C(5, 13).


F(10, 14)

B(17, 17)


B(17, 17),

F(B) =F


H(13, 16) loại

H(11, 14), G(5, 10),




C(5, 13)


B(17, 17)

cost>17


H(11, 14), G(5, 10),


cost=17


C(5, 13)


H(11, 14)

B(25, 25) loại


G(5, 10), C(5, 13)


G(5, 10)

H(16, 19) loại


C(5, 13)


C(5, 13)

G(9, 14) loại


dừng


Kết luận: đường đi ngắn nhất là 17, BFEDA

T


Bài 2.19.

Khởi tạo: uo=A, T={B}

u

Kề u

L

Father (F)



A(0, 12)


A(0, 12)

C(4, 11), D(7, 13),

K(10, 14)

C(4, 11), D(7, 13),

K(10, 14)

F(C) =A

F(D) =A

F(K) =A

C(4, 11)

G(10, 16)

D(7, 13),

K(10, 14), G(10, 16)

F(G) =C

D(7, 13)

G(13, 19) loại

E(12, 16)

K(10, 14), G(10, 16),

E(12, 16)

F(E) =D

K(10, 14)

F(16, 19)

G(10, 16), E(12, 16),

F(16, 19)

F(F) =K

G(10, 16)

H(24, 28)

E(12, 16),

F(16, 19),

H(24, 28)

F(H) =G

E(12, 16)

H(21, 25)

F(19, 22) loại

K(19, 23) loại

F(16, 19), H(21, 25)

F(H) =E

F(16, 19)

B(23, 23), H(19, 23)

B(23, 23), H(19, 23)

F(B) =F

F(H) =F

B(23, 23)

T

dừng



Kết luận: đường đi ngắn nhất là 23, BFKA


Bài 2.20.

cost=+

uo=A, T={G}


u

Kề u

L1

L

Father (F)




A(0, 12)


A(0, 12)

B(5, 10), C(7, 14)

B(5, 10),

C(7, 14)

B(5, 10), C(7,

14)

F(B) =A

F(C) =A

B(5, 10)

C(6, 13)

D(17, 21)

E(14, 17)

C(6, 13)

E(14, 17)

D(17, 21)

C(6, 13)

E(14, 17)

D(17, 21)

F(C) =B

F(E) =B

F(D) =B

C(6, 13)

D(10, 14)

E(16, 19) loại

D(10, 14)

D(10, 14)

E(14, 17)

F(D) =C

D(10, 14)

G(20, 20)

E(13, 16)

K(20, 23)

E(13, 16)

G(20, 20)

K(20, 23)

E(13, 16)

G(20, 20)

K(20, 23)

F(G) =D

F(E) =D

F(K) =D

E(13, 16)

G(18, 18)


G(18, 18)

K(20, 23)

F(G) =E

G(18, 18)

T

18<cost

cost=18


K(20, 23)


K(20, 23)

loại



dừng


Kết luận: đường đi ngắn nhất là 18, GEDCBA


Bài 2.21.

Khởi tạo: uo=A, T={G}

u

Kề u

L

Father (F)



A(0, 12)


A(0, 12)

B(5, 10)

C(13, 20)

K(5, 13)

B(5, 10)

K(5, 13)

C(13, 20)

F(C) =A

F(B) =A

F(K) =A

B(5, 10)

D(15, 19)

K(5, 13)

F(D) =B


C(6, 13)

C(6, 13)

F(C) =B


E(12, 15)

E(12, 15)

F(E) =B



D(15, 19)


K(5, 13)

C(11, 18) loại

H(9, 13)

F(H) =K

H(9, 13)

C(6, 13)

E(12, 15)

D(15, 19)


H(9, 13)

E(14, 17) loại

C(6, 13)

E(12, 15)

D(15, 19)


C(6, 13)

D(10, 14)

E(18, 21) loại

D(10, 14)

E(12, 15)

F(D) =C

D(10, 14)

G(15, 15)

G(15, 15)

E(12, 15)

F(G) =D

G(15, 15)

T

dừng



Kết luận: đường đi ngắn nhất là 15, GDCBA

Xem toàn bộ nội dung bài viết ᛨ

..... Xem trang tiếp theo?
⇦ Trang trước - Trang tiếp theo ⇨

Ngày đăng: 16/07/2022