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!
-
Mô Hình Vào/ra Của Một Thủ Tục Thực Hiện Một Danh Sách Các Đích -
Nhập môn trí tuệ nhân tạo - 25 -
Nhập môn trí tuệ nhân tạo - 26 -
Nhập môn trí tuệ nhân tạo - 28 -
Nhập môn trí tuệ nhân tạo - 29 -
Nhập môn trí tuệ nhân tạo - 30
Xem toàn bộ 272 trang tài liệu này.
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
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}
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}
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}
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}
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}
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}
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}
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}
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}
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 | |||