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

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


Bài 2.22.

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

u

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!

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}

u

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 1

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

11

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

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

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