<span class='text_page_counter'>(1)</span><div class='page_container' data-page=1>

<b>CÁC THUẬT TOÁN CƠ BẢN VỀ XỮ LÝ MÃNG TRONG </b>

<b>PASCAL.</b>

<b>Sơ lợc về các chủ đề</b>

Sau đây là sơ lợc về các chủ đề sẽ đợc đề cập trong phần này của chơng trình:

+ Phần cơ sở: là các công cụ và phơng pháp đợc dùng xuyên suốt cho tất cả các chơng sau của
phần này. Nó gồm một phần bàn luận ngắn về Pascal, theo sau là giới thiệu về các cấu trúc dữ liệu
cơ bản gồm mảng, xâu liên kết, ngăn xếp, hàng đợi và cây. Chúng ta sẽ bàn luận về công dụng
thực tiễn đệ quy và bắt đầu hớng tới việc phân tích và tiếp cận thực tốn.

+ Sắp xếp: Các phơng pháp sắp xếp sẽ đợc phát triển, đợc mô tả, đợc so sánh với nhau. Các thuật
tốn cho nhiều vấn đề có liên quan sẽ đợc xem xét gồm có hàng đợi u tiên, phép chọn và phép
trộn. Một vài nền tảng trong số này đợc dùng nh là nền tảng cho các thuật toán khác tiếp sau
trong phần này.

+ Xử lý chuỗi: gồm một loạt các phơng pháp để phân tích câu. Các ky thuật nén tập và mật mã
cũng sẽ đợc khảo sát. Cũng vậy, một giới thiệu về các chủ đề nâng cao cùng đợc cung cấp qua
việc xem xét một vài bài toán cơ bản quan trọng trong phạm vi của chúng.

+ Hình học: là một sự tập hợp có chọn lọc các phơng pháp để giải quyết các bài toán liên quan
đến điểm và đờng ( và các đối tợng hình học đơn giản khác ). Chúng ta sẽ xem xét các thuật tốn
để tìm bao lồi của một tập điểm, phần giao của các đối tợng, để giải bài tốn điểm gần nhất, tìm
kiếm nhiều chiều ...

+ Đồ thị: Một chiến lợc tổng quát để tìm kiếm trên các đồ thị sẽ đợc phát triển và đợc áp dụng
cho các bài tốn liên thơng cơ bản, gồm có đờng đi ngắn nhất, cây liên thơng tối thiểu, mạng và
so khớp. Một sự xem xét thống nhất đối với các thuật toán này chứng tỏ rằng tất cả đều dựa vào
một thủ tục và thủ tục này phụ thuộc vào một cấu trúc dữ liệu cơ bản đã phát triển trớc đó.

+ Các thuật tốn tốn học: gồm các phơng pháp cơ bản từ số học và các số nguyên, đa thức, và
ma trận cũng nh các thuật toán để giải quyết cac vấn đề toán học mà nó phát sinh trong nhiều ngữ
cảnh : việc tạo số ngẫu nhiên, lỡi giải của các chơng trình đồng thời, xấp xỉ dữ liệu, và lấy tích
phân. Sự nhấn mạnh thiên về các khía cạnh thuật tốn của phơng pháp, chứ khơng phải trên nền
tảng của tốn học

+ Các chủ đề cao cấp: đợc thảo luận nhằm mục đích liên hệ các chủ đề trong tập sách này với
nhiều lĩnh vực nghiên cứu cao cấp khác. Phần cứng chun dụng, quy hoạch động, quy hoạch
tuyến tính, tìm kiếm- vét cạn ...

<b>I. Sắp xếp:</b>

<b>1. Kh¸i niƯm:</b>

a) Sắp xếp là một quá trình tổ chức lại một dãy các dữ liệu theo một trật tự nhất định.

b) Mục đích của việc sắp xếp là nhằm giúp cho việc tìm kiếm dữ liệu một cách dễ dàng và
nhanh chóng. Sắp xếp là một việc làm hết sức cơ bản và đợc dùng rộng rãi trong các kĩ thuật lập
trình nhằm sử lý dữ liệu.

c) Các giải thuật sắp xếp đợc phân chia thành hai nhóm chính là:
- Sắp xếp trong (hay sắp xếp mảng).

Toàn bộ cơ sở dữ liệu cần sắp xếp phải đợc đa vào bộ nhớ chính của máy tính. Do đó nó thờng
đ-ợc sử dụng khi khối lợng dữ liệu khơng vợt q dung lợng bộ nhớ chính.

Nhóm sắp xếp trong bao gồm các phơng pháp :
* Phơng pháp đếm.

* Phơng pháp chèn.

* Phơng pháp chọn.
* Phơng pháp đổi chổ.
* Phơng pháp trộn.

</div>
<span class='text_page_counter'>(2)</span><div class='page_container' data-page=2>

Vận dụng trong trờng hợp ta phải sắp xếp các tập tin chứa nhiều mẫu tin và mỗi mẫu tin có chiều
dài tơng đối lớn do đó ta khơng thể nạp tồn bộ vào bộ nhớ chính để sắp xếp thứ tự. Vì vậy ta phải
có những phơng pháp thích hợp cho việc sắp xếp tập tin.

<b>2. S¾p xÕp trong:</b>
a) Kh¸i niƯm:

Cấu trúc dữ liệu thích hợp cho các phần tử cần sắp xếp thứ tự là Record. Mỗi phần tử có
hai vùng đặc trơng là: Vùng Key để chứa khoá của phần tử và đợc sử dụng trong các giải thuật
tìm kiếm, vùng info dùng để chứa đữ liệu các phần tử.

Ta khai b¸o :
Type

Item = Record
key : Integer;
Info : Integer;
End;

Var

A : Array[1..n] of Item;

Khoá của phần tử có thể là chữ hoặc số.

