Bạn muốn xem những bài viết hay và ngắn, đừng quên checkout và like facebook page: https://www.facebook.com/thietkegiaithuat/

Bài viết mới: Thuật toán Hopcroft-Karp tìm cặp ghép cực đại trên đồ thị hai phía trong thời gian O(m\sqrt{n}).

Bài viết mới: Giới thiệu về bài toán cặp ghép và cách tìm cặp ghép trong đồ thị hai phía.

Bài viết mới: phép xóa một nút khỏi cây AVL.

Bài viết mới: phép chèn trong cây cây AVL.

Bài viết mới: Giới thiệu về cây nhị phân cân bằng.

Bài viết mới: Quy hoạch động trên cây.

Bài viết mới: Mảng mở rộng và ứng dung trong thực thi ngăn xếp/hàng đợi.

Bài viết mới: Danh sách liên kết đơn và các biến thể.

Bài viết mới: Một số bài toán NP-complete khi đầu vào là các số nguyên lớn.

Bài viết mới: Một số bài toán NP-complete trên đồ thị.

Bài viết mới: NP-complete. Bài viết bao gồm lời giải cho bài toán domino-tiling dựa trên bài toán cặp ghép hoàn hảo.

Bài viết mới: P vs NP, bài toán triệu đô của viện Clay.

Bài viết mới: Thuật toán Kosaraju tìm thành phần liên thông mạnh trong đồ thị có hướng.

Bài viết mới: Thuật toán Stoer-Wagner tìm lát cắt cực tiểu trong đồ thị.

Bài viết mới: Một số ứng dụng của bài toán luồng cực đại: cặp ghép cực đại, làm tròn ma trận và phân vùng ảnh.

Bài viết mới: Một số biến thể của bài toán luồng cực đại: luồng với nhiều đỉnh phát-thu, luồng với định mức cạnh và luồng cực đại có chi phí nhỏ nhất.

Bài viết mới: Thuật toán Edmonds-Karp.
Bài viết mới: Thuật toán FordFulkerson. Đây là bài viết đầu tiên trong chuỗi bài về luồng trong mạng.

Bài viết mới: Lý thuyết phổ đồ thị IV Phổ của ma trận kề và bài toán tô màu. Bài thứ 4 trong loạt bài về lý thuyết phổ.
Bài viết mới: Lý thuyết phổ đồ thị III. Bài thứ 3 trong loạt bài về lý thuyết phổ.

Bài viết mới: Lý thuyết phổ đồ thị II. Bài thứ 2 trong loạt bài về lý thuyết phổ.

Bài viết mới: Lý thuyết phổ đồ thị I. Bài đầu tiên trong loạt bài về lý thuyết phổ.

Bài viết mới: Thuật toán KKT, thuật toán cuối cùng trong loạt bài cây khung nhỏ nhất

Bài viết mới trên facebook: Phát triển giải thuật cho hệ thống gợi ý cho dữ liệu lớn. Check out at: https://www.facebook.com/thietkegiaithuat/

Bài viết mới trên facebook: Bài toán User Hashing và cách chọn Collision Resistant Hash Functions. Check out at: https://www.facebook.com/thietkegiaithuat/

Bài viết mới trên facebook: Tìm một phần tử trong ma trận và lời giải. Check out at: https://www.facebook.com/thietkegiaithuat/

Bài viết mới trên facebook: Puzzle màu mắt dân trên đảo và lời giải. Check out at: https://www.facebook.com/thietkegiaithuat/

Bài viết mới: thuật toán Boruvka tìm cây khung nhỏ nhất. Xem tại đây.

Bài viết mới trên facebook: xóa các dòng giống nhau trong file và lời giải. Check out at: https://www.facebook.com/thietkegiaithuat/

Bài viết mới trên facebook: tìm phần tử trội. Check out at: https://www.facebook.com/thietkegiaithuat/

Bài viết mới trên facebook: lời giải bài toán tìm một số nguyên không xuất hiện trong file. Check out at: https://www.facebook.com/thietkegiaithuat/

Bài viết mới: Thuật toán Prim tìm cây khung nhỏ nhất: Xem tại đây.

