Luận văn ThS: Ứng dụng đồ thị euler tối ưu hóa bài toán tìm đường đi ngắn nhất

112 lượt xem
Share

Luận văn Ứng dụng đồ thị euler tối ưu hóa bài toán tìm đường đi ngắn nhất tìm hiểu đại cương về lý thuyết đồ thị; ứng dụng đồ thị Euler và so sánh hiệu quả của 02 giải thuật Tham lam, FindMinMatch đối với “bài toán phân công xe đi thu gom rác thải” tại Quận 4.

Mục lục nội dung

Luận văn ThS: Ứng dụng đồ thị euler tối ưu hóa bài toán tìm đường đi ngắn nhất

1. Mở đầu

Tìm đường đi ngắn nhất là một trong những bài toán kinh điển sử dụng lý thuyết đồ thị để mô phỏng và triển khai giải thuật. Bài toán có tính ứng dụng thực tiễn rất cao, đặc biệt là trong xã hội phát triển ngày nay có rất nhiều ứng dụng được đưa ra theo chủ đề như: hướng dẫn đường đi tự động, ứng dụng truyền dẫn tín hiệu mạng máy tính, đường đi của tín hiệu định vị toàn cầu (gps)…. Ngày nay, nhiều nhà toán học vẫn không ngừng nghiên cứu, để tìm giải pháp tối ưu hơn để giải quyết cho bài toán này. Chu trình đường đi ngắn nhất qua tất cả các cạnh trên đồ thị liên thông được biết đến là chu trình Euler, được công bố bởi nhà toán học cùng tên. Bài toán sau này có nhiều biến thể được đưa ra bởi nhiều vấn đề hóc búa hơn trong xã hội thực tiễn. Biến thể đầu tiên được nhà toán học Trung Hoa - Quản Mai Cốc đưa ra vào năm 1962 và được Alan Goldman của Cục Tiêu chuẩn quốc gia Hoa Kỳ đặt tên là bài toán “Người đưa thư Trung Hoa – Chinese postman problem”. Năm 1973 định lý Goodman Hedetniemi ra đời nhằm đưa ra một giải pháp để giải bài toán kinh điển này, các biến thể sau nữa như bài toán “Người quét rác New York - New York Street Sweeper problem” ….

2. Nội dung

2.1 Đại cương về lý thuyết đồ thị

Đồ thị và các khái niệm liên quan 

  • Định nghĩa đồ thị
  • Đồ thị vô hướng, đồ thị có hướng
  • Bậc của đồ thị
  • Một số dạng đồ thị đặc biệt

Biểu diễn đồ thị trên máy tính

  • Ma trận kề, ma trận trọng số
  • Danh sách cạnh (cung)
  • Danh sách kề

Chu trình Euler, Đường đi Euler và Đồ thị Euler

  • Khái niệm Đường đi, Chu trình, tính Liên thông trên Đồ thị
  • Khái niệm Chu trình Euler, Đường đi Euler và Đồ thị Euler
  • Thuật toán Fleury tìm chu trình Euler

Một số thuật toán trên Đồ thị

  • Thuật toán Floyed tìm đường đi ngắn nhất giữa mọi cặp đỉnh trên đồ thị
  • Giải thuật Tham lam
  • Tìm bộ ghép trên đồ thị

2.2 Ứng dụng đồ thị Euler

Phân tích bài toán “Thanh tra giao thông” của tác giả Nguyễn Tam Hùng

  • Phát biểu bài toán
  • Hướng giải bài toán theo tác giả Nguyễn Tam Hùng
  • Nhận xét về bài toán “Thanh tra giao thông” của tác giả Nguyễn Tam Hùng

Đề xuất bài toán “Phân công xe đi thu gom rác thải” tại Quận 4

  • Đặt vấn đề
  • Ý tưởng chính của thuật toán
  • Hướng giải quyết bài toán
  • Ứng dụng giải bài toán phân công việc thực tế tại Quận 4

2.3 Đánh giá

Độ phức tạp của các thuật toán được sử dụng trong bài toán

Đánh giá giải pháp dùng giải thuật Tham lam so với giải thuật FindMinMatch

  • Giải thuật Tham lam
  • Giải thuật FindMinMatch
  • So sánh hiệu quả của 02 giải thuật trên đối với “bài toán phân công xe đi thu gom rác thải” tại Quận 4

3. Kết luận

Bài toán tìm đường đi ngắn nhất trong đề tài có sử dụng giải pháp tìm cặp ghép tối ưu với điều kiện đề bài yêu cầu tổng chiều dài đường đi phải là nhỏ nhất có thể. Thuật toán ở bước xử lý này có ảnh hưởng rất lớn đến tốc độ xử lý cũng như giá trị tối ưu tìm được chung của cả bài toán là hai giải pháp Tham lam và FindMinMatch. Tuỳ vào nhu cầu thực tế mà có thể áp dụng một trong hai giải thuật này để thực thi cho bài toán. Đối với các bài toán có chiều dài của các cạnh trên đồ thị không chênh lệch nhau nhiều như: mạch điện, ô cờ… cũng như chi phí cho đường đi không lớn thì có thể sử dụng giải thuật Tham lam. Ngược lại, đối với các bài toán có chiều dài của cạnh trên đồ thị chênh lệch nhau nhiều như: lộ trình đường đi giao thông, tín hiệu GPS… hoặc chi phí cho đường đi lớn thì việc áp dụng giải Thuật FindMinMatch sẽ mang lại hiệu quả tiết kiệm cao về chi phí.

4. Tài liệu tham khảo

Gauvain Chaste, Aurélien Ooms and Robin Walravens (2014), Chinese postman problem, [online], viewed 10 May 2015, from:

Kenneth H. Rosen (Phạm Văn Thiều và Đặng Hữu Thịnh dịch, 2003), Toán rời rạc ứng dụng trong tin học, NXB Khoa học và Kỹ thuật, Hà Nội.

Lê Minh Hoàng (1999-2002), Giải thuật và lập trình, NXB Hà Nội, Hà Nội....

--- Nhấn nút TẢI VỀ hoặc XEM ONLINE để tham khảo đầy đủ nội dung Luận văn trên ---

112 lượt xem
Share
Ngày:03/09/2020 Chia sẻ bởi:
TẢI VỀ XEM ONLINE

CÓ THỂ BẠN QUAN TÂM