Yờu cu gii thớch là dùng ít vùng nhớ và thời gian thực hiện nhanh.

b) Phơng pháp đếm (Counting sort)

* Gi¶i thÝch:

Nội dung của phơng pháp này là đếm các phần tử có khố nhỏ hơn hay bằng khố của các phần
tử A[i]. Nếu có j phần tử có khố nhỏ hơn khố của phần tử A[i] thì phần tử A[i] sẽ có vị trí theo
thứ tự (j+1) trong dãy đã có thứ tự.

Trong giải thuật, ta dùng mảng Count[i] ( i = 1, 2, .. n ) với Count[i] cho biết số phần tử có khoá
nhỏ hơn khoá của phần tử A[i]. Nh vậy Count[i+1] là vị trí của phần tử A[i] trong dãy đã có thứ
tự.

* VÝ dơ:

S¾p xÕp d·y 2 3 1 5 2 7 6 9 4
i: 1 2 3 4 5 6 7 8
Count: 2 0 4 1 6 5 7 3

Nh vậy phần tử có khoá 9 ở vị trí 8 vì Count[9]=7.
* Thể hiện b»ng Pascal:

Procedure Count_Sort;
Var

Count : Array[1..n] of Integer;
A : Array[1..n] of Item;
i,j : Integer;

Begin

For i := 1 to n do Count[i] := 0;
For i := n downto 2 do

For j := i-1 downto 1 do
If A[i].Key < A[j].Key Then
Count[j] := Count[j] + 1
Else Count[i] := Count[i] + 1;

For i := 1 to n do S[Count[i] + 1] := A[i];
For i := 1 to n do A[i] := S[i];

End;

</div>
<span class='text_page_counter'>(3)</span><div class='page_container' data-page=3>

Nội dung của phơng pháp này là giả sử ta có dãy A[1]..A[i-1] đã có thứ tự, có phải xác định vị
trí thích hợp của phần tử A[i] trong dãy A[1]..A[i 1] bằng phơng pháp tìm kiếm tuần tự từ A[i
-1] trở về A[-1] để tìm ra vị trí thích hợp của A[i]. Ta chèn A[i] vào vị trí này và kết quả là đãy
A[1] .. A[i] có thứ tự. Ta áp dụng cách làm này với i = 2, 3, ..., n.

* VÝ dô:

Ta phải sắp xếp dÃy số:

39 50 7 37 89 13 1 62
i=2 39 50 7 37 89 13 1 62
i=3 39 50 7 37 89 13 1 62
i=4 7 39 50 37 89 13 1 62
i=5 7 37 39 50 89 13 1 62
i=6 7 37 39 50 89 13 1 62
i=7 7 13 37 39 50 89 1 62
i=8 1 7 13 37 39 50 89 62

1 7 13 37 39 50 89 62
* ThÓ hiÖn b»ng Pascal:

Procedure Insertion_Sort;
Var

x : Item;
i,j : Integer;
Begin

For i := 2 to n do
Begin

x := A[i];
A[0] := x;
j := j - 1;

While x.Key < A[j].Key do
Begin

A[j+1] := A[j];
j := j - 1;

End;

A[j+1] := x;
End;

End;

d) Phơng pháp chọn (Selection Sort)
* Gi¶i thÝch:

Nội dung của phơng pháp này là ở bớc thứ i (i = 1, 2, 3, ..., n-1 ) ta lựa chọn phần tử nhỏ nhất
trong dãy A[i]..A[n] rồi đổi chổ phần tử này với phần tử A[i]. Cuối cùng ta sẽ có dãy A[1]..A[n]
có th t.

* Ví dụ:

Ta phải sắp xÕp d·y sè :

</div>
<span class='text_page_counter'>(4)</span><div class='page_container' data-page=4>

Procedure Selection_Sort;
Var

x : Item;
i,j ,k : Integer;
min : Integer;
Begin

For i := 2 to n-1 do
Begin

min := A[i].Key;
k := i;

For i := 1 to n-1 do
For j := i+1 to n do
If A[j].Key < min Then
Begin

min := A[j].Key;
k := j;

End;
x := A[k];
A[k] := A[i];
A[i] := x;
End;
End;

e) Phơng pháp đổi chỗ:

Có rất nhiều phơng pháp sắp xếp dựa trên việc đổi chỗ giữa 2 phần tử của dãy. Sau đây chúng ta
xét các phơng pháp:

- Bubble Sort.
- Shake Sort.
- Sell Sort.
- Quick Sort.
* Bubble Sort:
* Gi¶i thÝch:

Nội dung của phơng pháp này là duyệt các dãy A[1], ..., A[n]. Nếu A[i].Key > A[i+1].Key (i = 1,
2, 3, ..., n-1)#0 thì ta đổi chỗ A[i].Key với phần tử A[i+1].Key. Lập lại q trình duyệt dãy này
cho đến khi khơng cịn việc đổi chổ của hai phần tử.

Chú ý rằng bất cứ lúc nào phần tử nhỏ nhất cũng gặp trớc tiên. Nó nh những bột khí nhẹ sẽ nổi
lên trên khi đun nớc. Sau đó ở thứ hai phần tử nhỏ thứ 2 sẽ đợc đặ vào đúng một vị trí. Vì vậy sắp
xếp nổi bột thao tác nh một kiểu sắp xếp chọn, mặc dù nó khơng làm nhiều việc hơn để đa từng
phần tử vào đúng vị trớ.

* Ví dụ:

Ta phải sắp xếp dÃy sè:

</div>
<span class='text_page_counter'>(5)</span><div class='page_container' data-page=5>

* ThĨ hiƯn b»ng Pascal:
Procedure Bubble_Sort;
Var

x : Item;
i,j : Integer;
Begin

For i := 2 to n do

For j := n downto i do

If A[j-1].Key > A[j].Key Then
Begin

