Một số thuật toán hình học
- Đ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 nhưng dùng tọa độ nguyên thì thuật toán sẽ
đơn giản hơn nhiều và phép tính thực hiện nhanh hơn đáng kể.
Nhiều đối tượng hình học phức tạp sẽ được
biểu diễn dựa trên các phần tử cơ sở này.
1/Giao các đoạn thẳng:
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 toá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 toán để giải quyết một bài toá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 nhưng chú ý phải đầy đủ các trường hợp.
2/ Đường khép kín đơn:
Để 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 toá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 hoành và tung thì góc cần tính trong giải thuật này là
cotan dy / dx. Nhưng 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ự nhưng 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 nhưng có cùng thuộc tính như góc đó.
Function theta ( p1 , p2 : pointer ) : real;
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;
3/ Điểm nằm trong đa giác:
Tiếp 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 toán. Biến j được dùng để lưu 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, nhưng đ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.
Nếu đa giác chỉ có 3 hay 4 cạnh, thường gặp
trong nhiều ứng dụng thì một chương trình phức tạp như vậy sẽ không được sử
dụng, một thủ tục đơn giản đặt cơ sở trên việc gọi ccw sẽ thích hợp hơn. Một
trường hợp đặc biệt quan trọng khác lá đối với đa giác lồi, được xét trong
chương kế, nó có đặc đ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.
III. Cặp ghộp:
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ộp. Hai cặp ghộ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 toá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 hoá 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
hoá.
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 toá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
a. Giới
thiệu bài toán
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 hoá. 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 toá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 toán phân công dưới đây:
Bài toá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 toà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. Xoá 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:
2 5 1 6
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 chưa phải là cặp ghép đầy đủ và tối ưu(
xem lại ví dụ này ở dưới).
c. Định lý cơ sở
Việc 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 thoã 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 toán tim cặp
ghép đầy đủ tội ưu theo hướng thứ hai .
d. Thuật toán Kuhn-Munkes
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 đó chưa đâỳ đủ (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 thoã 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 của đồ 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:
Khởi tạo :
Xây dựng được nhãn F chấp nhận được như sau :
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
chưa được ghép cặp. Nếu không còn đỉnh nào của X chưa 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 chưa 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 sửa nhãn F.
Bước 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, ngoài ra, tính tương thích giữa F và M
vẫn được bảo toà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. Ngoà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.
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:
<Khởi tạo nhãn và tập cặp ghép ban đầu>
FOR <U thuộc X>
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:
F
0 1 0 2
4
2 5 1 6
8
8 7 6 4
8
6 9 3 5
5
5 1 2 7
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 chưa 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
M = {(x1, y4), (x2, y1), (x3, y2), (x4,
y1)}
với tổng trọng số là 6 + 6 + 9 + 5 = 26.