Tiểu luận môn học Lập trình trí tuệ nhân tạo
ĐẠI HỌC ĐÀ NẴNG
TRƯỜNG ĐẠI HỌC BÁCH KHOA

TIỂU LUẬN
LẬP TRÌNH TRÍ TUỆ NHÂN TẠO
ĐỀ TÀI :
Phần I: LÝ THUYẾT LẬP TRÌNH HÀM
Đề tài: Áp dụng kiểu dữ liệu trừu tượng, xây dựng kiểu cấu trúc dữ liệu
truyền thống hàng đợi (Queue) trong Scheme. Cho ví dụ minh hoạ vận dụng
hàng đợi để quản lý nhập/xuất một sản phẩm.
Phần II: BÀI TOÁN LẬP TRÌNH HÀM
Đề tài: Hãy viết chương trình Scheme mô phỏng các hàm đệ quy thực hiện
các phép chia (Division) và tìm giá trị căn bậc hai (Square Root)
Phần III: BÀI TOÁN LẬP TRÌNH PROLOG
Đề tài: Cài đặt thuật toán tìm kiếm sâu (Depth-First-Search) trong lý thuyết trí
tuệ nhân tạo (Artificial Intelligence)
NHÓM HỌC VIÊN : Hoàng Đình Tuyền
Lê Nam Trung
Nguyễn Nương Quỳnh
Nguyễn Duy Linh
LỚP : KHMT K24 (Quảng Bình)
GVHD : PGS.TS Phan Huy Khánh
Quảng Bình, 12/2012
Nhóm 3
1
Tiểu luận môn học Lập trình trí tuệ nhân tạo
LỜI NÓI ĐẦU
Trí tuệ nhân tạo là "khả năng suy luận và thực hiện các hành động" của các
thiết bị, máy móc tương tự như trong não người. Thuật ngữ này được dùng để
nói đến các máy tính có mục đích không nhất định, ngành khoa học nghiên cứu

các phép chia (Division) và tìm giá trị căn bậc hai (Square Root)
Phần III: BÀI TOÁN LẬP TRÌNH PROLOG
Đề tài: Cài đặt thuật toán tìm kiếm sâu (Depth-First-Search) trong lý
thuyết trí tuệ nhân tạo (Artificial Intelligence). Cho ví dụ minh hoạ chạy demo.
Với thời gian và việc nghiên cứu của chúng tôi còn nhiều hạn chế nên
không tránh khỏi có những sai sót. Rất mong được sự góp ý và định hướng của
Thầy PGS.TS Phan Huy Khánh và các anh chị cùng lớp để chúng tôi có thể tiếp
tục nghiên cứu và đạt được kết quả tốt hơn trong thời gian tới.
Xin chân thành cảm ơn PGS.TS Phan Huy Khánh đã nhiệt tình giảng dạy,
góp ý để nhóm em hoàn thành tiểu luận này.
Nhóm học viên thực hiện:
Lê Nam Trung
Nguyễn Nương Quỳnh
Nguyễn Duy Linh
Hoàng Đình Tuyền
Nhóm 3
3
Tiểu luận môn học Lập trình trí tuệ nhân tạo
MỤC LỤC
Nhóm 3
4
Tiểu luận môn học Lập trình trí tuệ nhân tạo
Phần I
LÝ THUYẾT LẬP TRÌNH HÀM
Đề tài: Áp dụng kiểu dữ liệu trừu tượng, xây dựng kiểu cấu trúc dữ liệu
truyền thống hàng đợi (Queue) trong Scheme. Cho ví dụ minh hoạ vận dụng
hàng đợi để quản lý nhập/xuất một sản phẩm.
I. Tổng quan về Hàng đợi (Queue)
1. Hàng đợi (Queue)
Hàng đợi là một vật chứa (container) các đối tượng làm việc theo cơ chế