x := A[j-1];
A[j-1] := A[j];
A[j-1] := x;
End;

End;
* C¶i tiÕn:

Ta nhận thấy rằng nếu ở một lần duyệt dãy nào đó mà khơng co s xẩy ra sự đổi chổ giữa hai phần
tử thì dãy dang sắp đã có thứ tự và giải thuật kết thúc.

Ta có thể cài đặt cờ để ghi nhận điều này và có chơng trình sau:
Procedure Bubble_Sort2;

Var

x : Item;
i : Integer;
flag : Boolean;
Begin

flag := true;
While flag do
Begin

flag := False;
For i := 1 to n-1 do

If A[i].Key > A[i+1].Key Then
Begin

x := A[i];
A[i] := A[i+1];
A[i+1] := x;
End;

End;
End;

f* Shake Sort:

* Gi¶i thÝch:

Phơng pháp này là một cải tiến của phơng pháp Bubble Sort theo hớng "Không những phần tử
nhẹ nổi lên trên mà cả phần tử nặng cũng xuống dới" giống nh khi ta rung"rung" một cái nồi và
thuật toán sắp xếp phải đợc điều khiển cả hai quá trình "nổi lên" và "chìm xuống" này một cách tự
giác. Muốn vậy ta phải ghi nhớ lần đổi chổ cuối cùng khi duyệt dãy từ trên lên và khi duyệt từ
trên xuoóng để quyết định chu trình kế tiếp sẽ duyệt từ đâu đến đâu.

* VÝ dơ:

S¾p xÕp d·y sè:

</div>
<span class='text_page_counter'>(6)</span><div class='page_container' data-page=6>

c = 8 8 7 7 4
39 1 1 1 1
50 39 39 7 7
7 50 7 39 13
37 7 37 13 37
89 37 50 37 39
13 89 13 50 50
1 13 62 62 62
62 62 89 89 89
* ThĨ hiƯn b»ng Pascal:
Procedure Shake_Sort;
Var

x : Item;
i,k,d,c : Integer;
Begin

d := 2;

c := n;
k := n;
Repeat

For i := c downto d do

If A[i-1].Key > A[i].Key Then
Begin

x := A[i-1];
A[i-1] := A[i];
A[i-1] := x;
k := i;
End;
d := d + 1;

For i := d to c do

If A[i-1].Key > A[i].Key Then
Begin

x := A[i-1];
A[i-1] := A[i];
A[i-1] := x;
k := i;
End;
c := k-1;
Until d>c;
End;

g. * Shell Sort:
* Gi¶i thÝch:

</div>
<span class='text_page_counter'>(7)</span><div class='page_container' data-page=7>

* VÝ dụ:

Ta phải sắp xếp dÃy số:

39 50 7 39 89 13 1 62
Bíc 1: 4-Sort

39 50 7 39 89 13 1 62
39 13 1 37 89 50 7 62
Bíc 2: 2-Sort

39 13 1 37 89 50 7 62
1 13 7 37 39 50 89 62
Bíc 3: 1-Sort

1 13 7 37 39 50 89 62
1 7 13 37 39 50 89 62
* ThĨ hiƯn b»ng Pascal:

Chó ý:

- Ta dùng dãy phụ chứa dộ tăng h[i], ..., h[t] để điều khiển quá trình sắp xếp thứ tự với h[t]=1.
Việc chộn các độ tăng thích hợp sẽ làm giảm thời gian sắp th t.

- Dặt h1 = h[1] ta phải khai b¸o d·y a nh sau:
A : Array[1..n] of Item;

các phần tử A[i] (i<=0) là các lính canh. Sau đây ta chọn:
h[1] = 9, h[2] = 5, h[3] = 3, h[4] = 1

Procedure Shell_Sort;
Const

t = 4;
Var

x : Item;
i,j,k,s,m: Integer;

h : Array[1..t] of Integer;
Begin

h[1] = 9;
h[2] = 5;
h[3] = 3;
h[4] = 1;

For m := 1 to t do
Begin

k := h[m];
s := -k;

For i := k+1 to n do
Begin

x := A[i];

j := i - k;

If s = 0 Then s:=-k;
s := s + 1;

A[s] := x;

While x.Key<A[j].Key do
Begin

A[j+k] :=A[j];
j := j - k;
End;

</div>
<span class='text_page_counter'>(8)</span><div class='page_container' data-page=8>

End;
End;
h. Quick Sort:
* Gi¶i thÝch:

Nội dung của phơng pháp này là chọn phần tử x ở giữa của dãy làm chuẩn để so sánh. Ta phân
hoạch dãy này thành 3 dãy con liên tiếp nhau:

- D·y con thứ nhất gồm phần tử có khoá nhỏ hơn x.key.
- DÃy con thứ hai gồm các phần tư cã kho¸ b»ng x.key.
- D·y con thø ba gồm các phần tử có khoá lớn hơn x.key.

Sau đó áp dụng giải thuật phân hoạch này cho dãy con thứ nhất nhất và dãy con thứ ba, nếu các
dãy con có nhiều hơn một phần tử (Đệ qui).

Cụ thể là xét một doạn của dãy từ thành phần L đến thành phần thứ R.

- Lấy giá trị của thành phần thứ (L+R) Div 2 gán vào biến X.

- Cho i ban đầu là L.
- Cho j ban đầu là R.
- Lập lại.

* Chừng nào còn A[i] < X thì tăng i.
* Chừng nào còn A[j] > X thì giảm j.
* i<=j thì

+ Hoán vị A[i] và A[j]
+ Tăng i

+ Giảm j
Cho đến khi i>j

+ Sắp xếp đoạn từ A[L] đến A[j]
+ Sắp xếp đoạn từ A[i] đến A[R]
* Ví dụ:

S¾p xÕp d·y sè:

