DIVIDE AND CONQUER ON ARRAY

Thuật toán chia để trị: ta chia bài toán cần giải quyết thành nhiều bài toán con, giải quyết từng bài toán con, sau đó ta tổng hợp lại để giải bài toán lớn. Thuật toán chia để trị được biết đến tiêu biểu qua giải thuật merge-sort… Mặc dù nó được ứng dụng khá nhiều, nhưng nó không có một cách giải quyết tổng quát cho các bài toán. Ta phải hiểu tư tưởng của nó và áp dụng vào từng trường hợp cụ thể.

Trong bài viết này, tôi sẽ trình bày một trường hợp áp dụng thuật toán chia để trị, tuy chỉ là một trường hợp áp dụng, nhưng dạng này ta gặp rất thường xuyên. Ta sẽ đi đi từ bài toán tổng quát, rồi áp dụng vào ví dụ cụ thể.

Bài toán tổng quát: ta tìm một dãy con liên tiếp trong dãy đã cho để thỏa mãn một tính chất nào đó.

Cách giải quyết: Thông thường với kích thước của dãy khoảng N=10^3, ta dùng hai vòng lặp chạy lồng nhau với độ phức tạp O(N^2) để xét tất cả dãy con và tìm ra dãy con phù hợp nhất.

Khi N lớn hơn một chút, tầm khoảng N=10^5, ta phải có một giải thuật chạy tốt hơn mới giải quyết được. Tôi đã trình bày ở bài viết “two pointers” có thể giải quyết bài toán tìm dãy con liên tiếp trong O(N), tuy nhiên cách làm này không giải quyết mọi bài toán. Bài viết này sẽ trình bày một cách giải quyết khác cho bài toán tìm dãy con liên tiếp nhưng với độ phức tạp O(NlogN).

Ý tưởng giải quyết như sau, với một dãy {a} có N phần tử.

• Nếu dãy đó có 1 phần tử: ta xét trực tiếp phần tử đó thỏa mãn yêu cầu hay không.
• Nếu dãy đó nhiều phần tử, ta sẽ chia ra hai dãy con, mỗi dãy có N/2 phần tử {a1} và {a2}, trường hợp N lẻ thì kích thước hai dãy con chênh lệch nhau một. Kết quả cần tìm sẽ là:
•  Kết quả sẽ nằm hoàn toàn trong {a1},
• Hoặc kết quả sẽ nằm hoàn toàn trong {a2},
• Hoặc kết quả là một dãy liên tiếp nằm trên hai dãy con, một phần là dãy liên tiếp ở cuối {a1} và một phần là dãy liên tiếp nằm ở đầu {a2}.

Để tìm lời giải cho dãy {a1} và {a2}, ta lại tiếp tục chia ra làm hai dãy con. Tương tự vậy cho đến khi tìm được lời giải.

Mã giả:

Độ phức tạp:

Gọi f(N) là độ phức tạp khi tìm lời giải cho dãy {a}.

ð  Độ phức tạp cho việc tìm lời giải cho {a1} là f(N/2) và {a2} là f(N/2).

Gọi g(N) là độ phức tạp cho việc xét trường hợp kết quả nằm ở cả hai dãy con.

Vậy f(N) = 2*f(N/2) + g(N).

Nếu g(N) = O(N), ta có công thức truy hồi quen thuộc f(N) = 2*f(N/2) + O(N), trong trường hợp này độ phức tạp f(N) = O(NlogN).

Vì vậy nếu ta cố gắng giải quyết trường hợp kết quả nằm ở cả hai dãy con {a1} và {a2} trong O(N) thì ta có thể giải quyết cả bài toán với độ phức tạp trong O(NlogN). Ta sẽ xét những ví dụ để hiểu rõ hơn.

Nhìn vào mã giả, để bài toán này, ta chỉ cần tìm cách giải cho trường hợp kết quả nằm ở hai dãy con {a1} và {a2}, thể hiện ở câu Condiser tail of {a1} and head of {a2} trong mã giả, vì hai trường hợp kia chỉ là câu lệnh gọi đệ quy. Nhưng phải giải trường hợp này trong O(N), trong một vài trường hợp ta cũng có thể giải chúng trong O(NlogN) vẫn ok. Như vậy ta đã thấy mấu chốt của vấn đề là ở đâu, tập trung giải quyết nó thì coi như cả bài toán giải được giải quyết.

