RANGE OF VALUE

Bài viết này không trình bài về một kĩ thuật giải nào cả, chỉ là một tiểu xảo. Khi giải quyết vấn đề, ta thường chú ý tới kích thước của tập hợp mà không quan tâm đến độ lớn giá trị của các phần tử. Đôi khi nó là mấu chốt để giải quyết vấn đề.

Sau khi mình học xong các giải thuật sort, có bạn nói rằng đã từng đọc đâu đó có giải thuật sort chỉ chạy trong O(N). Lúc đó mình chắc chắn không tin rồi. Nhưng sau khi tìm hiểu thì lại có giải thuật chạy trong O(N), tiếp tục đọc kĩ lại thì ra giải thuật này không tổng quát. Ta sẽ xem chi tiết nó hiện thực như thế nào.

Ví dụ 1: Cho một dãy gồm N (0<N<10^6) số a1, a2,.., aN (0<=ai<=10^6). Bạn hãy sort lại dãy theo thứ tự tăng dần.

Với các giải thuật sort tổng quát, ta so sánh các giá trị của ai và aj, nếu thằng nào nhỏ hơn thì đặt ra trước. Với cách giải cho bài toán sort trong O(N), ta không cần thực hiện một phép so sánh nào cả.

Ta sẽ quét qua tất cà các giá trị của có thể của ai, tức là từ 0->10^6 dựa vào giả thuyết 0<=ai<=10^6. Ta đếm số lần xuất hiện của 0, 1, 2,...10^6 trong dãy {aN}. Nếu có k giá trị 0 trong dãy, ta in ra k số 0, cứ tiếp tục cho 1, 2…10^6

Ví dụ với dãy {1, 5, 2, 1}. Có hai giá trị 1, ta in ra hai số 1, tiếp tục in ra một số 2, không in 3 và 4, cuối cùng là in một số 5. Kết quả là {1, 1, 2, 5}.

Cụ thể code như sau:

Nhận xét:

1.       Với cách làm này, thực tế không phải là O(N). Giả sử giá trị lớn nhất của ai là Max (trong trường hợp này Max=10^6). Độ phức tạp của giải thuật là max{N, Max}. Do trường hợp này N=Max nên ta dễ nhầm lẫn là O(N). Tuy là hai vòng for lồng nhau nhưng đừng lầm tưởng độ phức tạp là O(Max*N) nhé, vì ta có ràng buộc Tổng(b[i])=N.

2.       Nếu miền giá trị của ai lớn lên, nghĩa là giải thuật cũng chạy chậm hơn, mà bộ nhớ dùng nhiều hơn. Vì ta ko lưu dãy {aN}, mà ta lưu số lần xuất hiện của mỗi giá trị {bMax}.

Ví dụ 2:

Cho một dãy N (N<10^6) số nguyên a1, a2,…, aN (0<ai<10^5) và một số nguyên P (P<10^10). Bạn hãy tính toán có bao nhiêu cách chọn hai số nguyên khác nhau ai và aj từ dãy đã cho sao cho ai*aj=P.

Ý tưởng đầu tiên trong đầu mọi người là 2 vòng for chạy lồng nhau với độ phức tạp O(N^2), đúng không? Cách làm này đúng nhưng chạy rất chậm với N=10^6. Với N=10^6 thì ta phải tìm ra giải thuật có thể chạy trong O(N) mới có thể đáp ứng yêu cầu thời gian. Ta để ý, miền giá trị của ai nhỏ hơn 10^5. Ta có thể lưu thành dãy {bM} trong đó b[i] chứa số lần xuất hiện của giá trị i. Như vậy kết quả sẽ là Tổng(b[i]*b[P/i]) với i chạy từ 1->10^5. Vài xử lý nhỏ nhặt nữa ta sẽ có lời giải. 

Bạn có thể tham khảo lời giải bằng C++ tại đây.

Khi ta chú ý vào miền giá trị của các phần tử, ta nhìn bài toán với góc độ khác một tí, thay vì chạy qua hai vòng lặp theo N.

Ví dụ 3 (chú ý ví dụ này)

Cho dãy N số nguyên a1, a2,…, aN (N<10^5 và 0<= ai<=10). Đối với mỗi số, bạn phải in ra có tất cả bao nhiêu số có thứ tự trước nó và nhỏ hơn nó. Cụ thể là với mỗi ai, ta phải đếm có bao nhiêu số trong dãy {a1, a2, .., ai-1} nhỏ hơn ai.

