tailieunhanh - BÀI GIẢNG GIẢI THUẬT VÀ LẬP TRÌNH - QUY HOẠCH ĐỘNG - LÊ MINH HOÀNG - 9

Các thuật toán trên đồ thị Vì đường pha chỉ là đường đi cơ bản trên đồ thị định hướng nên việc xác định những đỉnh nào có thể đến được từ x ∈ X bằng một đường pha có thể sử dụng các thuật toán tìm kiếm trên đồ thị (BFS hoặc DFS). Những đỉnh và những cạnh được duyệt qua tạo thành một cây pha gốc x Một đường mở (Augmenting Path) là một đường pha đi từ một X_đỉnh chưa ghép tới một Y_đỉnh chưa ghép. Như vậy: Đường đi trực tiếp từ một X_đỉnh chưa ghép tới. | Các thuật toán trên đồ thị 275 0_cạnh đã ghép xen kẽ nhau. Vì đường pha chỉ là đường đi cơ bản trên đồ thị định hướng nên việc xác định những đỉnh nào có thể đến được từ x e X bằng một đường pha có thể sử dụng các thuật toán tìm kiếm trên đồ thị BFS hoặc DFS . Những đỉnh và những cạnh được duyệt qua tạo thành một cây pha gốc x Một đường mở Augmenting Path là một đường pha đi từ một X_đỉnh chưa ghép tới một Y_đỉnh chưa ghép. Như vậy Đường đi trực tiếp từ một X_đỉnh chưa ghép tới một Y_đỉnh chưa ghép qua một 0_cạnh chưa ghép cũng là một đường mở. Dọc trên đường mở số 0_cạnh chưa ghép nhiều hơn số 0_cạnh đã ghép đúng 1 cạnh. . Thuật toán Hungari Bước 1 Khởi tạo Một bộ ghép M 0 Bước 2 Với mọi đỉnh x eX ta tìm cách ghép x như sau. Bắt đầu từ đỉnh x chưa ghép thử tìm đường mở bắt đầu ở x bằng thuật toán tìm kiếm trên đồ thị BFS hoặc DFS - thông thường nên dùng BFS để tìm đường qua ít cạnh nhất có hai khả năng xảy ra Hoặc tìm được đường mở thì dọc theo đường mở ta loại bỏ những cạnh đã ghép khỏi M và thêm vào M những cạnh chưa ghép ta được một bộ ghép mới nhiều hơn bộ ghép cũ 1 cạnh và đỉnh x trở thành đã ghép. Hoặc không tìm được đường mở thì do ta sử dụng thuật toán tìm kiếm trên đồ thị nên có thể xác định được hai tập VisitedX Tập những X_đỉnh có thể đến được từ x bằng một đường pha VisitedY Tập những Y_đỉnh có thể đến được từ x bằng một đường pha Gọi A là trọng số nhỏ nhất của các cạnh nối giữa một đỉnh thuộc VisitedX với một đỉnh không thuộc VisitedY. Dễ thấy A 0 bởi nếu A 0 thì tồn tại một 0_cạnh x y với xeVisitedX và yỂ VisitedY. Vì x đến được x bằng một đường pha và x y là một 0_cạnh nên x cũng đến được y bằng một đường pha dẫn tới y e VisitedY điều này vô lý. Biến đổi đồ thị G như sau Với Vx e VisitedX trừ A vào trọng số những cạnh liên thuộc với x Với V y e VisitedY cộng A vào trọng số những cạnh liên thuộc với y. Lặp lại thủ tục tìm kiếm trên đồ thị thử tìm đường mở xuất phát ở x cho tới khi tìm ra đường mở. Bước 3 Sau bước 2 thì mọi X_đỉnh đều được ghép