Ví dụ 1: Theo số liệu thống kê của một công ty về tình hình kinh doanh trong N (1<=N<=10^5) ngày, hằng ngày công ty này có doanh thu là ai (-10^6 <= ai <=10^6), ai có giá trị âm nghĩa là có chi nhiều hơn thu. Người ta cần phân tích xem khoảng thời gian nào công ty có doanh thu là nhiều nhất. Cụ thể là ta cần tìm một dãy con liên tiếp trong dãy {aN} sao cho tổng của chúng là lớn nhất.

Áp dụng bài toán tổng quát nêu ở trên vào trường hợp này. Ta cần giải quyết trường hợp kết quả nằm ở hai dãy con {a1} và {a2}. Rõ ràng để kết quả lớn nhất, thì mỗi phần bên mỗi dãy con cũng lớn nhất.

• Đối với dãy con {a1}, ta chạy từ cuối dãy {a1} cho đến đầu dãy {a1}, mỗi lần chạy ta cộng thêm một phần tử và cập nhật lại tổng có giá trị lớn nhất. Cách làm này chạy trong N/2.
• Đối với dãy con {a2}, ta chạy từ đầu dãy {a2} qua, chạy cho hết dãy và chọn ra dãy con có tổng lớn nhất. Cách làm này cũng chạy trong N/2.
• Tổng hai dãy con tìm được ở trên chính là kết quả cho trường hợp kết quả nằm ở hai dãy. Ta chú ý trường hai dãy con đó có tổng là âm, thì ta ko cần cộng lại hai thằng, mà chỉ lấy thằng lớn nhất.

ð  Ta thấy với cách làm này ta chỉ chạy trong O(N) để giải quyết trường hợp kết quả nằm ở hai dãy con. Như vậy ta hoàn toàn có thể giải quyết bài toán cho toàn bộ dãy trong O(NlogN).

Ý tưởng thì đã xong, ta bắt tay vào hiện thực. Bạn có thể xem code tại đây.

Thật ra bài này có cách làm đơn giản hơn, chỉ chạy trong O(N). Ta để ý nếu ta có dãy con a[i,i+1,…,j] là dãy con có tổng lớn nhất, tức là ai+a(i+1)+…+aj là lớn nhất. Thì rõ ràng các dãy con a[i,i+1,..,k] luôn có tổng lớn hơn hoặc bằng 0, với mọi k<j (nếu tổng này có giá trị nhỏ hơn 0 thì dãy con a[k+1,…,j] có tổng lớn hơn dãy a[i,i+1,…,j], mâu thuẩn với giả thuyết). Từ nhận xét này ta chạy từ trái qua phải, cộng dồn các giá trị ai vào, mỗi lần chạy ta coi tổng này có phải là giá trị lớn nhất hay không. Trong trường hợp tổng này nhỏ hơn hoặc bằng 0 thì ta bỏ nguyên cả đoạn đầu, ta tiếp tục chạy qua phải từ vị trí làm cho tổng nhỏ hơn 0. Do đây không phải là mục đích chính của bài viết, nên tôi không giải thích thêm về cách làm này, bạn có thể xem code đã cải tiến.

Ví dụ 2: Cho một dãy số {aN} có kích thước N (1<=N, ai<=10^5), ta cần tìm các dãy con liên tiếp có kích thước lớn nhất trong dãy sao cho tổng các phần tử đã chọn chia hết cho k (2<=k<=10^5). Nếu có nhiều dãy con thỏa mãn, ta cần in ra tất cả các dãy con như thế, với mỗi dãy con chỉ cần in ra chỉ số đầu và cuối.

Bài toán có 2 ý, ý thứ nhất là ta tìm kích thước dài nhất mà tồn tại dãy con có tổng chia hết cho k, ý thứ hai là in ra các dãy con có kích thước như thế và thỏa mãn tổng chia hết cho k. Nếu ta không tách ra, việc giải quyết vấn đề của ta sẽ hơi khó khăn một chút. Việc đầu tiên là ta giải quyết ý thứ nhất, tìm kích thước dài nhất có thể. Sau khi có được chiều dài này thì việc in ra tất cả các dãy con như thế dễ dàng hơn.

Cũng như ví dụ 1, ta áp dụng bài toán tổng quát vào, vấn đề là cần giải quyết trường hợp dãy dài nhất nằm ở cả hai dãy con. Nếu ta có tổng dãy con bên phải chia k dư x, thì ta cần dãy con dài nhất bên trái chia k dư k-x. Như vậy tổng hai dãy này sẽ chi hết cho k. Bài này ta kết hợp chút xíu quy hoạch động.

