Luận văn thạc sỹ: Nghiên cứu xây dựng thuật toán giải bài toán tìm đường đi ngắn nhất với dữ liệu mở dạng khoảng

Chia sẻ: Tyter Ewtt | Ngày: | Loại File: DOC | Số trang:88

Thêm vào BST

Báo xấu

353
lượt xem 106
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Nghiêu cứu ưń g duṇ g logic mờ trong tin hoc̣ và thuâṭ toań tim̀ đươǹ g đi ngăń nhât́ có cung là troṇ g số xać điṇ h từ đó xây dưṇ g thuâṭ toań giải bài toán tim̀ đường đi ngắn nhất có cung với số mờ dạng khoảng. Đưa ra mô phon̉ g thuâṭ toań giaỉ baì toań tim̀ đươǹ g đi ngăń nhât́ vơí troṇ g số là số mờ daṇ g khoan̉ g từ giaỉ thuâṭ Dijsktra và lý thuyết mờ quy hoạch tuyến tính dạng khoảng....

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Luận văn thạc sỹ: Nghiên cứu xây dựng thuật toán giải bài toán tìm đường đi ngắn nhất với dữ liệu mở dạng khoảng

BỘ GIÁO DỤC VÀ ĐÀO TẠO BỘ QUỐC PHÒNG HỌC VIỆN KỸ THUẬT QUÂN SỰ PHAN NHƯ MINH NGHIÊN CỨU, XÂY DỰNG THUÂT TOAN GIAI BAI TOAN TIM ̣ ́ ̉ ̀ ́ ̀ ĐƯỜNG ĐI NGĂN NHÂT VỚI DỮ LIÊU MỜ DANG KHOANG ́ ́ ̣ ̣ ̉ Chuyên ngành: Hệ thống thông tin LUẬN VĂN THẠC SĨ KỸ THUẬT Hà Nội - Năm 2011
BỘ GIÁO DỤC VÀ ĐÀO TẠO BỘ QUỐC PHÒNG HỌC VIỆN KỸ THUẬT QUÂN SỰ PHAN NHƯ MINH NGHIÊN CỨU, XÂY DỰNG THUÂT TOAN GIAI BAI TOAN TIM ̣ ́ ̉ ̀ ́ ̀ ĐƯỜNG ĐI NGĂN NHÂT VỚI DỮ LIÊU MỜ DANG KHOANG ́ ́ ̣ ̣ ̉ Chuyên ngành: Hệ thống thông tin Mã số: 60 48 05 LUẬN VĂN THẠC SĨ KỸ THUẬT Hà Nội - Năm 2011
CÔNG TRÌNH ĐƯỢC HOÀN THÀNH TẠI HỌC VIỆN KỸ THUẬT QUÂN SỰ Cán bộ hướng dẫn chính: PGS.TS. Nguyễn Thiện Luận Cán bộ chấm phản biện 1: .................................................................. Cán bộ chấm phản biện 2: .................................................................. Luận văn thạc sĩ được bảo vệ tại: HỘI ĐỒNG CHẤM LUẬN VĂN THẠC SĨ HỌC VIỆN KỸ THUẬT QUÂN SỰ Ngày tháng năm 2011
HỌC VIỆN KỸ THUẬT QUÂN SỰ CỘNG HOÀ XÃ HỘI CHỦ NGHĨA VIỆT NAM PHÒNG SAU ĐẠI HỌC Độc lập – Tự do – Hạnh phúc Hà Nội, ngày 12 tháng 05 năm 2011 NHIỆM VỤ LUẬN VĂN THẠC SĨ Họ tên học viên: PHAN NHƯ MINH Giới tính: Nam Nơi sinh: Vĩnh Phúc Ngày, tháng, năm sinh: 23/09/1978 Hệ thống thông tin Mã số: 60 48 05 Chuyên ngành: I- TÊN ĐỀ TÀI: Nghiên cứu, xây dựng thuât toan giai bai toan tim đường đi ngăn nhât ̣ ́ ̉ ̀ ́̀ ́ ́ với dữ liêu mờ dang khoang. ̣ ̣ ̉ II- NHIỆM VỤ VÀ NỘI DUNG: Trên cơ sở nghiên cứu, thuât toan Dijkstra: Mở rông, cai tiên ap dung ̣ ́ ̣ ̉ ́́ ̣ cho bai toan (Tim đường đi ngăn nhât) với cac dữ liêu về có trong số dang ̀ ́ ̀ ́ ́ ́ ̣ ̣ ̣ ̉ khoang. Đặt ra và giải quyết bài toán tìm đường đi ngắn nh ất với độ dài các cung là số mờ dạng khoảng 12/10/2010 III- NGÀY GIAO NHIỆM VỤ: 05/05/2011 IV- NGÀY HOÀN THÀNH NHIỆM VỤ: V- CÁN BỘ HƯỚNG DẪN: PGS.TS. Nguyễn Thiện Luận CÁN BỘ HƯỚNG DẪN CHỦ NHIỆM BỘ MÔN QL CHUYÊN NGÀNH PGS.TS. Nguyễn Thiện Luận Nội dung và đề cương luận văn thạc sĩ đã được Hội đồng chuyên ngành thông qua. Ngày tháng năm 2011 TRƯỞNG PHÒNG SĐH TRƯỞNG KHOA QL NGÀNH
MỤC LỤC Trang Trang phụ bìa...................................................................................................... Nhiệm vụ luận văn............................................................................................ Mục lục............................................................................................................... Tóm tắt luận văn................................................................................................ Danh mục hình vẽ.............................................................................................. MỞ ĐẦU...................................................................................................................................................................1 1. LÝ DO CHỌN ĐỀ TÀI............................................................................................................................................1 TRONG NHỮNG NĂM GẦN ĐÂY, CÁC PHƯƠNG PHÁP TỐI ƯU HOÁ NGÀY CÀNG ĐƯỢC ÁP DỤNG SÂU RỘNG VÀ HIỆU QUẢ VÀO CÁC NGÀNH GIAO THÔNG VẬN TẢI, MẠNG VIỄN THÔNG, KINH TẾ, KỸ THUẬT, CÔNG NGHỆ THÔNG TIN VÀ CÁC NGÀNH KHOA HỌC KHÁC. CÁC PHƯƠNG PHÁP TỐI ƯU LÀ CÔNG CỤ ĐẮC LỰC GIÚP NGƯỜI LÀM QUYẾT ĐỊNH CÓ NHỮNG GIẢI PHÁP TỐT NHẤT VỀ ĐỊNH LƯỢNG VÀ ĐỊNH TÍNH. ...................................................1 2. MỤC ĐÍCH NGHIÊN CỨU.......................................................................................................................................3 3. PHẠM VI NGHIÊN CỨU..........................................................................................................................................3 4. PHƯƠNG PHÁP NGHIÊN CỨU.................................................................................................................................3 1.1. KHÁI NIỆM CƠ BẢN VỀ LÝ THUYẾT ĐỒ THỊ...........................................................................................................5 1.1.1. Cac đinh nghia về đồ thi:.....................................................................................................................5 ̣́ ̃ ̣ 1.1.2. Bâc cua đồ thi.......................................................................................................................................8 ̣ ̉ ̣ 1.1.3. Biêu diên đồ thị băng ma trân............................................................................................................10 ̉ ̃ ̀ ̣ ́ 1.1.4. Tinh liên thông...................................................................................................................................11 1.1.5. Đường đi Euler và đồ thị Euler.........................................................................................................17 1.1.6. Bài toán người phát thư Trung Hoa:................................................................................................21 1.1.7. Đường đi Hamilton và đồ thị Hamilton...........................................................................................24 1.2. ĐỒ THỊ CÓ TRỌNG SỐ VÀ BÀI TOÁN TÌM ĐƯỜNG ĐI NGẮN NHẤT.............................................................................29 1.2.1. Bài toán tìm đường đi ngắn nhất:....................................................................................................30 1.2.2. Thuật toán Dijkstra:...........................................................................................................................31 ̀ ́́ ̣ 1.2.3. Bai toan ap dung: ...............................................................................................................................32 1.2.3. Thuật toán Floyd:...............................................................................................................................34 2.1. KHÁI NIỆM TẬP MỜ........................................................................................................................................36 2.1.1. Định nghĩa tập mờ ............................................................................................................................36 2.1.2. Một số khái niệm của tập mờ.........................................................................................................38 HÌNH 2.3. MIÊN CUA TÂP MỜ........................................................................................................................39 ̀ ̉ ̣ 2.1.3. Các ví dụ về tập mờ.........................................................................................................................39 2.2. CÁC PHÉP TOÁN TRÊN TẬP MỜ ........................................................................................................................41 2.2.1. Các phép toán trên tập hợp...............................................................................................................41 2.2.2. Khái niệm hàm liên thuộc ................................................................................................................42 2.3. MỆNH ĐỀ VÀ CÔNG THỨC...............................................................................................................................43 2.3.1. Khái niệm mệnh đề..........................................................................................................................43
2.3.2. Các kí hiệu.........................................................................................................................................44 2.3.3. Các phép toán trên mệnh đề.............................................................................................................44 2.3.4. Các tính chất......................................................................................................................................47 2.4. SUY LUẬN XẤP XỈ DỰA TRÊN LOGIC MỜ.............................................................................................................48 2.5. ỨNG DỤNG LOGIC MỜ XÂY DỰNG BÀI TOÁN TỐI ƯU MƠ......................................................................................51 ̀ 2.5.1. Tối ưu mờ..........................................................................................................................................51 3.1. MÔ HÌNH BÀI TOÁN........................................................................................................................................55 3.2. VÍ DỤ..........................................................................................................................................................56 3.3. BÀI TOÁN TÌM ĐƯỜNG ĐI NGẮN NHẤT CÓ CÁC CUNG MỜ......................................................................................56 3.3.1. Xây dựng tập mờ..............................................................................................................................57 3.3.2. Miền xác định của tập mờ:..............................................................................................................57 3.3.3. Miền tin cậy của tập mờ..................................................................................................................58 3.3.4. Miền biên của tập mờ......................................................................................................................58 3.4. KHÁI NIỆM SỐ MỜ.........................................................................................................................................59 3.4.1. Định nghĩa số mờ..............................................................................................................................59 3.4.2. Số mờ dạng tam giác:.......................................................................................................................59 3.4.3. Số mờ dạng hình thang:....................................................................................................................60 3.5. MỘT SỐ PHƯƠNG PHÁP GIẢI QUYẾT BÀI TOÁN....................................................................................................62 3.5.1. Phép toán thực hiện trên số mờ tam giác.........................................................................................62 3.6. VÍ DỤ ÁP DỤNG BÀI TOÁN:.............................................................................................................................63 4.1. MỘT SỐ GIAO DIỆN CỦA CHƯƠNG TRÌNH...........................................................................................................65 4.1.1. Giao diện chính của chương trình....................................................................................................65 4.1.2. Cac bước thực hiên chương trinh.....................................................................................................65 ́ ̣ ̀ 4.1.3. Các chức năng chính của chương trình............................................................................................66 4.2. CÀI ĐẶT – THỬ NGHIỆM.................................................................................................................................69 4.3. ĐÁNH GIÁ HIỆU QUẢ THUẬT TOÁN ĐÃ XÂY DỰNG................................................................................................71 1. KẾT LUẬN.......................................................................................................................................................73 2. KIẾN NGHỊ.......................................................................................................................................................74 TÀI LIỆU THAM KHẢO....................................................................................................................................75
Tóm tắt luận văn Họ và tên học viên: Phan Như Minh Lớp: Hệ thống thông tin Khoá: 21 Cán bộ hướng dẫn: PGS.TS. Nguyễn Thiện Luận Tên đề tài: Nghiên cứu, xây dựng thuât toan giai bai toan tim đường ̣ ́ ̉ ̀ ́̀ đi ngăn nhât với dữ liêu mờ dang khoang. ́ ́ ̣ ̣ ̉ Tóm tắt: Nghiêu cứu ứng dung logic mờ trong tin hoc và thuât toan ̣ ̣ ̣ ́ tim đường đi ngăn nhât có cung là trong số xac đinh từ đó xây dựng thuât ̀ ́ ́ ̣ ́ ̣ ̣ toan giai bai toan tim đường đi ngăn nhât có cung với số mờ dang khoang. ́ ̉̀ ́̀ ́ ́ ̣ ̉ Đưa ra mô phong thuât toan giai bai toan tim đường đi ngăn nhât với ̉ ̣ ́ ̉ ̀ ́̀ ́ ́ trong số là số mờ dang khoang từ giai thuât Dijsktra và lý thuy ết mờ quy ̣ ̣ ̉ ̉ ̣ ̣ ́́ ̣ ̉ hoach tuyên tinh dang khoang. ̉ ̀ ̣  Kiêm tra ham liên thuôc.  Tim ra tât cả cac đường đi từ cac cung mờ. ̀ ́ ́ ́  Tim ra độ dai cung mờ nhỏ nhât giá trị Lmin. ̀ ̀ ́  Tinh ra độ tương tự. ́  Tim ra đường đi ngăn nhât từ cac cung mờ với độ tương tự cao ̀ ́ ́ ́ ́ nhât.
DANH MỤC HÌNH VẼ Hinh 1.1 Đơn đồ thi, giả đồ thị......................................................................6 ̀ ̣ Hinh 1.2. Đồ thị có hướng và Đa đồ thị có hướng.......................................7 ̀ Hinh 1.3. Bâc cua đồ thi................................................................................ 8 ̀ ̣ ̉ ̣ Hình 1.4. Bâc cua đồ thị có hướng................................................................9 ̣ ̉ Hinh 1.5. Biêu diên đồ thị băng ma trân liên kề............................................10 ̀ ̉ ̃ ̀ ̣ ̀ Hinh 1.6. Biêu diên đồ thị băng ma trân liên kề............................................10 ̀ ̉ ̃ ̀ ̣ ̀ Hinh 1.7. Biêu diên đồ thị băng ma trân liên thuôc.......................................11 ̀ ̉ ̃ ̀ ̣ ̣ Hinh 1.8. Biêu diên đường đi sơ câp............................................................ 12 ̀ ̉ ̃ ́ Hinh 1.9. Biêu diên đồ thị G và G’................................................................12 ̀ ̉ ̃ Hinh 1.10. Biêu diễn các đỉnh cắt là v, w, s và các cầu là (x,v), (w,s).........13 ̀ ̉ Hinh 1.11. Đồ thị G là liên thông mạnh đồ thị G’ là liên thông yếu...........15 ̀ Hinh 1.12. Biêu diên Đường đi Euler và đồ thị Euler...................................17 ̀ ̉ ̃ Hinh 1.13. Đồ thị Euler và đồ thị nửa Euler..................................................18 ̀ Hinh 1.14. Xây dựng đường đi.....................................................................18 ̀ Hinh 1.15. Xây dựng đường đi.....................................................................19 ̀ Hinh 1.16. Xây dựng đường đi.....................................................................20 ̀ Hinh 1.17. Xây dựng đường đi GT và G......................................................22 ̀ Hinh 1.18. Chu trình sơ cấp chứa tất cả các đỉnh của đồ thị......................24 ̀ Hinh 1.19. Chu trình sơ cấp chứa tất cả các đỉnh của đồ thị......................25 ̀ Hinh 1.20. Đồ thị Hamilton...........................................................................27 ̀ Hinh 1. 21. Đồ thị phân đôi........................................................................... 28 ̀ Hinh 1.22. Tim đường đi ngăn nhât d(a,v) của đồ thị..................................29 ̀ ̀ ́ ́
Hình 2.1. Tâp mờ..........................................................................................34 ̣ Hình 2. 2. Đồ thị ham liên thuôc cua tâp mờ................................................ 35 ̀ ̣ ̣̉ Hình 2.3. Miên cua tâp mờ............................................................................37 ̀ ̣̉ Hình 2.4. Đồ thị đanh gia...............................................................................38 ́ ́ Hình 2. 5. Đồ thị đanh giá nhiêt đô................................................................38 ́ ̣ ̣ Hình 2.6. Ví dụ ham liên thuôc......................................................................41 ̀ ̣ ̉ ̀ ̃ ́̉ Bang 2.7. Mô hinh suy diên xâp si................................................................ 48 Bang 1.8. Suy luận xấp xỉ............................................................................ 46 ̉ Bang 1.9. Bang điêu kiên suy diên xâp sỉ......................................................47 ̉ ̉ ̀ ̣ ̃ ́ Hinh 3.1. Đồ thị G(u,v) có hướng.................................................................54 ̀ Hinh 3.2. Miên biên cua tâp mờ....................................................................56 ̀ ̀ ̣̉ Hình 3.3. Số mờ dang tam giac.....................................................................57 ̣ ́ Hình 3.4. Số mờ dang hinh thang..................................................................58 ̣ ̀ Hình 3.4.Biêu diên số mờ dang hinh thang...................................................58 ̉ ̃ ̣ ̀ Hình 3.5.Tim đường đi ngăn nhât ................................................................60 ̀ ́ ́ Hình 4.1. Giao diên chinh cua chương trinh.................................................62 ̣ ́ ̉ ̀ Hình 4.2. Cac bước thực hiên.......................................................................62 ́ ̣ ̉ ̣ ́ Hình 4.3. Mô phong thuât toan......................................................................63 Hình 4.4. Chon số đinh..................................................................................63 ̣ ̉ Hình 4.5. Chon cung đường đi......................................................................64 ̣ Hình 4.6. Nhâp cac cung a, b, c và thông bao............................................... 64 ̣ ́ ́ Hình 4.7. Tim tât cả cac đường đi.................................................................65 ̀ ́ ́ Hình 4.7. Tinh giá trị Lmin............................................................................65 ́ Hình 4.8. Bang độ tương tự.......................................................................... 66 ̉ Hình 4.9. Bang thông bao kêt quả tim được ................................................66 ̉ ́ ́ ̀ Hình 4.10. Chon đinh nhâp dữ liêu...............................................................67 ̣ ̉ ̣ ̣ Hình 4.11. Kêt quả kiêm tra xây dựng ham liên .......................................... 67 ́ ̉ ̀
Hình 4.12. Kêt quả tât cả cac đường đi.........................................................68 ́ ́ ́ Hình 4.13. Bang kêt quả tim Lmin................................................................ 68 ̉ ́ ̀ Hình 4.14. Bang kêt quả độ tương tự........................................................... 68 ̉ ́ Hình 4.15. Bang kêt quả đường đi ngăn nhât............................................... 68 ̉ ́ ́ ́
DANH MỤC BANG ̉ Bang 1.1. Kết quả tính toán theo thuật toán Dijkstra.................................. 31 ̉ Bang 2.1. Phep phủ đinh................................................................................42 ̉ ́ ̣ ̉ ́ ̣ Bang 2.2. Phep hoăc...................................................................................... 43 ̉ ́ Bang 2.3. Phep nhân logic.............................................................................43 ̉ ́ ̣ Bang 2.4. Phep công XOR.............................................................................44 ̉ ́ ́ Bang 2.5. Phep keo theo................................................................................44 Bang 2.6. Phep tương đương........................................................................45 ̉ ́ ̉ ̉ ́ Bang 2.7. Bang chân ly..................................................................................45 Bang 2.8. Suy luận xấp xỉ............................................................................ 46 ̉ Bang 2.9. Bang điêu kiên suy diên xâp sỉ......................................................47 ̉ ̉ ̀ ̣ ̃ ́ Bang 3.1. Độ tương tự giữa hai số mờ.......................................................60 ̉
1 MỞ ĐẦU 1. Lý do chọn đề tài Trong những năm gần đây, các phương pháp tối ưu hoá ngày càng được áp dụng sâu rộng và hiệu quả vào các ngành giao thông vận tải, mạng viễn thông, kinh tế, kỹ thuật, công nghệ thông tin và các ngành khoa học khác. Các phương pháp tối ưu là công cụ đắc lực giúp người làm quyết định có những giải pháp tốt nhất về định lượng và định tính. Một trong những lớp bài toán tối ưu đầu tiên được nghiên cứu là thuật toán giai bài toán tim đường đi ngăn nhât có trọng số xác định. ̉ ̀ ́ ́ Bài toán tìm đường đi ngắn nhất là vấn đề quan trọng trong lý thuy ết đồ thị, nó đã được nghiên cứu từ lâu và có nhi ều ứng dụng trong nhiều ngành khoa học nói chung, khoa học máy tính và hệ thông thông tin nói ́ riêng. Nhiều giải thuật (Dijkstra, Bellman-Ford, Floyd...) đã được phát tri ển để tìm đường đi ngắn nhất và ngay nay đã được nhiêu nhà nghiên cứu nhăm ̀ ̀ ̀ cai tiên xây dựng giai thuât giai bai toan tim đường đi ngăn nhât với dữ liêu ̉ ́ ̉ ̣ ̉ ̀ ́̀ ́ ́ ̣ mờ dang khoang. ̣ ̉ Bài toán tìm đường đi ngắn nhất cũng được phát triển rông rai và trở ̣ ̃ thành một chuyên ngành toán học từ những năm 1950. Giải đáp những câu hỏi đặt ra mà tim đường đi ngăn nhât với cac canh có trong số xac đinh. ̀ ́ ́ ́ ̣ ̣ ̣́ Có một số thuật toán tìm đường đi ngắn nhất; ở đây, ta có thu ật toán do E. Dijkstra, nhà toán học người Hà Lan, đề xuất năm 1959. Trong bao cao nay ́ ́ ̀ mà tôi sẽ trình bày, người ta giả sử đồ thị là vô hướng các trọng số là dương. Chỉ cần thay đổi đôi chút là có thể giải được bài toán tìm đ ường đi ng ắn nhất trong đồ thị có hướng. Phương pháp của thuật toán Dijkstra là: Xác định tuần tự đỉnh có khoảng cách đến u0 từ nhỏ đến lớn.
2 Nhưng câu hoi cân đăt ra là nêu trong số đã cho được biêu diên là môt ̉̀ ̣ ́ ̣ ̉ ̃ ̣ cung mở thuôc khoang ( a,b) thì sao? ̣ ̉ Nêu trong số có khoang năm ở đường biên trai thì có thể cac phương an ́ ̣ ̉ ̀ ́ ́ ́ là châp nhân được. ́ ̣ Nêu trong số có khoang năm ở đường biên phai thì khó có thể châp ́ ̣ ̉ ̀ ̉ ́ nhân được đó là đường đi tôi ưu, do vây ta chưa thể khăng đinh được đo ́ la ̀ ̣ ́ ̣ ̉ ̣ đường đi ngăn nhât vì giả sử bên canh cung đó con có cac cung khac liên kề ́ ́ ̣ ̀ ́ ́ ̀ và có trong số gân như tương đương thì sao? ̣ ̀ Nêu ap dung giai thuât ( Dijkstra, Bellman-Ford, Floyd...) thì rât khó ́́ ̣ ̉ ̣ ́ mới có thể tim ra được theo hướng đi ngăn nhât và tôi ưu. ̀ ́ ́ ́ Ví dụ : Trong môt chuyên đi du lich từ thanh phố A đên thanh phố E ̣ ́ ̣ ̀ ́ ̀ Vân biêt răng : A có thể đi hai đường. ̃ ́̀ A đi qua B rôi lai từ B đi đên D sau đó đên E. ̣̀ ́ ́ A đi qua C rôi lai từ C đi đên D sau đó đên E. ̣̀ ́ ́ Giả sử : Đường đi từ A→ B và A→ C là môt cung được biêu diên là ̣ ̉ ̃ môt cung mờ dang khoang thì sao? ̣ ̣ ̉ Để giai quyêt bai toan trên: Nhờ ứng dung logic mờ trong tin hoc. Bai ̉ ́ ̀ ́ ̣ ̣ ̀ toan tôi ưu bai toan quy hoach tuyên tinh dang khoang sẽ giup ta giai quyêt ́ ́ ̀ ́ ̣ ́́ ̣ ̉ ́ ̉ ́ vân đề nay. ́ ̀ Một phương án chấp nhận được được gọi là nghiệm hữu hiệu nếu không tồn tại một phương án chấp nhận được khác tốt hơn nó, ít nh ất là theo một mục tiêu, còn các mục tiêu khác không tồi hơn. Tuy nhiên, khối lượng tính toán của các thuật toán này tăng nhanh khi kích thước của bài toán tim đường đi ngăn nhât với cac cung khoang mờ cho ̀ ́ ́ ́ ̉ đường đi là quá lớn (tức số ràng buộc của miền chấp nhận, số chiều của không gian quyết định và số hàm mục tiêu) tăng.
3 Trong những năm gần đây nhiều nhà toán học đã chuy ển sang nghiên cứu giải quyết bài toán tim đường đi ngăn nhât có trong số là cac cung mờ ̀ ́ ́ ̣ ́ dang khoang. Trong báo cáo này, tôi sẽ trình bày thuật toán giai bai toan tim ̣ ̉ ̉̀ ́ ̀ đường đi ngăn nhât với dữ liêu mờ dang khoang. ́ ́ ̣ ̣ ̉ Vì những lý do trên, tôi chọn đề tài “Nghiên cứu, xây dựng thuât toan ̣ ́ giai bai toan tim đường đi ngăn nhât với dữ liêu mờ dang khoang.” làm ̉ ̀ ́̀ ́ ́ ̣ ̣ ̉ đề tài nghiên cứu của mình. 2. Mục đích nghiên cứu Nghiên cứu, thuât toan Dijkstra: Mở rông, cai tiên ap dung cho bai ̣ ́ ̣ ̉ ́́ ̣ ̀ toan (Tim đường đi ngăn nhât) với cac dữ liêu về có trong số dang khoang. ́ ̀ ́ ́ ́ ̣ ̣ ̣ ̉ Giải quyết bài toán tìm đường đi ngắn nhất với độ dài các cung là số mờ dạng khoảng. 3. Phạm vi nghiên cứu Trên cơ sở nghiên cứu, thuât toan Dijkstra: Mở rông, cai tiên ap dung ̣ ́ ̣ ̉ ́́ ̣ cho bai toan (Tim đường đi ngăn nhât) với cac dữ liêu về có trong số dang ̀ ́ ̀ ́ ́ ́ ̣ ̣ ̣ ̉ khoang. Dừng lại ở khâu Tim đường đi ngăn nhât với cac dữ liêu về có trong ̀ ́ ́ ́ ̣ ̣ số dang khoang. ̣ ̉ 4. Phương pháp nghiên cứu Nghiên cứu, thuât toan Dijkstra: Mở rông, cai tiên ap dung cho bai ̣ ́ ̣ ̉ ́́ ̣ ̀ toan (Tim đường đi ngăn nhât) với cac dữ liêu về có trong số dang khoang. ́ ̀ ́ ́ ́ ̣ ̣ ̣ ̉ Giải quyết bài toán tìm đường đi ngắn nhất với độ dài các cung là số mờ dạng khoảng. Xây dựng phần mềm thử nghiệm. Phân tích đánh giá kết quả để ứng dụng thực tế.
4 Nội dung của luận văn được trình bày trong 4 chương. Chương 1. Lý thuyêt đồ thị và thuât toan giai bai toan tim đường đi ́ ̣ ́ ̉ ̀ ́̀ ngăn nhât có trong số xac đinh ́ ́ ̣ ̣́ Chương 2. Lý thuyêt mờ và ứng dung bai toan quy hoach tuyên tinh ́ ̣ ̀ ́ ̣ ́́ ̣ ̉ dang khoang. Chương 3. Xây dựng thuât toan giai bai toan tim đường đi ngăn nhât ̣ ́ ̉ ̀ ́̀ ́ ́ biêu diên cung đường đi là số mờ dang khoang. ̉ ̃ ̣ ̉ Chương 4. Cài đặt thử nghiệm.
5 Chương 1 LÝ THUYẾT ĐỒ THỊ VÀ THUÂT TOAN GIAI BAI ̣ ́ ̉ ̀ TOAN TÌM ĐƯỜNG ĐI NGẮN NHẤT CÓ TRỌNG SỐ XÁC ĐỊNH ́ 1.1. Khái niệm cơ bản về lý thuyết đồ thị Lý thuyêt đồ thị là nganh khoa hoc được phat triên từ lâu nhưng lai có ́ ̀ ̣ ́ ̉ ̣ nhiêu ứng dung hiên đai. Những ý tưởng cơ ban cua nó được đưa ra từ thế ̀ ̣ ̣ ̣ ̉ ̉ kỷ thứ 18 bởi nhà toan hoc Thuy Sĩ tên là Leonard Euler. Ông đa ̃ dung đô ̀ thi ̣ ́ ̣ ̣ ̀ để giai quyêt bai toan câu Konigsberg nôi tiêng. ̉ ́̀ ́ ̀ ̉ ́ Đồ thị được dung để giai quyêt nhiêu bai toan khac nhau. Ví dụ dung đô ̀ ̀ ̉ ́ ̀ ̀ ́ ́ ̀ thị để xac đinh xem có thực hiên được môt mach điên trên môt bang điên ́ ̣ ̣ ̣ ̣ ̣ ̣ ̉ ̣ phăng không. Chung ta cung có thể phân biêt hai hợp chât hoa hoc có cung ̉ ́ ̃ ̣ ́ ́ ̣ ̀ công thức phân tử nhưng có câu truc khac nhau nhờ đồ thi. Chung ta cung có ́ ́ ́ ̣ ́ ̃ thể xac đinh xem hai may tinh có được nôi với nhau băng môt đường truyên ̣́ ́́ ́ ̀ ̣ ̀ thông hay không nêu dung mô hinh đồ thị mang may tinh. Đô ̀ thi ̣ v ới cac ́ ̀ ̀ ̣ ́́ ́ trong số được gan cho cac canh cua nó có thể dung để giai cac bai toan như ̣ ́ ́ ̣ ̉ ̀ ̉́ ̀ ́ bai toan: “ Tim đường đi ngăn nhât” giữa hai thanh phố trong môt mang giao ̀ ́ ̀ ́ ́ ̀ ̣ ̣ thông. 1.1.1. Cac đinh nghia về đồ thi: ̣́ ̃ ̣ Đồ 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 đó. Người ta thường ký hiêu đồ thị G = (V,E), trong đó V là tâp hợp cac đinh ̣ ̣ ́̉ (Verterx), E là tâp hợp cac canh (Edge). Người ta phân loai đồ thị theo cac đăc ̣ ́ ̣ ̣ ́ ̣ tinh và số canh nôi cac căp đinh cua đồ thi. ́ ̣ ́́ ̣̉ ̉ ̣ * Định nghĩa 1: Một đơn đồ thị G = (V, E) gồm một tập khác rỗng V mà các phần tử của nó gọi là các đỉnh và một tập E mà các ph ần t ử c ủa nó gọi là các cạnh, đó là các cặp không có thứ tự của các đỉnh phân biệt.
6 * Định nghĩa 2: Một đa đồ thị G = (V, E) gồm một tập khác rỗng V mà các phần tử của nó gọi là các đỉnh và một h ọ E mà các ph ần t ử c ủa nó g ọi là các cạnh, đó là các cặp không có thứ tự của các đ ỉnh phân bi ệt. Hai c ạnh được gọi là cạnh bội hay song song nếu chúng cùng tương ứng v ới m ột cặp đỉnh. Rõ ràng mỗi đơn đồ thị là đa đồ thị, nhưng không phải đa đồ thị nào cũng là đơn đồ thị. * Định nghĩa 3: Một giả đồ thị G = (V, E) gồm một tập khác rỗng V mà các phần tử của nó gọi là các đỉnh và một h ọ E mà các ph ần t ử c ủa nó gọi là các cạnh, đó là các cặp không có th ứ tự của các đ ỉnh (không nh ất thiết là phân biệt). Với v∈V, nếu (v,v)∈E thì ta nói có một khuyên tại đỉnh v. Tóm lại, giả đồ thị là loại đồ thị vô hướng tổng quát nh ất vì nó có th ể chứa các khuyên và các cạnh bội. Đa đồ thị là loại đồ thị vô h ướng có th ể chứa cạnh bội nhưng không thể có các khuyên, còn đơn đồ thị là loại đồ thị vô hướng không chứa cạnh bội hoặc các khuyên. v1 v2 v3 v4 v1 v2 v3 v5 v6 v7 v4 v5 v6 Đơn đồ thị Giả đồ thị Hinh 1.1 Đơn đồ thi, giả đồ thị ̀ ̣ * Định nghĩa 4: Một đồ thị có hướng G = (V, E) gồm một tập khác rỗng V mà các phần tử của nó gọi là các đỉnh và một t ập E mà các ph ần t ử của nó gọi là các cung, đó là các cặp có thứ tự của các phần tử thuộc V.
7 * Định nghĩa 5: Một đa đồ thị có hướng G = (V, E) gồm một tập khác rỗng V mà các phần tử của nó gọi là các đỉnh và một h ọ E mà các ph ần t ử của nó gọi là các cung, đó là các cặp có thứ tự của các phần tử thuộc V.  Đồ thị vô hướng nhận được từ đồ thị có hướng G bằng cách xoá bỏ các chiều mũi tên trên các cung được gọi là đồ thị vô h ướng n ền c ủa G. v1 v2 v3 v3 v5 v1 v2 V5 v6 v7 v4 v5 v6 Đồ thị có hướng Đa đồ thị có hướng Hinh 1.2. Đồ thị có hướng và Đa đồ thị có hướng ̀ Đồ thị ảnh hưởng: Khi nghiên cứu tính cách của một nhóm nguời,  ta thấy một số người có thể có ảnh hưởng lên suy nghĩ của những người khác. Đồ thị có hướng được gọi là đồ thị ảnh hưởng có thể dùng để mô hình bài toán này. Mỗi người của nhóm được biểu diễn bằng một đỉnh. Khi một người được biểu diễn bằng đỉnh a có ảnh hưởng lên người được biểu diễn bằng đỉnh b thì có một cung nối từ đỉnh a đến đỉnh b. Thi đấu vòng tròn: Một cuộc thi đấu thể thao trong đó m ỗi đ ội  đấu với mỗi đội khác đúng một lần gọi là đấu vòng tròn. Cuộc thi đ ấu nh ư thế có thể được mô hình bằng một đồ thị có hướng trong đó mỗi đội là một đỉnh. Một cung đi từ đỉnh a đến đỉnh b nếu đội a thắng đội b. Các chương trình máy tính có thể thi hành nhanh hơn bằng cách  thi hành đồng thời một số câu lệnh nào đó. Điều quan trọng là không đ ược thực hiện một câu lệnh đòi hỏi kết quả của câu lệnh khác ch ưa đ ược th ực hiện. Sự phụ thuộc của các câu lệnh vào các câu lệnh trước có th ể biểu
8 diễn bằng một đồ thị có hướng. Mỗi câu lệnh được biểu diễn bằng một đỉnh và có một cung từ một đỉnh tới một đỉnh khác nếu câu lệnh được biểu diễn bằng đỉnh thứ hai không thể thực hiện được trước khi câu l ệnh đ ược biểu diễn bằng đỉnh thứ nhất được thực hiện. Đồ thị này được gọi là đồ thị có ưu tiên trước sau. 1.1.2. Bâc cua đồ thi. ̣ ̉ ̣ * Định nghĩa 1: Hai đỉnh u và v trong đồ thị (vô hướng) G=(V,E) được gọi là liền kề nếu (u,v)∈E. Nếu e = (u,v) thì e gọi là cạnh liên thuộc với các đỉnh u và v. Cạnh e cũng được gọi là cạnh nối các đỉnh u và v. Các đỉnh u và v gọi là các điểm đầu mút của cạnh e. * Định nghĩa 2: Bậc của đỉnh v trong đồ thị G=(V,E), ký hiệu deg(v), là số các cạnh liên thuộc với nó, riêng khuyên tại một đỉnh được tính hai lần cho bậc của nó. Đỉnh v gọi là đỉnh treo nếu deg(v)=1 và gọi là đỉnh cô lập nếu deg(v)=0. v1 v2 v3 v4 v6 v5 v7 Hinh 1.3. Bâc cua đồ thị ̀ ̣ ̉ Ta có deg(v1)=7, deg(v2)=5, deg(v3)=3, deg(v4)=0, deg(v5)=4, deg(v6)=1, deg(v7)=2. Đỉnh v4 là đỉnh cô lập và đỉnh v6 là đỉnh treo. * Mệnh đề 1: Cho đồ thị G = (V, E). Khi đó ∑ deg(v) . 2|E| = v∈V
9 Chứng minh: Rõ ràng mỗi cạnh e = (u,v) được tính một lần trong deg(u) và một lần trong deg(v). Từ đó suy ra tổng tất cả các bậc của các đỉnh bằng hai lần số cạnh. Hệ quả 1: Số đỉnh bậc lẻ của một đồ thị là một số chẵn. Chứng minh: Gọi V1 và V2 tương ứng là tập các đỉnh bậc chẵn và tập các đỉnh bậc lẻ của đồ thị G = (V, E). Khi đó ∑ deg(v) + ∑ deg(v) 2|E| = v∈V1 v∈V2 Vế trái là một số chẵn và tổng thứ nhất cũng là một s ố ch ẵn nên t ổng thứ hai là một số chẵn. Vì deg(v) là lẻ với mọi v ∈ V2 nên |V2| là một số chẵn. Mệnh đề 2: Trong một đơn đồ thị, luôn tồn tại hai đỉnh có cùng bậc. Chứng minh: Xét đơn đồ thị G=(V,E) có |V|=n. Khi đó phát biểu trên được đưa về bài toán: trong một phòng họp có n người, bao giờ cũng tìm được 2 người có số người quen trong số những người dự họp là nh ư nhau (xem Thí dụ 6 của 2.2.3). * Định nghĩa 3: Đỉnh u được gọi là nối tới v hay v được gọi là được nối từ u trong đồ thị có hướng G nếu (u,v) là một cung của G. Đỉnh u gọi là đỉnh đầu và đỉnh v gọi là đỉnh cuối của cung này. * Định nghĩa 4: Bậc vào (t.ư. bậc ra) của đỉnh v trong đồ thị có hướng G, ký hiệu degt(v) (t.ư. dego(v)), là số các cung có đỉnh cuối là v. v2 v3 v1 v4 v5 v6 H 1.4. Bâc cua đồ thị có hướng ̣ ̉ degt(v1) = 2, dego(v1) = 3,