Có rất nhiều kĩ thuật hàng đợi: FIFO (first in first out), PQ (priority queue
- hàng đợi ưu tiên), FQ (fair queue - hàng đợi cân bằng). FIFO đây là kĩ thuật
xếp hàng vào trước ra trước cơ bản. Các gói đến trước sẽ là các gói đầu tiên
được xử lý. Khi hàng đợi đầy và có tắc nghẽn xảy ra thì các gói đến sẽ bị loại
bỏ. Hàng đợi FIFO dựa vào hệ thống đầu cuối để điều khiển tắc nghẽn thông
qua cơ chế điều khiển tắc nghẽn. Do loại hàng đợi này rất đơn giản nhiều khi
không điều khiển được tắc nghẽn nên ta thường xét các loại hàng đợi hiệu quả
hơn: hàng đợi ưu tiên(PQ), hàng đợi cân bằng (FQ), hàng đợi có trọng số (WQ).
a. Hàng đợi FIFO (First In First Out)
FIFO là hàng đợi mặc định được sử dụng trong hầu hết các router trên thế
giới. Hoạt động của FIFO. Các gói đến từ các luồng khác nhau được đối xử
công bằng bằng cách đưa vào các hàng đợi theo trật tự đến (gói nào đến trước
sẽ được đưa vào trước và được phục vụ trước).
Hàng đợi hoạt động như một nơi lưu giữ các gói để tránh việc loại bỏ các
gói không cần thiết khi có dấu hiệu của tắc nghẽn. Khi có tắc nghẽn xảy ra, và
Nhóm 3
6
Tiểu luận môn học Lập trình trí tuệ nhân tạo
hàng đợi tràn thì tất cả các gói đến sẽ bị loại bỏ. Hàng đợi FIFO được sử dụng
hầu hết trong các router, nó đơn giản do không phải định cấu hình cho nó mà
chỉ việc sử dụng luôn. Trong các router của cisco, khi không có kế hoạch hàng
đợi nào khác được cấu hình, thì tất cả các giao diện(ngoại trừ các giao diện có
tốc độ bằng hoặc nhỏ hơn luồng E1) đều sử dụng hàng đợi FIFO mặc định. Tốc
độ xử lý gói phải nhanh hơn tốc độ các gói đến hàng đợi IF0 thì mới tránh được
hiện tượng tắc nghẽn trong mạng (hàng đợi IF1 rỗng), khi tốc độ xử lý quá thấp
hơn so với tốc độ các gói vào, có nghĩa là tốc độ ra nhỏ hơn tốc gói vào (hàng
đợi đầu ra dễ bị tràn) thì sẽ xảy ra tắc nghẽn khi có quá nhiều gói đi vào trong
mạng, và khi vấn đề này xảy ra thì các gói đến sau sẽ bị loại bỏ.
b. Hàng đợi ưu tiên PQ (Priority Queue)
Kĩ thuật này được sử dụng trong trường hợp đa hàng đợi, mỗi hàng đợi có

nghĩa theo chiều dài giới hạn. Khi một hàng đợi dài hơn chiều dài hàng đợi giới
hạn thì các gói đến sau sẽ bị loại bỏ.
Cơ chế hàng đợi đầu ra ưu tiên có thể được sử dụng để quản lý lưu lượng
từ tất cả các giao thức trong mạng. PQ cung cấp cách đối sử ưu tiên cho các
luồng lưu lượng có độ ưu tiên cao, chắc chắn rằng các luồng lưu lượng then
chốt khi qua các kết nối WAN sẽ đạt được độ ưu tiên cao.
Các gói được phân loại như thế nào trong kĩ thuật PQ: Danh sách ưu tiên
là một tập các luật lệ mô tả các gói sẽ được ấn định các độ ưu tiên như thế nào
trong các hàng đợi. Ngoài ra nó cũng có thể mô tả độ ưu tiên mặc định hoặc
giới hạn kích thước hàng đợi của các hàng đợi ưu tiên.
Các gói được phân loại theo:
- Loại giao thức hoặc giao thức con
- Giao diện đầu vào
- Kích thước các gói tin
- Các Fragment
- Danh sách truy nhập
Tất cả các lưu lượng dùng để quản lý và điều khiển mạng đều được ấn
định độ ưu tiên cao nhất để trong trường hớp có tắc nghẽn xảy ra thì chúng
được ưu tiên truyền trước. Các lưu lượng không được ấn định mức ưu tiên nào
thì được đưa vào các hàng đợi bình thường.
PQ cung cấp thời gian đáp ứng nhanh hơn so với các kĩ thuật hàng đợi
khác. Mặc dù có thể ấn định các độ ưu tiên cho các hàng đợi tại bất kì giao diện
đầu nào nhưmg nó thường được sử dụng cho các lưu lượng có băng thông thấp.
Để giải quyết vấn đề các hàng đợi có độ ưu tiên thấp không được xử lý khi có
quá nhiều hàng đợi có độ ưu tiên cao thì ta có thể sử dụng các kiểu hàng đợi
Nhóm 3
8
Tiểu luận môn học Lập trình trí tuệ nhân tạo
khác: hàng đợi cân bằng có trọng số (WFQ) hay hàng đợi cân bằng (FQ), đơn
giản hơn ta có thể sử dụng cơ chế định dạng lưu lượng hay CAR để giới hạn tốc