Giả sử N1 là chiều dài dãy con {a1}. Gọi f[x] là chỉ số nhỏ nhất cũa dãy con {a1} mà tổng a[f[x], f[x]+1,….,N1] chia k dư x, tức là ta đang lưu lại dãy con dài nhất tính từ bên phải của dãy {a1} mà chia k dư x.

• Đối với dãy con {a1}, ta chạy từ cuối dãy {a1} đến đầu dãy. Mỗi lần chạy đến phần tử thứ i, ta cộng dồn phần tử ai vào tổng S1, giả sử tổng này chia k dư x. Ta cập nhật lại f[x] = i.
• Đối với dãy con {a2}, ta chạy từ đầu dãy cho đến hết dãy. Đến mỗi phần tử ai ta cũng cộng vào tổng S2. Giả sử S2 chia k dư x. Ta xét f[k-x] có giá trị không, nếu có thì ta có một dãy con có tổng chia hết cho k là a[f[k-x],f[k-x]+1,…,i] có kích thước là (i-f[k-x]+1). Qua mỗi lần chạy ta cập nhật lại kích thước dài nhất có thể.
• Việc còn lại là in kết quả ra, tới đây thì chắc dễ dàng hơn ta chỉ thực hiện trâu bò là được, vì việc in ra tất cả dãy con có chiều dài cụ thể chỉ trong độ phức tạp O(N).

Nói thì nhiều như vậy chứ thật sự nó chỉ tập trung vào tìm cách giải quyết trường kết quả nằm ở cả hai dãy con trong O(N). Bạn hãy tự code bài này, có thể so sánh với code mình tại đây.

Trong đoạn code của mình có vài điểm lưu ý:
- Nếu dãy con bên phải chia hết cho k, thì ta tìm dãy con dài nhất bên trái chia hết cho k, chứ không phải tìm dãy con bên trái chia k dư k.
- Việc lưu dãy từ 1->N, chứ không phải từ 0->(N-1). Mục đích của mình là đánh dấu nếu f[x] =0, tức là không có dãy con bên trái chia k dư x. Và dùng hàm memset() của C++ để reset lại giá trị của dãy f[]. Nếu bạn bạn dùng vòng for để reset giá trị của dãy thì chạy rất lâu. 

Tổng kết:

Đối với bài toán tìm dãy con liên tiếp, ta đã có phương pháp “two pointers” để giải quyết, nhưng nó không thể giải hết các bài toán dạng tìm dãy con liên tiếp, ta đã tìm hiểu cách áp dụng chia để trị vào giải quyết dạng này. Tuy mình trình bày hơi dài dòng nhưng mấu chốt cũng chỉ giải quyết một trường hợp kết quả nằm ở cả hai dãy con.

Bài viết đã trình bày một bài toán áp dụng chia để trị để giải quyết, mình cũng hy vọng có ai đó sẽ chia sẻ thêm về việc dùng giải thuật chia để giải quyết bài toán khác.

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

SEQUENCE

Trong rất nhiều bài toán, ta đã đưa về được công thức truy hồi để giải quyết vấn đề, việc cuối cùng là giải công thức truy hồi đó để đưa ra lời giải. Thông thường thì tìm ra công thức truy hồi mới khó vì để tìm ra công thức truy hồi thì ta cần biết lý thuyết liên quan vấn đề cần giải quyết và phải suy luận nhiều, việc giải công thức truy hồi đơn giản hơn một chút, ta có một số kỹ thuật sau:

I. Dãy truy hồi và quy hoạch động

Đây là cách làm thông dụng nhất mà ta dùng khi đã có công thức truy hồi, vì nó dễ lập trình. Nhưng những bài toán rơi vào dạng này thì thường quá trình tìm ra công thức truy hồi hơi cực.

Do cách làm này khá quen thuộc, nên tôi chỉ lướt sơ qua. Giả sử ta có công thức F[N] = min{2*F[N-1], 3*F[N-2] + 3}+N. Với F[1] = 1, F[2] = 2, 1<=N<=10^6.

Ta khai báo một array để lưu lại các giá trị F[i] và tính kết quả từ dưới lên.

II. Dãy truy hồi tuyến tính và ma trận

