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

{Tìm cung (i,j) có c[i,j] nhỏ nhất, nếu có thì d = c[i,j] và đấnh dấu cung (i,j) là true, ngược lại d = 0 }

Var

l,p: byte; begin

d:=0;

for l:= 1 to m do

if (A[l].dau = i) and (A[l].kc < d) and not B[l] then begin

j:= A[l].cuoi; p:= l;

d:= A[l].kc; end;

B[l]:= true;

end;

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

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

Function DenDich(i,j: byte; var d:word): boolean;

Var

l: byte; begin

for l:= 1 to m do

if (A[l].dau = i) and (A[l].cuoi = j) then begin

d:= A[l].kc;

DenDich:= true;

end else

begin

DenDich:= false; d:= 0;

end;

Procedure Inkq(j:byte);

Var

d:word; k: byte;

begin

d:=0;

for k:= 1 to Top do begin

write(S[k].dau);

d:=d + S[k].kc; end;

writeln(j);

writeln(„ Chi phi: „,d); end;

Procedure Duongdi(i,j: byte);

Var

k,d: byte;

Begin

if Dendich(i,j) then begin

push(i,j,d); inkq(j); exit;

end; Timkiem(i,k,d); if d > 0 then begin

push(i,j,d);

duongdi(k,j); end

else

if Top > 0 then begin

pop(i,j,d);

duongdi(i,j); end

else

writeln(„Khong co duong di‟);

end;

234

Begin {leo doi} Khoitao; Duongdi(i0,j0);

end;

Bài 2.45. Tìm kiếm đường đi từ đỉnh i0 đến đỉnh J0 trong đồ thị. Dữ liệu được lưu vào file Text có cấu trúc như sau:

- Dòng đầu tiên chứa 3 số n, i0, j0 (n là số đỉnh của đồ thị)

- n dòng tiếp theo lần lượt chứa giá trị n dòng của ma trận A. Tên file được nhập từ bàn phím khi thực hiện chương trình. Truoc[j] xác định đỉnh đứng trước j trong đường đi tìm được. Program đuongdi;

Var

A: array[1..50,1..50] of byte; Dau: array[1..50] of boolean; Truoc: array[1..50] of byte; n, i0, j0: byte;

Procedure khoitao;

Var

Begin

i, j: byte; f:text; tenfile:string;

write(„ten file‟); readln(tenfile);

assign(f, tenfile); reset(f); readln(f,n,i0,j0);

for i:=1 to n do begin

for j:=1 to n do read(f, A[i,j]);

readln(f); end;

close(f);

Fillchar (Dau,n,true);

235

End;

Procedure BFS(i:byte);

Var

Begin

Q: array [1..50] of byte; d,c,j,k: byte;

d:=1;

c:=1;

Q[c]:=i;

Dau[i]:=true;

Truoc[i]:= 0; While d<=c do begin

j:=Q[d];

inc(d);

for k:=1 to n do

if (A[j,k]=1) and not Dau[k] then begin

inc(c) ;

Q[c]:=k;

Dau[k]:=true;

Truoc[k]:= j; end;

end;

End;

Procedure inkq(j: byte);

Begin

if Truoc[j] <> 0 then inkq(Truoc[j]);

write(j:4);

End;

Procedure Duyet;

Var i:byte;

Begin

BFS(i0);

if Dau[j0] then inkq(j0)

else

writeln(„ Khong co duong di‟);

End;

BEGIN {main} Khoitao; Duyet; Readln;

END.

2. Bài tập Chương 3 Bài 3.9.

Chuẩn hóa công thức sau về dạng chuẩn hội: (A  B)  CD

 (AB)  CD

 (ABCD) (CDAB)

((AB) CD) (CDAB)

((AB) CD) ((CD) AB)

((AB)CD) ((CD) AB)

((AB) CD) ((CD) AB)

(ACD) (BCD) (CAB) (DAB)

Bài 3.10.

Sử dụng phương pháp chứng minh diễn dịch chứng minh công thức (M N  P) (Q  R) suy ra M N  P, Q  R

(S  N)(P  Q) suy ra S  N, P  Q (M  S) M suy ra M  S, M

M, MS suy ra S S, SN suy ra N M, N suy ra MN

MN, MNP suy ra P

P, PQ suy ra Q, Q, QR suy ra R

Sử dụng phương pháp phản chứng chứng minh công thức Bổ sung R

(R, QR) suy ra Q (Q, PQ) suy ra P

(P, MNP) suy ra (MN)

(MN) MN

MN, M suy ra N (N, SN) suy ra S (S, MS) suy ra M

M, M suy ra câu 

Kết luận: R được chứng minh

Bài 3.11.

Sử dụng phương pháp chứng minh diễn dịch chứng minh công thức (A  B) (B  C) suy ra A  B, B  C

(CD) (D  E) suy ra CD, D  E (DE, E) suy ra (D)

(D)  D

(D, CD) suy ra C (BC, C) suy ra B (B, AB) suy ra A

Sử dụng phương pháp phản chứng chứng minh công thức Bổ sung (A)

(A) A

(A, AB) suy ra B (B, B C) suy ra C (C, CD) suy ra D

D, DE suy ra E E, E suy ra câu 

Kết luận: R được chứng minh

Bài 3.12.

Sử dụng phương pháp chứng minh diễn dịch chứng minh công thức

+ (M  N) (NP) suy ra M  N, NP

+ (P Q) (QR) suy ra (P Q), QR (MN, M) suy ra N

N, NP suy ra P

(PQ) PQ

P, PQ suy ra Q

Q, QR suy ra R

Sử dụng phương pháp phản chứng chứng minh công thức Bổ sung R

R, QR suy ra Q Q, PQ suy ra P

P, NP suy ra N

N, MN suy ra M

M, M  câu rỗng

Kết luận: R được chứng minh

Bài 3.13.

Sử dụng phương pháp chứng minh diễn dịch chứng minh C: (AB  C) ((DE) C) (1)

E (AB) (2)

AD (3)

- Chuẩn hóa công thức

(1)  ((AB) C) ((DE) C)

 (ABC) ((DE) C)

 (ABC) (DC) (EC)

(2)  EAB

(3) AD

- Đưa về câu tuyển ABC (4)

DC (5)

EC (6)

EAB (2)

AD (3)

- Chứng minh bằng diễn dịch (2) (6) suy ra ABC (7) (5), (3) suy ra AC (8)

(7), (8) suy ra BC (9)

(8), (4) suy ra BC (10)

(9), (10) suy ra C

Sử dụng phương pháp phản chứng chứng minh C Bổ sung C (11)

(11), (5) suy ra D (12)

(12), (3) suy ra A (13)

(13), (4) suy ra BC (14)

(14), (11) suy ra B (15)

(13), (15), (2) suy ra E (16)