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: Isolation Lemma và ứng dụng.

Bài viết mới: Ứng dụng của cặp ghép trong đồ thị hai phía: phủ chu trình, phủ đỉnh và phủ ma trận.

Bài viết mới: phân tích thuật toán. Bài này dành cho các bạn mới bắt đầu học cách phân tích thuật toán cũng như tìm hiểu ý nghĩa của các kí hiệu O(.), o(.), \Omega(.), \Theta(.).

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

Đẹp 5

Trong bài này, chúng ta tìm hiểu một kết quả vô cùng đẹp của lý thuyết khoa học máy tính: Isolation Lemma (bổ đề cô lập). Bổ đề này lần đầu tiên được phát biểu và chứng minh bởi Valiant và Vazirani [1]. Sau đó Mulmuley, Vazirani và Vazirani [2] ứng dụng một phiên bản hơi khác trong bài toán cặp ghép, làm cho bổ đề này trở nên nổi tiếng. Bổ đề phát biểu như sau:

Isolation Lemma: Cho một tập gốc (ground set) gồm $n$ phần tử $[n] = \{1,2,\ldots, n\}$ và một họ (family) các tập con $\mathcal{F}$ của $[n]$. Với mỗi $x \in [n]$, ta gán cho nó một trọng số $w(x)$ là một số ngẫu nhiên từ tập $[N] = \{1,2,\ldots, N\}$. Ta định nghĩa trọng số của mỗi tập con $S \in \mathcal{F}$ như sau:

$w(S) = \sum_{x\in S}w(x)\qquad(1)$

Với xác suất ít nhất $1-n/N$, tồn tại duy nhất một tập $S \in \mathcal{F}$ có trọng số nhỏ nhất.

 
Về mặt lí thuyết, Isolation Lemma thực sự đáng kinh ngạc: nếu chọn $N = 2n$ thì xác suất tồn tại duy nhất tập con $S$ có trọng số nhỏ nhất $\geq 1/2$; không phụ thuộc vào kích thước của tập $\mathcal{F}$. Trong trường hợp tồi nhất, $\mathcal{F}$ có thể có tới $2^{n}-1$ tập con.

Nếu vào trang Wikipedia, bạn sẽ thấy một loạt các ứng dụng của Isolation Lemma trong lý thuyết khoa học máy tính. Ở đây có một ứng dụng mà mình rất thích: đảm bảo tính duy nhất của đường đi ngắn nhất giữa mọi cặp đỉnh trong đồ thị có trọng số không âm.

Remark: Ta sử dụng $[n]$ để kí hiệu tập các số nguyên $\{1,2,\ldots, n\}$.

Ứng dụng trong đường đi ngắn nhất

Weight Perturbation: Gọi $G(V,E)$ là một đồ thị đơn, vô hướng trong đó mỗi cạnh $e\in E$ có một trọng số $w(e) \geq 0$. Bài toán đặt ra là tìm một hàm trọng số không âm $\ell(.)$ cho các cạnh của $G$ sao cho với mọi cặp đỉnh $u,v$ bất kì của đồ thị ($u \not= v$):

  1. Đường đi ngắn nhất $u$ và $v$ với hàm trọng số $\ell(.)$ cũng là đường đi ngắn nhất giữa hai đỉnh đó với hàm trọng số $w(.)$.
  2. Đường đi ngắn nhất giữa $u,v$ với hàm trọng số $\ell(.)$ là duy nhất.

 
Lời giải: Để đơn giản, trước hết ta giả sử trọng số của mỗi cạnh trong $G$ là $0$, i.e, $w(e) = 0 \quad \forall e\in E$. Ta gán cho mỗi cạnh một trọng số \ell'(e) là một số ngẫu nhiên từ tập $[|V|^2|E|]$. Cố định hai đỉnh $u,v$. Gọi $\mathcal{F}_{uv}$ là tập các đường đi ngắn nhất (có cùng trọng số 0) từ $u$ tới $v$. Theo Isolation Lemma, xác xuất tồn tại duy nhất một tập con $S \in \mathcal{F}_{uv}$ có trọng số nhỏ nhất ít nhất là:

$1 - \frac{|E|}{|V|^2|E|} = 1- \frac{1}{|V|^2}\qquad(2)$

Đây cũng là xác suất mà đường đi ngắn nhất giữa $u,v$ với hàm trọng số $\ell'(.)$ là duy nhất. Do có không quá $|V|^2/2$ cặp đỉnh $u,v$, xác suất đề đường đi ngắn nhất giữa hai đỉnh bất kì với hàm trọng số $\ell'(.)$ trở nên duy nhất là ít nhất:

$1 - \frac{|V|^2/2}{|V|^2} = 1/2 \qquad(3)$

Ta quay trở lại trường hợp tổng quát với hàm trọng số $w(.)$ không âm bất kì. Coi trọng số của mỗi cạnh được biểu diễn bởi một số nguyên $p$ bít trong đó $p = \lfloor \log_2( \max_{e\in E }w(e)) \rfloor +1$. Thêm q bít 0 vào sau biểu diễn nhị phân của trọng số mỗi cạnh (tương đương với nhân trọng số mỗi cạnh với $2^q$); ở đây:

