1. Cây con cân bằng

Ðối với kỹ thuật chia để trị, nói chung sẽ tốt hơn nếu ta chia bài toán cần giải thành các bài toán con có kích thước gần bằng nhau. Ví dụ, sắp xếp trộn (MergeSort) phân chia bài toán thành hai bài toán con có cùng kích thước n/2 và do đó thời gian của nó chỉ là O(nlogn). Ngược lại trong trường hợp xấu nhất của QuickSort, khi mảng bị phân hoạch lệch thì thời gian thực hiện là O(n2).

Nguyên tắc chung là chúng ta tìm cách chia bài toán thành các bài toán con có kích thước xấp xỉ bằng nhau thì hiệu suất sẽ cao hơn.

2. Tối ưu tổ hợp

Là một dạng của bài toán tối ưu, nó có dạng tổng quát như sau:

  • Cho hàm f(X) xác định trên một tập hữu hạn các phần tử D. Hàm f(X) được gọi là hàm mục tiêu.
  • Mỗi phần tử X Î D có dạng X = (x1, x2, .. xn) được gọi là một phương án.
  • Cần tìm một phương án X*ΠD sao cho f(X*) đạt min (max). Phương án X* như thế được gọi là phương án tối ưu.

– Ta có thể tìm thấy phương án tối ưu bằng phương pháp “vét cạn” nghĩa là xét tất cả các phương án trong tập D (hữu hạn) để xác đinh phương án tốt nhất. Mặc dù tập hợp D là hữu hạn nhưng để tìm phương án tối ưu cho một bài toán kích thước n bằng phương pháp “vét cạn” ta có thể cần một thời gian mũ.

– Các phần tiếp theo của chương này sẽ trình bày một số kỹ thuật giải bài toán tối ưu tổ hợp mà thời gian có thể chấp nhận được

3. Giải thuật tiết kiệm bộ nhớ

int Comb(int n, int k) {

            int V[n+1];

            int i, j, p1, p2;

/*1*/    V[0] = 1;

/*2*/    V[1] = 1;

/*3*/    for (i = 2; i <= n; i++) {

/*4*/                p1 = V[0];

/*5*/                for (j = 1; j < i) {

/*6*/                            p2 = V[j];

/*7*/                            V[j]= p1+p2;

/*8*/                            P1= p2;

                        }

/*9*/                V[i] := 1;

            }

/*10*/  return V[k];

}

Dễ dàng tính được độ phức tạp của giải thuật vẫn là O(n2).

4. Bài toán TSP

Chúng ta có thể áp dụng kỹ thuật quy hoạch động để giải bài toán TSP

Đặt S = {x1, x2, …, xk} là tập hợp con các đỉnh của đồ thị G = (V,E). Ta nói rằng một đường đi P từ v đến w phủ lên S nếu P = {v, x1, x2, …, xk, w}, trong đó xi có thể xuất hiện ở một thứ tự bất kì, nhưng chỉ xuất hiện duy nhất một lần. Ví dụ đường cho trong hình sau, đi từ a đến a, phủ lên {c, d, e, g}.

Ta định nghĩa d(v, w, S) là tổng độ dài của đường đi ngắn nhất từ v đến w, phủ lên S. Nếu không có một đường đi như vậy thì đặt d(v, w, S) = ¥. Một chu trình Hamilton nhỏ nhất Cmin của G phải có tổng độ dài là c(Cmin) = d(v,v, V – {v}). Trong đó v là một đỉnh nào đó của V. Ta xác định Cmin như sau:

Nếu |V| = 1 (G chỉ có một đỉnh) thì c(Cmin) = 0, ngược lại ta có công thức đệ qui để tính d(v, w, S) là:

§         d(v, w, {}) = c(v,w)