39 50 7 37 89 13 1 62
X = 37

Sau 2 lần đổi chổ ta đợc dãy:
1 13 7 37 89 50 39 62
Xử lý dãy con:

1 13 7

Ta đợc:
1 7 13
Sử lý dãy con:
89 50 39 62
Ta đợc:

39 50 89 62
39 50 62 89
Vậy dãy đã sắp xếp là:
1 7 13 39 50 62 89
* Thể hiện bằng Pascal:

Để đơn giản ta viết thủ tục sắp một mảng số nguyên đợc truyền tham biến.
Procedure Quick_Sort(Var A : Array[1..n] of Integer);

Procedure Sort(L,R : Integer);
Var

i,j,Tg,X : Integer;
Begin

</div>
<span class='text_page_counter'>(9)</span><div class='page_container' data-page=9>

i := L;
j := R;
Repeat

While (A[i] < X) do Inc(i);
While (A[j] > X) do Dec(j);
If i <= j Then

Begin

Tg := A[i];
A[i] := A[j];
A[j] := Tg;
Inc(i);
Dec(j);
End;
Until i>j;

If L < j Then Sort(L,j);
If i < R Then Sort(i,R);
End;

Begin
Sort(1,n);
End;

i. Phơng pháp trọn (Merging Sort)
* Giải thÝch:

Nội dung của phơng pháp này là chia dãy số cần sắp thành các dãy con đã có thứ tự(goi là các
Run) và có số phần tử là luỹ thừa 2 sau đó tìm cách trộn dần chúng với nhau thành các Run có thứ
tự chiều dài tăng dần cho đến khi chỉ cịn một Run thì q trình sắp xếp kết thúc.

Ta có giải thuật sau đây để trộn 2 Run x và y cùng thứ tự có chiều dài lần lợt là m và n thành một
run z có chiều dài là m + n.

Procedure Merge;
Var

i,j,k : Integer;
Begin

i := 1;
j := 1;
k := 1;

While (i <= m) and (j <= n) do
Begin

If X[i] < Y[j] Then
Begin

Z[k] := X[j];
i := i + 1;
End

Else
Begin

Z[k] := Y[j]
j := j + 1;
End;

k := k + 1;
End;

While i<=m do
Begin

</div>
<span class='text_page_counter'>(10)</span><div class='page_container' data-page=10>

k := k + 1;
i := i + 1;
End;

While j<=n do
Begin

Z[k] := X[j];
k := k + 1;
j := j + 1;
End;

End;

Cụ thể là nếu ta phải s¾p xÕp d·y: A[1], A[2], ...,A[n].

Ta phải sử dụng 2*n phần tử đợc chia thành 2 vùng. Vùng 1 gồm các phần tử A[1] .. A[n], vùng 2
gồm các phần tử A[n+1] .. A[2*n]. Ta trộn các Run từ vùng này và phân phối vào vùng kia. Khi
trộn và phân phối, ta trộn các Run ngợc chiều nhau của vùng trộn và phân phối luân phiên vào 2
đầu của vùng phân phối bớc kế tiếp dễ trộn hơn. Quá trình sắp xếp sẽ kết thúc nếu vùng phân phối
chỉ còn một Run. Khi kết thúc, nếu vùng phân phối gồm các phần tử A[n+1] .. A[2*n] thì ta chép
dãy A[n+1] .. A[2*n] vào dãy A[1] .. A[n]

ThĨ hiƯn b»ng Pascal

Procedure mergesort ( l , r : integer );
Var i , j , k , m: integer;

Begin

If r-l>0 then
Begin

m := (r+l) div 2;

mergesort (l,m); mergesort (m+1,r);
for i:=m downto l do b [i] := a [i];
for j:=m+1 to r do b [r+m+1-j] := a [j];
for k := l to r do

if b[i] < b [j] then

begin a [k] := b[i]; i:=i+1; end else
begin a [k] := b[j]; j:=j-1; end;
end;

End;
End;

<b>II. Hình học:</b>

- Điểm là đối tợng cơ sở trong hình học. Mỗi điểm mà chúng ta xét sau đây đợc biểu diễn bằng
một cặp số nguyên- toạ độ điểm đó trong hệ trục Descart thờng dùng.

- Một đoạn thẳng là một cặp điểm đợc nối với nhau bởi 1 phần của đờng thẳng.

- Một đa giác là một danh sách các điểm, với hai điểm cạnh nhau đợc nối bởi một đờng thẳng và
điểm đầu nối với điểm cuối tạo thành một hình đóng.

Thông thờng chúng ta dùng một mảng để biểu diễn một đa giác, dù rằng trong một số trờng hợp

ta có thể dùng danh sách liên kết hay các kiểu khác. Hầu hết trong các chơng trình chúng ta dùng
kiểu sau đây:

Type point = record x , y : integer; end;
line = record p1 , p2 : pointer; end;
Var polygon : array [0 .. nmax] of point;

Chú ý rằng các điểm đợc biểu diễn trên toạ độ nguyên, cũng có thể dùng số thực nhng dùng tọa
độ ngun thì thuật tốn sẽ đơn giản hơn nhiều và phép tính thực hiện nhanh hơn đáng kể.

</div>
<span class='text_page_counter'>(11)</span><div class='page_container' data-page=11>

Trong bài học sơ cấp đầu tiên, chúng ta sẽ xét xem 2 đoạn thẳng có giao nhau hay không. Một
phơng pháp dễ hiểu để giải quyết bài tốn này là tìm giao điểm của các đ ờng thẳng xác định bởi
các đoạn thẳng đó rồi kiểm tra xem nó có nằm giữa hai điểm đầu của hai đoạn thẳng đó hay
khơng. Một cách dễ dàng khác là xem thử xem đờng đi từ điểm thứ nhất sang điểm thứ 2 rồi sang
điểm thứ 3 theo chiều kim đồng hồ hay ngợc chiều kim đồng hồ:

