Tải miễn phí ðề thi, eBook, Tài liệu học tập

67

CHƯƠNG V
MỘT SỐ BÀI TOÁN TỐI ƯU TRÊN ðỒ THỊ

5.1. ðỒ THỊ CÓ TRỌNG SỐ VÀ BÀI TOÁN ðƯỜNG ðI NGẮN NHẤT.
5.1.1. Mở ñầu:

Trong ñời sống, chúng ta thường gặp những tình huống như sau: ñể ñi từ ñịa
ñiểm A ñến ñịa ñiểm B trong thành phố, có nhiều ñường ñi, nhiều cách ñi; có lúc ta
chọn ñường ñi ngắn nhất (theo nghĩa cự ly), có lúc lại cần chọn ñường ñi nhanh nhất
(theo nghĩa thời gian) và có lúc phải cân nhắc ñể chọn ñường ñi rẻ tiền nhất (theo nghĩa
chi phí), v.v
Có thể coi sơ ñồ của ñường ñi từ A ñến B trong thành phố là một ñồ thị, với ñỉnh
là các giao lộ (A và B coi như giao lộ), cạnh là ñoạn ñường nối hai giao lộ. Trên mỗi
cạnh của ñồ thị này, ta gán một số dương, ứng với chiều dài của ñoạn ñường, thời gian
ñi ñoạn ñường hoặc cước phí vận chuyển trên ñoạn ñường ñó,
ðồ thị có trọng số là ñồ thị G=(V,E) mà mỗi cạnh (hoặc cung) e∈E ñược gán bởi
một số thực m(e), gọi là trọng số của cạnh (hoặc cung) e.
Trong phần này, trọng số của mỗi cạnh ñược xét là một số dương và còn gọi là
chiều dài của cạnh ñó. Mỗi ñường ñi từ ñỉnh u ñến ñỉnh v, có chiều dài là m(u,v), bằng
tổng chiều dài các cạnh mà nó ñi qua. Khoảng cách d(u,v) giữa hai ñỉnh u và v là chiều
dài ñường ñi ngắn nhất (theo nghĩa m(u,v) nhỏ nhất) trong các ñường ñi từ u ñến v.
Có thể xem một ñồ thị G bất kỳ là một ñồ thị có trọng số mà mọi cạnh ñều có
chiều dài 1. Khi ñó, khoảng cách d(u,v) giữa hai ñỉnh u và v là chiều dài của ñường ñi từ
u ñến v ngắn nhất, tức là ñường ñi qua ít cạnh nhất.
5.1.2. Bài toán tìm ñường ñi ngắn nhất:

