Tiểu Luận Tiểu luận môn phân tích thiết kế thuật toán: Một số thuật toán cặp ghép trên đồ thị hai phía

A/ MỞ ĐẦU

Trong cuộc sống, chúng ta thường gặp nhữmg vấn đề mà trong đó ta cần tìm phương án thực hiện sao cho đạt được mục đích của mình một cách tốt nhất. Chẳng hạn, bài toán tìm lộ trình đi từ một điểm này đến một điểm khác sao cho quãng đường đi là ngắn nhất hoặc lộ phí rẻ nhất . Một trong những bài toán đó là tìm phương án tối ưu trên một mạng lưới.
Bài toán luồng cực đại trong mạng là một trong những bài toán tối ưu trên đồ thị có nhiều ứng dụng trong thực tế và trong lý thuyết tổ hợp. Bài toán này đã được hai nhà toán học Mỹ là Ford và Fulkerson tập trung giải quyết và đã đưa ra thuật giải chính xác. Tuy nhiên, đối với những mạng trong đó đồ thị có dạng “hai phía”, thuật toán trên chi phí quá nhiều bộ nhớ mà thực ra không cần thiết.
Tiểu luận này nhằm đưa ra thuật toán hữu hiệu của một số bài toán liên quan đến đồ thị hai phía mà trong đó có sự cải tiến để sử dụng một cách tối đa hiệu quả của bộ nhớ.
Tiểu luận gồm 4 phần. Phần 1: Giới thiệu một số khái niệm chung. Phần2: Trình bày thuật toán tìm cặp ghép đầy đủ tối ưu. Phần 3: Trình bày thuật toán tìm cặp ghép tối đa. Phần 4: Trình bày hai chương trình ví dụ, đó là chương trình tìm cặp ghép đầy đủ có tổng trọng số đạt max và chương trình tìm cặp ghép tối da.