Function ccw ( p0 , p1 , p2 : pointer ) : integer;
Var dx1 , dx2 , dy1 , dy2 : integer;

Begin

dx1:=p1.x; dy1:=p1.y-p0.y;
dx2:=p2.x; dy2:=p2.y-p0.y;
If dx1*dy2>dy1*dx2 then ccw:=1;
If dx1*dy2<dy1*dx2 then ccw:=1;
If dx1*dy2=dy1*dx2 then

Begin

If (dx1*dx2<0) or (dy1*dy2<0) then ccw:=-1 else

If (dx1*dx1+dy1*dy1) >= (dx2*dx2+dy2*dy2) then
ccw := 0 else ccw := 1;

End;
End;

Để hiểu đợc chơng trình hoạt động nh thế nào, đầu tiên ta giả sử tất cả các giá trị dx1 , dx2 ,
dy1 , dy2 đều dơng. Sau đó nhận xét rằng độ dốc của đờng nối p0 với p1 là dy1 / dx1, của đờng
nối p0 với p2 là dy2 / dx2. Do đó, nếu độ dốc của đờng thứ hai lớn hơn đờng thứ nhất thì đờng đi
từ p0 sang p1 , p2 là ngợc chiều kim đồng hồ và ngợc lại. So sánh độ dốc hơi bất tiện vì đờng có
thể theo phơng thẳng đứng ( dx1 hay dx2 = 0 ), chúng ta tính tích dx1 * dx2 để tránh trờng hợp
này. Do đó độ dốc không cần phải dơng mới đúng. Hàm ccw trả lại giá trị 0 cho trờng hợp p2 ở
giữa p0 và p1, bằng -1 nếu p0 ở giữa p2 và p1 và nếu p1 ở giữa p0 và p2 thì chúng ta gán ccw = 1.
Chúng ta có thể dùng trực tiếp ccw để cài đặt hàm intersect ( xét giao nhau ). Nếu cả hai đầu của
một đoạn thẳng ở hai bên đoạn kia, nghĩa là có giá trị ccw khác nhau thì chúng giao nhau:

Function intersect ( l1 , l2 : line ) : boolean;
Begin

intersect:=(( ccw(l1.p1,l1.p2,l2.p1)

* ccw(l1.p1,l1.p2,l2 .p2)) <= 0)
and (( ccw(l1.p1,l1.p2,l2 .p1)

* ccw(l1.p1,l1.p2,l2 .p2)) <= 0);
End;

Giải pháp này có vẽ đã dùng một số lợng lớn tính tốn để giải quyết một bài tốn đơn giản. Ngời
đọc hãy mạnh dạn thử tìm một phơng pháp đơn giảm hơn nhng chú ý phải đầy đủ các trờng hợp.
<b>2/ Đờng khép kín đơn:</b>

Để thấy đợc đặc điểm riêng của bài toán ứng với tập hợp các điểm, chúng ta xét bài tốn tìm một
đờng đi, qua một tập hợp n điểm xác định, qua tất cả các điểm, không giao nhau và cuối cùng trở
về điểm bắt đầu. Đờng đi nh trên gọi là đờng khép kín đơn.

Để giái quyết bài toán này ta phải chọn một điểm làm "điểm gốc". Sau đó tính góc tạo bằng cách
vẽ một đờng từ mỗi điểm trong tập hợp đến gốc vẽ ra theo phơng ngang. Sau đó, sắp thứ tự các
điểm theo thứ tự tăng dần của góc tơng ứng, cuối cùng nối các điểm cạnh nhau lại.

Gọi dx , dy là khoảng cách từ điểm gốc đến một điểm khác theo trục hồnh và tung thì góc cần
tính trong giải thuật này là cotan dy / dx. Nhng hàm này có vẽ chậm, vì vậy ta có thể thay bằng
một hàm khác tơng tự nhng dễ tính hơn, đó là dy / ( dy + dx ). Chơng trình sau trả lại giá trị từ 0
đến 360, không phải là góc tạo bởi p1 và p2 so với phơng ngang nhng có cùng thuộc tính nh góc
đó.

</div>
<span class='text_page_counter'>(12)</span><div class='page_container' data-page=12>

Var dx , dy , ax , ay : integer;
Begin

dx:=p2.x - p1.x; ax:= abs(dx);
dy:=p2.y - p1.y; ay:= abs(dy);
If (dx=0) and (dy=0) then t:=0 else
t:=dy/(ax+ay);

If dx < 0 then t:=2-t else
If dy < 0 then t:=4+t;
theta := t*90;

End;

<b>3/ Điểm nằm trong đa giác:</b>

Tip theo, chúng ta sẽ xét một bài toán rất tự nhiên: cho một điểm và một đa giác biểu diễn bằng
một mảng các điểm, xác định xem điểm này nằm trong hay ngoài đa giác. Một giải pháp dễ hiểu
để giải bài toán này là vẽ một đọan thẳng dài bắt đầu từ điểm đó theo một hớng bất kỳ và đếm số
lợng đoạn thẳng tạo đợc do nó cắt qua đa giác. Nếu là số lẽ, điểm đó nằm trong đa giác và ngợc
lại. điều này dễ thấy nếu chúng ta theo dõi những gì xãy ra khi đi từ một điểm nằm ngoài đa giác.
Tuy nhiên, khơng phải chỉ nh thế, bởi vì một số giao điểm có thể trùng với đa giác, hoặc đoạn
thẳng dùng để kiểm tra trùng với một cạnh của đa giác.