$q = \lfloor \log_2( |V|^2|E|) \rfloor +1 \qquad(4)$

Chú ý, trọng số $\ell'(e)$ tìm được bằng cách áp dụng Isolation Lemma ở trên có thể biểu diễn bởi tối đa $q$ bít. Ta định nghĩa:

$\ell(e) = w(e)2^q + \ell'(e) \qquad(5)$

Do $\ell'(.)$ là một hàm ngẫu nhiên, $\ell(.)$ cũng là một hàm ngẫu nhiên. Không khó để thấy rằng, với xác suất ít nhất $1/2$, hàm $\ell(.)$ thỏa mãn hai tính chất cần có của bài toán Weight Perturbation. Ta có thể tăng cường xác suất này lên $1-\epsilon$ với $\epsilon$ nhỏ tùy ý bằng cách lặp đi lặp lại nhiều lần gán trọng số cạnh ngẫu nhiên.


Trong một số tình huống, giả thiết đường đi ngắn nhất giũa mọi cặp đỉnh là duy nhất làm việc thiết kế giải thuật trở nên đơn giản hơn rất nhiều. Ví dụ, Krauthgamer, Nguyễn, Zondiner [3] sử dụng giả thiết này trong bài toán preserving terminal distance. Borradaile, Zafirani và Nayyeri [4] sử dụng một giải thiết tương tự để giải bài toán shortest disjoint paths.

Tóm lại, nếu bạn làm việc các bài toán liên quan đến đường đi thì Isolation Lemma cho phép bạn giả sử rằng đường đi ngắn nhất giữa một hoặc nhiều cặp đỉnh là duy nhất.

Chứng minh Isolation Lemma

Chứng minh Isolation Lemma khá đơn giản (nhưng không tầm thường). Trên trang wikipedia trình bày chi tiết 2 chứng minh khác nhau: chứng minh của Mulmuley, Vazirani, và Vazirani [2] và chứng minh của Joel Spencer. Gần đây, Ta-Shma [5] trình bày một chứng minh khác (tại thời điểm paper này được publish, Ta-Shma là một học sinh cấp 3), cho một kết quả mạnh hơn Isolation Lemma một chút.

Chứng minh Isolation Lemma: Xét một phần tử $x \in [n]$. Gọi:

$\alpha(x) = \min_{S\in \mathcal{F}, x\not\in S}w(S) - \min_{S \in \mathcal{F}, x\in S } w(S\setminus \{x\})\qquad(6)$

Nhận xét: giá trị của $\alpha(x)$ không phụ thuộc vào $w(x)$. Do đó, ta có thể giả sử giá trị của $w(x)$ được gán sau tất cả các phần tử khác thì $\alpha(x)$ xác định trước khi $w(x)$ được gán (ta đang sử dụng deferred decision principle). Như vậy, xác suất để $w(x) = \alpha(x)$ là không quá $\frac{1}{N}$. Từ đó suy ra:

Claim: Xác suất để tồn tại một phần tử $x\in [n]$ sao cho $w(x) = \alpha(x)$ là không quá $\frac{n}{N}$.

Giả sử tồn tại $A, B \in \mathcal{F}, A\not= B$ sao cho $w(A) = w(B)$ và $w(A), w(B)$ là nhỏ nhất. Gọi $y$ là một phần tử bất kì của $A\setminus B$. Ta có:

$\begin{array}{lcl} \alpha(y) & = & \min_{S\in \mathcal{F}, y\not\in S}w(S) - \min_{S \in \mathcal{F}, y\in S } w(S\setminus \{y\}) \\ & = & w(B) - (w(A) - y) \\ & = & w(y) \end{array} \qquad (7)$

Theo Claim trên, xác suất này không quá $n/N$. Như vậy, xác suất không tồn tại $A,B$ như vậy là ít nhất $1 - n/N$.


Tham khảo

[1] L. G. Valiant and V. V. Vazirani. NP is as easy as detecting unique solutions. Proceedings of the Seventeenth Annual ACM Symposium on Theory of Computing (STOC'85). ACM, 1985.
[2] K. Mulmuley and U. V. Vazirani and V. V. Vazirani. Matching is as easy as matrix inversion. Proceedings of the Nineteenth Annual ACM Symposium on Theory of Computing (STOC'87). ACM, 1987.
[3] R. Krauthgamer and H. L Nguyễn, and T. Zondiner. Preserving terminal distances using minors. SIAM Journal on Discrete Mathematics 28.1 (2014): 127-141.
[4] G. Borradaile and A. Nayyeri and F. Zafarani. Towards single face shortest vertex-disjoint paths in undirected planar graphs. Algorithms-ESA 2015. Springer, Berlin, Heidelberg, 2015. 227-238.
[5] N. Ta-Shma. A simple proof of the Isolation Lemma. Electronic Colloquium on Computational Complexity (ECCC). Vol. 22. 2015.

Facebook Comments

Tags: , , , ,

« Older entries