Cách giải thì tương tự như trên, chỉ cần ghi nhận lại số lần lặp lại của các giá trị từ 0->10. Bạn tự code bài này thử nge, có thể xem code bằng C++ tại đây. Điều mình muốn nói ở đây là hai nhận xét sau:

Nhận xét 1

Đối với ví dụ trên, nếu miền giá trị của ai là [-10, 10], rõ ràng ta không thể đếm được số lượng của các giá trị âm, vì trong các ngôn ngữ lập trình thông dụng, không cho phép ta truy xuất chỉ số âm. Ví dụ ta không thể gọi b[-1]++; Tuy nhiên ta có một kĩ thuật giải quyết vấn đề này: dịch chuyển các giá trị một đoạn 10, lúc này miền giá trị là [0, 20]. Khi ta cộng thêm 10, nó không làm ảnh hưởng bản chất của bài toán, vì ta chỉ quan tâm thứ tự của chúng, chứ ko quan tâm giá trị thật của chúng (ai < aj) <=> (ai+10 < aj+10). Đối với ví dụ 2 thì áp dụng chiêu này là ko được rồi, nó cần giá trị thật của ai.

Tới đây ta vẫn làm như trên, code được viết bằng C++ tại đây.

Nhận xét 2:

Ta xét bài toán khó hơn, giá trị của ai trong [0, 10^9]. Rõ ràng thì cách làm này không khả thi. Thứ nhất là bộ nhớ, thứ hai là thời gian chạy. Ta nhận thấy rằng, dù ai nằm trong [0, 10^9], nhưng N<10^5. Vì vậy, chỉ có tối đa 10^5 giá trị trong [0, 10^9] sẽ xuất hiện trong dãy {aN}. Song song đó, ta không quan tâm giá trị thực của chúng, mà ta chỉ quan tâm thứ tự (sự lớn bé) của chúng. Ta sẽ chuyển các giá trị của {aN} từ [0, 10^9] thành [0, N].

Ví dụ ta có dãy 5 phần tử {1, 10^7, 7, 10^7, 10^9} thì kết quả là 0, 1, 1, 2, 4. Ta sẽ chuyển dãy đã cho thành {1, 3, 2, 3, 4} thì kết quả vẫn không thay đổi 0, 1, 1, 2, 4. Vì thứ tự của chúng vẫn không thay đổi: số đầu tiên vẫn nhỏ nhất, số thứ hai thì lớn nhì,…,số cuối cùng vẫn lớn nhất.

Để làm được việc này, ta có thể dùng binary search, tuy nhiên nên dùng các util của các ngôn ngữ lập trình, chẳng hạn map của C++, hay Hashtable của Java…

Tới đây, bài toán của ta là: Cho dãy N số nguyên a1, a2,…, aN (N<10^5 và 1<= ai<=N). Đối với mỗi số, bạn phải in ra có tất cả bao nhiêu số có thứ tự trước nó và nhỏ hơn nó. 
Để giải bài toán này, ta cần dựa vào miền giá trị của ai và một cấu trúc dữ liệu để giải quyết nó. Cấu trúc dữ liệu đó là Binary Index Tree. Ta sẽ tìm hiểu về nó trong bài viết sau về các cấu trúc dữ liệu hay dùng. Bạn có thể tham khảo trước lời giải bằng C++ tại đây, chú ý cách chuyển từ dãy cũ sang dãy mới. Ý tưởng ở đây là ta dùng một hashtable để giữ mapping giữa giá trị cũ và mới.

Tổng kết:

Với bài viết này, tôi chỉ muốn bạn chú ý vào miền giá trị của vấn đề cần giải quyết. Cùng một vấn đề, miền giá trị khác nhau thì độ khó của bài toán khác nhau hẳn.Vì thế ta nên chú ý vào miền giá trị của các phần tử, đôi khi cũng cho ta góc nhìn khác về bài toán.

Người viết: Dương Thành Phong

BINARY SEARCH

