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

xi = j nghĩa là quân hậu dòng i được xếp vào cột j. Các giá trị đề cử cho xi là từ 1 đến 8. Giá trị j là được chấp nhận nếu ô (i, j) chưa bị quân hậu nào chiếu đến (quân hậu có thể ăn ngang, dọc và hai đường chéo). Để kiểm soát được điều này, ta cần phải ghi nhận trạng thái của bàn cờ trước cũng như sau khi xếp được một quân hậu.

Việc kiểm soát theo chiều ngang là không cần thiết vì mỗi dòng được xếp đúng một quân hậu. Việc kiểm soát chiều dọc được ghi nhận nhờ dãy biến aj với qui ước rằng aj bằng 1 nếu cột j còn trống. Hai đường chéo đi qua ô (i, j) thì một đường chéo gồm những ô có i + j không đổi, còn một đường chéo gồm những ô có i - j không đổi (2 i+j  16, -7 i-j  7).

Từ đó đường chéo thứ nhất được ghi nhận nhờ dãy biến bj (2 j  16) và đường chéo thứ hai nhờ nhờ dãy biến cj (-7 j  7) với qui ước các đường này còn

trống nếu biến tương ứng có giá trị 1.

Các biến trạng thái aj, bj, cj được khởi gán giá trị 1 trong hàm Init(). Như vậy giá trị j được chấp nhận khi và chỉ khi cả 3 biến ai, bi+j, ci-j cùng có giá trị 1. Các biến này phải được gán lại giá trị 0 khi xếp xong quân hậu thứ i và được trả lại giá trị 1 sau khi gọi Result() hay Try(i+1).

Tổ chức dữ liệu:

- Mảng x để lưu trữ cách xếp 8 quân hậu tìm được.

- Mảng c với các phần tử c[j] để ghi nhận trạng thái cột j (c[j]=1 thì cột j chưa có quân hậu nào xếp, c[j]=0 thì cột j đã có quân hậu xếp)

- Mảng ct để ghi nhận trạng thái đường chéo tổng i+j:

+ ct[i+j]=1 thì đường chéo i+j chưa có quân hậu nào chiếu đến

+ ct[i+j]=0 thì đường chéo i+j đã có quân hậu chiếu đến

- Mảng ch để ghi nhận trạng thái đường chéo hiệu i-j: Để chỉ số của mảng chạy từ 1 nên với i-j chạy từ -7 đến 7 ta đặt tương ứng với i-j+8 chạy từ 1 đến 15.

+ ct[i-j+8]=1thì đường chéo i-j chưa có quân hậu nào chiếu đến

+ ct[i-j+8]=0 thì đường chéo i-j đã có quân hậu chiếu đến

Các hàm:

init() //Hàm khởi tạo

{

for(i=1;i<=8;i++) c[i]=1;

for(i=2;i<=2*8;i++) ct[i]=1;

for(i=1;i<=2*8-1;i++) ch[i]=1;

}

try(i) // Xếp quân hậu hàng i;

{

for(j=1;j<=8;j++) if(c[j]&&ct[i+j]&&ch[i-j+8])

{

x[i]=j;

c[j]=0;

ct[i+j]=0; ch[i-j+8]=0; if(i==8)

ht(); // Hàm đưa ra cách xếp vừa tìm được else try(i+1);

c[j]=1;

ct[i+j]=1; ch[i-j+8]=1;

}

main()

{

init();

try(1);

}

4.2.5. Tìm đường đi trên đồ thị

1) Bài toán

G = (V, E) là đơn đồ thị (có hướng hoặc vô hướng). V = {1,. ., n} là tập các đỉnh, E là tập cạnh (cung). Với s, t  V, tìm tất cả các đường đi từ s đến t.

Các thuật toán tìm kiếm cơ bản :

Thuật toán DFS : Tìm kiếm theo chiều sâu. Thuật toán BFS : Tìm kiếm theo chiều rộng.

2) ThiÒt kÒ thuËt to¸n

* Thuật toán DFS tiến hành tìm kiếm trong đồ thị theo chiều sâu. Thuật toán thực hiện việc thăm tất cả các đỉnh có thể đạt được cho tới đỉnh t từ đỉnh s cho trước. Đỉnh được thăm càng muộn sẽ càng sớm được duyệt xong (cơ chế LIFO –Vào sau ra trước). Nên thuật toán có thể tổ chức bằng một thủ tục đệ quy quay lui.