Cho ñơn ñồ thị liên thông, có trọng số G=(V,E). Tìm khoảng cách d(u

1
. Ta có:
d(u
0,
u
1
) = k
1
.
Tải miễn phí ðề thi, eBook, Tài liệu học tập

68

Trong các ñỉnh v ≠ u
0
và v ≠ u
1
, tìm ñỉnh có khoảng cách k
2
ñến u
0
là nhỏ nhất. ðỉnh
này phải là một trong các ñỉnh kề với u
0
hoặc với u
1
. Giả sử ñó là u
2
. Ta có:
d(u

,u
n
).
5.1.3. Thuật toán Dijkstra:

procedure Dijkstra (G=(V,E) là ñơn ñồ thị liên thông, có trọng số với trọng số dương)
{G có các ñỉnh a=u
0
, u
1
, , u
n
=z và trọng số m(u
i
,u
j
), với m(u
i
,u
j
) =
∞ nếu (u
i
,u
j
) không là một cạnh trong G}
for i := 1 to n
L(u
i
) := ∞

e

d

g

m

c

h

k

1

3

3
2

1

4

2

4

2

5.1.4. ðịnh lý:
Thuật toán Dijkstra tìm ñược ñường ñi ngắn nhất từ một ñỉnh cho trước
ñến một ñỉnh tuỳ ý trong ñơn ñồ thị vô hướng liên thông có trọng số.


∞

−

3

3

2

1

∞

∞

∞

∞

∞

−

−

5

2


∞

−

−

−

−

4

6

3

∞

∞

∞

−

−

−

−


∞

−

−

−

−

−

−

−

9

6

8

−

−

−

−


8

Tải miễn phí ðề thi, eBook, Tài liệu học tập

70

trước khi vào vòng lặp thứ k+1, các ñỉnh không thuộc S ñã ñược gán nhãn bằng ñộ dài
của ñường ñi ngắn nhất từ a. ðỉnh v cũng vậy phải ñược gán nhãn bằng ñộ dài của
ñường ñi ngắn nhất từ a. Nếu ñiều này không xảy ra thì ở cuối bước lặp thứ k sẽ có
ñường ñi với ñộ dài nhỏ hơn L
k
(v) chứa cả ñỉnh thuộc S (vì L
k
(v) là ñộ dài của ñường ñi
ngắn nhất từ a tới v chứa chỉ các ñỉnh không thuộc S sau bước lặp thứ k). Gọi u là ñỉnh
ñầu tiên của ñường ñi này thuộc S. ðó là ñường ñi với ñộ dài nhỏ hơn L
k
(v) từ a tới u
chứa chỉ các ñỉnh không thuộc S. ðiều này trái với cách chọn v. Do ñó (i) vẫn còn ñúng
ở cuối bước lặp k+1.
Gọi u là ñỉnh thuộc S sau bước k+1. ðường ñi ngắn nhất từ a tới u chứa chỉ các
ñỉnh không thuộc S sẽ hoặc là chứa v hoặc là không. Nếu nó không chứa v thì theo giả
thiết quy nạp ñộ dài của nó là L
k
(v). Nếu nó chứa v thì nó sẽ tạo thành ñường ñi từ a tới
v với ñộ dài có thể ngắn nhất và chứa chỉ các ñỉnh không thuộc S khác v, kết thúc bằng
cạnh từ v tới u. Khi ñó ñộ dài của nó sẽ là L
k
(v)+m(v,u). ðiều ñó chứng tỏ (ii) là ñúng vì

n
} và có ma trận trọng số là W ≡ W
0
. Thuật toán Floyd xây
dựng dãy các ma trận vuông cấp n là W
k
(0 ≤ k ≤ n) như sau:

procedure Xác ñịnh W
n

for i := 1 to n
for j := 1 to n
W[i,j] := m(v
i
,v
j
) {W[i,j] là phần tử dòng i cột j của ma trận W
0
}
for k := 1 to n
if W[i,k] +W[k,j] < W[i,j] then W[i,j] := W[i,k] +W[k,j]
{W[i,j] là phần tử dòng i cột j của ma trận W
k
}

5.1.7. ðịnh lý:
Thuật toán Floyd cho ta ma trận W*=W
n
là ma trận khoảng cách nhỏ

trong {v
1
, v
2
, , v
k
}, có một ñường ñi γ sao cho v
k
∉ γ. Khi ñó γ cũng là ñường ñi ngắn
nhất nối v
i
với v
j
ñi qua các ñỉnh trung gian trong {v
1
, v
2
, , v
k-1
}, nên theo giả thiết quy
nạp,
W
k-1
[i,j] = chiều dài γ ≤ W
k-1
[i,k]+W
k-1
[k,j].
Do ñó theo ñịnh nghĩa của W
k

k
v
j
cũng là những ñường ñi ngắn nhất ñi qua các ñỉnh trung gian trong
{v
1
, v
2
, , v
k-1
} và
W
k-1
[i,k]+W
k-1
[k,j] = chiều dài(v
1
v
k
) + chiều dài(v
k
v
j
)
= chiều dài γ < W
k-1
[i,j].
Do ñó theo ñịnh nghĩa của W
k
thì ta có:









1
22
4
3
14
27

v
1

v
2

v
3

v
4


=




















1
4292
4
3
14
27
, W
2
=

=




















8251
5104292
11584
3
714
1482117
, W
4
=

=




