Mình sẽ start một series các posts nhỏ về giải thuật cho Big-Data trên facebook. Mình có lẽ sẽ repost lại một số bài viết trên facebook tại đây nhưng facebook vẫn là kênh chính để chúng ta thảo luận các topics kiểu này. Check out at: https://www.facebook.com/thietkegiaithuat/

Bài viết mới trên facebook: tìm 3 điểm nằm trên cùng một đường thẳng. Check out at: https://www.facebook.com/thietkegiaithuat/

Bài viết mới trên facebook: hiểu đúng về độ phức tạp. Check out at: https://www.facebook.com/thietkegiaithuat/

Bài viết mới Thuật toán Kruskal cho bài toán cây khung nhỏ nhất.

Bài viết mới trên facebook: bình chọn thuật toán tìm cây khung nhỏ nhất mà bạn yêu thích. Check out at: https://www.facebook.com/thietkegiaithuat/

Bài viết mới: lời giải bài bug bug bug Xem tại đây.

Bài viết mới: Cơ sở toán học của băm địa chỉ mở và băm hoàn hảo: Xem tại đây.

Bài viết mới trên facebook: tìm bugs. Check out at: https://www.facebook.com/thietkegiaithuat/

Bài viết mới trên facebook: bài toán mở cửa và lời giải: Check out at: https://www.facebook.com/thietkegiaithuat/.

Bài viết mới: Cơ sở toán học của xích ngăn cách trong phép băm: Xem tại đây.

Bài viết mới trên facebook: lời giải bài toán chọn quân bài: Check out at: https://www.facebook.com/thietkegiaithuat/

Bài viết mới trên facebook: Bài toán chọn quân bài: Check out at: https://www.facebook.com/thietkegiaithuat/

Bài viết mới trên facebook: Bài toán thả trứng và lời giải: Check out at: https://www.facebook.com/thietkegiaithuat/

Bài viết mới trên facebook: Một chút về dynamic memory allocation: Check out at: https://www.facebook.com/thietkegiaithuat/

Bài viết mới trên facebook: ArrayList trong Java. Check out at: https://www.facebook.com/thietkegiaithuat/

Bài viết mới trên facebook: Nghịch lí ngày sinh và ứng dụng trong bài toán phân tích thành
nhân tử.

Bài toán mới: Balls into Bins đã được upload lên facebook page. Check out!!!

Mình vừa up một bài toán khá hay về ứng dụng của Heap nhị phân lên trang facebook. Check it out!!!!

Mình vừa tạo một facebook page: https://www.facebook.com/thietkegiaithuat/. Mình sẽ dùng page này để cập nhật những bài viết mới nhất. Ngoài ra, mình cũng sẽ cập nhật những nghiên cứu mới nhất về giải thuật và cấu trúc dữ liệu thông qua page này. Những bài viết trong blog sẽ chỉ là những bài viết về kiến thức cơ bản. Like ngay nếu bạn quan tâm.

tsp

Facebook Comments

Bài này chúng ta tìm hiểu thuật toán Hopcroft-Karp [1] tìm cặp ghép cực đại trong đồ thị hai phía. Mình khuyến khích bạn đọc xem lại các khái niệm đã nhắc đến trong bài trước; chúng ta không nhắc lại các khái niệm đó ở đây. Các bạn phải nắm rõ hai khái niệm quan trọng nhất, đường tăng (augmenting path) và hiệu đối xứng (symmetric difference), để tiếp tục đọc bài này. Trong bài này, ta sẽ sử dụng Observation 1 của bài trước nên mình sẽ copy nguyên bản ra đây.

Observation 1: Gọi M_1, M_2 là hai cặp ghép của đồ thị G(V,E). Đồ thị con H(V, M_1\oplus M_2) sẽ bao gồm: (1) các đỉnh cô lập (isolated vertices), i.e, các đỉnh không kề với cạnh nào cả, (2) các đường pha và (3) các chu trình pha.

 

Ý tưởng trung tâm của thuật toán Hopcroft-Karp là mỗi lần tìm đường tăng bằng duyệt đồ thị, thay vì tìm một đường tăng, ta tìm một tập các đường tăng rời nhau (vertex-disjoint), kí hiệu là \mathcal{P}. Tập đường tăng rời nhau này có tính chất:

  1. Tối đại (maximal): mọi đường tăng khác đều có chung ít nhất một đỉnh với \mathcal{P}.
  2. Ngắn nhất: mỗi đường tăng trong \mathcal{P} là một đường tăng có chiều dài ngắn nhất so với tất cả các đường tăng của cặp ghép hiện tại M.