Binary Search là kĩ thuật rất quen thuộc, có ứng dụng nhiều. Nhắc tới Binary Search, ai cũng nghĩ ngay đến "có một dãy số đã sort, để tìm một phần tử nào trong dãy thì chia dãy làm hai phần, rồi so sánh phần tử cần tìm với phần tử ngay giữa, còn nhiều xử lí nữa ..., quan trọng là ta tìm kiếm được phần tử trong dãy trong thời gian log(n), với n là kích thước của dãy". Có phải bạn cũng nghĩ như vậy? Uh, bạn hiểu đúng rồi đó. Hầu hết các ngôn ngữ lập trình phổ biến có hỗ trợ sort và search, nên đôi khi ta ít trực tiếp viết code binary search. Thật sự binary search được dùng khá nhiều hơn là ta thường nghĩ. Ứng dụng của binary search thì khá nhiều, mình đưa ra hai trường hợp sau để bạn hiểu rõ hơn về binary search.

1. Binary search và bài toán tối ưu

Bài toán tối ưu: có nhiều phương án cho một vấn đề, nhiệm vụ là phải chọn ra một phương án tốt nhất dựa trên một tiêu chí nào đó.

Ta xét ví dụ sau đây:

Ví dụ: Bạn muốn mua N (N<=10^5) món hàng trong một cửa hàng. Mỗi món hàng có giá trị là Vi (1<=i<=N, 1<=Vi <= 10^6 VND). Cửa hàng đang có đợt khuyến mãi đặc biệt, chủ cửa hàng cho bạn trả giá với cách sau: Bạn đưa ra một số M, tất cả các món hàng nào có giá lớn hơn M thì bạn được quyền mua với giá là M, ngược lại thì bạn có thể mua với giá đúng giá trị của nó.

Chẳng hạn cửa hàng có 3 món hàng trị giá 30, 50 ,90. Nếu bạn trả giá với M=60, thì bạn sẽ mua 3 món hàng này với giá 30, 50, 60.

Dĩ nhiên là có điều kiện ràng buộc rồi: sau khi bạn đưa ra M, thì tổng giá tiền mà bạn phải trả phải lớn hơn hoặc bằng S, 0<=S<=(tổng các Vi). Ví dụ như trường hợp vừa nêu, nếu chủ cửa hàng yêu cầu S=140, thì bạn không thể đưa ra giá M = 59.

Nhiệm vụ của mình là dựa vào các giá trị V1, V2, ..., VN và S để tìm ra M tối ưu, tức là số tiền phải trả là nhỏ nhất.

Phân tích: Dĩ nhiên là ta cần tìm M càng nhỏ càng tốt sao cho thỏa mãn điều kiện của cửa hàng. Với yêu cầu của cửa hàng, ta có thể chạy qua từng giá trị của M từ 1 đến giá trị lớn nhất, nếu giá trị nào M thỏa yêu cầu thì ta ngừng và đó chính là kết quả mà ta cần tìm. Tuy nhiên với cách làm này thì trong trường hợp xấu nhất ta phải mất O(10^6*N) để tìm ra M. Con số này không thể chấp nhận được với các máy tính thông thường để tìm ra kết quả trong vài giây.

Ta có một số nhận xét sau:

+ Nếu M = M0 không thỏa yêu cầu, thì (M0-1) cũng sẽ không thỏa yêu cầu, từ đây suy ra tất cả M nhỏ hơn M0 đều ko thỏa (bạn tự chứng minh, dùng phản chứng) (*)

+ Nhận xét trên tương đương với, nếu M = M0 thỏa yêu cầu, thì (M0+1) cũng thỏa yêu cầu (bạn tự chứng minh)

+ M = max(Vi) luôn thỏa yêu cầu vì S<=(tổng các Vi)

Từ những nhận xét này ta suy ra nhận xét tiếp theo:

Gọi M' là kết quả cần tìm, tức là M’ là số nhỏ nhất thỏa.

       + Nếu M=M0 thỏa yêu cầu, thì M'<=M0 (vì M' là nhỏ nhất).

       + Nếu M=M0 không thỏa yêu cầu, thì M'>M0 vì theo nhận xét (*).

Tới đây ta có thể suy luận ra để giải quyết bài toán:

Với cách này, chương trình của mình sẽ chạy trong log(10^6)*N = 20*N

Code được viết bằng C++ tại https://www.dropbox.com/s/ajz5xsrgsxrilm3/Buying.cpp . Bạn chú ý khi dùng binary search trên số nguyên, cần thận với việc làm tròn số nguyên, ví dụ nếu left=2, right=3. Nếu ko cẩn thận sẽ bị lặp vô tận trong vòng lặp.