726414
594282
1059747
3
615393
1272969
, W* = W
6
=

trận W cần ñặt bằng 0.
ðồ thị có hướng G là liên thông mạnh khi và chỉ khi mọi phần tử nằm trên ñường
chéo trong ma trận trọng số ngắn nhất W* ñều hữu hạn.
5.2. BÀI TOÁN LUỒNG CỰC ðẠI.
5.2.1. Luồng vận tải:
5.2.1.1. ðịnh nghĩa:
Mạng vận tải là một ñồ thị có hướng, không có khuyên và có
trọng số G=(V,E) với V={v
0
, v
1
, , v
n
} thoả mãn:
1) Mỗi cung e ∈ E có trọng số m(e) là một số nguyên không âm và ñược gọi là khả năng
thông qua của cung e.
2) Có một và chỉ một ñỉnh v
0
không có cung ñi vào, tức là deg
t
(v
0
)=0. ðỉnh v
0
ñược gọi
là lối vào hay ñỉnh phát của mạng.
3) Có một và chỉ một ñỉnh v
n
không có cung ñi ra, tức là deg
o

ve
e
ϕ
, ∀v ∈V, v≠v
0
, v≠v
n
. Ở ñây,
−
Γ
(v)={e∈E | e có ñỉnh cuối là v},
+
Γ
(v)={e∈E | e có ñỉnh ñầu là v}.
3) ϕ(e) ≤ m(e), ∀e ∈ E.
Ta xem ϕ(e) như là lượng hàng chuyển trên cung e=(u,v) từ ñỉnh u ñến ñỉnh v và
không vượt quá khả năng thông qua của cung này. Ngoài ra, từ ñiều kiện 2) ta thấy rằng
nếu v không phải là lối vào v
0
hay lối ra v
n
, thì lượng hàng chuyển tới v bằng lượng
hàng chuyển khỏi v.
Từ quan hệ 2) suy ra:
4)
∑
+
Γ∈
)(
0

n
v
ϕ
ñạt giá trị
lớn nhất, tức là tìm giá trị lớn nhất của luồng.
5.2.1.3. ðịnh nghĩa:
Cho mạng vận tải G=(V,E) và A ⊂ V. Ký hiệu
−
Γ
(A)={(u,v)∈E | v∈A, u∉A},
+
Γ
(A)={(u,v)∈E | u∈A, v∉A}.
ðối với tập cung M tuỳ ý, ñại lượng ϕ(M)=
∑
∈Me
e)(
ϕ
ñược gọi là luồng của tập
cung M.
Từ ñiều kiện 2) dễ dàng suy ra hệ quả sau.
5.2.1.4. Hệ quả:
Cho ϕ là luồng của mạng vận tải G=(V,E) và A ⊂ V \{v
0
,v
n
}. Khi ñó:
ϕ(
−
Γ

)(
Ae
em
ñược gọi là khả năng thông qua của thiết diện
−
Γ
(A).
Tải miễn phí ðề thi, eBook, Tài liệu học tập

74

Từ ñịnh nghĩa thiết diện và khả năng thông qua của nó ta nhận thấy rằng: mỗi
ñơn vị hàng hoá ñược chuyển từ v
0
ñến v
n
ít nhất cũng phải một lần qua một cung nào
ñó của thiết diện
−
Γ
(A). Vì vậy, dù luồng ϕ và thiết diện
−
Γ
(A) như thế nào ñi nữa
cũng vẫn thoả mãn quan hệ:
ϕ
n
≤ m(
−
Γ

,1)(
)('
αϕ
αϕ
ϕ
ekhie
ekhie
e

Khi ñó ϕ’ cũng là một luồng, mà giá trị của nó là:
ϕ’
n
= ϕ
n
+1 > ϕ
n
.
Như vậy, ñối với mỗi luồng không ñầy ta có thể nâng giá trị của nó và nâng cho
tới khi nhận ñược một luồng ñầy.
Tuy vậy, thực tế cho thấy rằng có thể có một luồng ñầy, nhưng vẫn chưa ñạt tới
giá trị cực ñại. Bởi vậy, cần phải dùng thuật toán Ford-Fulkerson ñể tìm giá trị cực ñại
của luồng.
5.2.2.3. Thuật toán Ford-Fulkerson:

ðể tìm luồng cực ñại của mạng vận tải G, ta xuất phát từ luồng tuỳ ý ϕ của G, rồi
nâng luồng lên ñầy, sau ñó áp dụng thuật toán Ford-Fulkerson hoặc ta có thể áp dụng
thuật toán Ford-Fulkerson trực tiếp ñối với luồng ϕ.
Thuật toán gồm 3 bước:
Bước 1 (ñánh dấu ở ñỉnh của mạng): Lối vào v
0

một xích α, mọi ñỉnh ñều khác nhau và ñược ñánh dấu theo chỉ số của ñỉnh liền
trước nó (chỉ sai khác nhau về dấu). Khi ñó chắc chắn ta nâng ñược giá trị của luồng.
Bước 2 (nâng giá trị của luồng): ðể nâng giá trị của luồng ϕ, ta ñặt:
ϕ’(e) = ϕ(e), nếu e∉α,
ϕ’(e) = ϕ(e)+1, nếu e∈α ñược ñịnh hướng theo chiều của xích α ñi từ v
o
ñến v
n
,
ϕ’(e) = ϕ(e)−1, nếu e∈α ñược ñịnh hướng ngược với chiều của xích α ñi từ v
o
ñến v
n
.
ϕ’ thoả mãn các ñiều kiện về luồng, nên ϕ’ là một luồng và ta có:
ϕ’
n
= ϕ
n
+1.
Như vậy, ta ñã nâng ñược luồng lên một ñơn vị.

n
v
+−
Γ−Γ=
ϕϕϕ
.
Chứng minh: ðặt A
1
=A \{v
n
}. Theo Hệ quả 5.2.1.4, ta có:
))(())((
11
AA
+−
Γ=Γ
ϕϕ
(1).
ðặt C
1
={(a,v
n
)∈E | a∉A}. Khi ñó
∪Γ=Γ
−−
)()(
1
AA
C
1

++
)()(
1
AA
C
2
và
∩Γ
+
)(A
C
2
= ∅, nên
ϕϕϕ
−Γ=Γ
++
))(())((
1
AA
(C
2
) (3).
y

v
j

z
1
∪C
2
và C
1
∩C
2
= ∅, nên
n
v
ϕ
=
))((
n
v
−
Γ
ϕ
=
ϕ
(C
1
)+
ϕ
(C
2
) (4).
Từ (1), (2), (3) và (4), ta có:
))(())(( AA
n

0
∉B, v
n
∈B. Do ñó
−
Γ
(B) là một thiết diện của mạng
vận tải G và theo Bổ ñề 5.2.2.4, ta có:
))(())((
000
BB
n
v
+−
Γ−Γ=
ϕϕϕ
(1).
ðối với mỗi cung e=(u,v)∈
−
Γ
(B) thì u∉B và v∈B, tức là u ñược ñánh dấu và v
không ñược ñánh dấu, nên theo nguyên tắc ñánh dấu thứ nhất, e ñã là cung bão hoà:
ϕ
0
(e) = m(e).
Do ñó,
))(()()())((
)()(
00
BmemeB

(3).
Từ (1), (2) và (3) ta suy ra:
))((
0
Bm
n
v
−
Γ=
ϕ
.
Vì vậy,
0
n
v
ϕ
là giá trị lớn nhất của luồng ñạt ñược, còn m(
−
Γ
(B)) là giá trị nhỏ
nhất trong các khả năng thông qua của các thiết diện thuộc mạng vận tải G.
Thí dụ 3: Cho mạng vận tải như hình dưới ñây với khả năng thông qua ñược ñặt trong
khuyên tròn, luồng ñược ghi trên các cung. Tìm luồng cực ñại của mạng này.
Luồng ϕ có ñường ñi (v
0
,v
4
), (v
4
,v
Xét xích α=(v
0
, v
4
, v
6
, v
3
, v
7

3
, v
7
, v
8
). Quá trình ñánh dấu từ v
0
ñến v
8
ñể có thể
nâng luồng ϕ
2
lên một ñơn vị bằng cách biến ñổi luồng tại các cung thuộc xích β ñược
ñánh dấu. Sau ñó ta có luồng ϕ
3
.
v
1

v
5

v
2

v
3

v
4


4

4

3

2

2

2

3

4

5

6

5

6

8

5

5

6

v
7

v
0

v
8

3

4

4

7

4

4

4

4

4

4


6

12
9

12

6

ϕ
1

0

+0

+4

−
6

+3

+7

v
0

v


+7

0

+0

+4

xích
α Tải miễn phí ðề thi, eBook, Tài liệu học tập

78
Γ
(B) với B={v
1
, v
2
, , v
8
} là
−
Γ
(B)={(v
0
,v
1
), (v
0
,v
2
), (v
0
,v
3
), (v
0
,v
4
)}.
v
1


7

4

4

4

4

4

4

4

3

2

3

4

2

4

5


+1

−
5

+2

+7

−
6

+3

v
0

v
1

v
2

v
6

v
3

v

−
1

−
6

2
−
1

3+1

7+1

xích
βv
1

v
5

v
2

v
3



4

4

4

2

3

4

4

1

4

5

6

5

8

8

5

thành phố có thể hiểu là cự ly thông thường hoặc thời gian cần ñi hoặc chi phí của hành
trình, và xem như cho trước).
Xét ñồ thị ñầy ñủ G=(V,E), với V={1, 2, , n}, có trọng số với trọng số m
ij
=
m(i,j) có thể khác m
ji
= m(j,i). Như vậy, ta có thể xem G như là một ñồ thị có hướng ñầy
ñủ “mạnh” theo nghĩa với mọi i, j=1, 2, , n, i≠j, luôn có (i,j), (j,i)∈E. Bài toán trở
thành tìm chu trình Hamilton có ñộ dài ngắn nhất trong G.
Bài toán nổi tiếng này ñã có lời giải bằng cách sử dụng phương pháp “nhánh và
cận”.
5.3.2. Phương pháp nhánh và cận:
Giả sử trong một tập hữu hạn các phương án của
bài toán, ta phải chọn ra ñược một phương án tối ưu theo một tiêu chuẩn nào ñó (thí dụ
làm cho hàm mục tiêu ñạt giá trị nhỏ nhất). Ta sẽ tìm cách phân chia tập phương án
ñang xét thành hai tập con không giao nhau. Với mỗi tập này, ta sẽ tính “cận dưới”
(chặn dưới ñủ tốt) của các giá trị hàm mục tiêu ứng với các phương án trong ñó. Mang
so sánh hai cận dưới vừa tính ñược, ta có thể phán ñoán xem tập con nào có nhiều triển
vọng chứa phương án tối ưu và tiếp tục phân chia tập con ñó thành hai tập con khác
không giao nhau, lại tính các cận dưới tương ứng Lặp lại quá trình này thì sau một số
hữu hạn bước, cuối cùng sẽ ñược một phương án tốt, nói chung là tối ưu. Nếu không thì
lặp lại quá trình phân chia ñể kiểm tra và sau một vài bước, ta sẽ ñược phương án tối ưu.
Người ta thường mô tả quá trình phân chia ñó bằng một “cây có gốc” mà gốc sẽ
tượng trưng cho tập toàn bộ các phương án, còn các ñỉnh ở phía dưới lần lượt tượng
trưng cho các tập con trong quá trình “phân nhánh nhị phân”. Vì vậy, phương pháp này
mang tên nhánh và cận.
5.3.3. Cơ sở lý luận của phép toán:
Nếu không xác ñịnh thành phố xuất phát thì có
n! hành trình, mỗi hành trình ứng với một hoán vị nào ñó của tập {1, 2, , n}. Còn nếu

hằng số rút gọn dòng (t.ư. cột) ñang xét. Ma trận với các phần tử không âm và có ít nhất
một phần tử bằng 0 trên mỗi dòng và mỗi cột ñược gọi là ma trận rút gọn của ma trận
ban ñầu.
Thí dụ 4:
M =










5109
726
534

→














5109
726
534

→
M’’ =










085
202
010
. 5.3.5. Mệnh ñề:
Phương án tối ưu xét trên ma trận trọng số ban ñầu cũng là phương án
tối ưu của bài toán xét trên ma trận rút gọn và ñảo lại.
Chứng minh: Có thể xem việc ñi tìm chu trình Hamilton của người du lịch như là một
bài toán vận tải ñặc biệt dưới dạng bảng. Như vậy thì trong bảng (ma trận trọng số hoặc


2

5

1

0

0

4

2

0

0

0

5

Tải miễn phí ðề thi, eBook, Tài liệu học tập

81

5.3.6. Phân nhánh:
Sự phân hoạch tập hợp tất cả các hành trình ở một giai ñoạn nào
ñó thành hai tập con rời nhau ñược biểu diễn bằng sự phân nhánh của một cây. Trên

=0
và phần tử nhỏ nhất trong cột j không kể
ij
m'
=0 vì thành phố j nhất thiết phải nối liền
với một thành phố nào ñó ở trước nó trên hành trình. Ký hiệu tổng của hai phần tử nhỏ
nhất ñó là θ
ij
thì ta có f′(h) ≥ θ
ij
, ∀h∈
),( ji
.
Vì lý do trên, số θ
ij
có thể dùng làm tiêu chuẩn so sánh giữa các cặp thành phố
(i,j) cùng có
ij
m'
=0. Một cách tổng quát, ở mỗi giai ñoạn ta sẽ chọn cặp thành phố (i,j)
có
ij
m'
=0 trong ma trận rút gọn và có θ
ij

lớn

nhất ñể tiến hành phân nhánh từ một ñỉnh
trên cây.

Nếu tiếp tục phân nhánh thì cận dưới của các ñỉnh tiếp sau ñược tính toán tương
tự, vì ñây là một quá trình lặp. Ta chỉ cần xem ñỉnh xuất phát của các nhánh giống như
ñỉnh X ban ñầu ðể tiết kiệm khối lượng tính toán, người ta thường chọn ñỉnh có cận
dưới nhỏ nhất ñể phân nhánh tiếp tục.
5.3.8. Thủ tục ngăn chặn hành trình con:
Một ñường ñi hoặc chu trình Hamilton
không thể chứa chu trình con với số cạnh tạo thành nhỏ hơn n. Vì vậy ta sẽ ñặt m
ii
=∞
(i=1, , n) ñể tránh các khuyên.
Với i≠j và nếu (i,j) là ô chọn thì phải ñặt ngay m’
ji
=∞ trong ma trận rút gọn.
Nếu ñã chọn (i,j) và (j,k) và n>3 thì phải ñặt ngay m’
ji
=m’
kj
=m’
ki
=∞.
Chú ý rằng việc ñặt m’
ij
=∞ tương ñương với việc xoá ô (i,j) trong bảng hoặc xem
(i,j) là ô cấm, nghĩa là hai thành phố i và j không ñược kề nhau trong hành trình ñịnh
kiến thiết. Ở mỗi giai ñoạn của quá trình ñều phải tiến hành thủ tục ngăn chặn này trước
khi tiếp tục rút gọn ma trận.
5.3.9. Tính chất tối ưu:
Quá trình phân nhánh, tính cận, ngăn chặn hành trình con, rút
gọn ma trận phải thực hiện cho ñến khi nào có ñủ n ô chọn ñể kiến thiết một hành trình
Hamilton, nói cách khác là cho ñến khi trên cây phân nhánh ñã xuất hiện một ñỉnh chỉ

∞
∞
∞
∞
595523
548274612
1818251621
05351320
25301147
2630164327
Tổng các hằng số rút gọn bước ñầu là s=48. Trong ma trận rút gọn ta có:
m’
14
=m’
24
=m’
36
=m’
41
=m’
42
=m’
56
=m’
62
=m’
63


và θ
14
=10, θ
24
=1, θ
36
=5, θ
41
=1, θ
42
=0, θ
56
=2, θ
62
=0, θ
63
=9, θ
65
=2. Sau khi so sánh ta
thấy θ
14
=10 là lớn nhất nên ta chọn ô (1,4) ñể phân nhánh. Cận dưới của ñỉnh
)4,1(
là
s+θ
14
=58. Xoá dòng 1 cột 4 rồi ñặt m’
41
=∞.

22900
05351315
24290131
101402711
.

















∞
∞
∞
∞
∞
00013
022412
2290

.
Tổng hằng số rút gọn là s’=1. Vậy cận dưới của ñỉnh (1,4) là s+s’=49. Vì 49<58 nên tiếp
tục phân nhánh tại ñỉnh (1,4). Trong ma trận còn lại, sau khi rút gọn ta có
m”
21
=m”
36
=m”
42
=m”
56
=m”
62
=m”
63
=m”
65
=0.
Ở giai ñoạn này, sau khi tính toán ta thấy θ
21
=14 là lớn nhất nên chọn tiếp ô (2,1). Cận
dưới của ñỉnh
)1,2(
là 49+θ
21
=63. Xoá dòng 2 cột 1. ðặt m”
42
=∞. Rút gọn ma trận còn
lại, ta có:









∞
∞
∞
∞
000
02241
007
0513
.
Tổng hằng số rút gọn là 2. Cận dưới của ñỉnh (2,1) là 49+2=51.
Tiếp tục như vậy cuối cùng ta ñược 6 ô chọn là:
(1,4), (2,1), (5,6), (3,5), (4,3), (6,2)
và kiến thiết hành trình h
0
=(1 4 3 5 6 2 1) với f(h
0
)=63 là cận dưới của ñỉnh cuối cùng.
cận dưới của ñỉnh cuối cùng là 63, trong khi ñó ñỉnh treo
)4,1(
có cận dưới là 58<63 nên
phải tiếp tục phân nhánh từ ñó ñể kiểm tra. Sau sự phân nhánh này thì mọi ñỉnh treo ñều
có cận dưới không nhỏ hơn 63 nên có thể khẳng ñịnh rằng hành trình h
0

4

5

6

1

2

3

5

6

2

3

4

5

6

1

2


6

3

3

4

4

5

6

6

5

Tải miễn phí ðề thi, eBook, Tài liệu học tập

84

phân nhánh. Cận dưới của ñỉnh
)3,6(
là 58+9=67. ðặt m’
36
=∞. Rút gọn ma trận với tổng
hằng số rút gọn là 15. Cận dưới của ñỉnh (6,3) là 58+15=73. X)
4
,
1
()
3
,
6
()
3
,
6
(

)5,3(
X
)
2,6(
X

)
3,4(
X)
2
,
6
(

48

58

67

63

65


4

4

3

2

2

1

2

7

5

4

3

7

11

12

5


1

4

1

3

6

8

10

4

2

2

5

3

5

2

8














414
422
1224
4214
24126
423
63

5.
Tìm W* bằng cách áp dụng thuật toán Floyd vào ñồ thị sau:
H

M

I

N

7

3

8

3

2

9

5

7

3

5

2


1

2

3

A

B

C

D

E

F

G

A

B

C

D

E


13

4

6

8

v
1

v
5

v
2

v
6

v
3

v
4

v
0

v

86

7.
Giải bài toán mạng vận tải sau bằng thuật toán Ford-Fulkerson với luồng vận tải khởi
ñầu ñược cho kèm theo.
8.
Hãy giải bài toán người du lịch với 6 thành phố, có số liệu cho trong ma trận trọng số
sau:











3

v
2

v
4

v
5

v
6

v
7

v
8

v
9

v
10

v
11

4

20
10
10
3

30
15
8

6

2

8

6

0

16

0

2

2

0

2