Mục đích của việc mô hình hóa và đánh giá đặc tính hoạt động của hệ thống p5

Bây giờ ta đã có thể xem xét sâu hơn các câu lệnh của thuật toán "háu ăn". Các câu lệnh của thuật toán hơi khó hiểu vì chúng dựa trên định nghĩa của hai hàm, Test và SelestBestElement (là hàm kiểm tra tính khả thi và đánh giá các tập). Chúng ta cũng giả sử rằng có một cấu trúc properties, là một danh sách của các danh sách chứa tất cả các thông tin cần
Nội dung trích xuất từ tài liệu:
Mục đích của việc mô hình hóa và đánh giá đặc tính hoạt động của hệ thống p5 listcử. Có rất nhiều cách thực hiện các quá trình này. properties có thể là một dãy và các hàm Append, Delete v à ElementsOf có thể hoạt động với các danh sách chỉ số (danh sách mà các phần tử là các chỉ số mạng). Trong thực tế cách thực hiện được chọn là cách làm sao cho việc thực hiện các hàm Test và SelectBestElement là tốt nhất. Đoạn giả mã trên giả thiết rằng thuật toán háu ăn sẽ dừng lại khi không còn phần tử nào để xem xét. Trong thực tế, có nhiều nguyên nhân để thuật toán dừng lại. Một trong những nguyên nhân là khi kết quả xấu đi khi các phần tử được tiếp tục thêm vào. Điều nay xảy ra khi tất cả các phần tử còn lại đều mang giá trị âm trong khi chúng ta đang cố tìm cho một giá trị tối đa. Một nguyên nhân khác là khi biết rằng không còn phần tử nào ở trong tập ứng cử có khả năng kết hợp với các phần tử vừa được chọn tạo ra một lời giải khả thi. Điều này xảy ra khi một cây bắc cầu toàn bộ các nút đã được tìm thấy. Giả sử rằng thuật toán dừng lại khi điều đó là hợp lý, còn nếu không, các phần tử không liên quan sẽ bị loại ra khỏi lời giải. Giả thiết rằng, các lời giải cho một bài toán thoả mãn tính chất 1 và giá trị của tập đơn giản chỉ là tổng các giá trị của các phần tử trong tập. Ngoài ra, giả thiết thêm rằng tính chất sau được thoả mãn: Tính chất 2: Nếu hai tập Sp và Sp+1 lần lượt có p và p+1 phần tử là các lời giải và tồn tại một phần tử e thuộc tập Sp+1 nhưng không thuộc tập Sp thì Sp{e} là một lời giải. Chúng ta thấy rằng, các cạnh của các rừng thoả mãn tính chất 2, nghĩa là nếu có hai rừng, một có p cạnh và rừng kia có p+1 thì luôn tìm được một cạnh thuộc tập lớn hơn mà việc thêm cạnh đó vào tập nhỏ hơn không tạo ra một chu trình. Một tập các lời giải thoả mãn các tính chất trên gọi là một matroid. Định lý sau đây là rất quan trọng (chúng ta chỉ thừa nhận chứ không chứng minh). Định lý 4.1 Thuật toán “háu ăn” đảm bảo đảm một lời giải tối ưu cho một bài toán khi và chỉ khi các lời giải đó tạo ra một matroid. Có thể thấy rằng, tính chất 1 và tính chất 2 là điều kiện cần và đủ để đảm bảo tính tối ưu của thuật toán “háu ăn” . Nếu có một lời giải cho một bài toán nào đó mà nó thoả mãn hai tính chất 1 và 2 thì cách đơn giản nhất là dùng thuật toán “háu ăn” để giải quyết nó. Điều đó đúng với một cây bắc cầu. Sau đây là một định lý không kém phần quan trọng. Định lý 4.2 50 Nếu các lời giải khả thi cho một bài toán nào đó tạo ra một matroid thì tất cả các tập khả thi tối đa có số lượng phần tử như nhau. Trong đó, một tập khả thi tối đa là một tập mà khi thêm các phần tử vào thì tính khả thi của nó không được bảo toàn; Nó không nhất thiết phải có số lượng phần tử tối đa cũng như không nhất thiết phải có trọng lượng lớn nhất. Định lý đảo của định lý trên cũng có thể đúng nghiã là nếu tính chất 1 được thoả mãn và mọi tập khả thi tối đa có cùng số lượng phần tử, thì tính chất 2 được thoả mãn. Định lý 4.2 cho phép chúng ta chuyển đổi một bài toán tối thiểu P thành một bài toán tối đa P' bằng cách thay đổi các giá trị của các phần tử. Giả thiết rằng tất cả v(xj) trong P có giá trị âm. Lời giải tối ưu cho bài toán P có số lượng phần tử tối đa là m thì chúng ta có thể tạo ra một bài toán tối đa P' từ P bằng cách thiết lập các giá trị của các phần tử trong P' thành -v(xj). Tất cả các phần tử đều có giá trị dương và P' có một lời giải tối ưu chứa m phần tử. Thực ra, thứ tự của các lời giải tối đa phải được đảo lại: lời giải có giá trị tối đa trong P' cũng là lời giải có giá trị tối thiểu trong P. Giả sử lúc nay ta cần tìm một lời giải có giá trị tối thiểu, tuân theo điều kiện là có số lượng tối đa các phần tử. Sẽ tính cả các phần tử có giá trị dương. Có thể giải quyết bài toán P như là một bài toán tối đa P' bằng cách thiết lập các giá trị của các phần tử thành B-v(xj) với B có giá trị lớn hơn giá trị lớn nhất của xj. Khi đó các giá trị trong P' đều dương và P' là một lời giải tối ưu có m phần tử. Thứ tự của tất cả các tập khả thi tối đa đã bị đảo ngược: một tập có giá trị là V trong P thì có giá trị là mB-V trong lời giải P'. Một giá trị tối đa trong P' thì có giá trị tối thiểu trong P. Quy tắc này cũng đúng với các cây bắc cầu thoả mãn tính chất 1 và tính chất 2 và có thể tìm một cây bắc cầu tối thiểu bằng cách sử dụng một thuật toán “háu ăn”. Thuật toán Kruskal Thuật toán Kruskal là một thuật toán “háu ăn” được sử dụng để tìm một cây bắc cầu tối thiểu. Tính đúng đắn của thuật toán dựa trên các định lý sau: Định lý 4.3 Các rừng thì thoả mãn tính chất 1 và 2. Như chúng ta đã biết, một rừng là một tập hợp các cạnh mà tập hợp đó không chứa các chu trình. Rõ ràng là bất kỳ một tập con các cạnh nào của một rừng (thậm chí cả tập rỗng) cũng là một rừng, vì vậy tính chất 1 được thoả mãn. 51 Để thấy rằng tính chất 2 cũng thoả mãn, xét một graph được biểu diễn trong hình 4.4. Hình 4.3. Giả sử có một rừng F1 có p cạnh. Rừng {2,4} là một ví dụ với p=2, và nó được biểu diễn bằng nét đứt trong hình 4.4. Khi đó xét một rừng khác F2 có p+1 cạnh. Có hai trường hợp được xét. Trường hợp 1: F2 đi tới một nút n, nhưng F1 không đi tới nút đó. Một ví dụ của trường hợp này là rừng {1, 4, 6}, rừng này đi tới E còn F1 thì không. Trong trường hợp này, có thể tạo ra rừng {2, 4, 6} bằng cách thêm cạnh 6 vào rừng {2,4}. Trường hợp 2: F2 chỉ đi tới các nút mà F1 đi tới. Một ví dụ của trường hợp này là rừng {1. 4. 5}. Xét S, một tập các nút mà F1 đi tới. Cho rằng có k nút trong tập S. Vì F1 là một rừng nên mỗi cạnh trong F1 giảm số lượng thành phần trong S đi một, do đó tổng số lượng thành phần là k-p. Tương tự, F2 tạo ra k-(p+1) thành phần từ S (số lượng thành phần vừa nói bé hơn với số lượng thành phần của F1). Vì vậy, một cạnh tồn tại trong F2 mà các điểm cuối của nó nằm ở các thành phần khác nhau trong F1 thì có thể thêm cạnh đó vào F1 mà không tạo ra một ...