Đó chính là ý tưởng binary search. Để tìm một phần tử x trong tập hợp A thỏa điều kiện nào đó. Ta chia A thành hai tập A1, và A2 có số phần tử gần bằng nhau. Sau đó xác định x thuộc A1 hoặc A2. Loại bỏ một tập và tiếp tục quá trình này cho đến khi tìm được x hoặc xác định x không thuộc tập A. Còn về thời gian để tìm ra phần tử x, ta dễ dàng tính được log(n)*(thời gian để xác định x thuộc một trong A1 hoặc A2), với n = |A|.

Ta tìm lời giải tối ưu (nhỏ nhất hoặc lớn nhất) cho một bài toán. Bài toán có dạng:

Tìm M nhỏ nhất (lớn nhất) sao cho hàm Check(M) là true. Check() chính là yêu cầu bài toán. Để áp dụng được binary search thì phải thỏa điều kiện sau: nếu Check(M0) là false thì Check(M) là false với mọi M<=M0 hoặc phát biểu tương đương nếu Check(M0) là true thì Check(M) là true với mọi M>=M0.

2. Binary search và kĩ thuật phân tập

Một kĩ thuật cũng khá hay khi áp dụng binary search, đó là kĩ thuật phân tập.

Ví dụ: cho một tập S có N phần tử {a1, a2, a3,… aN}, bạn hãy kiểm tra có tồn tại tập con của S thỏa mãn tổng các phần tử của tập con đó là K. (N<=30)

Cách giải: đây là bài toán NP, vì thế ta phải duyệt qua tất cả các tập con để tìm ra kết quả. Nếu duyệt qua bình thường thì ta tốn thời gian 2^N, con số này cũng khá cao không thể duyệt qua hết nỗi.

Độ phức tạp: tập S có 2^N tập con => độ phức tạp 2^N khoảng 10⁹ , thời gian chạy này không thể cho phép được.

Cải tiến: Ta chia tập S thành 2 tập S1 = {a1, a2, …, aN/2} và S2={aN/2+1, aN/2+2,…, aN} hai tập này có số phần tử bằng nhau, nếu N lẻ thì S2 nhiều hơn 1 phần tử, ta liệt kê tất cả các tập con của S1, S2; sau đó sort lại các tập con của S2 theo thứ tự tăng dần theo giá trị tổng các phần tử của tập con đó. Ứng với mỗi tập con của S1 (giả sử tập con này là A có tổng là K1) ta dùng binary search để tìm ra tập con tương ứng của S2 có tổng là K-K1 (gọi tập con này là B). Lúc này ta có một tập con C = A U B của S thỏa tổng các phần tử là K. Cứ duyệt qua hết tập con S1 là ta có đáp án.

Độ phức tạp: Sinh S1, S2 mất 2*2^(N/2), mỗi tập con của S1, ta tìm một tập con của S2, thao tác này mất chi phí : 2^(N/2)*log₂(2^(N/2)) = N/2*2^(N/2)

=>  O(N/2*2^(N/2)) = 10⁶, chạy 1s là Ok.

Nhận xét:

1. Với cách làm này thì ta có thể giải cho các trường hợp N<=30, nếu N lớn hơn cũng không khả thi vì bản chất bài này vẫn là NP.
2. Việc sinh tập S1, S2 ta có thể vận dụng từ bài viết BITMASKS.

Bạn có thể xem code C++ tại https://www.dropbox.com/s/ikct96n7hnpep89/SubSet.cpp, code này tìm ra tất cả các tập con thỏa tổng của các phần tử bằng K.

Các bài toán áp dụng kĩ thuật phân tập: 

http://vn.spoj.pl/problems/LQDDIV/

https://vn.spoj.pl/problems/VECTOR/

https://vn.spoj.pl/problems/COIN34/

http://vn.spoj.pl/problems/CHNREST/

Tổng kết:
Binary search thường được sử dụng khá nhiều, nhưng nó hay được dùng  kết hợp với những kỹ thuật để giải quyết vấn đề. Bạn có thể luyện skill về binary search tại http://codeforces.com/problemset/tags/binary%20search

Người viết: Dương Thành Phong

BITMASKS