Để bắt đầu tôi muốn hỏi một câu: để tính a^N mod M (trong đó a, N, M là số nguyên dương nhỏ hơn 10^9, mod là phép lấy phần dư) bạn thực hiện thế nào? Thông thường ta vẫn hay thực hiện:

Cách làm này chạy trong O(N), khá chậm khi N lớn. Nếu để ý a^N = (a^(N/2))^2, ta chỉ cần tính a^(N/2), sau đó bình phương lên. Tương tự để tính a^(N/2), ta cũng tính a^(N/4) rồi bình phương lên. Với cách làm này ta tính a^N chỉ trong O(logN).

Bỏ qua vấn đề đó đi, ta quay lại vấn đề chính. Ta xét ví dụ sau:

Bài toán: Ta có N (1<=N<=10^9) viên gạch kích thước 1x2, ta cần xếp N viên gạch kín cả vùng hình chữ nhật có kích thước 2xN. Có bao nhiêu cách xếp như vậy, bạn chỉ cần tính kết quả lấy phần dư khi chia cho 10003.

Giải quyết:

Với N=1, ta có 1 cách xếp.

Với N=2, ta có 2 cách xếp.

Với N>2, ta xét

Gọi F[N] là số cách xếp các viên gạch vào hình chữ nhật 2xN.

Nhìn hình vẽ, ta suy ra công thức truy hồi, F[N] = F[N-1]+F[N-2], với F[1]=1, F[2]=2. Đây chính là dãy Fibonacy.
Dựa vào công thức truy hồi này, ta có thể dùng một vòng for để chạy tìm ra kết quả, độ phức tạp là O(N), nhưng bài toán yêu cầu N có thể lên tới 10^9, cách làm này không giải quyết được trường hợp N lớn.

Thật ra ta có thể tìm ra công thức tổng quát của dãy Fibonacy. F[N] = q^N+(1/q)^N với q=(1+sqrt(5))/2. Khi N khá lớn, (1/q)^N tiến về 0. Ta chỉ cần tính Round(q^N), với Round() là hàm làm tròn. Nhưng khó khăn ở chổ q không là số nguyên, ta không dễ tính Round(q^N) (mod M). Hướng đi này có lẽ cũng khó hiện thực, ta thử tìm hướng đi khác:

Xét ma trận A = 

và vector f(N) = 

Ta thấy f(N) = A*f(N-1)

     = A*Af(N-2) = A^2*f(N-2)

     = A^3*f(N-3) = … = A^(N-2)f(2) (với N>1)

Quay lại yêu cầu bài toán, ta tìm F[N]. Thật ra tìm ra f(N) cũng là tìm được kết quả F[N], vì khi tìm được f(N) thì ta biết được F[N] và F[N-1]. Chú ý f(N) là một vector.

Theo công thức ta tính toán f(N) = A^(N-2)*f(2). Vậy chỉ cần tính A^(N-2) là ta có f(N), quay về bài toán nhân ma trận, ở đây N có thể lên tới 10^9.

Không phải tự dưng tôi hỏi bạn câu hỏi làm sao tính a^N. Để tính A^N cũng tương tự vậy, chỉ khác ở chổ thay vì nhân hai số, thì ta nhân 2 ma trận. Như vậy ta có thể tính A^N trong log(N), vấn đề coi như được giải quyết. Ta nhắc lại nhé, ta tìm F[N] => phải tìm f(N) => phải tìm A^N. Ý tưởng đã xong, bây giờ hiện thực thôi.

Đánh giá độ phức tạp: Do ma trận này kích thước 2x2, nhân hai ma trận ta mất thời gian khá ít, nên việc tính A^N chỉ mất trong O(logN).

Bạn có thể xem code tại đây

Nhận xét nhỏ: nếu bạn để ý, bài toán tính a^N chính là giải dãy truy hồi g[N]=a*g[N-1] với g[0]=1. Mọi thứ có liên quan với nhau, cái khó ta phải tìm ra tính tổng quát của các vấn đề cụ thể.
                                 

Tổng quát:

Tại sao ta lại có ma trận A, ta xét công thức truy hồi tuyến tính tổng quát:

F[N] = a0*F[N-1] + a1*F[N-2] + … + ak-1*F[N-k], với các số ai là hằng số và ta biết các giá trị F[0], F[1],...,F[k-1]. Ta tìm giá trị F[N] với N>=k.

Đặt ma trận A = 

