Bài 2.22.
Khởi tạo: cost=+ uo=A, T={G}
Kề u | L1 | L | Father (F) | |
A(0, 12) | ||||
A(0, 12) | B(8, 15) F(10, 14) C(6, 13) | C(6, 13) F(10, 14) B(8, 15) | C(6, 13) F(10, 14) B(8, 15) | F(C) =A F(F) =A F(B) =A |
C(6, 13) | F(8, 12) E(14, 17) | F(8, 12) E(14, 17) | F(8, 12) E(14, 17) B(8, 15) | F(F) =C F(E) =C |
F(8, 12) | B(11, 18) loại D(25, 29) E(10, 13) | E(10, 13) D(25, 29) | E(10, 13) D(25, 29) B(8, 15) | F(E) =F F(D) =F |
E(10, 13) | D(13, 17) G(18, 18) | D(13, 17) G(18, 18) | D(13, 17) G(18, 18) B(8, 15) | F(D) =E F(G) =E |
D(13, 17) | G(15, 15) | G(15, 15) | G(15, 15) B(8, 15) | F(G) =D |
G(15, 15) | cost>15 | B(8, 15) |
Có thể bạn quan tâm!
-
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 - 27 -
Nhập môn trí tuệ nhân tạo - 29 -
Nhập môn trí tuệ nhân tạo - 30 -
Nhập môn trí tuệ nhân tạo - 31
Xem toàn bộ 272 trang tài liệu này.
cost=15 | ||||
B(8, 15) loại | dừng |
T
Bài 2.23.
Khởi tạo: uo=A, T={G}
Kề u | L | Father (F) | |
A(0, 12) | |||
A(0, 12) | B(5, 10) C(10, 17) K(4, 8) | K(4, 8), B(5, 10), C(10, 17) | F(C) =A F(B) =A F(K) =A |
K(4, 8) | E(10, 13) H(11, 15) | B(5, 10), E(10, 13), H(11, 15), C(10, 17) | F(E) =K F(H) =K |
B(5, 10) | D(19, 23) C(7, 14) E(17, 20) loại | E(10, 13) C(7, 14) H(11, 15) D(19, 23) | F(C) =B F(D) =B |
E(10, 13) | G(20, 20), H(15, 19) loại | C(7, 14) H(11, 15) G(20, 20) D(19, 23) | F(G) =E |
C(7, 14) | D(11, 15) E(25, 28) loại | D(11, 15) H(11, 15) G(20, 20) | F(D) =C |
D(11, 15) | G(26, 26) loại | H(11, 15) G(20, 20) | |
H(11, 15) | G(19, 19) | G(19, 19) | F(G) =H |
G(19, 19) T | dừng | ||
Kết luận: đường đi ngắn nhất là 19, GHKA | |||
Bài 2.24.
*Xây dựng đồ thị và /hoặc
a
R1
j
c
e
l
R5
f
R2
R3
R4
g
h
b
d
R8
R6
R7
i
n
m
*Tìm kiếm trên đồ thị và/hoặc Solvable(a)
Xét R1 tại a Solvable(c)
Xét R2 áp dụng tại c Solvable(g)
Do Solvable(i) =true, từ R6 Solvable(g) =true Solvable(h) =true
Do Solvable(n) =true, từ R7 Solvable(h) =true Solvable(b)
Do Solvable(n) =true, Solvable(m) =trure, từ R8 Solvable(b) =true Solvable(c) =true và Operator(c) =R2
tương tự Solvable(e) Xét R3 áp dụng tại e Solvable(h) =true Solvable(b) =true Operator(e) =R3 Solvable(e) =true
Xét Solvable(l) =false Kết luận: a không giải được
Bài 2.25.
Xây dựng đồ thị và/hoặc
Tìm kiếm trên đồ thị và/hoặc Solvable(a)
Xét R1 tại a Solvable(d)
Xét R4 áp dụng tại d Solvable(b) =true Solvable(c) =true Operator(d) =R4 Solvable(d) =true
Solvable(e) =true Solvable(f)
Xét R6 áp dụng tại f Solvable(c) =true Solvable(j) =true Operator(f) =R6 Solvable(f) =true
Solvable(a) =true Operator(a) =R1
Kết luận: a giải được
Bài 2.28.
Hướng dẫn: Ta xem hai đảo là kề nhau nếu khoảng cách giữa chúng không vượt quá m (km). Bài toán cần tìm đường đi từ đảo d1 đến đảo d2 thông qua các đảo kề nhau. Thuật toán tìm kiếm theo bề rộng cho phép tìm đường tìm ra đường đi nối hai đảo qua ít cạnh trung gian nhất (tức là ít đảo trung gian nhất). Dữ liệu vào lưu trong file dạng text, dòng đầu chứa số đảo n, dòng thứ hai chứa khoảng cách lớn nhất cano
có thể đi liên tục, n dònh tiếp theo mỗi dòng chứa hai giá trị tương ứng với toạ độ của mỗi đảo.
Program cano_di_tuan; uses crt;
type
var
dao = record x,y: integer;
end;
n,d1,d2,so: byte;
m: word;
a: array[byte] of dao;
b: array[byte] of boolean; tr: array[byte] of byte;
procedure nhap; var
f: text; s: string[20]; i: byte;
begin clrscr;
write('ten file du lieu:'); readln(s);
assign(f,s);
reset(f);
readln(f,n);
readln(f,m); for i:=1 to n do
with a[i] do readln(f,x,y); close(f);
end;
procedure indulieu; var
i: byte;
begin
writeln('so dao:',n);
writeln('gioi han khoang cach:',m); for i:=1 to n do
with a[i] do writeln('toa do dao ',i,': (',x,',',y,')'); end;
procedure khoitao; var
i: byte;
begin
for i:=1 to n do
b[i]:= true;
end;
function kc(i,j: byte):real; begin
kc:= sqrt(sqr(a[i].x-a[j].x)+sqr(a[i].y-a[j].y)); end;
procedure bfs(i: byte); var
j,k,d,c: byte;
q: array[byte] of byte; begin
d:=1;
c:=1; q[1]:=i;
b[i]:= false; while d<=c do begin
j:= q[d]; d:=d+1;
for k:=1 to n do
222
if b[k] and (kc(k,j) <= m) then begin
c:=c+1;
q[c]:=k;
b[k]:= false;
tr[k]:=j; end; end; end;
procedure inketqua; var
i:byte;
begin
write('duong di ghe dao it nhat nhu sau: '); write(d1);
i:=d1;
so:=0;
while i<>d2 do begin
write('-->',tr[i]); so:=so+1; i:=tr[i];
end; writeln;
writeln('duong di tren ghe qua ',so-1,' dao'); end;
procedure timduongdi; begin
write('dao xuat phat: '); readln(d1);
write('dao ket thuc: '); readln(d2);
bfs(d2);
223
if b[d2] then write('khong co duong di tu ',d1,' den ',d2) else inketqua;
readln; end;
BEGIN
nhap; khoitao; indulieu; timduongdi; END.
Bài 2.31.
Hướng dẫn: Giá trị aij có thể nhận tương ứng với số thập phân từ 0 đến 15. Vì vậy ta lưu dữ liệu trong file dạng text có cấu trúc như sau: dòng đầu chứa hai số m,n. Từ dòng thứ hai đến dòng thứ m+1, chứa các hàng của ma trận A = (aij). Kết quả đưa ra file dạng text có cấu trúc như sau: dòng đầu chứa số phòng, dònh hai chứa diện tíach phòng lớn nhất và dong ba chứa hàng, cột, hướng của bức tường cần phá.
Chẳng hạn dữ liệu vào là: 4 6
6 | 11 | 6 | 3 10 | 6 | ||
7 | 9 | 6 | 13 | 5 15 | 5 | |
1 | 10 | 12 | 7 | 13 | 7 | 5 |
13 | 11 | 10 | 8 | 10 | 12 | 13 |
Dữ liệu ra sẽ là:
5
9
4 1 Dong
Program laudai; uses crt;
type
var
size = 0..100;
m,n,so,p,hang,cot: size;
A:array[size,size] of 0..15;
224