Mình chắc chắn ai từng lập trình đều đã dùng kĩ thuật này, nhưng mọi người có thể gọi bằng những tên gọi khác nhau hoặc chẳng thèm gọi tên là gì. Ta bắt đầu làm rõ kĩ thuật này.

Chẳng hạn ta có 3 bóng đèn. Mỗi bóng đèn có 2 trạng thái là bật hay tắt. Để biểu diễn trạng thái của 3 bóng đèn, ta có thể dùng một dãy có 3 phần tử để biểu diễn, ví dụ bool a[3]. Nếu số bóng đèn ít, ta có thể dùng một cách khác để biểu diễn: ta dùng duy nhất một số nguyên để biểu diễn chúng. Giả sử hai bóng đầu bật và bóng cuối tắt, ta có thể biểu diễn 110(cơ số 2) = 6(cơ số 10). Như vậy với một số 6 ta có thể biết được trạng thái hiện tại của ba bóng đèn, tương tự 7 = 1112 biểu diễn cả 3 bóng đều bật.

Bitmask: Để biểu diễn trạng thái cho nhiều đối tượng, ta phải dùng nhiều biến để lưu lại trạng thái của chúng. Thay vào đó ta dùng duy nhất một biến để biểu trạng thái cho tất cả. Chắc chắn là bạn đã dùng kĩ thuật này rồi? Khi làm web, người ta cũng hay dùng cách này để biểu diễn role của user.

Ta sẽ đi qua từng ví dụ để rõ hơn về nó. 

1.   Dùng bitmask để duyệt “trâu bò“

Bắt đầu bằng một ví dụ:

Một đầu bếp đang chuẩn bị một bữa ăn với N nguyên liệu (N < 20). Vị đầu bếp muốn bữa ăn phải có đầy đủ K chất (K < 20) C1, C2, …, Ck. Để vấn đề dễ hiểu, ta chưa quan tâm đến lượng của các chất trong bữa ăn. Với mỗi nguyên liệu ta biết được nó có chứa chất nào trong thành phần của nó. Đầu bếp muốn biết tất cả các tập nguyên liệu mà tập đó chứa đầy đủ K chất.

Dữ liệu:

Dòng 1: N và K

N dòng tiếp theo: mỗi dòng chứa K số thể hiện thành phần của mỗi nguyên liệu, số thứ i thể hiện nó có chứa chất Ci hay ko, là 1 nếu nó chứa chất Ci,  0 ngược lại.

Chẳng hạn:

6 7

1 0 0 1 0 1 0

0 1 0 0 1 0 0

1 0 0 0 0 0 1

0 0 1 1 0 0 0

1 1 0 0 0 0 0

0 0 0 0 0 1 0

Đầu bếp có 6 nguyên liệu, và ông ta quan tâm bữa ăn phải chứa đủ 7 chất. Nguyên liệu thứ nhất chỉ chứa chất C1, C4, C6

Giải quyết:

Với mỗi nguyên liệu, nó sẽ có trạng thái là được chọn hoặc không được chọn. Mỗi nguyên liệu có 2 trạng thái, vậy sẽ có tất cả 2^N trạng thái cho N nguyên liệu. Với những trường hợp N nhỏ  thì duyệt qua tất cả các trạng thái là chuyện dễ dàng (2^20 ~ 10^6). Cách duyệt qua tất cả các phương án để tìm lời giải gọi là duyệt trâu bò. Vấn đề là thể hiện cách duyệt qua tất cả trạng thái bằng ngôn ngữ lập trình. Bạn có thể dùng đệ qui để giải quyết, nó vẫn ok. Tuy nhiên, mình muốn trình bày bằng bitmask, code ngắn, dễ sử dụng lại.

Do có 2^N trạng thái, tất cả trạng thái là 0000002=0, 0000012=1, 0000102=2, …, 1111112=2^N-1. Tất cả trạng thái là các số nguên chạy từ 0 đến 2^N-1. Nên chỉ với một vòng lặp for(state=0; state < 2^N; state++) đã biểu diễn được việc “duyệt qua tất cả trạng thái“

Với mỗi giá trị của state, ta muốn biết nguyên liệu thứ i có được chọn hay ko, ta chỉ cần xét biểu thức (state and 2^i), i tính từ 0 đến K-1. Nếu biểu thức này lớn hơn 0 nghĩa là nguyên liệu thứ i được chọn trong trạng thái state, ngược lại thì 0. and ở đây là phép and bit.(Bạn tự kiểm chứng biểu thức này).

