Sưu tầm bởi:

www.daihoc.com.vnThiết kế và đánh giá thuật toán - 65 - Đường đi ngắn nhất tìm được là 4
← 6 ← 5 ← 1 , có chiều dài là 3.
ợc biểu diễn bằng ma trận kề a= (a
uv
)
nxn

∈
=
;),(;1 Evu
a

mảng . Thuật toán được cài đặt như sau :
queue[cuoiQ] = s;
axet[s] = 1;
for ( j = 1; j <= n; j++)
if( a[u][j] == 1 && !Daxet[j] )

⎨
⎧
BFS(s)
≡
int u, j, dauQ = 1, cuoiQ = 1;

D
while ( dauQ <= cuoiQ)
{
u = queue[dauQ];
dauQ++; {
cuoiQ++;
2
5
3 4
Trần Tuấn Minh Khoa Toán-Tin
Simpo PDF Merge and Split Unregistered Version - http://www.simpopdf.com
Sưu tầm bởi:

www.daihoc.com.vnThiết kế và đánh giá thuật toán - 66 - queue[cuoiQ] = j;
Daxet[j] = 1;

:
c số đôi một khác nhau.
. L ät a a.

Bài
Cho dãy a = (a
, a
1 2
, . . ., an ) gồm cá
1. Liệt kê tất cả các hoán vò của dãy n phần tử của a.
2 kê tất cả các tổ hợp chặp k trong tập gồm n phần tử củie
3
:
Giả sử ổ khóa có n công tắc. Mỗi công tắc có một trong 2 trạng thái “đóng”
hay “mở”. Khóa mở được nếu có ít nhất [n/2] công tắc có trạng thái mở.
Liệt kê tất cả các cách mở khóa.

Bài 4
( Ngựa đi tuần ).
Cho bàn cờ n x n ô. Một con ngựa được phép đi theo luật cờ vua.
Tìm hành trình của ngựa, bắt đầu từ ô <x
0
, y
0
> đi qua tất cả các ô của bàn
cờ, mỗi ô đúng một lần.
Liệt kê tất cả các hành trình.

Bài 5
:

( Ngựa đi tuần ).
Cho bàn cờ n x n ô. Một con ngựa được phép đi theo luật cờ tướng.
Tìm hành trình của ngựa, bắt đầu từ ô <x
0
, y
0
> đi qua tất cả các ô của bàn
cờ, mỗi ô đúng một lần.
Liệt kê tất cả các hành trình.

Bài 7
:
Một người du lòch muốn tham quan n thành phố T
1
, T
2
, . ., Tn . 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
á T
j
thỏa yêu cầu bài toán (nếu
có) sao cho có chi phí ít nhất.

ài 8
thành phố đi qua đúng một lần rồi quay trở lại thành phố xuất phát.
Gọi C
ij
là chi phí đi từ thành phố Ti đến thành phố T
j
.

1. Xác đònh số thành phần liên thông của G
2. Xuất các đỉnh nằm trong trong mỗi thành phần liên thông.

Bài 10
:
mo mảnh đất hình vuông, ta chia thành n x n ô, mỗi ô ta ghi một số là
0 hoặc
Trên ät
1. Ô mang số 0 ta đào ao, mang số 1 ta trồng cỏ. Hai ô trồng cỏ có cạnh liền
nhau được xem là cùng nằm trong bồn cỏ. Hãy xác đònh diện tích của bồn cỏ lớn
nhất ( theo nghóa có số ô nhiều nhất ).

Trần Tuấn Minh Khoa Toán-Tin
Simpo PDF Merge and Split Unregistered Version - http://www.simpopdf.com
Sưu tầm bởi:

www.daihoc.com.vnThiết kế và đánh giá thuật toán - 68 - Bài 11 :
Cho 3 ký tự A, B, C và n là một số nguyên dương.
. Liệt ỗi tạo ra từ 3 ký tự trên, với chiều dài n.
ø 3 ký tự trên, với chiều dài n, thỏa điều kiện
ên tiếp nào giống nhau.
á ký tự B là ít nhất.
1 kê tất cả các chu
2. Liệt kê tất cả các chuỗi tạo ra tư

n
,1,;:)
1

Bài 13
:
Cho n xâu ký tự khác rổng a
1
, a
2
, . .,an , và một xâu ký tự S. Tìm cách biểu
âu ai có thể không xuất hiện
nhiều lần.
Liệt kê tất cả

ài 14
diễn S qua các xâu ai, dưới dạng ghép xâu, mỗi xa
trong S, hoặc xuất hiện trong S
cách cách biểu diễn.
B
:
Bài 15
Có n đồ vật, mỗi v
ật i đặc trưng bởi trọng lượng Wi và giá trò sử dụng Vi,
với mọi i
∈ {1, ,n}.
Cần chọn các vật này đặt vào một chiếc túi xách có giới hạn trọng lượng m,
sao cho tổng giá trò sử dụng các vật được chọn là lớn nhất.

:

thuật. Cho nên ta cần phải cải tiến thuật toán
cải tiến, trong đó
của phương pháp quay lui, dùng để
như sau :
ng án mẫu ( có thể xem là lời
ù giá nhỏ nhất tại thời điểm đó ). Đánh giá nhánh
a
xây dựng có thể tốt hơn phương án mẫu
ọn ớng khác.
chọn phương án tối ưu
k gian các lời giải là quá lớn,
đ ûo ời gian cũng như kỹ ảm ba về th
quay lui để hạn chế bớt việc duyệt các phương án. Có nhiều cách
có phương pháp nhánh cận.
Phương pháp nhánh cận là một cải tiến
tìm lời giải tối ưu của bài toán. Ý tưởng chính của nó
Trong quá trình duyệt ta luôn giữ lại một phươ
giải tối ưu cục bộ – chẳng hạn co
cận là phương pháp tính giá của phương ùn ngay trong quá trình xây dựng các
thành phần của phương án theo hướng đang
hay không. Nếu không ta lựa ch theo hư
2. Mô hình
Giả sử ài toá
Tìm Min{f(x) : x
∈ D};
=1
i
b n tối ưu cho là :
Với X =
()

i
A
1
Nghiệm của bài toán nếu có sẽ được biểu diễn dưới dạng
Trong o
thành phần của nghiệm.
Một bộ phận i thành phần (x
1
, , x
i
) sẽ gọi là một lời giải (phương án) b
phận cấp i. Ta gọi X
i
là tập các lời giải bộ phận cấp i,
ni ,1=∀
.
Đánh giá cận là tìm một hàm g xác đònh trên các X
i
sao cho :
},1,,),,(:)({),,(
11
iiaxXaaaafMinxxg =∀=∈=≤ LL hơn giá trò của
các phương án mở rộng từ lời giải bộ phận
au khi tìm được hàm đánh giá cận g, ta dùng g để giảm bớt chi phí duyệt
các phương án theo phương pháp quay lui.
hương án mẫu), còn f* là giá trò tốt
nha

Thiết kế và đánh giá thuật toán - 70 - Nên chắc rằng các lời giải mở rộng từ sẽ không tốt hơn phương
án mẫu iển lời giải bộ phận
để tìm
lời giải øi to .
ại thành thủ tục nhánh cận như sau :
Ghi nhận trạng thái mới;
(i == n)
hật lời giải tối ưu ;
se
;
kiếm theo chiều sâu trên cây
ù một điều là khi tìm được x
i

ta cắt bỏ các nhánh con từ x
i
đi xuống, mà
ùnh giá cận như thế nào ?
),,(
1 i
xx L
, do đó có thể bỏ đi không cần phát tr
),,(
1 i

),,( xxg > f* thì
1 i
L
quay lên ngay cha của nó là x
i-1
.
đa Vấn đề là xác đònh hàm
I øi d hI. Ba toán ngøi u lòc
1. Bài toán
Một ngøi du lòch muốn tham quan n thành phố T
1
, , T
n
. Xuất phát từ một
ành ố nào đó, n ua tất cả các thành phố còn lại, mỗi
ïi thành phố xuất phát.
í đi từ thành phố T
i
đến T
j
. Hãy tìm một hành trình thỏa yêu
sao cho chi phí là nhỏ nhất.
2. Ý tưởng
th ph gười du lòch muốn đi q
thành phố đi qua đúng 1 lần rối quay trở la
Gọi C
ij
là chi ph
cầu bài toán


, , a
n
) : (a
2
, , a
n
) là hoán vò của {2, ,n}}.
ới V
1,,,11
1322
),,(
nnn
aaaaaan
CCCCaaf
+
+
+
+
=
−
LL

Cách giải bài toán sẽ kết hợp đánh giá nhánh cận trong quá trình liệt kê
hương án của thuật toán quay lui.
3. Thiết kế
p

put C = (C
ij
)

ij
: i, j ∈ {1, ,n}
øo bước i ta tìm được lời giả bộ phận cấp i là (x
1
, ,x
i
), tức là đã đi
g T
1
→ T
2
→ . . . →T
i
, tương ứng với chi phí :
S
i
=
hành trình bộ phận này thành một hành trình đầy đủ, ta còn
hải đi nữa, gồm n-i thành phố còn lại và đoạn quay lại T
1
.
-i+1 đoạn còn lại không nhỏ hơn CMin, nên hàm
đònh như sau :
In
O

T {

Do chi phí mỗi một trong n
đánh giá cận có thể xác

CMinSxxg
ii
)1(),,(
1
in
+
−+=L
hành phố T
j
chưa đi qua.
ãn trạng thài này
đưđã

i
• Điều kiện chấp nhận được của j là t
Ta dùng một mảng logic Daxet[] để biểu die

⎪
⎨
=
T
jDaxet
;0
][
⎪
⎧
quiợc

vừa tìm được :

for (j = 2
→ n)
{
x[i] = j;
Daxet[j] = 1;
//Cap nhat toi uu
ong = S + C[x[n]][x[1]];
< f*)
* = Tong;
}
else
{
S + (n-i+1)*Cmin; //Danh gia can
if ( g < f*)
Try(i+1);
Min
⎢
⎢
⎡
∞
∞
∞
∞
=
12726
4169
202243
1518143

{
T
if(Tong
{
Lgtu = x;
f

}

g =
}
S = S - C[x[i-1]][x[i]];
Daxet[j] = 0;
}
h họa :
Ma trận chi phí :
⎢
⎢
17
⎥
⎥
⎢
⎢
⎣
∞
511159
⎥
⎥
⎥
⎥

(1,2)
3; g = 11
(1,3)
S=14; g=22
(1,4)
S=18; g = 26
(1,5)
S=15;g=23 S=
(1,2,3) (1,2,5)
S=23; g = 29
(1,2,4)
g
≥ f* (=22) :

4. Cài đặt

f* = 35 + 9 = 44
Hành trình TU mới
1→2→3→4→5

Hành t
1→2→3→5→4

Trần Tuấn Minh Khoa Toán-Tin
Simpo PDF Merge and Split Unregistered Version - http://www.simpopdf.com
Sưu tầm bởi:

www.daihoc.com.vnThiết kế và đánh giá thuật toán - 74 - if(Tong < Gttu)
{ } {

if < Gttu) ][x[i]];

int i, j;
Cmin = VC;//Chi phi nho nhat giua
for(i = 1; i <= n; i++)
for(i = 1; i <= n; i++

if

C;//Gia tri to Gttu = V
S = 0;
[1] = x 1; // Xuat phat tu di 1
}
I à n cái túi hII. B i toá
1. Bài toán
Có n loại đồ vật, mỗi loại có số lượng không hạn chế. Đồ vật loại i, đặc
i, với mọi i
∈ {1, ,n}.
hiếc túi xách có giới hạn trọng lượng m,
trưng bởi trọng lượng Wi và giá trò sử dụng V
Cần chọn các vật này đặt vào một c
sao cho tổng giá trò sử dụng các vật được chọn là lớn nhất.
2. Ý tưởng
Đặt :
⎨
⎧
==
uD
⎭
⎬
≤∈
∑

n
uuf ),,() La
; Duu
n
∈
),,(
1
L
n
uu
1
,,( L
=
i
iin
vu
1
1
Bài toán chiếc túi xách chuyển về bài toán sau :
) =
{
}
Duuf
∈
:)(

Tìm x*
∈ D : f* = f(x*
Cho nên ta sẽ kết hợp đánh giá nhánh cận trong quá trình liệt kê các lời giải
pháp quay lui.


T
fo
t⎟
⎟
⎠
⎞
⎜
⎜
⎝
⎛
=
n
n
w
v
w
v
Dg ,,
1
1
L

Ta chọn vật theo đơn giá giảm dần.
Không mất tính tỏng quát, ta giả sử các loại vật cho theo thứ tự giảm dần
của đơn giá.
• Đánh giá cận trên :

=
i
j
jj
wx
1
∑
=
i
j
jj
wx
1
.
Trần Tuấn Minh Khoa Toán-Tin
Simpo PDF Merge and Split Unregistered Version - http://www.simpopdf.com
Sưu tầm bởi:

www.daihoc.com.vnThiết kế và đánh giá thuật toán - 76 - {
}
⎟
⎟
⎠
⎞

11
1
*:
:
,1,;),,(:)(
i
i
ii
n
ij
jj
n
ij
jj
i
n
ij
jj
n
ij
jj
jjn
w
m
vSmwuvuMaxS
mwuvuSMax
ijxuDuuuufMax L

Do đó, cận trên cho các lời giải bộ phận cấp i có thể xác đònh bởi :
()

⎞
⎜
⎜
⎝
⎛
+1i
i
w
m• Thao tác ghi nhận trạng thái mới khi xác đònh được x
i
chẳng qua là cập nhật
lại giá trò thu được và giới hạn trọng lượng mới của chiếc túi :
S = S + x
i
v
i
T = = T + x
i
w
i
.
• Vì vậy, thao tác trả lại trạng thái cũ cho bài toán :
S = S – x
i
v
i
T

tput x* = (x
1
, , x
n
) : x
i
∈ N,∀i;
=
w
Ou
f* = f(x*)=
⎭
⎬
⎫
⎩
⎨
⎧
∈∀∈≤
∑∑
==
niNumwuvuMax
i
n
i
ii
n
i
ii
,1,,:
11

www.daihoc.com.vnThiết kế và đánh giá thuật toán - 77 - if(i==n) //Cap nhat toi uu
= x;
f* = S;

; //Danh gia can
( g > f*)
+1);
L = TL – w
i
*x
i
;
S = S - v
i
*x
i
;

2 3 4
5 3 2 4
10 5 3 6
{
if(S > f*)
{

www.daihoc.com.vnThiết kế và đánh giá thuật toán - 78 -
4. Cài đặt
void Try(int i)
{
int j, t, g;
t = (int)((m-Tl)/w[i]);
for (j = t; j >=0 ; j )
{
x[i] = j;
Tl = Tl + w[i]*x[i]; //Trong luong thu duoc
S = S + v[i]*x[i]; //Gia tri thu duoc
if(i==n) //Cap nhat toi uu
{
Gốc
f* = 0
(1) (0)
x
S = 10;
TL = 5;
g = 15;
S = 0 ;
TL = 0 ;
g = 10;


x
4
=0
Cắt 2 nhánh này vì :
g < f*
Lời giải tối ưu :
x* = (1,1,0,0)
f* = 15
Trần Tuấn Minh Khoa Toán-Tin
Simpo PDF Merge and Split Unregistered Version - http://www.simpopdf.com
Sưu tầm bởi:

www.daihoc.com.vnThiết kế và đánh giá thuật toán - 79 - if(S > Gttu)
{
Gan();
Gttu = S;
}
}
Try(i+1); x[i] = 0;
}


vật i đặc trưng bởi trọng lượng w
i
và giá trò sử dụng v
i
, với
các vật này đặt vào một chiếc túi xách có giới hạn trọng lượng m,
ò sử dụng các vật được chọn là lớn nhất.
mọi i
∈ {1, ,n}.
Cần chọn
sao cho tổng giá tr

Bài 2
:
Cho 3 ký tự A, B, C và n là một số nguyên dương.
ra từ 3 ký tự trên, với chiều dài n, thỏa điều kiện
u và sao cho số ký tự B là ít nhất.
Xác đònh chuỗi thỏa tạo
không có 2 chuỗi con liên tiếp nào giống nhaTrần Tuấn Minh Khoa Toán-Tin
Simpo PDF Merge and Split Unregistered Version - http://www.simpopdf.com
Sưu tầm bởi:

www.daihoc.com.vnThiết kế và đánh giá thuật toán - 80 -