Nhu cầu xử lý các tình huống khi các đỉnh cảu đa giác rơi trên đoạn thẳng kiểm tra buộc chúng
ta phải làm nhiều hơn là chỉ đếm số giao điểm của các cạnh đa giác với đoạn thẳng kiểm tra. Thực
chất, chúng ta muốn đi vòng quanh đa giác, tăng một biến đếm khi nào ta di từ một bên của đoạn
thẳng kiểm tra sang một bên khác. Một cách để thực hiện là đơn giản bỏ qua các điểm rơi trên
đoạn thẳng kiểm tra, nh trong chơng trình sau đây:

Function inside (t:point):boolean;
Var count,i,j:integer;

lt,lp:line;
Begin

count:=0; j:=0; p[0]:=p[N]; p[N+1]:=p[1];
lt.p1:=t; lt.p2:=t; lt.p2.x:=maxint;
For i:=1 to N do

Begin

lp.p1 := p [i]; lp.p2 := p [i];
If not intersect (lp,lt) then
Begin

lp . p2 := p [j]; j := i;

If intersect (lp,lt) then count := count + 1;
End;

End;

inside := ((count mod 2) = 1);
End;

Chơng trình này dùng đờng thẳng kiểm tra theo phơng ngang để dễ tính tốn. Biến j đợc dùng để
lu trữ chỉ số của điểm cuối cùng của đa giác mà khơng nằm trên đoạn kiển tra. Chơng trình giả sử
rằng p [ 1 ] là điểm có tọa độ x nhỏ nhất trong số tất cả các điểm có tọa độ y nhỏ nhất, vì vậy nếu
p [ 1 ] nằm trên đoạn kiểm tra thì p [ 0 ] khơng thể. Cùng một đa giác có thể biểu diễn bằng N
mảng khác nhau, nhng điều này cho thấy áp dụng một quy luật chuẩn cho p [ 1 ] đôi khi lại tiện
lợi. Nếu điểm kết tiếp trên đa giác mà không nằm trên đoạn kiểm tra, ở cùng một phía nh điểm
thứ j đối với đoạn kiểm tra thì chúng ta khơng cần phải tăng biến đếm giao điểm ( count ). Ngợc
lại, chúng ta có đợc một giao điểm.

</div>
<span class='text_page_counter'>(13)</span><div class='page_container' data-page=13>

điểm là khơng có đoạn kiểm tra nào có hơn 2 giao điểm với đa giác. Trong trờng hợp này, một thủ
tục nh tìm nhị phân có thể dùng để xác định trong O ( log N ) bớc để biết đợc điểm có ở bên trong
hay khơng.

<b>III. Cặp ghép:</b>

1. Giíi thiệu chung:

Xét hai tạp hữu hạn X, Y gåm n phÇn tư:
X= { x1, x2, ... xn }

Y= { y1, y2, ... yn }

Cặp phần tử (x, y) với x thuộc X, y thuộc Y đợc gọi là một cặp gh<b>ộ</b>p. Hai cặp gh<b>ộ</b>p (x , y) và (x1,
y1) đợc gọi là rời nhau nếu x # x1 và y # y1. Tập M gồm các cặp ghép rời nhau đợc gọi là một tập
cặp ghép.

Thơng thờng bài tốn xây dựng các cặp ghép đợc tiếp cận theo 2 hớng: Hoặc thoả mãn một số
điều kiện ghép cặp nào đấy, khi đó ngời ta quan tâm đến khả năng ghép cặp tối đa, hoặc lợng hố
việc ghép cặp, khi đó ngời ta quan tâm đến việc tối u hoá theo các giá trị đã lợng hố.

Vì số tập cặp ghép là hữu hạn, nên có một phơng pháp xây dựng tầm cỡ là thử tất cả các khả
năng. Tuy nhiên, số khả năng nh vậy rất lớn (cỡ n!). Vì thế, ngời ta quan tâm đến việc tìm kiếm
những thuật giải hữu hiệu, dễ cài đặt chơng trình và có tính khả thi cao. Bài tốn này nhằm giới
một số mụ hình ghép cặp nh vậy.

2. Cặp ghép đầy đủ tối u
<b>a. Giới thiệu bài toán</b>

Một cặp ghép, sao cho tất cả các phần tử của X và Y đều đợc ghép cặp (nghĩa là có đủ n cặp với
n là số phần tử của X và Y), đợc gọi là ghép cặp đầy đủ.

Rõ ràng mỗi song ánh p: X -> Y xác định một tập ghép cặp đầy đủ, trong đó mỗi cặp ghép đợc
viết dới dạng (x , p(x)), x thuộc X. Từ đó suy ra có tất cả n! cách xây dựng tập cặp ghép đầy đủ
khác nhau.

Với các tập cặp ghép đầy đủ, một cách tự nhiên, ngời ta quan tâm đến tập cặp ghép "tốt nhất"
theo một nghĩa nào đó đã đợc lợng hố. Tập cặp ghép này đợc gọi là "Tập cặp ghép đầy đủ và tối
-u",

Bài tốn tìm cặp ghép đầy đủ tối u có nhiều mơ hình ứng dụng thực tế. Một trong những mơ hình
này ngời ta quan tâm dến việc ghép cặp sao cho có hiệu qủa nhất.

Để lợng hoá việc ghép cặp mỗi phần tử x thuộc X với một phần tử y thuộc Y, ngời ta đa vào ma
trận trọng số Cij (i,j = 1, 2, .., n) với ý nghĩa Cij mô tả hiệu quả của việc ghép xi với ỵ. Bài toán đ
-ợc đặt ra là: Xây dựng một tập cập ghép đầy dủ có tổng hiệu quả lớn nhất.

Bài toán vừa nêu thờng đợc phát biểu dới dạng một mơ hình thực tế là bài tốn phân cơng dới
đây:

Bài tốn phân cơng: Có n ngời và n công việc. Biết Cij là số tiền làm ra nếu giao công việc j cho
ngời thứ i thực hiện. Hãy tìm cách phân cơng mỗi ngời mỗi việc để tổng số tiền làm ra là lớn nhất.
b. Phơng pháp tham lam