; Không
; Kết quả:
; QUEUE, một thủ tục
; Điều kiện đầu:
; Không có.
; Quá trình thực hiện:
; (1) QUEUE ban đầu rỗng.
; (2) Khi QUEUE được gọi với các đối số: EMPTY?, nó báo cáo
; Cho dù đó là sản phẩm nào.
; (3) Khi QUEUE đã được gọi với đối số đầu tiên: Enqueue! và
; Một đối số thứ hai, ta gọi NEW-VALUE, NEW-VALUE ở phía sau, và
; Tất cả các giá trị khác trong hàng đợi ở phía trước của nó, theo thứ tự
thời gian.
; (4) Khi QUEUE đã được gọi với đối số: Dequeue!,
; Trả về giá trị lâu nhất enqueued, ở phía trước, và
; Giữ lại tất cả các giá trị khác, theo thứ tự thời gian.
; (5) Khi QUEUE được gọi với các đối số: FRONT, nó trả về
; Giá trị ở phía trước (có sẵn cho dequeuing).
; (6) Khi QUEUE được gọi với đối số: SIZE, nó trả về
; Số các giá trị trong hàng đợi.
; (7) Đây là một lỗi để cung cấp cho QUEUE bất kỳ đối số khác khi gọi
nó.
; (8) Khi QUEUE được gọi với đối số đầu tiên: EMPTY?,:DEQUEUE!,
;: FRONT, hoặc :SIZE, đó là một lỗi để cho nó hai hoặc nhiều đối số.
; (9) Khi QUEUE được gọi với đối số đầu tiên: :ENQUEUE!, nó là một
; Lỗi để cho nó chỉ có một đối số hoặc ba hoặc nhiều hơn.
Nhóm 3
10
Tiểu luận môn học Lập trình trí tuệ nhân tạo
(define make-queue

((null? (cdr fore))
(error "queue:dequeue!: the queue is empty"))
(else
; Recover the first element of the queue (not
; including the dummy header).
(let ((removed (cadr fore)))
; Splice out the element to be dequeued.
(set-cdr! fore (cddr fore))
; If we just spliced out the last element of the
; queue, reset AFT so that it holds the dummy
; header.
(if (null? (cdr fore))
(set! aft fore))
; Decrement SIZE.
(set! size (- size 1))
removed))))
((eq? message ':front)
(cond ((not (null? arguments))
(error "queue:front: no argument is required"))
((null? (cdr fore))
(error "queue:front: the queue is empty"))
(else
(cadr fore))))
((eq? message ':size)
Nhóm 3
12
Tiểu luận môn học Lập trình trí tuệ nhân tạo
(if (null? arguments)
size
(error "queue:size: no argument is required")))

13: (lambda (cmd . data)
14: (define exchange
15: (lambda ()
16: (set! front (reverse back))
17: (set! back '())))
18: (case cmd
19: ((push) (push (car data) back))
20: ((pop) (or (pop front)
21: (begin
22: (exchange)
23: (pop front))))
24: ((peek) (unless (pair? front)
25: (exchange))
26: (car front))
27: ((show) (format #t "~s\n" (append front (reverse back))))
28: ((fb) (format #t "front: ~s, back: ~s\n" front back))
29: (else (error "Illegal cmd to queue object" cmd)))))))
Có thể đẩy và bật các Sản phẩm vào và ra hàng đợi bằng cách gửi nó đẩy
hoặc lệnh pop.
(define q (make-queue))
(q 'push "Hello, World!")
(q 'pop) → "Hello, World!"
Nhóm 3
14
Tiểu luận môn học Lập trình trí tuệ nhân tạo
Phần II
BÀI TOÁN LẬP TRÌNH HÀM
Đề tài: Hãy viết chương trình Scheme mô phỏng các hàm đệ quy thực
hiện các phép chia (Division) và tìm giá trị căn bậc hai (Square Root)
Bài làm:

(define (sqrt-iter guess)
(if (good-enough? guess)
Guess
(sqrt-iter (improve guess))))
(sqrt-iter 1.0))
; divides two numbers until cutoff is reached
(define (divide n d cutoff)
(let ((step 10)) ; any value >1 will work
(define (loop i p sum)
(letrec ((sp (expt step p))
(dp (* d sp))
(q (quotient i dp))
(r (remainder i dp))
(new-sum (+ sum (* q sp))))
(cond
((= r 0)
new-sum)
((< (abs r) cutoff)
(exact->inexact new-sum))
(else
(loop r (- p 1) new-sum)))))
(loop n 0 0)))
; divides two numbers until cutoff is reached without quotient/remainder
(define (divide-2 n d cutoff)
(let ((step 10)) ; any value >1 will work
(define (loop i ud p sum)
(cond
Nhóm 3
16
Tiểu luận môn học Lập trình trí tuệ nhân tạo

Trong tìm kiếm theo chiều sâu, tại trạng thái (đỉnh) hiện hành, ta chọn một
trạng thái kế tiếp (trong tập các trạng thái có thể biến đổi thành từ trạng thái
hiện tại) làm trạng thái hiện hành cho đến lúc trạng thái hiện hành là trạng thái
đích. Trong trường hợp tại trạng thái hiện hành, ta không thể biến đổi thành
trạng thái kế tiếp thì ta sẽ quay lui (back-tracking) lại trạng thái trước trạng thái
hiện hành (trạng thái biến đổi thành trạng thái hiện hành) để chọn đường khác.
Nếu ở trạng thái trước này mà cũng không thể biến đổi được nữa thì ta quay lui
lại trạng thái trước nữa và cứ thế. Nếu đã quay lui đến trạng thái khởi đầu mà
vẫn thất bại thì kết luận là không có lời giải. Hình ảnh sau minh họa hoạt động
của tìm kiếm theo chiều sâu.
Hình 1: Hình ảnh của tìm kiếm chiều sâu. Nó chỉ lưu ý "mở rộng" trạng
thái được chọn mà không "mở rộng" các trạng thái khác (nút màu trắng trong
hình vẽ).
2. Kỹ thuật tìm kiếm chiều sâu
Tìm kiếm sâu trong không gian bài toán được bắt đầu từ một nút rồi tiếp
tục cho đến khi hoặc đến ngõ cụt hoặc đến đích. Tại mỗi nút có luật trong tài,
chẳng hạn, “đi theo nút cực trái”, hướng dẫn việc tìm. Nếu không đi tiếp được,
Nhóm 3
18
Tiểu luận môn học Lập trình trí tuệ nhân tạo
gọi là đến ngõ cụt, hệ thống quay lại một mức trên đồ thị và tìm theo hướng
khác, chẳng hạn, đến nút “sát nút cực trái”. Hành động này gọi là quay lui.
Thuật toán tìm kiếm theo chiều sâu được hình dung như việc khảo sát một cây
bắt đầu từ gốc đi theo mọi cành có thể được, khi gặp cành cụt thì quay lại xét
cành chưa đi qua.
- Ở bước tổng quát, giả sử đang xét đỉnh i, khi đó các đỉnh kề với i có các
trường hợp:
+ Nếu tồn tại đỉnh j kề i chưa được xét thì xét đỉnh này (nó trở thành đỉnh
đã xét) và bắt đầu từ đó tiếp tục quá trình tìm kiếm với đỉnh này
+ Nếu với mọi đỉnh kề với i đều đã được xét thì i coi như duyệt xong và

nondeterm stack(STATE,PATH,PATH)
nondeterm member(STATE,PATH)
nondeterm member_set(STATE,PATH)
nondeterm member_stack(STATE,PATH)
add_if_not_in_set(STATE,PATH,PATH)
nondeterm path(PATH,PATH,PATH,STATE)
empty_set(PATH)
empty_stack(PATH)
nondeterm go(STATE,STATE)
nondeterm move(STATE,STATE)
nondeterm reverse_print_stack(PATH)
nondeterm test
clauses
path(Open_stack,_,_,_):-
empty_stack(Open_stack),
write("No solution found with these rules").
Nhóm 3
20
J
HGFE
DCB
A
Tiểu luận môn học Lập trình trí tuệ nhân tạo
path(Open_stack,_,Path_stack,Goalstate):-
stack(Top,_,Open_stack),Top = Goalstate,
write("A solution found :\n"),
reverse_print_stack(Path_stack).
path(Open_stack,Closed_set,Path_stack,Goalstate):-
stack(Top,Res_open_stack,Open_stack),
move(Top,Next_state),

empty_set([]).
stack(Top,Stack,[Top|Stack]).
reverse_print_stack(S):-
empty_stack(S).
reverse_print_stack(S):-
stack(E,Res,S),
reverse_print_stack(Res),write(E),nl.
member(X,[X|_]):-
!.
member(X,[_|L]):-
member(X,L).
member_stack(Element,Stack):- member(Element,Stack).
member_set(S,L):- member(S,L).
add_if_not_in_set(X,S,S):-
member(X,S),!.
add_if_not_in_set(X,S,[X|S]).
test:-
go(state(0,0),state(2,_)).
goal
test.
4. Ưu và nhược điểm của phương pháp tìm kiếm chiều sâu:
* Ưu điểm:
- Nếu bài toán có lời giải, phương pháp tìm kiếm sâu bảo đảm tìm ra lời
giải.
- Kỹ thuật tìm kiếm sâu tập trung vào đích, con người cảm thấy hài lòng
khi các câu hỏi tập trung vào vấn đề chính.
- Do cách tìm của kỹ thuật này, nếu lời giải ở rất sâu, kỹ thuật tìm sâu sẽ
tiết kiệm thời gian.
* Nhược điểm:
Nhóm 3

23
F
H
LKJ
E
D
CB
A
G
P
I
Tiểu luận môn học Lập trình trí tuệ nhân tạo
Cho cây như hình vẽ:
Đỉnh đầu: A
Đỉnh đích: K
Các bước chi tiết thực hiện giải thuật:
Lần
Lặp
L = Ø
U U € T V L
0 A
1 False A False B,C,D B,C,D
2 False B False E,F C,D,E,F
3 False C False G D,E,F,G
4 False D False H,I E,F,G,H,I
5 False E False J,K F,G,H,I,J,K
6 False F False Ø G,H,I,J,K
7 False G False L H,I,J,K,L
8 False H False Ø I,J,K,L
9 False I False P J,K,L,P

Tiểu luận môn học Lập trình trí tuệ nhân tạo
PATH = STATE*
predicates
nondeterm member(STATE,PATH)
nondeterm member_set(STATE,PATH)
add_if_not_in_set(STATE,PATH,PATH)
nondeterm path(PATH,PATH,STATE)
empty_set(PATH)
empty_queue(PATH)
nondeterm go(STATE,STATE)
nondeterm move(STATE,STATE)
nondeterm dequeue(STATE,PATH,PATH)
nondeterm add_to_queue(STATE,PATH,PATH)
nondeterm moves(STATE,PATH,PATH,STATE)
get_children(STATE,PATH,PATH,PATH)
nondeterm union(PATH,PATH,PATH)
nondeterm append(PATH,PATH,PATH)
nondeterm add_list_to_queue(PATH,PATH,PATH)
nondeterm member_queue(STATE,PATH)
nondeterm printsolution(STATE,PATH)
nondeterm reverse_writelist(PATH)
nondeterm test
clauses
go(Start,Goalstate):-
empty_queue(Empty_open_queue),
add_to_queue(Start,Empty_open_queue,Open_queue),
empty_set(Closed_set),
path(Open_queue,Closed_set,Goalstate).
path(Open_queue,_,_):-
empty_queue(Open_queue),