Một điểm chú ý nữa, Với mỗi nguyên liệu thứ i ta cũng chuyển thành một số b[i] để diễn tả thành phần của nó. Ví dụ với nguyên liệu thứ nhất, ta sẽ biểu diễn b[0] = 10010102=74.

Như vậy nếu các nguyên liệu được chọn có các giá trị b[i] or với nhau hợp thành 11111112=(2^K-1) thì tập đó thỏa mãn. or ở đây là phép or bit

Code:

For(state=0; state < 2^N; state++){

            Sumarize = 0;

            For(i=0; i < N; i++) if((state and 2^i) > 0){

                     Sumarize = Sumarize or b[i];

            }

            If(Sumarize == (2^K-1)){

                    //Print the result

            }

}

Độ phức tạp của đoạn code trên là O(2^N*K), với N=K=20 thì chạy trong 1s là ok.

Nhìn code rất dễ hiểu phải không? Bạn có thể xem code bằng C++ tại https://www.dropbox.com/s/u387lban20nk3l7/cheif.cpp

2.     Bitmask để biểu diễn trạng thái.

Từ đầu bài viết tới giờ, chúng ta chỉ biểu diễn không hoặc có. Thực tế kĩ thuật này được hiểu xa hơn một tí, ta xét ví dụ khá quen thuộc sau:

Ta có ba chai nước có thể tích là V1, V2, V3 (Vi < 10)  (đơn vị thể tích). Ban đầu ta có chai nước thứ nhất đầy nước và hai chai còn lại không chứa gì cả. Bạn cần tìm cách rót sao cho bình V3 chứa K (K<=V3) thể tích nước và số lần rót là ít nhất. Bạn được thực hiện một trong các cách sau:

1. Rót hết nước từ chai này sang chai khác (được phép tràn)
2. Rót nước từ chai này sang chai khác cho đến lúc chai khác được nhận đầy nước.
3. Rót bỏ hết nước từ một chai.

Với mỗi trạng thái (x1, x2, x3) thì ta cũng có thể dùng dãy 3 phần tử để diễn tả chúng. Tuy nhiên ta cũng có thể diễn tả trạng thái của ba chai bằng một số nguyên X= (x1*(V2+1)+x2)*(V3+1)+x3. Bạn có thắc mắc tại sao nhân với V2+1 và V3+1. Thật ra nhân với số lớn hơn 2 số này vẫn thỏa, hai số này là hai số nhỏ nhất có thể nhân vào, dựa vào tính chất của phép mod. Với cách diễn đạt này, thì đảm bảo với mỗi bộ số (x1, x2, x3) khác nhau thì X cũng khác nhau (bạn tự kiểm tra bằng phản chứng). Với mỗi số nguyên X biểu diễn cho một thái, ta có thể biết được lượng nước trong mỗi chai

-       x1 = X / ((V2+1)(V3+1))

-       x2 = (X/(V3+1)) mod (V2 +1)

-       x3 = X mod (V3+1)

Tổng cộng ta có (V1+1)*(V2+1)*(V3+1) trạng thái, ta cũng biết được quy tắc chuyển từ trạng thái này sang trạng thái khác thông qua các cách rót nước. Ta xây dựng một đồ thị có (V1+1)*(V2+1)*(V3+1) đỉnh, xây dựng các cạnh nối bằng các quy tắc của đề bài. Trạng thái bắt đầu là (V1, 0 ,0), số nguyên biểu diễn là V1*(V2+1)*(V3+1). Trạng thái kết thúc là (0, 0, K), số nguyên biểu diễn là K.

Có đồ thị, việc tìm đường đi ngắn nhất từ đỉnh này đến đỉnh khác là dễ dàng thông qua các giải thuật có sẵn. Với bài này ta có thể dùng breadth first search hoặc dijkstra. Ở đây ta không chú tâm đến việc giải bài này, ta chỉ tìm hiểu cách tiếp cận biểu diễn trạng thái bằng một số nguyên. Bạn có thể xem lời giải bằng C++ tại https://www.dropbox.com/s/3sl45k6hskgtypm/ThreeBottles.cpp.

