Chia sẻ miễn phí cho các bạn tài liệu: Phân tích thiết kế thuật toánMét sè thuËt to¸n ghÐp cÆp trªn ®å thÞ hai phÝa
2
B/ NỘI DUNG
I. Một số khái niệm chung
Xét hai tập hữu hạn X, Y gồm n phần tử:
X = {x
1
, x
2
, ..., x
n
}
Y = {y
1
, y
2
, ..., x
n
}
-Cặp phần tử (x, y) với x
X, y Y được gọi là một cặp ghép.
-Hai cặp ghép (x, y) và (x’, y’) được gọi là rời nhau nếu x
¹ x’ và y ¹ y’. --
--Tập M gồm các cặp ghép rời nhau được gọi là một tập cặp ghép.Thông thường bài toán xây dựng các cặp ghép được tiếp cận theo 2 hướng:
Hướng thứ nhất: Khi ghép cặp phải thỏa mãn điều kiện nào đấy, khi đó người ta quan tâm đến khả năng ghép cặp tối đa. Hướng thứ hai: lượng hóa việc ghép cặp, khi đó người ta quan tâm đến phương án ghép cặp tối ưu theo các giá trị đã lượng hóa.
Vì số tập cặp ghép là hữu hạn, nên có một phương pháp xây dựng tầm
thường là thử tất cả các khả năng. Tuy nhiên, số khả năng như vậy là rất lớn (cỡ n!). Vì thế, người ta quan tâm đến việc tìm kiếm những thuật giải hữu hiệu, dễ cài đặt chương trình và có tính khả thi cao. Bài này nhằm giới thiệu một số mô hình ghép cặp như vậy.II. Cặp ghép đầy đủ tối ưu2.1. Giới thiệu bài toán
Một tập cặp ghép, sao cho tất cả các phần tử của X và Y đều được ghép cặp
(nghĩa là có đủ n cặp với n là số phần tử của X và Y), được gọi là một tập cặp ghép đầy đủ.
Rõ ràng mỗi song ánh p: X
® Y xác định một tập cặp ghép đầy đủ, trong
đó mỗi cặp ghép được viết dưới dạng (x, p(x)), x
X. Từ đó suy ra có tất cả
n! cách xây dựng tập cặp ghép đầy đủ khác nhau.
Với các tập cặp ghép đầy đủ, một cách tự nhiên, người ta quan tâm đến tập
cặp ghép “tốt nhất” theo một nghĩa nào đó đã được lượng hóa. Tập cặp ghép này được gọi là tập cặp ghép đầy đủ tối ưu.
Bài toán tìm cặp ghép đầy đủ tối ưu có nhiều mô hình ứng dụng thực tế.
Một trong những mô hình này là người ta quan tâm đến việc ghép cặp sao cho có hiệu quả nhất.
Để lượng hóa việc ghép mỗi phần tử x
X với một phần tử y Y, người
ta đưa vào ma trận trọng số C
i j
(i, j = 1, 2, ..., n) với ý nghĩa C
i j
mô tả hiệ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
Dành riêng cho anh em Ket-noi, bác nào cần
download miễn phí bản đầy đủ thì trả lời topic này, Nhóm Mods sẽ gửi tài liệu cho bạn qua hòm tin nhắn nhé.
- Bạn nào có tài liệu gì hay thì up lên đây chia sẻ cùng anh em.
- Ai cần tài liệu gì mà không tìm thấy ở forum, thì đăng yêu cầu down tại đây nhé:
Nhận download tài liệu miễn phí
source: content/getpagecontent?id=381352&pageNumber=2&documentKindID=1