Ta gọi \mathcal{P} là một tập đường tăng ngắn nhất rời nhau tối đại (maximally vertex-disjoint shortest augmenting paths), ta gọi tắt là tập đường tăng tối đại. Chú ý \mathcal{P} là tối đại chứ không phải cực đại (maximum). Không dễ để tìm được một tập đường tăng cực đại nhưng tìm tập đường tăng tối đại có thể tìm được trong thời gian O(m + n) mà ta sắp mô tả dưới đây.

Hopcroft-Karp(G(A\cup B, E)):
    M \leftarrow \emptyset
    while there is an augmenting path of M
        \mathcal{P} \leftarrow \{P_1,P_2,\ldots, P_k\} a set of maximally short. disj. aug. path
        M \leftarrow M \oplus P_1 \oplus P_2 \ldots \oplus P_k
    return M

 

Như đã nói ở trên, ta có thể tìm được một tập đường tăng tối đại trong thời gian O(m+n). Tạm thời bỏ qua chi tiết làm sao ta có thể tìm được tập như vậy, ta tập trung vào câu hỏi: thuật toán Hopcroft-Karp cần bao nhiêu lần tăng (bao nhiêu lần lặp trong vòng lặp while).

Số lần lặp

Ta sẽ chứng minh:

Theorem 1: Số lần lặp trong vòng lặp while của thuật toán Hopcroft-KarpO(\sqrt{n}) lần.

 

Bản thân mình cảm thấy con số O(\sqrt{n}) rất khó hiểu. Trong phân tích thuật toán, rất ít khi chúng ta gặp con số kiểu này, mà chủ yếu là kiểu đa thức như O(n), O(n^2), \ldots hoăc là logarithm như O(\log n). Để hiểu lịch sử của con số này có lẽ phải truy ngược lại thuật toán blocking-flow áp dụng trong luồng cực đại của Dinitz [3] (mối quan hệ giữa luồng cực đại và cặp ghép trên đồ thị hai phía đã được giải thích ở đây), mà chúng ta không có đủ thời gian để nói đến ở đây. Thay vào đó, mình mô tả một chút ý tưởng ở mức cao trước khi đi vào chứng minh chi tiết.

Gọi M^* là một cặp ghép cực đại. Trong vòng lặp đầu tiên, tập các đường tăng tối đại cũng chính là một cặp ghép tối đại. Cặp ghép này có kích thước ít nhất một nửa kích thước của cặp ghép cực đại M^* (xem bài tập 5 của post trước). Sau vòng lặp thứ hai, ta có thể chứng minh rằng cặp ghép tìm được có kích thước ít nhất 2/3 \cdot |M^*| (mình khuyến khích bạn đọc nên thử). Tổng quát hóa lên, sau \sqrt{n} vòng lặp, cặp ghép hiện tại có kích thước ít nhất \frac{\sqrt{n}}{\sqrt{n} + 1} |M^*| (chứng minh tỉ mỉ sẽ được trình bày dưới đây). Như vậy, sau \sqrt{n} lần lặp, ta có:

|M^*| - |M| \leq \frac{1}{\sqrt{n} + 1}  |M^*| \leq \frac{1}{\sqrt{n} + 1} n/2 \leq \sqrt{n}

Do đó, chỉ cần thêm \sqrt{n} lần tăng nữa (vì mỗi lần tăng kích thước của M tăng lên ít nhất 1 đơn vị) thì ta thu được một cặp ghép cực đại. Như vậy, tổng số lần lặp cần thiết là 2\sqrt{n}. Sau đây ta sẽ trình bày cách chứng minh hình thức và tổng quát hơn.

Lemma 1: Gọi M là một cặp ghép và M^* là một cặp ghép cực đại. Nếu |M^*| = |M| + k thì đường tăng ngắn nhất của M có chiều dài không quá \frac{n}{k}-1.

 
Chứng minh: Theo Observation 1, M^* \oplus M có đúng k đường tăng (của cặp ghép M). Các đường này thỏa mãn không có hai đường nào có chung đỉnh. Do đó, đường ngắn nhất có không quá n/k đỉnh, hay nói cách khác, không quá \frac{n}{k}-1 cạnh.


