Chia sẻ miễn phí cho các bạn tài liệu:
LỜI MỞ ĐẦU
Bài toán cây Steiner trong đồ thị là một bài toán NP-khó trong nhóm các bài toán thiết kế mạng (network designed problem). Bài toán tìm cây Steiner nhỏ nhất trên đồ thị được ứng dụng trong nhiều lĩnh vực thực tế như thiết kế mạng viễn thông, thiết kế vi mạch hay nghiên cứu sự tiến hóa trong sinh học…. Do tầm quan trọng của bài toán, rất nhiều hướng tiếp cận để giải xấp xỉ bài toán đã được đề xuất với mục đích đưa ra lời giải xấp xỉ tốt nhất với thời gian chấp nhận được.
Trong đồ án này trình bày cách giải quyết bài toán theo thuật toán di truyền, đây là một hướng giải quyết khá thành công. Cấu trúc đồ án gồm có năm chương như sau:
• Chương 1. Trình bày lý thuyết cơ sở về đồ thị và bài toán Cây Steiner.
• Chương 2. Trình bày lý thuyết cơ bản về giải thuật di truyền.
• Chương 3. Trình bày thuật toán di truyền giải bài toán Cây Steiner trên đồ thị.
• Chương 4. Các kết quả thực nghiệm.
• Chương 5. Hướng dẫn sử dụng chương trình.
Để có được kết quả này, em xin gửi lời Thank chân thành nhất đến cô giáo Ths.Huỳnh Thị Thanh Bình bộ môn khoa học máy tính, cơ đã tận tình hướng dẫn, chỉ bảo em trong quá trình thực tập và làm đồ án. Em xin gửi lời Thank đến thầy Nguyễn Việt Huy bộ môn khoa học máy tính, thầy đã nhiệt tình giúp đỡ em trong việc tìm hiểu bài toán. Em xin gửi lời Thank đến tất cả các thầy cô trong bộ môn khoa học máy tính, các thầy cô đã giúp chúng em có rất nhiều kiến thức rất bổ ích. Cuối cùng, em xin gửi lời Thank đến gia đình và bạn bè, mọi người là nguồn động viên tinh thần rất lớn cho em!
Hà nội, tháng 5 năm 2008
Sinh viên
Nguyễn Thanh Tăng
CHƯƠNG 1
GIỚI THIỆU BÀI TOÁN
1. Một số các khái niệm cơ sở
1.1. Đồ thị
1.1.1. Định nghĩa đồ thị
Đồ thị là một cấu trúc rời rạc bao gồm các đỉnh và các cạnh nối các đỉnh này, các loại đồ thị được phân biệt bởi sự khác biệt giữa kiểu cũng như số lượng cạnh nối các đỉnh của đồ thị. Trong các tài liệu, khái niệm về đồ thị đôi khi được đề cập không đồng nhất, dưới đây đưa ra một số định nghĩa về đồ thị [32].
Hình 1.1. Đồ thị vô hướng (trái) và đồ thị có hướng (phải).
Định nghĩa 1: Đơn đồ thị vô hướng G=(V, E) bao gồm V là tập các đỉnh, và E là tập các cặp không có thứ tự gồm hai phần tử khác nhau của V gọi là cạnh.
Định nghĩa 2: Đa đồ thị vô hướng G=(E, V) bao gồm V là tập các đỉnh và E là họ các cặp không có thứ tự gồm hai phần tử khác nhau của V gọi là các cạnh. Hai cạnh e1 và e2 được gọi là cạnh lặp nếu chúng cùng tương ứng với một cặp đỉnh.
Đồ thị có trọng số là một khái niệm hết sức quan trọng trong các nghiên cứu lý thuyết về đồ thị bởi tính ứng dụng rộng dãi của nó. Ví dụ, một mạng máy tính mô phỏng bằng đồ thị thì trọng số có thể là khoảng cách vật lý hay thông lượng truyền dữ liệu giữa hai máy tính được nối trực tiếp trong mạng, một mạng lưới giao thông có thể được mô phỏng bằng một đồ thị có trọng số trong đó trọng số của mỗi cạnh nối hai đỉnh có thể được dựng để biểu diễn khoảng cách vật lý của đoạn đường nối hai điểm này… Trên thực tế, có rất nhiều bài toán được mô phỏng rất mềm dẻo trên đồ thị và đã cho những kết quả lời giải rất tốt.
/file/d/0Bz7Zv9 ... sp=sharing
