Chương 1 Kiến Thức Chuẩn Bị Chương này trình bày lại một số khái niệm tối ưu hóa và hình học tính toán trong tài liệu [1], [2], [4] và [5]. Ký hiệu bởi R2 , k · k không gian tọa độ thực qP 2 2 2 với độ dài đoạn ka − bk = i=1 (ai − bi ) , trong đó a, b ∈ R , a = (a1 , a2 ) và b = (b1 , b2 ). Ký hiệu được viết lại: B(a, r) = p ∈ R2 | kp − ak < r , B[a, r] = p ∈ R2 | kp − ak ≤ r , và ∂B[a, r] = p ∈ R2 | kp − ak = r , với r > 0. Đối với bất kỳ hai điểm a, b ∈ R2 , tập hợp [a, b] := {(1 − λ)a + λb | 0 ≤ λ ≤ 1}, được gọi là một đoạn thẳng với hai điểm đầu mút là a và b.
Nhắc lại định nghĩa ]a, b] := [a, b]\{a}, và ]a, b[:= [a, b]\{a, b}. Lưu ý rằng khi a = b, ta có [a, b] = {a}, và [a, b[=]a, b] =]a, b[= ∅.1 Định nghĩa đường đi dọc theo dãy các bó đoạn thẳng. Một đường đi γ nối p và q được gọi là một đường đi dọc theo một dãy các đoạn thẳng e1 , e2 ,. , en nếu có một dãy các số t0 ≤ t1 ≤ t2 ≤.
≤ tn ≤ t1 sao cho γ(ti ) ∈ ei cho i = 1, 2,. , n, cũng gọi hình ảnh γ([t0 , t1 ]) là đường đi γ. Đường đi ngắn nhất nối p và q dọc theo một dãy các đoạn thẳng e1 , e2 ,. , em , được ký hiệu là SP(p, q), được xác định là đường đi có độ dài ngắn nhất.
[a, bm ]} (m ≥ 1) là một bó đoạn thẳng gồm m đoạn thẳng khác nhau trong R2. Nó được gọi là một bó đoạn thẳng gồm m đoạn thẳng với đỉnh chung là a. Một điểm đơn lẻ được coi là một bó suy biến. Nói rằng hai bó Trần Văn Thắng 2 Toán ứng dụng Luận văn Thạc sĩ đoạn thẳng khác nhau a và a0 giao nhau, nếu có hai đoạn thẳng [a, b] của a và [a0 , b0 ] của a0 có một điểm chung ngoại trừ các điểm cuối.
Nếu không, nói rằng a và a0 không giao nhau. Xét một tập hợp được sắp xếp của các bó đoạn thẳng a1 , a2 ,. Nó được gọi là một dãy các bó đoạn thẳng. Trong luận văn sử dụng thuật ngữ "đường đi dọc theo dãy các bó đoạn thẳng" là một đường đi dọc theo dãy các đoạn thẳng với thứ tự của các bó đoạn thẳng và thứ tự của các đoạn thẳng trong mỗi bó.1 cho thấy một đường đi nối hai điểm p và q dọc theo dãy các bó đoạn thẳng a1 , a2 , a3 , a4 .1: Đường đi nối hai điểm p và q dọc theo dãy các bó đoạn thẳng F = {a1 , a2 , a3 , a4 } .2 Định nghĩa đường gấp khúc có ràng buộc góc Định nghĩa 1.
Tức là tia ray(b|a) chứa [a, b] nhưng kéo dài từ b ra xa khỏi a. Đối với một đoạn thẳng [a, b] và một số thực ε ≥ 0 cho trước. Định nghĩa vùng lân cận Rε ([a, b]) là tập hợp các điểm có khoảng cách Euclid từ [a, b] không vượt quá ε: Rε ([a, b]) = p ∈ R2 , ||[a, b] − p|| ≤ ε. Cho một đường gấp khúc tùy ý P = (p1 , p2 , ., pn ) có n số đỉnh trong R2.
Trong đó bất kỳ hai đỉnh liên tiếp pi , pi+1 trên P được nối bởi đoạn thẳng [pi , pi+1 ], với Trần Văn Thắng 3 Toán ứng dụng Luận văn Thạc sĩ 1 ≤ i < n, tìm một đường gấp khúc khác P 0 = (p1 = pi1 , pi2 , ., pim = pn ) có m số đỉnh (m < n), thỏa mãn các điều kiện sau đây: (1) Các chỉ số nguyên thỏa mãn 1 = i1 < i2 <. (2) Đối với mọi j = 1, 2, ., m−1 thì đường gấp khúc Pij ,ij+1 = pij , pij +1 , ., pij+1 của P được hoàn toàn chứa trong vùng lân cận Rε [pij , pij+1 ] với ε > 0. Trường hợp 1: Góc quay giữa hai đoạn thẳng kề nhau [ph , pi ] và [pi , pk ] trên P 0 ít nhất phải là một giá trị δ , với 0 6 δ ([ph , pi ]) < π2. Đây là trường hợp góc quay tối thiểu trong Hình 1.2: Minh họa điều kiện ràng buộc góc cho trường hợp góc quay tối thiểu trong R2 : (a) các cạnh [ph , pi ] và [pi , pk ] liên tiếp trong đường đi P 0 , và (b) các cạnh [ph , pi ] và [pi , pk ] không thể liên tiếp trong P 0.
Trần Văn Thắng 4 Toán ứng dụng Luận văn Thạc sĩ Trường hợp 2: Góc quay giữa hai đoạn thẳng liên tiếp [ph , pi ] và [pi , pk ] trên đường gấp khúc P 0 không vượt quá một giá trị xác định δ , với π2 6 δ ([ph , pi ]) < π. Đây là trường hợp góc quay lớn nhất trong Hình 1.3: Ràng buộc góc cho vấn đề góc quay tối đa trong R2 : δ là một góc quay giữa [ph , pi ] và [pi , pk ]; (a) các cạnh [ph , pi ] và [pi , pk ] liên tiếp trong đường đi P 0 , và (b) các cạnh [ph , pi ] và [pi , pk ] không thể liên tiếp trong P 0 .3 Kết luận Chương này trình bày lại định nghĩa đường đi dọc theo dãy các bó đoạn thẳng, định nghĩa đường gấp khúc có ràng buộc góc trong hình học tính toán. Trần Văn Thắng 5 Chương 2 Phương Pháp Bắn Nhiều Lần Tìm Đường Đi Gần Nhất Xấp Xỉ Trên R2 2.1 Giới thiệu Chương này trình bày lại phương pháp bắn nhiều lần là tìm đường đi từ một điểm p đến điểm q dọc theo dãy các bó đoạn thẳng F = {a0 , a1 , a2 ,. aN +1 } (với N ≥ 1), trong đó p = a0 và q = aN +1 là 2 điểm đầu và cuối của dãy với dãy bó các đoạn thẳng phải nằm trong góc < 180 độ tại đỉnh.
Ba yếu tố (f1), (f2) và (f3) của phương pháp bao gồm phân hoạch, thiết lập - kiểm tra điều kiện thẳng hàng và cập nhật các điểm bắn. Tại một bước lặp nào đó, nếu một đường đi thỏa mãn điều kiện thẳng hàng tại tất cả các điểm bắn, thì trả về một đường gấp khúc mới P nối từ p đến q dọc theo dãy F ngắn hơn γ 0 = {a0 , a1 , a2 ,. aN +1 } ban đầu.2 Phát biểu bài toán Cho F = {a0 , a1 , a2 ,. aN +1 } (với N ≥ 1), trong đó p = a0 và q = aN +1 là 2 điểm đầu và cuối của dãy với dãy bó các đoạn thẳng phải nằm trong góc < 180 độ tại đỉnh.
Tìm một đường gấp khúc mới P nối từ p đến q dọc theo dãy F ngắn hơn γ 0 = {a0 , a1 , a2 ,. aN +1 } ban đầu. (P ) Một đường gấp khúc nối từ p đến q dọc theo dãy F ngắn hơn γ 0 = {a0 , a1 , a2 ,. aN +1 } ban đầu.3 Phương pháp bắn nhiều lần Phần này trình bày lại phương pháp bắn nhiều lần để tìm đường đi xấp xỉ ngắn nhất nối hai điểm dọc theo một dãy các bó đoạn thẳng trong [2].
Để giải bài toán phát biểu trên, tôi trình bày lại với ba yếu tố như sau: (f1) Chia dãy F các bó đoạn thẳng thành các dãy con gồm các bó đoạn thẳng. Lấy một tập hợp các đoạn thẳng cắt được sắp xếp, chúng là các đoạn thẳng cuối cùng của mỗi dãy con. Lấy một tập hợp các điểm bắn ban đầu được sắp xếp trên các đoạn thẳng cắt. 6 Toán ứng dụng Luận văn Thạc sĩ (f2) Xây dựng một đường đi dọc theo F nối p và q , được tạo thành bởi tập hợp các điểm bắn.
Đường đi này là sự ghép nối của các đường đi ngắn nhất nối hai điểm bắn liên tiếp dọc theo dãy con tương ứng. Một điều kiện dừng được thiết lập tại các điểm bắn. (f3) Phương pháp thực hiện (f2) tại tất cả các điểm bắn. Nếu điều kiện thẳng hàng được thỏa mãn tại tất cả các điểm bắn, phương pháp dừng lại.
Ngược lại, cập nhật của các điểm bắn là cải thiện các đường đi nối p và q dọc theo F. Phần tiếp theo sẽ cung cấp một lời giải chi tiết về các yếu tố này. Yếu tố (f1): Phân hoạch Cho K là một số tự nhiên sao cho 1 ≤ K ≤ N , với N là số lượng bó của F ngoại trừ p và q. Phân chia F thành K dãy con Fi của các bó đoạn thẳng và chọn các đoạn cắt gọi là ξi , với i = 0, 1,.
, K + 1 như sau: +Fi bao gồm một bó hoặc một số bó kề nhau của F cho i = 0, 1,. +ξi là đoạn cắt cuối cùng của Fi−1 , với i = 1, 2,. SK +Fi ∩ Fj = ∅, cho i 6= j, i, j ∈ {0, 1,. Ký hiệu ξi = [ui , vi ], cho tất cả i = 0, 1,.
, K + 1, trong đó vi và ui được xác định như sau: Nếu ξi có một đầu mút nằm bên phải của γ 0 khi đi từ p đến q , thì vi là đầu mút trên γ 0 , còn ui là đầu mút còn lại. Ngược lại, vi là đỉnh của bó chứa ξi và ui là đầu mút γ 0 còn lại. Ngoài ra ta còn có u0 = v0 = p, uK+1 = vK+1 = q. Vì dãy các bó là khác nhau, hai đoạn đường cắt tùy ý không giao nhau.
Tiếp theo, khởi tạo một tập hợp các điểm theo thứ tự bằng cách lấy một điểm đầu trong mỗi đoạn cắt. Hai điểm ban đầu liên tiếp được nối bằng đoạn ngắn nhất, nối hai điểm này dọc theo dãy con phù hợp của các bó. Đoạn đường nhận được bằng cách hợp những đoạn thẳng ngắn nhất này được gọi là đoạn đường khởi tạo của thuật toán xem Hình 2. Để tiện cho làm việc, những điểm ban đầu này được chọn là vi , cho i = 0, 1,.
Đối với mỗi bước lặp, mà được nhắc lại trong các phần kế tiếp Trần Văn Thắng 7 Toán ứng dụng Luận văn Thạc sĩ Hình 2.