Chia sẻ cho anh em link tải luận văn miễn phí Một số phương pháp Heuristic giải bài toán thiết kế mạng viễn thông
MỞ ĐẦU
Cơ sở khoa học của đề tài
Hiện nay, việc trao đổi thông tin qua các thiết bị không dây ngày càng trở nên
phổ biến. Để nâng cao chất lƣợng dịch vụ, các nhà mạng đang phải mở rộng hệ
thống mạng viến thông bằng cách tăng thêm số cột thu, nhận tín hiệu từ các thiết bị
không dây. Do đó các nhà mạng đều mong muốn có một mạng viễn thông hoạt
động hiệu quả, có hiệu suất cao và tiết kiệm đƣợc các chi phí mua thiết bị. Sử dụng
phƣơng pháp Heuristic là cách làm thiết thực để đƣa ra một thiết kế cho mạng viễn
thông một cách tối ƣu.
Nhận thấy tính thiết thực của bài toán này và đƣợc sự gợi ý của giảng viên
hƣớng dẫn, tui đã chọn đề tài “Một số p n p p eur st c ả bà to n t ết kế
mạng viễn t ôn ” làm đề tài cho luận văn tốt nghiệp của mình.
Mục tiêu và nhiệm vụ của luận văn
- Thu thập tài liệu và nghiên cứu về một số phƣơng pháp Heuristic
- Nghiên cứu để hiểu cách giải các bài toán tối ƣu bằng phƣơng pháp Heuristic
- Tìm hiểu bài toán thiết kế mạng viễn thông và vận dụng phƣơng pháp
heuristic để giải bài toán này.
- Xây dựng chƣơng trình mô phỏng bài toán trên máy tính và thực hiện các thử
nghiệm trên các bộ dữ liệu.
Đối tƣợng và phạm vi nghiên cứu
- Phƣơng pháp Heuristic nhƣ phƣơng pháp tham, giải thuật di truyền và mạng
nơ ron giải các bài toán tối ƣu tổ hợp
- Bài toán thiết kế mạng viễn thông
- Giải bài toán thiết kế mạng viễn thông bằng các phƣơng pháp Heurristic
Phƣơng pháp nghiên cứu
Tìm hiểu một số phƣơng pháp Heuristic giải bài toán thiết kế mạng Viễn
thông thông qua việc thu thập, tổng hợp các sách, các bài báo, các tài liệu trên mạng
bằng tiếng Việt, tiếng Anh.
Cấu trúc và nội dung chính của luận văn
Cấu trúc và nội dung chính của luận văn gồm:
- Phần mở đầu.
- Chƣơng 1. Giới thiệu một số phƣơng pháp Heuristic.
Chương này trình bày tổng quan về Thuật toán tham; Mạng nơ ron nhân tạo và
Giải thuật di truyền.
- Chƣơng 2. Tìm hiểu về tình hình truyền thông bằng thiết bị không dây của
thành phố Thái Nguyên.
Chương này Giới thiệu chung về hệ thống Viễn thông thành phố Thái Nguyên;
Tham khảo các số liệu thống kê về tình hình sử dụng các thiết bị không dây. Tìm
hiểu mục đích thiết kế mạng viễn thông không dây mới của thành phố.
- Chƣơng 3. Sử dụng một số phƣơng pháp Heuristic để giải bài toán thiết kế mạng
Viễn thông.
Nêu phát biểu bài toán và ứng dụng một số phương pháp Heuristic giải bài toán
thiết kế mạng Viễn thông. Đề xuất các thử nghiệm và kết quả.
- Phần kết luận và đề nghị.
- Tài liệu tham khảo.
Chƣơng 1
GIỚI THIỆU MỘT SỐ PHƢƠNG PHÁP HEURISTIC
1.1. Thuật toán tham lam
1.1.1. Giới thiệu chung
* Định nghĩa
Giải thuật tham lam là một thuật toán giải quyết một bài toán dựa trên tri thức
về vấn đề để tìm kiếm một tối ƣu địa phƣơng ở mỗi bƣớc đi với hy vọng tìm đƣợc
tối ƣu toàn cục.
Giải thuật tham lam có 5 thành phần:
a) Một tập hợp các ứng viên để từ đó tạo ra lời giải;
b) Một hàm lựa chọn để lựa chọn ứng viên tốt nhất để bổ sung vào lời giải;
c) Một hàm khả thi dùng để quyết định một ứng viên có thể là một lời giải;
d) Một hàm mục tiêu để ấn định giá trị lời giải hay một lời giải chƣa hoàn chỉnh;
e) Một hàm đánh giá để chỉ ra khi nào ta tìm ra một lời giải hoàn chỉnh.
* Hai thành phần quyết định nhất tới quyết định tham lam
Tính chất lựa chọn tham lam: Chúng ta có thể lựa chọn giải pháp nào đƣợc đánh giá là
tốt nhất ở thời điểm hiện tại và sau đó giải bài toán con nảy sinh từ việc thực hiện lựa chọn
vừa rồi. Lựa chọn của thuật toán tham lam có thể phụ thuộc vào các lựa chọn trƣớc đó.
Thuật toán tiến triển theo kiểu thực hiện các chọn lựa theo một vòng lặp, cùng lúc
đó thu nhỏ bài toán đã cho về một bài toán con nhỏ hơn. Giải thuật tham lam lựa chọn
sớm và thay đổi đƣờng đi thuật toán theo lựa chọn đó, và không bao giờ xét lại các lựa
chọn cũ. Đối với một số bài toán, đây có thể là một thuật toán không chính xác.
Cấu trúc con tối ưu: Một bài toán đƣợc gọi là "có cấu trúc tối ƣu", nếu một lời
giải tối ƣu của bài toán con chứa lời giải tối ƣu của bài toán lớn hơn.
* Ý tƣởng của phƣơng pháp tham lam
Phƣơng pháp tham lam là kỹ thuật thiết kế thƣờng đƣợc dùng để giải các bài
toán tối ƣu. Phƣơng pháp đƣợc tiến hành theo nhiều bƣớc. Tại mỗi bƣớc, theo một
lựa chọn nào đó (xác định bằng một hàm chọn), sẽ tìm một lời giải tối ƣu cho bài
toán nhỏ tƣơng ứng. Lời giải của bài toán đƣợc bổ sung dần từng bƣớc từ lời giải
Do Drive thay đổi chính sách, nên một số link cũ yêu cầu duyệt download. các bạn chỉ cần làm theo hướng dẫn.
Password giải nén nếu cần: ket-noi.com | Bấm trực tiếp vào Link để tải:
MỞ ĐẦU
Cơ sở khoa học của đề tài
Hiện nay, việc trao đổi thông tin qua các thiết bị không dây ngày càng trở nên
phổ biến. Để nâng cao chất lƣợng dịch vụ, các nhà mạng đang phải mở rộng hệ
thống mạng viến thông bằng cách tăng thêm số cột thu, nhận tín hiệu từ các thiết bị
không dây. Do đó các nhà mạng đều mong muốn có một mạng viễn thông hoạt
động hiệu quả, có hiệu suất cao và tiết kiệm đƣợc các chi phí mua thiết bị. Sử dụng
phƣơng pháp Heuristic là cách làm thiết thực để đƣa ra một thiết kế cho mạng viễn
thông một cách tối ƣu.
Nhận thấy tính thiết thực của bài toán này và đƣợc sự gợi ý của giảng viên
hƣớng dẫn, tui đã chọn đề tài “Một số p n p p eur st c ả bà to n t ết kế
mạng viễn t ôn ” làm đề tài cho luận văn tốt nghiệp của mình.
Mục tiêu và nhiệm vụ của luận văn
- Thu thập tài liệu và nghiên cứu về một số phƣơng pháp Heuristic
- Nghiên cứu để hiểu cách giải các bài toán tối ƣu bằng phƣơng pháp Heuristic
- Tìm hiểu bài toán thiết kế mạng viễn thông và vận dụng phƣơng pháp
heuristic để giải bài toán này.
- Xây dựng chƣơng trình mô phỏng bài toán trên máy tính và thực hiện các thử
nghiệm trên các bộ dữ liệu.
Đối tƣợng và phạm vi nghiên cứu
- Phƣơng pháp Heuristic nhƣ phƣơng pháp tham, giải thuật di truyền và mạng
nơ ron giải các bài toán tối ƣu tổ hợp
- Bài toán thiết kế mạng viễn thông
- Giải bài toán thiết kế mạng viễn thông bằng các phƣơng pháp Heurristic
Phƣơng pháp nghiên cứu
Tìm hiểu một số phƣơng pháp Heuristic giải bài toán thiết kế mạng Viễn
thông thông qua việc thu thập, tổng hợp các sách, các bài báo, các tài liệu trên mạng
bằng tiếng Việt, tiếng Anh.
Cấu trúc và nội dung chính của luận văn
Cấu trúc và nội dung chính của luận văn gồm:
- Phần mở đầu.
- Chƣơng 1. Giới thiệu một số phƣơng pháp Heuristic.
Chương này trình bày tổng quan về Thuật toán tham; Mạng nơ ron nhân tạo và
Giải thuật di truyền.
- Chƣơng 2. Tìm hiểu về tình hình truyền thông bằng thiết bị không dây của
thành phố Thái Nguyên.
Chương này Giới thiệu chung về hệ thống Viễn thông thành phố Thái Nguyên;
Tham khảo các số liệu thống kê về tình hình sử dụng các thiết bị không dây. Tìm
hiểu mục đích thiết kế mạng viễn thông không dây mới của thành phố.
- Chƣơng 3. Sử dụng một số phƣơng pháp Heuristic để giải bài toán thiết kế mạng
Viễn thông.
Nêu phát biểu bài toán và ứng dụng một số phương pháp Heuristic giải bài toán
thiết kế mạng Viễn thông. Đề xuất các thử nghiệm và kết quả.
- Phần kết luận và đề nghị.
- Tài liệu tham khảo.
Chƣơng 1
GIỚI THIỆU MỘT SỐ PHƢƠNG PHÁP HEURISTIC
1.1. Thuật toán tham lam
1.1.1. Giới thiệu chung
* Định nghĩa
Giải thuật tham lam là một thuật toán giải quyết một bài toán dựa trên tri thức
về vấn đề để tìm kiếm một tối ƣu địa phƣơng ở mỗi bƣớc đi với hy vọng tìm đƣợc
tối ƣu toàn cục.
Giải thuật tham lam có 5 thành phần:
a) Một tập hợp các ứng viên để từ đó tạo ra lời giải;
b) Một hàm lựa chọn để lựa chọn ứng viên tốt nhất để bổ sung vào lời giải;
c) Một hàm khả thi dùng để quyết định một ứng viên có thể là một lời giải;
d) Một hàm mục tiêu để ấn định giá trị lời giải hay một lời giải chƣa hoàn chỉnh;
e) Một hàm đánh giá để chỉ ra khi nào ta tìm ra một lời giải hoàn chỉnh.
* Hai thành phần quyết định nhất tới quyết định tham lam
Tính chất lựa chọn tham lam: Chúng ta có thể lựa chọn giải pháp nào đƣợc đánh giá là
tốt nhất ở thời điểm hiện tại và sau đó giải bài toán con nảy sinh từ việc thực hiện lựa chọn
vừa rồi. Lựa chọn của thuật toán tham lam có thể phụ thuộc vào các lựa chọn trƣớc đó.
Thuật toán tiến triển theo kiểu thực hiện các chọn lựa theo một vòng lặp, cùng lúc
đó thu nhỏ bài toán đã cho về một bài toán con nhỏ hơn. Giải thuật tham lam lựa chọn
sớm và thay đổi đƣờng đi thuật toán theo lựa chọn đó, và không bao giờ xét lại các lựa
chọn cũ. Đối với một số bài toán, đây có thể là một thuật toán không chính xác.
Cấu trúc con tối ưu: Một bài toán đƣợc gọi là "có cấu trúc tối ƣu", nếu một lời
giải tối ƣu của bài toán con chứa lời giải tối ƣu của bài toán lớn hơn.
* Ý tƣởng của phƣơng pháp tham lam
Phƣơng pháp tham lam là kỹ thuật thiết kế thƣờng đƣợc dùng để giải các bài
toán tối ƣu. Phƣơng pháp đƣợc tiến hành theo nhiều bƣớc. Tại mỗi bƣớc, theo một
lựa chọn nào đó (xác định bằng một hàm chọn), sẽ tìm một lời giải tối ƣu cho bài
toán nhỏ tƣơng ứng. Lời giải của bài toán đƣợc bổ sung dần từng bƣớc từ lời giải
Do Drive thay đổi chính sách, nên một số link cũ yêu cầu duyệt download. các bạn chỉ cần làm theo hướng dẫn.
Password giải nén nếu cần: ket-noi.com | Bấm trực tiếp vào Link để tải:
You must be registered for see links