Thiết kế và đánh giá thuật toán

khoitao()

{

scanf(n);

scanf(k); d=0;

for(i=1;i<=n;i++) b[i]=0;

}

try(i)

{

Có thể bạn quan tâm!

Xem toàn bộ 205 trang tài liệu này.

for(j=1;j<=n;j++) if(b[j]==0)

{

c[i]=a[j]; b[j]=1;

if(i==k) ht(); else

try(i+1);

b[j]=0;

}

5. Ma phương bậc n là ma trận vuông cấp n với các phần tử là các số tự nhiên từ 1 đến n2 thoả mãn tính chất: Tổng các phần tử trên mỗi hàng, mỗi cột và mỗi đường chéo đều bằng nhau. Liệt kê các ma phương bậc 3.

Hướng dẫn:

- Các phần tử của ma trận vuông cấp ba A lần lượt được lưu trữ trong các phần tử từ x[1] đến x[9] của mảng x:

a11 được lưu trữ trong x[1] a12 được lưu trữ trong x[2]

a13 được lưu trữ trong x[3] a21 được lưu trữ trong x[4] a22 được lưu trữ trong x[5] a23 được lưu trữ trong x[6] a31 được lưu trữ trong x[7] a32 được lưu trữ trong x[8] a33 được lưu trữ trong x[9]

- Dùng thuật toán quay lui xây dựng tất cả các hoán vị của 9 phần tử 1, 2, 3,..., 9 Mỗi hoán vị sẽ được lưu trữ trong các phần tử của mảng x.

- Mỗi khi được một hoán vị thì kiểm tra điều kiện, tức là kiểm tra các tổng: x[1] + x[2] + x[3]; x[4] + x[5] + x[6]; x[7] + x[8] + x[9] (tổng các hàng)

x[1] + x[4] + x[7]; x[2] + x[5] + x[8]; x[3] + x[6] + x[9] (tổng các cột) x[1] + x[5] + x[9]; x[3] + x[5] + x[7] (tổng các đường chéo)

nếu các tổng đó bằng nhau thì hiển thị các phần tử của mảng x ra màn hình dưới dạng ma trận (Nếu i mod 3 = 0 thì xuống hàng)

5.1. Nội dung kỹ thuật

Chương 5

KỸ THUẬT NHÁNH VÀ CẬN

Kỹ thuật quay lui, vét cạn có thể được sử dụng để giải các bài toán tối ưu tổ hợp bằng cách tiến hành duyệt các phương án của bài toán, đối với mỗi phương án ta đều tính giá trị hàm mục tiêu tại nó, sau đó so sánh giá trị hàm mục tiêu tại tất cả các phương án để tìm ra phương án tối ưu. Tuy nhiên trong thực tế với nhiều bài toán phương pháp áp dụng kỹ thuật này rất khó có thể chấp nhận được về thời gian. Vì vậy cần phải có những biện pháp nhằm hạn chế việc tìm kiếm thì mới có hy vọng giải được các bài toán tối ưu tổ hợp thực tế. Tất nhiên để có thể đề ra những biện pháp như vậy cần phải nghiên cứu kỹ tính chất của bài toán tối ưu tổ hợp cụ thể. Nhờ những nghiên cứu như vậy, trong một số trường hợp cụ thể ta có thể xây dựng những thuật toán hiệu quả để giải bài toán đặt ra. Khi đó, một vấn đề đặt ra là trong quá trình liệt kê lời giải ta cần tận dụng các thông tin đã tìm được để loại bỏ những phương án chắc chắn không phải là tối ưu. Kỹ thuật nhánh và cận (gọi tắt là nhánh cận) là một cải tiến của kỹ thuật quay lui theo hướng này.

Ta sẽ mô tả nội dung của kỹ thuật nhánh cận trên mô hình bài toán tối ưu tổ hợp tổng quát sau:

min { f( x ): trong đó D là tập hữu hạn các phần tử. Giả thiết D được mô tả như sau:

x D }

D = { x = (x1, x2, ..., xn) A1 A2 ... An: x thỏa mãn tính chất P}, với A1, A2, ..., An là các tập hữu hạn, còn P là tính chất cho trên tích Đềcac

A1 A2 ... An.

Với giả thiết về tập D nêu trên, chúng ta có thể sử dụng thuật toán quay lui để liệt kê các phương án của bài toán. Trong quá trình liệt kê theo thuật toán quay lui, ta sẽ xây dựng dần các thành phần của phương án. Một bộ gồm k thành phần (a1, a2, ..., ak) xuất hiện trong quá trình thực hiện thuật toán sẽ gọi là phương án bộ phận cấp k.

Kỹ thuật nhánh cận có thể áp dụng để giải bài toán đặt ra nếu như có thể tìm được một hàm g xác định trên tập tất cả các phương án bộ phận của bài toán thỏa mãn bất đẳng thức sau:

g(a1, a2, ..., ak) min{f(x): xD, xi =ai, i= 1,2, ..., k } (*)

với mọi lời giải bộ phận ( a1,a2, ..., ak ), và với mọi k= 1,2,...

Bất đẳng thức (*) có nghĩa là giá trị của hàm g tại phuơng án bộ phận (a1, a2,

..., ak ) là không vượt quá giá trị nhỏ nhất của hàm mục tiêu của bài toán trên tập con các phương án

D(a1, a2, ..., ak ) = { xD :xi= ai , i = 1, 2, ..., k}

hay nói một cách khác, g(a1, a2, ..., ak ) là cận dưới của giá trị hàm mục tiêu trên tập D(a1, a2,..., ak). Vì lẽ đó, hàm g được gọi là hàm cận dưới , và giá trị g(a1, a2, ..., ak) được gọi là cận dưới của tập D(a1, a2,..., ak). Do có thể đồng nhất tập D(a1, a2,...,ak) với phương án bộ phận (a1, a2,..., ak), nên ta cũng gọi giá trị g(a1, a2, ..., ak) là cận dưới của phương án bộ phận (a1, a2, ..., ak).

Giả sử đã có hàm g. Ta xét cách sử dụng hàm này để giảm bớt khối lượng duyệt trong quá trình duyệt tất cả các phương án theo thuật toán quay lui. Trong quá trình liệt kê các phương án có thể đã thu được một số phương án của bài toán. Gọi x* là phương án với giá trị hàm mục tiêu nhỏ nhất trong số các phương đã tìm được,

kí hiệu f*= f(x*). Ta sẽ gọi x* là phương án tốt nhất hiện có, còn 

là kỷ lục. Giả sử

ta đã có f*. Khi đó nếu

g(a1, a2, ..., ak) > f*

thì từ bất đẳng thức (*) suy ra

f* < g(a1, a2, ..., ak) min {f(x): xD, xi =ai, i= 1,2,..., k },

vì thế tập con các phương án của bài toán D(a1, a2,...,ak) chắc chắn không chứa phương án tối ưu. Trong trường hợp này ta không cần tiếp tục phát triển phương án bộ phận (a1, a2,...,ak), nói cách khác là ta có thể loại bỏ các phương án trong tập D(a1, a2,...,ak) khỏi quá trình tìm kiếm.

Thuật toán quay lui liệt kê phương án cần sửa đổi lại như sau Try(k)

/* Phát triển phương án bộ phận (a1, a2,...,ak) theo thuật toán quay lui có kiểm tra cận dưới trước khi tiếp tục phát triển phương án */

{

for ak Ak do

if (<chấp nhận ak>)

{

xk = ak;

if(k == n)

<cập nhật kỷ lục>; else

if(g((a1, a2,...,ak) f*)

Try(k+1)

}

Khi đó, kỹ thuật nhánh cận được thực hiện như sau: Nhánh_cận()

{

f*= ;

/* Nếu biết một phương án x* nào đó ta có thể đặt f*= f(x*) */ Try(1);

if (f*< )

< f* là giá trị tối ưu, x* là phương án tối ưu > else

< bài toán không có phương án>;

}

Chú ý rằng nếu trong hàm Try ta thay câu lệnh if(k == n)

<cập nhật kỷ lục>; else

if(g((a1, a2,...,ak) f*)

Try(k+1)

bởi :

if(k == n)

<cập nhật kỷ lục>; else

Try(k+1)

thì hàm Try sẽ liệt kê toàn bộ các phương án của bài toán, và ta thu đựơc thuật toán duyệt toàn bộ.Việc xây dựng hàm g phụ thuộc vào từng bài toán tối ưu tổ hợp cụ

thể. Thông thường ta cố gắng xây dựng nó sao cho:

 Việc tính giá trị của g phải đơn giản hơn việc giải bài toán tối ưu tổ hợp ở vế phải cuả (*).

 Giá trị của g( a1, a2,..., ak) phải sát với giá trị của vế phải của (*). Tuy nhiên hai yêu cầu này trong thực tế thường đối lập nhau.

5.2. Các ví dụ áp dụng

5.2.1. Bài toán người du lịch

1) Bài toán

Một người du lịch muốn đi tham quan n thành phố được đánh số là 1, 2, ...,

n. Xuất phát từ một thành phố nào đó người du lịch muốn đi qua tất cả các thành phố còn lại, mỗi thành phố đúng một lần, rồi quay trở lại thành phố xuất phát. Biết cij là chi phí đi từ thành phố i đến thành phố j ( i, j = 1, 2,…, n), hãy tìm hành trình (một cách đi thoả mãn điều kiện đặt ra) với tổng chi phí là nhỏ nhất.

Phân tích bài toán:

Với nội dung như vậy của bài toán rất khó hình dung mô hình của nó, ta sẽ phân tích và đưa về dạng tổng quát. Có hai yếu tố cần phải xác định và chỉ ra: Tập D và hàm mục tiêu F(x).

Ta có thể thiết lập tương ứng 1-1 giữa hành trình

(1) -> (2) ->…-> (n)-> (1)

với một hoán vị  = ((1), (2) ,…, (n)) của n số tự nhiên 1, 2, …, n. Đặt F() = c(1,(2) + ... + c(n-1),(n) + c(n),(1)

và ký hiệu D là tập tất cả các hoán vị  = ((1), (2),…, (n)) của n số tự nhiên 1, 2,

…, n. Khi đó bài toán được đưa về dạng tổng quát như sau:

min { F() :  D }.

2) Thiết kế thuật toán

Bài toán người du lịch dẫn về bài toán: Tìm cực tiểu của hàm:

f(x1, x2, x3,...,xn) = c[x1, x2] + c[ x2, x3] +...+ c[ xn-1 + xn] + c[ xn, x1]

Với điều kiện (x1, x2, x3,...,xn) là hoán vị của các số 1, 2, 3,..., n.

input: ma trận chi phí C = (cij)

output: phương án tối ưu x* và f*=f(x*) Hàm try() có thể phác thảo như sau: Try (i)

{

for (j = 1 -> n)

if( Chấp nhận J )

{

Xác định xi theo j; Ghi nhận trạng thái; if(i == n)

Cập nhật phương án tối ưu;

else

{

}

Xác định cận g(x1 ,..., xi ) ;

if( g(x1 ,..., xi ) ≤ f* ) Try (i+1);

Hoàn trả trạng thái;

}

- Xác định cận g( x1 ,..., xi )

Ký hiệu Cmin = min{c[ i, j ], i, j = 1,2,...,n, i  j } là chi phí đi lại nhỏ nhất giữa các thành phố.

Giả sử ta đang có phương án bộ phận (u1, u2,...,ui). phương án này tương ứng với hành trình bộ phận qua i thành phố:

u1 u2 ... ui-1 ui

Vì vậy, chi phí phải trả theo hành trình bộ phận này sẽ là

= c[u1,u2] + c[u2,u3] + ...+ c[ui-1,ui].

Để phát triển hành trình bộ phận này thành hành trình đầy đủ, ta còn phải đi qua n-k thành phố còn lại rồi quay trở về thành phố u1, tức là còn phải đi qua n-i+1 đoạn đường nữa.

Do chi phí phải trả cho việc đi qua mỗi một trong số n-i+1 đoạn đường còn lại đều không ít hơn cmin nên cận dưới cho phương án bộ phận (u1,u2,..,ui) có thể tính theo công thức

g(u1, u2,..., ui) = + (n-i+1).cmin

- Điều kiện chấp nhận được của j là thành phố j chưa đi qua. Ta dùng một mảng Daxet[] để biểu diễn trang thái này với qui ước:

+ Daxet[j] = 0 : thành phố j chưa được đi qua

+ Daxet[j] = 1: thành phố j đã được đi qua

Mảng Daxet[] được khởi tạo bằng 0 (mọi phần tử bằng 0)

- Xác định xi theo j bằng câu lệnh : xi = j

- Ghi nhận trạng thái : Daxet[j] = 1.

- Cập nhật lại chi phí khi xác định được xi : S = S+ Cxi −1,xi

- Cập nhật lời giải tối ưu :

Tính chi phí hành trình vừa tìm được : Tong = S + Cxn, 1 ;

Nếu (Tong < f*) thì

x* = x;

f* = Tong;

- Hoàn trả trạng thái :

Daxet[j] = 0.

Trả lại chi phí cũ : S = S- Cxi −1,xi

- Ta cố định thành phố xuất phát là thành phố 1.

Các hàm: Init()

/* Hàm tính cmin, Ban đầu tất cả các thành phố đều chưa được đến; Khởi tao giá trị tối ưu, xuất phát từ thành phố 1*/

{

Cmin = maxint;//Chi phi nho nhat giua 2 thanh pho for(i = 1; i <= n; i++)

Daxet[i] = 0; for(i = 1; i <= n; i++)