§         d(v, w, S) = min [c(v, x) + d(x, w, S – {x}], lấy với mọi x Î S.

Trong đó c(v, w) là độ dài của cạnh nối hai đỉnh v và w nếu nó tồn tại hoặc là ¥ nếu ngược lại. Dòng thứ hai trong công thức đệ qui trên ứng với tập S không rỗng, nó chỉ ra rằng đường đi ngắn nhất từ v đến w phủ lên S, trước hết phải đi đến một đỉnh x nào đó trong S và sau đó là đường đi ngắn nhất từ x đến w, phủ lên tập S – {x}.

Bằng cách lưu trữ các đỉnh x trong công thức đệ qui nói trên, chúng ta sẽ thu được một chu trinh Hamilton tối tiểu.

5. Cây biểu thức toán học

Ðịnh trị cây biểu thức số học

Trong các ngôn ngữ lập trình đều có các biểu thức số học, việc dịch các biểu thức này đòi hỏi phải đánh giá (định trị) chúng. Ðể làm được điều đó cần phải có một biểu diễn trung gian cho biểu thức. Một trong các biểu diễn trung gian cho biểu thức là cây biểu thức.

Cây biểu thức số học là một cây nhị phân, trong đó các nút lá biểu diễn cho các toán hạng, các nút trong biểu diễn cho các toán tử.

Ví dụ: Biểu thức 5 + 2 * 3 – 4 sẽ được biểu diễn bởi cây trong hình dưới đây:

Trị của một nút lá chính là trị của toán hạng mà nút đó biểu diễn.

Trị của một nút trong có được bằng cách lấy toán tử mà nút đó biểu diễn áp dụng vào các con của nó.

Trị của nút gốc chính là trị của biểu thức.

2. Giải thuật quay lui (vét cạn) cho việc định trị cho cây biểu thức số học

Để định trị cho nút gốc, chúng ta phải định trị cho hai con của nó, đối với mỗi con ta xem nó có phải là nút lá hay không, nếu không phải ta lại phải xét hai con của nút đó. Quá trình cứ tiếp tục như vậy cho tới khi gặp các nút lá mà giá trị của chúng đã được biết, quay lui để định trị cho các nút cha của các nút lá và cứ như thế mà định trị cho tổ tiên của chúng. Ðó chính là kỹ thuật quay lui vét cạn, vì chúng ta phải lần đến tất cả các nút lá mới định trị được cho các nút trong và do thế mới định trị được cho nút gốc.

Với cây biểu thức trong ví dụ trên, để định trị cho nút “-” chúng ta phải định trị cho nút “+” và nút “4”. Nút “4” là nút lá nên giá trị của nó là 4. Ðể định trị cho nút “+” ta phải định trị cho nút “5” và nút “*”.  Nút “5” là nút lá nên giá trị của nó là 5. Ðể định trị cho nút “*”, ta phải định trị cho nút “2” và nút “3”. Cả hai nút này đều là lá nên giá trị của chúng tương ứng là 2 và 3. Quay lui lại nút “*”, lấy toán tử * áp dụng cho hai con của nó là 2 và 3 ta được trị của nút “*” là 6. Quay lui về nút “+”, lại áp dụng toán tử “+” vào hai con của nó là 5 và 6 được trị của nút “+” là 11. Cuối cùng quay về nút “-”, áp dụng toán tử – vào hai con của nó là 11 và 4 ta được trị của nút “-”(nút gốc) là 7. Ðó chính là trị của biểu thức. Trong hình 3-9î, mũi tên nét đứt minh họa quá trình đi tìm nút lá và mũi tên nét liền minh họa quá trình quay lui để định trị cho các nút, các  số bên phải mỗi nút là trị của nút đó.

Giải thuật sơ bộ để định trị một nút bất kỳ như sau:

float Eval(node n) {

            if (n là lá)

                        return (trị của toán hạng trong n);

            return (Toán tử trong n (Eval (Con trái của n), Eval (Con phải của n)));

}

Muốn định trị cho cây biểu thức T, ta gọi Eval(ROOT(T)).

5. Sinh chuỗi nhị phân

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <stdio.h>
#include <conio.h>
#define n 3
int a[n];   
int dem;
void InKq()
{
    printf("%3d: ", ++dem);
    for (int i=0; i<n; i++)
        printf("%d", a[i]);
    printf("\n");
}
void Tim(int k)
{
    for (int i=0; i<=1; i++)
    {
        a[k] = i;
        if (k < n-1) Tim(k+1);
        else InKq();
    }
}
void main()
{
    dem = 0;
    Tim(0);
    getch();
}

6. Sinh hoán vị

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include <stdio.h>
#include <conio.h>
#define m 4
int dem;
int xet[m];
int a[m];
void InKq()
{
    printf("%3d: ", ++dem);
    for (int i=0; i<m; i++)
    {
        printf("%d", a[i]+1);
    }
    printf("\n");
}
void Tim(int k)
{
    for (int i=0; i<m; i++)
        if (!xet[i])
        {
            a[k] = i;
            if (k == m-1)
            {
                InKq(); return;
            }
            xet[i] = 1;
            Tim(k+1);
            xet[i] = 0;
        }
}
void main()
{
    int a[m];
    for (int i=0; i<m; i++) xet[i] = 0;
    dem = 0;
    Tim(0);
    getch(); //dừng màn hình để xem kết quả
}
13. Phân tích một số thành tổng các số nhỏ hơn
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <stdio.h>
#include <conio.h>
#define n 6
int a[n];   
int dem;
void KiemTra()
{
    int i,s=0;
    for (i=0; i<n; i++)
        if (a[i]==1) s += i+1;
    if (s==n)
    {
        dem++;
        printf("Chuoi %d: ", dem);
        for (i=0; i<n; i++)
            if (a[i]==1)
                printf("%d ", i+1);
        printf("\n");
    }
}
void Tim(int k)
{
    for (int i=0; i<=1; i++)
    {
        a[k] = i;
        if (k == n-2) KiemTra();
        else Tim(k+1);
    }
}
void main()
{
    dem = 0;
    Tim(0);
    printf("\nPress any key to quit...");
    getch(); //dừng màn hình để xem kết quả
}