Download miễn phí Chuyên đề Niên luận kỹ thuật nhánh cận
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
Để tải bản Đầy Đủ của tài liệu, xin Trả lời bài viết này, Mods sẽ gửi Link download cho bạn sớm nhất qua hòm tin nhắn.
Ai cần download tài liệu gì mà không tìm thấy ở đây, thì đăng yêu cầu down tại đây nhé:
Nhận download tài liệu miễn phí
Tóm tắt nội dung tài liệu:
MỤC LỤCPHẦ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
PHẦN I: TỔNG QUAN
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.
Yêu cầu của đề tài: trình bày cơ sở xuất phát và nội dung kỹ thuật nhánh cận. Tuyển chọn ít nhất 3 bài toán có thể giải bằng kĩ thuật nhánh cận. Mỗi bài cần mô tả cấu trúc dữ liệu, giải thuật thực hiện, độ phức tạp của giải thuật và cài đặt chương trình.
Đây là niên luận đầu tiên nên không tránh khỏi sai xót trong quá trình làm. Mong thầy cô thông cảm và đóng góp ý kiến chân tình để em rút kinh nghiệm cho bài niên luận sau tốt hơn. Chân thành Thank quý thầy cô!!!
MỤC TIÊU VÀ HƯỚNG GIẢI QUYẾT
1. Mục tiêu cần đạt được:
Lý thuyết:
- Cần hiểu và nắm rõ các giải thuật của kỹ thuật “nhánh cận” trong môn học “giải thuật”.
- Hiểu các kiểu cấu trúc dữ liệu và áp dụng một kiểu phù hợp để cài đặt cho chương trình.
- Nắm vững ngôn ngữ lập trình C nhằm giải quyết một cách hiệu quả các vấn đề đặt ra.
- Đưa ra các bài toán có thể giải bằng phương pháp nhánh cận, ứng dụng lý thuyết giải đúng các bài toán đề ra.
- Trình bày nội dung rõ ràng, chặt chẽ và dễ hiểu. Với nội dung và hình thức sao cho đúng với yêu cầu.
Về chương trình demo:
- Phải thiết kế chương trình đúng với giải thuật có sẵn. Chương trình chạy đúng, và chọn phương án tối ưu nhất để viết chương trình.
- Cung cấp giao diện thân thiện với người dùng.
2. Hướng giải quyết: Với các yêu cầu đặt ra ta có thể giải quyết các vấn đề như sau:
a)Về cấu trúc dữ liệu:
- Dữ liệu dầu vào được nhập từ bàn phím.
- 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.
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 hay bằng giá của phương án, ngược lại cận trên là giá trị lớn hơn hay bằng giá của phương án.
Để dễ hình dung ta sẽ xét hai bài toán quen thuộc là bài toán TSP và bài toán cái ba lô.
BÀI TOÁN ĐƯỜNG ĐI CỦA NGƯỜI GIAO HÀNG:
1. Giới thiệu: Bài toán tìm đường đi của người giao hàng là có một người giao hàng cần đi giao hàng tại n thành phố T1, T2… Xuất phát từ một thành phố nào đó, đi qua các thành phố khác để giao hàng và trở về thành phố ban đầu. Mỗi thành phố chỉ đến một lần. Biết Cij là chi phí đi từ thành phố Ti thành phố Tj (I = 1, 2, 3,…, n), hãy tìm hành trình với tổng chi phí là nhỏ nhất (một hành trình là một cách đi thỏa mãn điều kiện.
2. Hướng giải quyết:
- Cố định thành phố xuất phát là T1. Bài toán người đi giao hàng được đưa về bài toán: tìm cực tiểu của phiếm hàm:
F(x1, x2, …, xn) = c[1,x1]+c[x2,x3]+…+c[xn-1,xn]+c[xn,x1]→ min
- Với điều kiện
- Cmin = 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 (u1,u2,…,uk). Phương án tương ứng với hành trình bộ phận qua k thành phố:
T1→T(u2)→…→T(uk-1)→(uk)
-Vì vậy chi phí phải trả theo hành trình bộ phận này sẽ là tổng các chi phí
theo từng node của hành trình bộ phận.
∂=c[1,u2]+c[u2,u3]+…+c[uk-1,uk]
- Để phát triển hành trình bộ phận này thành hành trình đầy đủ, ta còn phải đi qua n-k thành phố còn lại rồi quay trở về thành phố T1, tức là còn phải đi qua n-j+1 đoạn đường nữa. Do đó chi phí phải trả cho việc đi qua mỗi trong n-k+1 đoạn đường còn lại đều không nhiều hơn cmin, nên cận dưới cho phương án bộ phận (u1, u2,…, uk) có thể được tính theo công thức
g(u1, u2, …, uk) =∂+(n-k+1)cmin
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.
Dưới đây là lưu đồ cho phần nhập:
end
Begin
i<=n; j<=n
i=1; j=1
Tăng i, j lên 1
Nhập n, C[j]
In C[j]
Dữ liệu được lấy từ trong tập tin test2.txt.
Sai
Đúngg
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);
printf("\n\t So thanh pho nhap vao la: %d\n",n);
printf("\n\t Ma tran chi phi nhap vao la: ");
for (i=1; i<=n; i++)
{
printf("\n\n");
for(j=1; j<=n;
{
fscanf(fp,"\t %d",&C[j]);
printf("\t %5d", C[j]);
}
printf("\n");
}
}
b) Tính cận dưới:
- Cận dưới tại mỗi nút là một số nhỏ hơn hay bằng giá của ...