Một phiên bản khác mạnh hơn Lemma 1 sẽ được coi như bài tập cho bạn đọc (bài tập 1). Một cách phát biểu khác của Lemma 1 là:

Corollary 1: Nếu đường tăng ngắn nhất có k cạnh thì |M| \geq |M^*| - \frac{n}{k+1}.

 
Ý nghĩa của Corollary 1 đó là nếu đường tăng ngắn nhất có chiều dài ít nhất \sqrt{n} thì:

|M| \geq |M^*| -\sqrt{n} \qquad (1)

Do đó, chỉ cần tăng thêm \sqrt{n} lần nữa là cặp ghép M sẽ cực đại. Vậy khi nào thì đường tăng ngắn nhất có chiều dài ít nhất \sqrt{n}? Nếu ta chứng minh được, sau mỗi lần lặp của thuật toán Hopcroft-Karp, chiều dài đường tăng ngắn nhất tăng lên 1, do đó, sau \sqrt{n} lần tăng thì chiều dài đường tăng ngắn nhất sẽ là \sqrt{n}. Như vậy tổng số vòng lặp của thuật toán Hopcroft-Karp chính là 2\sqrt{n} như trong phát biểu của Theorem 1.

Lemma 2: Gọi M là một cặp ghép, và P là một đường tăng ngắn nhất của M. Gọi P' là một đường tăng của cặp ghép M\oplus P. Ta có:

|P'| \geq |P| + 2|P\cap P'| \qquad (2)

 
Chứng minh: Nếu P\cap P' = \emptyset thì dễ thấy (2) đúng vì lúc đó P' cũng là đường tăng của MP ngắn nhất.

Gọi N = (M \oplus P) \oplus P'. N là một cặp ghép và |N| = |M|+2. Theo Observation 1, N \oplus M sẽ bao gồm 2 đường tăng (của M) mà ta gọi là P_1,P_2. Do P ngắn nhất, |P_1|, |P_2| \geq |P|.

Do N \oplus M = P\oplus P', ta có |P \oplus P'| = |P_1| + |P_2|. Theo định nghĩa của hiệu đối xứng (symmetric difference), |P \oplus P'| = |P| + |P'| - 2 |P\cap P'|. Từ đó ta suy ra dpcm.


Chứng minh Theorem 1: Như đã thảo luận ở trên, ta chỉ cần chứng minh sau mỗi lần lặp của thuật toán Hopcroft-Karp chiều dài đường tăng ngắn nhất tăng lên 1.

Do \mathcal{P} là tối đại, bất kì đường tăng nào, giả sử Q, của cặp ghép M\oplus P_1 \oplus \ldots \oplus P_k cũng phải chứa một cạnh nào đó của \mathcal{P}. Chú ý, |P_1| = |P_2| = \ldots = |P_k|. Không mất tính tổng quát, ta giả sử Q \cap P_k \not= \emptyset. Theo Lemma 2, Q \geq |P_k| + 2. Do đó Q > P_k (dpcm).


Tìm bộ đường tăng tối đại trong thời gian O(n+m)

Trong phần này ta sẽ tìm hiểu cách tìm một bộ đường tăng tối đại trong thời gian O(n+m). Kết hợp với Theorem 1, ta có:

Theorem 2: Thuật toán Hopcroft-Karp có thời gian O(m\sqrt{n}).

 

Một điều đáng chú ý trong giải thuật BipartiteMaximumMatching của bài trước là trong vòng lặp repeat-until, ta không chỉ tìm một đường tăng sau mỗi lần lặp mà một tập đường tăng tối đại (maximal set of augmenting paths), và tập này tìm được bằng thuật toán DFS. Tuy nhiên, trong thuật toán Hopcroft-Karp, ta phải tìm tập đường tăng tối đại ngắn nhất.

