Niên luận 1
MỤC LỤC
PHẦN I: TỔNG QUAN
I.GIỚI THIỆU CHUNG Trang 2
II. MỤC TIÊU VÀ HƯỚNG GIẢI QUYẾT Trang 2
PHẦN II: LÝ THUYẾT VÀ ỨNG DỤNG Trang 4
I. BÀI TOÁN ĐƯỜNG ĐI CỦA NGƯỜI GIAO HÀNG Trang 4
II. BÀI TOÁN CÁI BA LÔ Trang 12
PHẦN III: CHƯƠNG TRÌNH DEMO Trang 25
I. HƯỚNG DẪN CÀI ĐẶT CHƯƠNG TRÌNH Trang 25
II. HƯỚNG DẪN SỬ DỤNG Trang 25
PHẦN IV: KẾT LUẬN Trang 28
I. NHẬN XÉT KẾT QUẢ ĐẠT ĐƯỢC Trang 28
II. NHỮNG MẶT HẠN CHẾ Trang 28
III. HƯỚNG PHÁT TRIỂN Trang 28
TÀI LIỆU THAM KHẢO Trang 29
Trang 1
Niên luận 1
PHẦN I: TỔNG QUAN
I. GIỚI THIỆU CHUNG:
Niên luận được xem như là đề tài dành cho sinh viên năm 3 chuyên ngành
Công Nghệ Thông Tin (CNTT). Niên luận giúp cho sinh viên tự nghiên cứu, tự
đánh giá khả năng học tập của mình trong suốt thời gian học vừa qua. Mỗi sinh viên
sẽ bóc thăm chọn cho mình một đề tài. Sinh viên tự tìm tài liệu, tự nghiên cứu về đề
tài của mình. Đồng thời với kiến thức các môn học cơ sở ngành và dưới sự hướng
dẫn của giáo viên để viết chương trình demo và một quyển báo cáo niên luận theo
yêu cầu.
Đề tài niên luận của em là: “CHUYÊN ĐỀ KỸ THUẬT NHÁNH CẬN”.
Nội dung đề tài này em đã được học ở bô môn “Giải thuật”. Đây là một trong
những kỹ thuật thiết kế giải thuật. Và kỹ thuật “nhánh cận” là một trong những kỹ
thuật tối ưu nhất của kỹ thuật quay lui.

- Về cấu trúc cài đặt: sử dụng danh sách liên kết để viết chương trình con
nhập các đồ vật cho bài toán cái ba lô.
- Bên cạnh đó xây dựng nhiều chương trình con: sắp xếp, phân nhánh,
quay lui, kết quả, và thoát chương trình. Và chương trình chính để gọi các chương
trình con thực hiện.
b)Về ngôn ngữ lập trình: Sau khi tìm hiểu và so sánh một số ngôn ngữ
lập trình gồm: Pascal, C, C
++
… em quyết định chọn ngôn ngữ lập trình C để cài đặt
chương trình Demo với các lý do sau:
- C là ngôn ngữ lập trình khá sinh động và phổ biến.
- C hỗ trợ các thư viện đáp ứng được các hàm dùng để sử lý chuỗi thích
hợp với đề tài của em.
- Chọn cấu trúc danh sách để cài đặt.
- Ngoài ra, C là ngôn ngữ mà em am hiểu và ưu thích.
Trang 3
Niên luận 1
PHẦN II: LÝ THUYẾT VÀ ỨNG DỤNG
Với các bài toán tìm phương án tối ưu, nếu chúng ta xét hết tất cả các
phương án thì mất rất nhiều thời gian, nếu sử dụng phương pháp tham ăn thì
phương án tìm được chưa hẳn đã là phương án tối ưu. Nhánh cận là kỹ thuật xây
dựng cây tìm kiếm phương án tối ưu, nhưng không xây dựng toàn bộ cây mà sử
dụng giá trị cận để hạn chế bớt các nhánh.
Cây tìm kiếm phương án có nút gốc biểu diễn cho tập tất cả các phương án
có thể có , mỗi nút lá biểu diễn cho một phương án nào đó. Nút n có các nút con
tương ứng với các khả năng có thể lựa chọn tập phương án xuất phát từ n. Kỹ thuật
này được gọi là phân nhánh.
Với mỗi nút trên cây ta sẽ xác định một giá trị cận. Giá trị cận là một giá trị
gần với giá của các phương án. Với bài toán tìm Min ta sẽ xác định cận dưới, còn
với bài toán tìm Max ta sẽ xác định cận trên. Cận dưới là giá trị nhỏ hơn hoặc bằng

, …, x
n
) = c[1,x
1
]+c[x
2
,x
3
]+…+c[x
n-1
,x
n
]+c[x
n
,x
1
]→ min
- Với điều kiện
- C
min
= min{c[i,j],I,j = 1,2,…, n;i ≠ j là chi phí đi lại giữa các thành phố.
- Giả sử ta đang có phương án bộ phận (u
1
,u
2
,…,u
k
). Phương án tương ứng
với hành trình bộ phận qua k thành phố:
theo từng node của hành trình bộ phận.

, …, u
k
) =∂+(n-k+1)c
min

3. Sau đây là giải thuật của giải bài toán này:
a) Đầu tiên ta phải nhập tên các cạnh và trọng số của các đỉnh. Chương
trình con nhập được thiết kế là ma trận vuông. Số dòng và cột bằng nhau và bằng số
đỉnh đã cho. Đồng thời sắp xếp tên các cạnh theo thứ tự từ điển để xét phân nhánh.
Trang 5
Niên luận 1
 Dưới đây là lưu đồ cho phần nhập:

 Code được viết như sau:
void Nhap_dulieu(void)
{
int i, j;
FILE *fp; //Doc du lieu tu trong tap tin
fp = fopen("E:\\nhanhcan\\test2.txt","r");
fscanf(fp,"%d", &n);
Trang 6
end
Begin
i<=n;
j<=n
i=1; j=1
Tăng i, j lên 1
Nhập n, C[i][j]
In C[i][j]
Dữ liệu được lấy

 Code được viết như sau:
Trang 8
Begin
i<>j && min > C[i][j]
Tăng i, j lên 1
end
In min
min =1000, i =1, j = 1
i<=n; j<=n
min = C[i][j]
Sai
Đúng
Sai
Đúng
Niên luận 1
int Min_Matrix(void)
{
int min=1000, i, j;
for(i=1; i<=n; i++)
{
for(j=1; j<=n; j++)
{
if (i!=j && min>C[i][j])
min=C[i][j];
}
} return(min); }
- Cận dưới của nút gốc bằng tổng độ dài tất cả các cạnh được chọn
chia cho 2.
- Đối với các nút khác, chúng ta phải lựa chọn hai cạnh có độ dài nhỏ
nhất thỏa điều kiện ràng buộc (phải chứa cạnh này, không chứa cạnh kia).

end
Menu xử lý
Nhập dữ liệu
In kết quả
Chương trình
Tất cả các phương án
16
AB
16
23
AC,
25
BD,
21
AD,
16
BC,
16
Tạo thành chu trình thiếu
CD
ABCDA
16
Niên luận 1
5. Bài toán ứng dụng phần cho giải thuật trên: Xét bài toán TSP có 4
đỉnh với độ dài các cạnh được cho trong hình là:
A 3 B

11
1 5
9