Đây là một phơng pháp gần đúng, xuất phát từ việc chọn tối u trong từng bớc vì thế nó
khơng đảm bảo đợc tính tối u tồn cục. Tuy nhiên, nó cho ngay một phơng án, gần đúng với
ph-ơng án tối u:

1. Xuất phát từ bản Cij đóng vai trị bảng hiện hành. Tập cặp ghép đợc khởi gán bằng rỗng.
2. Tìm dịng i cột j ra khỏi bảng hiện hành và lặp lại bớc thứ 2 cho đến khi bảng rỗng.
3. Xố dịng i, cột j ra khỏi bảng hiện hành và lặp lại bớc 2 cho đến khi bảng rỗng.
Thí dụ, xét bảng trọng số với n = 4:

</div>
<span class='text_page_counter'>(14)</span><div class='page_container' data-page=14>

8 7 6 4
6 9 3 5
5 1 2 7

các cặp ghép đợc chọn lần lợt là (1 8 9 7)
(x3, y2), (x2, y1), (x4, y4), (x1, y3).

Với phơng án trên ta có tổng trọng số là 25. Trờng hợp này các cách ghép tìm đợc cha phải là
cặp ghép đầy đủ và tối u( xem li vớ d ny di).

<b>c. ịnh lý cơ sở</b>

Vic xây dựng tập cặp ghép đầy đủ tối u dựa vào dấu hiệu nhận biết một tập ghép đầy đủ
khi nào là tối u. Dĩ nhiên việc thử dấu hiệu này không phải là việc so sánh với tất cả các cặp ghép,
mà phải đợc mang tính khả thi. Để lam điều này ngời ta xây dựng hàm số F, xác định trên tập của
các phần tử Xi thuộc X , Yj thuộc Y , mà ta sẽ gọi là nhãn của các phần tử . Nhãn F đợc gọi là
nhãn chấp nhận đợc nếu thõa mãn bất đẳng thức F(Xi)+F(Yj)>=Cij với mọi Xi thuộc X , Yj thuộc
Y . Tập cặp ghép M và nhãn F đợc gọi là tơng thích với nhau nếu thỗ mãn đẳng thức F(Xi)
+F(Yj)=Ci với mọi (Xi,Yj)thuộc M , Noi riêng , tập cặp ghép rỗng đợc xem nh tơng thích với mọi
nhãn .

Định lý: Tập cặp ghép đầy đủ M* là tối u khi tồn tại nhãn F chấp nhận đợc là tơng thích với
nó .

Dựa vào định lý vừa chứng minh , ngời ta có 2 hớng tiếp cận cặp ghép đầy đủ tối u :

* Một là , xuất phát từ cặp ghép đầy đủ M nào đó , ngời ta xây dựng một nhãn F tơng thích với
M . Nếu F chấp nhận đợc , thì M tối u . Trái lại , ngời ta điều chỉnh M cho đến khi F tơng thích là
chấp nhận đợc khi đó M là tội u .

* Hai là , xuất phát từ một nhãn F chấp nhận đợc và một cặp ghép M bất kỳ tơng ứng với F ( có
thể rỗng ) , ngời ta tăng dần số cặp ghép M sao cho vẫn đảm bảo tim đợc nhãn F tơng thích với M
chấp nhận đợc . Quá trình tăng sẽ kết thúc khi M đầy đủ và khi đó M là tối u .

Dới đây trình bầy một thuật tốn tim cặp ghép đầy đủ tội u theo hớng thứ hai .
<b>d. Thuật toán Kuhn-Munkes</b>

Nội dung chủ yếu của phơng pháp là xuất phát từ một tập cặp ghép nào đó cha đâỳ đủ (co
thể lập hợp rỗng ) , ta tăng dần số cặp ghép sao cho khi trở thành đầy đủ , các cặp ghép thu đợc
cũng đồng thời thỗ mãn tính tối u . Có nhiều hình thức trình bày phơng pháp này . Dới đây là
cách trình bầy trên ngơn ngữ đồ thị với các thao tác tìm kiếm . Cách này có nhiều u điểm : trực
giác , dễ pháp biểu , dể chứng minh và đặc biệt , dể cài đặt chơng trình vì việc tìm dờng trên đồ
thị là một thao tác cơ bản và quen thuộc .

Giả sử F là một nhãn chấp nhận đợc và M một tập cặp ghép tơng thích với F . Xem các phần tử
của X và Y nh những đỉnh của đồ thị có hai hớng (một phía X một phía Y ). Các cạnh của đồ thị
này đợc xác định tuỳ thuộc nội dung của nhãn F và tập cặp ghép M nh sau :

- Mỗi cặp phần tử Xi thuộc X , Yj thuộc Y thoã mãn đẳng thức F(Xi)+F(Yj)=Cij sẽ xác
định một cạnh ca th ,

- Cạnh này có hớng từ X sang Y nếu cặp (Xi ,Yj) không thuộc M gọi (là cạnh thuận) và ngợc
lại , có xu híng tõ Y sang X nÕu cỈp (Xi ,Yj) thuộc M (gọi là cạnh nghịch).

th xây dựng theo quy tắc vừa nêu đợc gọi là đồ thị cân bằng tơng ứng với F , M và đợc ký
hiệu là G(F,M).

Bíc 1:

</div>
<span class='text_page_counter'>(15)</span><div class='page_container' data-page=15>

F( xi ) := Max {C[ i , j ] , yj thuéc Y }
F( yj ) := 0 yj thuéc Y

M là tập cặp ghép rỗng .

Chỳ ý rằng , có thể xuất pháp từ bất kỳ nhãn F nào chấp nhận đợc và bất ký một tập cặp ghép M
nào tơng ứng với F.

Bíc 2:

Tìm đỉnh tự do thuộc X: Tìm đỉnh u thuộc X cha đợc ghép cặp. Nếu khơng cịn đỉnh nào của X
cha ghép cặp thì kết thúc, tập cặp ghép M hiện hành là tập cập ghép tối u. Trái lại sang bớc tiếp
theo.

Bíc 3:

Xuất phát từ u, thực hiện việc tìm kiếm trên đồ thị G(F, M). Kết quả tìm đợc có hai trờng hợp
sau:

- Nếu đến đợc một đỉnh z thuộc Y cha ghép cặp thì ghi nhận đờng đi từ u -> z (gọi là đờng tăng
cặp ghép) và chuyển sang bớc tăng cặp ghép trên đờng đi này.

- Nếu không tồn tại một đờng đị nh vậy thì chuyển sang bớc sa nhón F.
Bc 4:

Tăng cặp ghép: Điều chỉnh M nh sau:

- Giữ nguyên những cặp ghép của M nằm ngoài đờng tăng cặp ghép

- Trên đờng tăng cặp ghép, thay đổi những cặp ghép của M (cạnh ngợc) băng những cặp ghép
cạnh thuật (về mặt đồ thị nghĩa là đổi chiều các cạnh trên đờng tăng cặp ghép)

Sau bớc này, số cặp ghép thuộc M đợc tăng them 1 và đỉnh u trở thành đã ghép cặp, ngồi ra,
tính tơng thích giữa F và M vẫn đợc bảo tồn. Sau đó quay lại bớc 2 để thực hiện việc sửa nhãn tự
do khác.

Bíc 5: Sưa nh·n:

Gọi S là tập các đỉnh thuộc X và T là tập cặp ghép thuộc Y đã đợc đi trong quá trình tìm đờng
đi ở bớc 3. Việc sửa nhãn đợc tiến hành nh sau:

- Tìm lợng sửa nhÃn:

d := Min { F(xi) + F(yj) - C[i,j] , yj thuéc T}
- Gán lại nhÃn:

F(xi) := F(xi) - d víi xi thuéc S
F(yj) := F(yj) + d víi yj thuéc T

Sau đó, quay trở lại bớc 3 để lặp lại tìm đờng tăng cặp ghép (với đỉnh xuất phát u cũ và nhãn F
mới).

Chú ý rằng, sau khi thay đổi, nhãn F vẫn giữ nguyên tính chấp nhận đợc và tính tơng thích M.
Ngồi ra có thêm ít nhất một cặp (xi, yj) thoả mãn F(xi) + F(yj) = C[i,j], vì thế, sau một số lần đổi
sữa nhãn, chắc chắn sẽ tăng đợc cặp ghép.

Dới đây là sơ đồ minh hoạ các bớc đã nêu:
(Sơ đồ)

Nhận xét rằng, khi tăng cặp ghép, các đỉnh đã đợc tiến ghép cặp rồi khơng bao giờ trở thành tự
do, vì thế việc tìm đỉnh tự do có thể đợc tiến hành tuần tự. Quá trình tìm tập cặp ghép đầy đủ tối u
có thể đợc mơ phỏng qua doạn chơng trinh sau:

</div>
<span class='text_page_counter'>(16)</span><div class='page_container' data-page=16>

IF <u cßn tù do> THEN
BEGIN

WHILE NOT <Tìm thấy đờng tăng cặp ghép từ u>
DO <sửa nhãn>

END;
e. VÝ dô

Quay trá lại thí dụ trớc. NhÃn F chấp nhận ban đầu lµ:
F 0 0 0 0

6 2 5 1 6
8 8 7 6 4
9 6 9 3 5
7 5 1 2 7

Xuất phát từ cặp ghép M rỗng, lần lợt tăng cặp ghép cho các đỉnh tự do x1, x2, x3, ta nhận đợc
M={ (x1, y4), (x2, y1), (x3, y2) } và đồ thị G(F,M) tơng ứng:

Việc tìm đờng tăng cặp ghép tơng đối với đỉnh tự do x4 khơng tìm thấy và cho ta các tập S =
{x1, x4}, T ={y4). Tiến hành sữa nhãn trên các tập cặp ghép này, ta đợc d=1 và nhãn F mới là
F 0 0 0 1

5 2 5 1 6
8 8 7 6 4
9 6 9 3 5
6 5 1 2 7

nhãn F này thêm đợc cẵp1, y2 thoả mãm F(x1) + F(x2) = C[1,2] và ta đợc đồ thị G(F,M):

Đờng tăng cặp ghép đối với x4 vẫn không tồm tại. Tuy nhiên S và T đã đợc mở rộng thêm:
S ={x1, x3, x4} và T = {y2, y4} và lợng nhãn đợc sủa trên các tập này là d = 1:

</div>
<span class='text_page_counter'>(17)</span><div class='page_container' data-page=17>

Lần này F thêm đợc cặp x4, y1 thoả mãm F(x4) + F(y1) = C[4,1] và đợc đồ thị G(F,M):

Việc tìm kiếm vẫn cha kết thúc và cho S = {x1, x2, x3, x4}, T = {y1, y2, y4}. Lợng nhãn đợc
sửa lần này là 2, và ta nhận đợc:

F 2 3 0 4
2 2 5 1 6
6 8 7 6 4
6 6 9 3 5
3 5 1 2 7

cùng với đồ thị G(F,M) (thêm cạnh x2, y3):

Việc tìm kiếm trên đồ thị này kết thúc tại y1 cho ta đờng tăng cặp ghép:
x4 -> y1 -> x2 -> y3

và trên đờng này, cặp ghép cũ (x2, y1) đợc thay bằng 2 cặp ghép mới (x2, y3) và (x4, y1)
Kết quả cuối cùng cho tập cặp ghép đầy đủ tối u

</div>

<!--links-->