Để tìm tập đường tăng này, đầu tiên ta sẽ thực hiện định hướng cạnh đồ thị như bài trước: các cạnh không thuộc cặp ghép được định hướng từ A sang B và các cạnh thuộc cặp ghép được định hướng từ B sang A. Tiếp theo, ta thêm một đỉnh ảo s, nối đỉnh này với tất cả các cạnh chưa ghép của A bằng các cạnh có hướng. Từ s, ta thực hiện BFS để tìm độ dài của đường tăng ngắn nhất. Giả sử đường này có độ dài k. Khi thực hiện BFS, ta sẽ gán nhãn mỗi đỉnh v \in A\cup B bằng một số L[v] = d(s,v) chính là độ dài đường đi ngắn nhất từ s tới v. Ta có nhận xét:

Observation 2: Các điểm cuối của các đường tăng nằm trong bộ đường tăng tối đại ngắn nhất đều có nhãn k+1.

 

Sau khi thực hiện BFS, theo Observation 2, ta chỉ giữ lại các đỉnh có nhãn không quá k+1. Lúc này ta có thể thực hiện BFS như trong giải thuật BipartiteMaximumMatching của bài trước để tìm bộ đường tăng tối đại ngắn nhất. Chú ý, khi thực hiện DFS, ta chỉ thăm từ đỉnh có nhãn i tới đỉnh có nhãn i+1 mà thôi. Chi tiết giả mã như sau:

Hopcroft-Karp(G(A \cup B, E)):
    M \leftarrow \emptyset
    repeat
        L[1,\ldots, n] \leftarrow FindBFSLevel (G, M)
        k \leftarrow +\infty             \ll k is the length of the shortest aug. path\gg
        for each unmatched v \in B
            k \leftarrow \min(k, L[v])
        mark every vertex of G unvisited
        for each u \in A
            if u is univisited and unmatched
                Augmenting (G, u, L, M, k)
    until no augmenting path exists
    return M

 

FindBFSLevel(G(A \cup B, E), M):
    Q \leftarrow \emptyset             \ll Q is a queue \gg
    mark every vertex of G unvisited
    for each unmatched vertex u \in A
        L[u] \leftarrow 1
        Enqueue(Q,u)             \ll put u to queue Q \gg
        mark u visiting.
    while Q \not= \emptyset
        u \leftarrow Dequeue(Q)
        mark u visited
        if u \in A
            for each unvisited v\in N[u]
                Enqueue(Q,v)
                L[v] \leftarrow L[u]+1
                mark v visiting
        else             \ll u \in B\gg
            if M[u] is unvisited
                Enqueue(Q,M[u])
                mark M[u] visiting
                L[M[u]] \leftarrow L[u]+1
    return L[1,\ldots, n]

 

Augmenting(G(A \cup B, E), u, L, M, k):
    mark u visited
    for each v \in N[u]             \ll v \in B \gg
        if v is unmatched             \ll found an augmenting path \gg
            M[v] \leftarrow u             \ll augmenting \gg
            return True
        if v is unvisited and L[v] = L[u] + 1
            mark v visited
            if M[v] unvisited and L[v] < k and Augmenting(G, M[v],L, M,k)
                M[v] \leftarrow u
                return True
    return False

 

Code C:
to-do

Remark: Mặc dù thuật toán Hopcroft-Karp được đề xuất cách đây hơn 40 năm, cho đến tận 2013 Madry [4] mới tìm ra thuật toán thực sự nhanh hơn Hopcroft-Karp khi đồ thị đầu vào đủ thưa. Tuy nhiên, thuật toán của Madry phức tạp hơn thuật toán Hopcroft-Karp rất nhiều.

Tham khảo

[1] J. E. Hopcroft and R. M. Karp. An n^{5/2} algorithm for maximal matchings in bipartite graphs. SIAM Journal on Computing (1973): 225-231.
[2] U. Zwick. Maximum matching in bipartite and non-bipartite graphs. Tel Aviv University, 2009.
[3] E. A. Dinic. Algorithm for Solution of a Problem of Maximum Flow in a Network with Power Estimation. Soviet Math Doklady (1970): 1277-1280.
[4] A. Madry. Navigating central path with electrical flows: From flows to matchings, and back. 2013 IEEE 54th Annual Symposium on Foundations of Computer Science (FOCS). IEEE, 2013.

Bài tập

Bài tập 1: Chứng minh rằng Lemma 1 vẫn đúng nếu ta thay \frac{n}{k}-1 bằng \frac{|2M^*|}{k}-1.

Facebook Comments

Tags: , , , ,

« Older entries