Input: G = (V,E), s, t

Output: Tất cả các đường đi từ s đến t (nếu có). DFS (s)

{

for ( u = 1; u <= n; u++)

{

if (chấp nhận được)

{

Ghi nhận nó; if (u  t)

DFS(u);

else

In đường đi; bỏ việc ghi nhận;

}

Ta cần mô tả dữ liệu đồ thị và các mệnh đề được phát biểu trong mô hình. Ðồ thị sẽ được biểu diễn bằng ma trận kề : a =(aij) 1<=i, j<=n và:

aij = 1 nếu (i, j )  E

aij = 0 nếu (i, j )  E

Ghi nhận đỉnh được thăm để tránh trùng lặp khi quay lui bằng cách đánh dấu.

Ta sữ dụng một mảng một chiều Daxet[] với qui ước :

Daxet[u] = 1 , u đã được thăm. Daxet[u] = 0 , u chưa được thăm.

Mảng Daxet[] lúc đầu khởi t?o bằng 0 tất cả.

Điều kiện chấp nhận được cho đỉnh u chính là u kề với v (avu = 1) và u chưa được thăm ( Daxet[u] = 0).

Để ghi nhận các đỉnh trong đường đi, ta dùng một mảng một chiều Truoc[ ], với qui ước :

Truoc[u] = v với v là đỉnh đứng trước đỉnh u, và u kề với v Ta khởi tạo mảng Truoc[ ] bằng 0 tất cả.

Thuật toán đượcc làm mịn hơn : Input G = (aij)nxn , s, t

Output Tất cả các đường đi từ s đến t (nếu có).

DFS(s)

{

daxet[s] = 1;

for( u = 1;u <= n; u++)

{

if( a[s][u] && !daxet[u])

{

Truoc[u] = s; if ( u == t )

duongdi();

else

DFS(u);

daxet[u] = 0;

}

Mảng truoc[ ] lưu trử các đỉnh trên đường đi. Nếu kết thúc thuật toán, Daxet[t] = 0 ( Truoc[t] = 0 ) thì không có đường đi từ s đến t.

Trong trường hợp tồn tại đường đi, xuất đường đi chính là xuất mảng Truoc[].

Thao tác này có thể viết như sau duongdi()

{

printf(t,"<--"); j = t;

while (truoc[j] != s)

{

printf(truoc[j],"<--"); j = truoc[j];

}

printf(s);

}

* Thuật toán BFS tiến hành tìm kiếm trên đồ thị theo chiều rộng. Thuật toán thực hiện việc thăm tất cả các đỉnh có thể đạt được cho tới đỉnh t từ đỉnh s cho trước theo từng mức kề. Đỉnh được thăm càng sớm thì sẽ càng sớm được duyệt xong (cơ chế FIFO – Vào trước ra trước).

Input G = (V,E),

s, t V;

Output

Đường đi từ s đến t.

Mô tả :

Bước 0 : A0 = {s}.

Bước 1 : A1 = {x V A0 : ( s, x) E}.

Bước 2 : A2 = {x ? V {A0?A1} : ?y  A1 , ( y, x)  E}.

....



i1

Bước i : Ai = {xV/ Ak : yAi-1, (y,x)E} .

k 0

…

Thuật toán có không quá n bước lặp, một trong hai trường hợp sau xảy ra :

- Nếu với mọi i, t  Ai : không có đường đi từ s đến t;

- Ngược lại, tAm với m nào đó. Khi đó tồn tại đường đi từ s tới t, và đó là một đường đi ngắn nhất từ s đến t.

Trong trường hợp này, ta xác định được các đỉnh trên đường đi bằng cách quay

ngược lại từ t đến các đỉnh trước t trong từng các tập trước cho đến khi gặp s.

Trong thuật toán BFS, đỉnh được thăm càng sớm sẽ càng sớm trở thành duyệt xong, nên các đỉnh được thăm sẽ được lưu tr? trong hàng đợi queue. Một đỉnh sẽ trở thành duyệt xong ngay sau khi ta xét xong tất cả các đỉnh kề của nó .

Ta dùng một mảng Daxet[] để đánh dấu các đỉnh được thăm, Daxet[i]=0 là đỉnh i chưa được thăm, Daxet[i]= là đỉnh i đã được thăm. Mảng này được khởi động bằng 0 tất cả để chỉ rằng lúc đầu chưa đỉnh nào được thăm.

Một mảng truoc[ ] để lưu trữ các đỉnh nằm trên đường đi ngắn nhất cần tìm (nếu có), với ý nghĩa Truoc[i] là đỉnh đứng trước đỉnh i trong đường đi. Mảng Truoc[ ] được khởi tạo bằng 0 tất cả để chỉ rằng lúc đầu chưa có đỉnh nào.

Đồ thị sẽ được biểu diễn bằng ma trận kề : a =(aij) 1<=i, j<=n và: aij = 1 nếu (i, j ) E

aij = 0 nếu (i, j ) E

Queue được tổ chức bằng mảng. Thuật toán được viết mịn hơn như sau : BFS(s)

{

dauQ = 1, cuoiQ = 1; queue[cuoiQ] = s; Daxet[s] = 1;

while ( dauQ <= cuoiQ)

{

u = queue[dauQ]; dauQ++;

for ( j = 1; j <= n; j++)

if( a[u][j] == 1 && !Daxet[j] )

{

Nhận xét :

cuoiQ++; queue[cuoiQ] = j; Daxet[j] = 1; Truoc[j] = u;

}

Ta có thể thấy mỗi lần gọi DFS(s), BFS(s) thì mọi đỉnh thuộc cùng một thành phần liên thông với s sẽ được thăm, nên sau khi thực hiện hàm trên thì :

• Truoc[t] = 0 : không tồn tại đường đi từ s đến t,

• Ngược lại, có đường đi từ s đến t. Khi đó lời giải được cho bởi : t ← p1 = Truoc[t] ← p2 = Truoc[p1] ← … ← s .

4.2.6. Bài toán ngựa đi tuần

1) Bài toán

Cho bàn cờ có n x n ô. Một con ngựa được phép đi theo luật cờ vua, đầu tiên được đặt x0 , y0. Một hành trình của ngựa là đi qua tất cả các ô của bàn cờ, mỗi ô đi qua đúng một lần. Hãy đưa ra các hành trình (nếu có) của ngựa.

2) ThiÒt kÒ thuËt to¸n

Cách giải quyết rò ràng là xét xem có thể thực hiện một nước đi kế nữa hay không. Sơ đồ đầu tiên có thể phát thảo như sau :

Try(i)

{

for ( j = 1 -> k)

if ( xi chấp nhận được khả năng j)

{

Xác định xi theo khả năng j; Ghi nhận trạng thái;

if( i < n2 )

Try(i+1); else

Ghi nhận nghiệm; Hoàn trả trạng thái ;

}

Để mô tả chi tiết thuật toán, ta phải qui định cách mô tả dữ liệu và các thao tác, đó là :

- Biểu diễn bàn cờ .

- Các khả năng chọn lựa cho xi

- Cách thức xác định xi theo j.

- Cách thức gi nhận trạng thái mới, trả về trạng thái cũ.

- Ghi nhận nghiệm.

* Ta sẽ biểu diễn bàn cờ bằng 1 ma trận vuông cấp n: h[n][n] mà h[i][j] tương ứng với ô ở hàng i cột j (1 ≤ i, j ≤ n) và dùng các phần tử của ma trận để ghi nhận quá trình di chuyển của con ngựa với qui ước như sau:

h[x][y] = 0: Ô <x,y> ngựa chưa đi qua;

h[x][y] = i : Ô <x,y> ngựa đã đi qua ở bước thứ i (1  i  n2 ).

* Các khả năng lựa chọn cho xi? Đó chính là các nước đi của ngựa mà xi có thể chấp nhận được.

Với ô bắt đầu <x,y> như trong hình vẽ, có tất cả 8 ô <u,v> mà con ngựa có thể đi đến. Giả sử chúng được đánh số từ 0 đến 7 như hình sau :

( ô có dấu * là ô ở hàng x cột y nơi ngựa đang đứng)