Dòng đầu tiên là các hệ số trong công thức truy hồi, dòng thứ hai có tất cả các số là 0 trừ số thứ nhất là 1,…, dòng cuối cùng thì số kế cuối cùng là 1.
 và f(N) = 

Bạn hãy nhân A*f(N-1), kết quả chính là f(N). Nói cụ thể f(N) = A*f(N-1).=...=A^(N-k)*f(k).
Tới đây bạn có thể thực hiện tương tự như dãy Fibonacy.

Bạn có thể xem code tại đây.

Về độ phức tạp, như đã nói ở trên ta mất thời gian nhân hai trận và tính A^N, vậy độ phức tạp tổng cộng là O(k^3*logN), với k là kích thước của ma trận A.

III. Dãy số có công thức tổng quát dạng đa thức
Đối với dạng này, ta sẽ không cần biết công thức truy hồi của dãy số, nhưng ta vẫn có thể tìm ra công thức tổng quát của nó. Tức là ta tìm ra chính xác F[N] = p(N), với p(x) là một đa thức. Để tính F[N] thì ta chỉ việc thay số vào tính p(N). Để làm được điều này ta cần nhắc lại một ít lý thuyết.
1. Nếu ta có F[N] = F[N-1] + g(N), với g(N) là một đa thức bậc k, thì công thức tổng quát của F[N] là một đa thức bậc k+1.
2. Ta hoàn toàn có thể xác định được đa thức bậc k nếu ta biết được giá trị tại k+1 điểm khác nhau.

Dựa vào hai tính chất này, ta có thể tìm được công thức tổng quát của dãy số nếu ta dự đoán được nó có dạng đa thức.

Ví dụ: Xét hình vuông NxN (1<=N<=10^9) được kẻ như hình vẽ. Bạn hãy tính xem có bao nhiêu hình tam giác trong hình vuông đó, tính số dư kết quả khi chia cho 10003. 

Giải quyết: gọi F[N] là kết quả cho hình vuông NxN, hình vuông đỏ là F[N-1]. Với mỗi hình tam giác con bên ngoài hình vuông đỏ, nó góp phần tạo nhiều nhất không quá N tam giác. Mà ta có 2N-2 tam giác con bên ngoài, nên số tam giác F[N] hơn F[N-1] là đa thức theo N bậc không quá 2 ,vì nó sẽ không vượt quá N*(2N-2). Vì vậy F[N] = F[N-1]+g(N) với g(N) là một đa thức bậc không quá 2. Suy ra F[N] là đa thức bậc không quá 3. Để xác định đa thức bậc 3, ta cần giá trị tại 4 điểm, để đơn giản ta chọn N=1,2,3,4, tức là ta phải tính F[1], F[2], F[3], F[4].
Bằng cách đếm bằng tay, ta tính được F[1] = 2, F[2] = 10, F[3] = 28, F[4]= 60. Thật ra tôi viết một chương trình nhỏ để tính F[1], F[2], F[3], F[4]. Code đây, với code này chỉ chạy được khoảng tới N=10.

Do F[N] là đa thức bậc không quá 3, ta đặt F[N]=a*N^3+b*N^2+c*N+d. Thay N=1,2,3,4 vào ta giải hệ phương trình
a+b+c+d=1
8a+4b+2c+d=10
27a+9b+3c+d=28
64a+16b+4c+d=60.
Giải hệ này, ta được a=2/3, b=1, c=1/3, d=0.
Vậy F[N] = (2*N^3+3*N^2+N)/3 = N(N+1)(2N+1)/3.

Đã có công thức tổng quát, việc code thì dễ dàng. Chú ý với N=10^9 thì ta cần một xử lí nhỏ để tránh tràn số.

IV. Tổng kết:

Bài viết đã trình bày một vài phương pháp để giải các bài toán khi ta tìm được công thức truy hồi của chúng. Đối với N<=10^6, ta thường dùng quy hoạch động để giải chúng. Những trường hợp cần giải quyết với N lớn như N=10^9, ta cần xài 1 số kỹ thuật:
1. Giải ra công thức tổng quát theo N, thông thường thì ta ít tiếp cận cách làm này, vì nó mất ta nhiều thời gian và sử dụng nhiều phép biến đổi để giải.
2. Nếu công thức truy hồi dạng tuyến tính, ta có thể dùng ma trận để giải như đã đề cập mục II
3. Nếu ta xác định được F[N] là một đa thức, ta có thể áp dụng mục III để giải nó.

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

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