3.     Bitmask và quy hoạch động (copy từ Giang Vi)

Bài toán tìm đường đi Hamilton là một bài toán khá quen thuộc: cho N đỉnh, tìm đường đi sao cho mỗi đỉnh được thăm duy nhất một lần, và chi phí thăm N đỉnh là thấp nhất.

Với bài toán này, thông thường nếu N nhỏ (N <=10), ta có thể giải quyết bài toán bằng phương pháp nhánh cận. Tuỳ vào cách đặt cận mà tốc độ chương trình có thể được nâng lên, tuy nhiên thời gian chạy chương trình vẫn có thể không đảm bảo với một số test khó.

Không những vậy, nếu giới hạn N tăng lên đến 20, thì việc sử dụng phương pháp nhánh cận để giải quyết sẽ không còn khả thi nữa. Trong trường hợp này, ta có cách tiếp cận khác để giải quyết bài toán một cách hiệu quả hơn, với độ phức tạp O(N^2*2^N). Đó chính là sử dụng quy hoạch động và bitmask (cách thường gọi là quy hoạch động trạng thái).

Ý tưởng

Để giải quyết bài toán này theo phương pháp quy hoạch động, các buớc thiết lập lời giải phải được lưu trữ để có thể tính toán từ các bài toán con. Rõ ràng ở đây, chúng ta phải lưu các đỉnh đã đi qua và đỉnh cuối cùng của một hành trình bất kỳ. Để làm việc này, ta dùng một mảng nhị phân N phần tử với ý nghĩa bit 1 tượng trưng cho các đỉnh đã được thăm và ngược lại. Từ đó, ta định nghĩa Fx [i,j] là chi phí tối ưu trong trạng thái i, j là đỉnh kết thúc hành trình (0 <= i <= 2^N -1; 1 <= j <= N).

Ví dụ:

Dãy [010011]2 tương đương trạng thái có 3 đỉnh được đi, và đỉnh kết thúc hành trình là đỉnh 5 (tính từ phải qua, bạn có thể lưu từ phải qua, vấn đề này không ảnh hưởng gì), với biểu diễn trong hệ thập phân tương ứng của dãy này là 19. Vậy hàm quy hoạch động của trạng thái này là Fx[19,5]

Chi tiết thuật toán

Với mỗi trạng thái I có j là đỉnh đến cuối cùng trong trạng thái này, xét mọi đỉnh k khác j mà k chưa được thăm trong trạng thái I. Gọi trạng thái mà hành trình của nó có chứa đỉnh k là X.

Ví dụ:

I = [010011] có các đỉnh 1,2,5 đã thăm. Giả sử k = 3 (thoả vì chưa đến được thành phố 3 trong trạng thái I), ta được trạng thái X = [010111].

Tóm lại, ở bước này: trạng thái X và trạng thái I chỉ khác nhau duy nhất ở đỉnh k. Dễ nhận thấy số thành phố đi được thấy đi được ở trạng thái X = số thành phố đi được ở trạng thái I + 1, suy ra việc tính toán Fx[X,k] sẽ dựa vào kết quả bài toán có kích thước nhỏ hơn nó là Fx[I,j]

Tiếp theo, ta sẽ tối ưu Fx[X,k] theo công thức : Fx[X,k] = Min (Fx[X,k], Fx[I,j] + C[j,k]);

Công thức trên sẽ lấy chi phí nhỏ hơn giữa trạng thái hiện tại (hành trình kết thúc tại k) và trạng thái hành trình kết thúc tại j cộng với chi phí di chuyển từ j -> k.

Bước tìm đường đi có chi phí ngắn nhất chính là giá trị nhỏ nhất trong tất cả đường đi qua N đỉnh mà đường đi đó kết thúc tại thành phố i. Từ đó ta có kết quả bài toán là Min (Fx [2^N - 1, i]) với i =1..N.

Số 2^N-1 thể hiện trạng thái mà N đỉnh đã được thăm. Ví dụ: 2^6 - 1 = 6310 = 1111112

Như đã đề cập ở trên, độ phức tạp cở khoảng 2^N*(N^2), dù sao cũng nhỏ hơn N!

Bạn có thể xem code viết bằng C++ tại https://www.dropbox.com/s/f1u4af4dpxghu72/Hamilton.cpp

Người viết: Dương Thành Phong