Gửi các anh chị một số đề luyện thi của HV KTQS vài năm lại đây liên quan đến Thuật toán nhánh cận để tìm 1 hoặc 2 (nếu có) hành trình du lịch tối ưu cho bài toán người du lịch với ma trận kinh phí cho sẵn.
Đề 2009:
[You must be registered and logged in to see this image.]
Đề 2008:
[You must be registered and logged in to see this image.]

Thuật toán nhánh cận
Những bài toán áp dụng thuật toán nhánh cận không phải là bài toán khó. Vì đã xây dựng thành thuật toán thì cứ thế mà áp dụng. Những bài toán này, chẳng đòi hỏi Khách viếng thăm là người phải thông minh xuất chúng gì cả, mà là những bài toán yêu cầu sinh viên phải tỉ mỉ, cẩn thận và thực tế rất chua chát là những bài này khi cho vào các bài thi lại là bài giết thí sinh nhiều nhất. Bản thân nó không khó, nhưng vì khi giải nó rất dài dòng và tốn kém (tốn giấy đã đành vì mỗi bài phải viết tới vài trang) nó còn dã man ở chỗ là khiến thí sinh phải dành rất nhiều thời gian làm các phép tính cộng cộng, trừ trừ đơn giản. Các đề thi đưa thuật toán nhánh cận để tuyển thạc sĩ hay tiến sĩ thì có nghĩa là người ra đề cũng muốn biến các "thạc sĩ, tiến sĩ tương lai" thành một chút công nhân lao động khổ sai. Nó âm thầm tiêu diệt nguồn tài sản quý nhất của người đi thi đó là thời gian, cho dù thế nào đi nữa, Khách viếng thăm cố làm bài này cũng được trả công rất bạc bẽo. Nếu đề thi có câu này, thì đó là câu bạc bẽo nhất để Khách viếng thăm luôn hiểu rằng cuộc đời nhiều khi thời gian, công sức của mình bỏ ra nhiều nhưng thu được chẳng được bao nhiêu.

Tôi với Admin đều là người đi thi, chẳng có lời khuyên gì. Nếu chẳng biết làm bài nào thì lấy tạm câu này ra làm để giết thời gian lấy phần chăm chỉ, cẩn thận bù vào sự thiếu thông minh, kém cỏi thôi thì cũng là điều vạn bất đắc dĩ. Lẽ ra câu hỏi dạng này thì chỉ nên để ở phần nghiên cứu thôi, cho vào đề thi thì nhiều khi tiêu tốn hai thứ đã nói ở trên đó là thời gian và công sức của cả người đi thi và người chấm thi. Người ra đề dạng này chắc Khách viếng thăm hiểu được sẽ là người như thế nào rồi đấy.

Tôi copy cái ý đoạn văn trên từ một blogger google trên mạng để làm mào đầu cho câu chuyện của chúng ta về cái thuật toán này. Mỗi người nói một kiểu về nó, nhưng có hỏi 100% thí sinh đi thi thì chẳng ai thích làm câu hỏi dạng này cả, chỉ cần để biết thôi. Mấy năm rồi đề thi vào Học viện KTQS không có, nhưng những năm trước có, những đề luyện tập luôn có. Năm nay câu hỏi dạng này có hay không thật khó trả lời, nhưng có một điều chắc chắn rằng, nếu có cho dù biết cách làm mười mươi, nhưng sẽ có nhiều thí sinh bỏ qua, nếu các câu khác hòm hòm. Chẳng ai đâm đầu vào làm bằng tay cái công việc vô bổ này, vì có thể dùng thuật toán hoặc viết giải thuật chỉ mất vài dòng, nhưng cứ làm ra thì tiêu hao thời gian và tàn lực của chúng ta không hề ít.

Tôi cũng chẳng tài ba gì, thôi thì mình lấy tí cần cù gõ vào đây làm căn cứ cho thiên hạ copy vậy, vì có google chẳng có thằng điên nào gõ một bài nhánh cận trên mạng nên hồn. Và cũng để cho những bạn nào vì một lý do bận việc đi đâu đó không đi học được có chỗ để mà tham khảo.

Trong bài toán người du lịch, khi tiến hành tìm kiếm lời giải chúng ta sẽ phân tập các hành trình ra thành 2 tập con:

- Một tập chứa hành trình một cung (i, j) nào đó.
- Tập kia gồm những hành trình không chứa cung này.

Ta gọi việc làm đó là phân nhánh và mỗi tập con nói trên sẽ được gọi là một nhánh hay một nút của cây tìm kiếm.
[You must be registered and logged in to see this image.]
Việc phân nhánh sẽ được thực hiện dựa trên một quy tắc Hơristic nào đó cho phép ta rút ngắn quá trình tìm kiếm phương án tối ưu. Sau khi phân nhánh ta sẽ tính cận dưới của giá trị hàm mục tiêu của mỗi một tập con (trên 2 tập trên).Việc tìm kiếm sẽ được tiếp tục trên tập con có giá trị cận dưới nhỏ hơn.
Thủ tục này sẽ tiếp tục cho đến khi thu được một hành trình đầy đủ tức là một phương án của bài toán người du lịch. Khi đó ta chỉ việc xét những tập con các phương án nào có cận dưới nhỏ hơn giá trị hàm mục tiêu tại phương án đã tìm được.
Quá trình phân nhánh và tính cận dưới trên tập các phương án của bài toán thông thường cho phép rút ngắn một cách đáng kể quá trình tìm kiếm do ta loại được khá nhiều tập con chắc chắn không chứa phương án tối ưu.

1. Thủ tục rút gọn (tính chi phí cận dưới)
Rõ ràng tổng chi phí của một hành trình của người du lịch sẽ chứa:
+ đúng một phần tử của mỗi dòng
+ đúng một phần tử của mỗi cột
trong ma trận chi phí C. Do đó, nếu ta trừ đi vào mỗi phần tử của một hàng (một cột) một số α thì chi phí của tất cả hành trình sẽ giảm đi α , vì thế hành trình tối ưu sẽ không thay đổi.
Nên trừ để mỗi dòng, mỗi cột đều chứa ít nhất một số 0 thì tổng các hằng số trừ đó sẽ cho ta cận dưới của mọi hành trình. Thủ tục này gọi là thủ tục rút gọn.

2. Thủ tục cung phân nhánh
Sau khi rút gọn, mỗi hàng, mỗi cột có ít nhất 1 phần tử 0.
Đối với mỗi phần tử 0 này, ta tính chỉ số của nó là tổng các phần tử khác không đang xét và nhỏ nhất tương ứng với hàng và cột đó. Chọn phần tử 0 có chỉ số lớn nhất, tương ứng với cung cần chọn để phân nhánh và đặt phần tử đối xứng với nó qua đường chéo là ∞.

Sau khi đã tiến hành tính cận dưới và phân nhánh, chia các hành trình làm 2 tập con.
- Tập T1 gồm các hành trình chứa cung (p, q)
- Tập T2 gồm các hành trình không chứa cung (p, q)
Đối với tập T1, ma trận chi phí tương ứng C1 nhận được từ ma trận C bằng cách loại bỏ hàng p cột q, kích thước giảm xuống 1 bậc.
Đối với tập T2 ma trận chi phí tương ứng C2 nhận được từ ma trận C bằng cách đặt Cpq = ∞ , tức là trong bước tiếp theo không chọn cung (p, q) nữa.

Bây giờ ta giải một bài toán áp dụng thuật toán nhánh cận để biết cuộc đời nó phũ phàng đến thế nào nhé:
Ma trận chi phí sẽ cho như sau:

	∞	3	93	13	33	9
	4	∞	77	42	21	16
C =	45	17	∞	36	16	28
	39	90	80	∞	56	7
	28	46	88	33	∞	25
	3	88	18	46	92	∞

Để rút gọn ma trận theo hàng thực hiện như sau:
Viết những con số nhỏ nhất của hàng ra một cột bên ngoài tay phải. Số được chọn là số đã tô đỏ. Gọi là αi. Cộng tổng bọn chúng lại là số M.
Ta có:

							αi
	∞	3	93	13	33	9	3
	4	∞	77	42	21	16	4
C =	45	17	∞	36	16	28	16
	39	90	80	∞	56	7	7
	28	46	88	33	∞	25	25
	3	88	18	46	92	∞	3
					M	=	58

Thực hiện trừ các số trong hàng cho con số nhỏ nhất của hàng này (Trừ hết giá trị cho số màu đỏ) ta được:

	∞	0	90	10	30	6
	0	∞	73	38	17	12
C =	29	1	∞	20	0	12
	32	83	73	∞	49	0
	3	21	63	8	∞	0
	0	85	15	43	89	∞
			15	8

Tương tự, làm theo cột ta thấy chỉ có 2 cột có giá trị nhỏ nhất khác 0 là 15 và 8, thực hiện trừ các số trong cột chứa 2 giá trị đó, cho chính giá trị màu đỏ. Ta được ma trận rút gọn:

	∞	0	75	2	30	6
	0	∞	58	30	17	12
C =	29	1	∞	12	0	12
	32	83	58	∞	49	0
	3	21	48	0	∞	0
	0	85	0	35	89	∞
					M	=	81

M lúc này được tính bằng cách cộng các giá trị đã trừ gồm: 58 + 15 + 8 = 81. Lưu ý, sách in đúng, nhưng trong mấy cái quyển phô tô, học sinh khóa trước họ sửa sai vào đó đấy nha, đừng có mà theo số của họ.

Bây giờ ta sang bước chọn cung phân nhánh để tính B(i, j). Làm như thế nào? Đầu tiên đánh dấu các phần tử có giá trị 0. Rồi, khoanh nó lại. Ở hình vẽ chính là số màu đỏ đó nha. Làm từng số phần tử mang giá trị 0 một nha. Tìm trong hàng chứa phần tử 0 này xem giá trị nào nhỏ nhất gọi là r_i tạm tô màu đỏ, tìm trong cột chứa phần tử 0 này xem giá trị nào nhỏ nhất gọi là s_i tạm tô màu đỏ,cộng các số màu đỏ lại, ghi ra một số be bé bên cạnh màu hồng làm chỉ số. Ví dụ số 3 được tạo thành bằng cách cộng số 1 và số 2. Tương tự ở các vị trí khác. Ở đây được phóng to lên cho dễ nhìn. Sau đó chọn trong số các số màu hồng giá trị nào lớn nhất để làm căn cứ phân tập. Do hàng 6, cột 3 (Phần tử 6, 3) có giá trị chỉ số lớn nhất là 48.
[You must be registered and logged in to see this image.]

Vậy chọn cung (6, 3) để phân tập thành 2 nhánh:
Nhánh T1 gồm các hành trình chứa cung (6, 3) có ma trận chi phí C1 tương ứng, bằng cách bỏ hàng 6 và cột 3. Đặt C(3, 6) = ∞ ta có:
[You must be registered and logged in to see this image.]
Nhánh T2, gồm các hành trình không chứa cung (6, 3) có ma trận chi phí C2 bằng cách thay C (6, 3) = ∞ ta có:
[You must be registered and logged in to see this image.]
Ta thấy C2 có thể rút gọn theo phương pháp trên vì cột 3 có thể trừ tất cả đi 48, như vậy chi phí cận dưới của nhánh này sẽ tăng lên là M = 81 + 48 = 129

Xét tiếp nhánh T₁ có chi phí cận dưới M = 81 nhỏ hơn, Khách viếng thăm hãy tiếp tục tính chỉ số các phần tử 0 để chọn cung phân nhánh. Cách làm như phần trên nha. Ta có, ở đây ta đánh lại số hàng và cột vì đã bỏ đi hàng 6  và cột 3 ở bước trên, nên nếu không đánh lại số sẽ nhầm lẫn, và công của Khách viếng thăm và tôi sẽ thành công cốc:
[You must be registered and logged in to see this image.]
M = 81
Như vậy phần tử 0 tương ứng với hàng 4 cột 6 (hay cung 4, 6) có chỉ số lớn nhất là 32, ta tiếp tục chọn cung này để phân nhánh cho tập T1 gồm:
- Nhánh T₁₁ gồm cách hành trình chứa (6, 3) và (4, 6) rõ ràng 2 cung này không tạo thành chu trình con kín. Ma trận chi phí C₁₁ tương ứng (sau khi bỏ hàng 4, cột 6  và đặt C_6,4 = ∞ như cách làm ở các bước trên) sẽ như sau:

- Nhánh T₁₂ gồm các hành trình chứa cung (6, 3) nhưng không chứa cung (4, 6) có ma trận chi phí C₁₂ tương ứng. Thay C_4,6 = ∞ ta có:

Ta thấy có thể rút gọn bằng cách trừ hàng 4 cho 32, nên chi phí cận dưới của C₁₂ sẽ là 81 + 32 = 113.
Như vậy ta sẽ phải chọn tiếp nhánh T₁₁.
Làm tiếp thế nào?
Lại tính chỉ số các phần tử 0, chọn chỉ số to nhất phân nhánh. Ta lại có:

Tiếp tục chọn cung này để phân nhánh cho tập T₁₁, phân làm 2
Nhánh T₁₁₁ gồm các hành trình chứa (6, 3), (4, 6) và (2, 1) rõ ràng cung này không tạo thành chu trình con khép kín Ma trận chi phí tương ứng C₁₁₁ được tạo → Bỏ hàng và cột của chỉ số to nhất này là bỏ hàng 2, cột 1. Đặt c₁₂ = ∞ ta có:

Rút gọn bằng cách trừ các phần tử cột 4 cho 2, và trừ các phần tử hàng 3 cho 1.
Chi phí cận dưới bằng M = 81 + 2 + 1 = 84.

Nhánh T112 gồm các hành trình chứa cung (6, 3), (4, 6) và không chứa cung (2, 1). Ta thay C21 = ∞ sẽ nhận được ma trận chi phí C112 tương ứng như sau:
[You must be registered and logged in to see this image.]
Có thể trừ hàng 1 cho 2, hàng 2 cho 17, cột 1 cho 3, cột 2 cho 1 để rút gọn, ta sẽ nhận được:
Chi phí cận dưới sẽ là M = 81 + 3 + 1 + 2 + 17 = 104. Để đây đã, tý nữa xét.
Tiếp tục xét nhánh T111, tính các chỉ số:
[You must be registered and logged in to see this image.]
Có thể lấy cung (3, 5) hoặc (2, 4) vì cùng có chỉ số là 28. Thôi ta chọn 1 nhé, chọn cung (3, 5) để phân nhánh là 2 tập:
- Tập T1111 gòm các hành trình chứa (6, 3), (4, 6), (2, 1) và (3, 5) các cung này không tạo thành các chu trình con kín. thì bớt bỏ hàng 3, cột 5 ta có:
[You must be registered and logged in to see this image.]
Rút gọn bằng cách trừ các phàn tử cột 2 cho 20:
[You must be registered and logged in to see this image.]
Khi ma trận chi phí còn lại là cấp 2, ta chọn 2 cung còn lại theo đường chéo ao cho không tạo thành chu trình con kín và có tổng bé hơn. Trường hợp này là (5, 2) và (1, 4).
Như vậy có được một hành trình hoàn chỉnh là:
T = {(6, 3), (4, 6), (2, 1), (3, 5), (5, 2), (1, 4)} với chi phí G = 84 + 20 = 104.
Viết lại cho đúng thứ tự:
T = {(1, 4), (4, 6), (6, 3), (3, 5), (5, 2), (2, 1)} với chi phí G = 104.
Đường đi: 1 → 4 → 6 → 3 → 5 → 2 → 1

Nhánh T1112 gồm các hành trình chứa các cung (6, 3), (4, 6), (2, 1) và không chứa cung (3, 5) có ma trận chi phí bằng cách thay c35 = ∞ ta có:
[You must be registered and logged in to see this image.]
Có thể rút gọn bằng trừ các phần tử cột 5 cho 28.
Ta thấy chi phí cận dưới này M = 81 + 28 = 109 mặc dù chưa hết chu hành trình mà đã lớn hơn chi phí G = 104 nên bỏ qua.
Xét tất cả các chi phí cận dưới của các nhánh đã bỏ qua thấy có nhánh T112 gồm các hành trình chứa cung (6, 3) và (4, 6) và không chứa cung (2, 1) có M = 103 nhỏ hơn G = 104 nên có thể xét tiếp. Rút gọn ta có:
[You must be registered and logged in to see this image.]
Tương tự, Khách viếng thăm tự xét tiếp để lấy hành trình nha. Nếu hành trình < 104 thì lấy, lớn hơn thì thôi nha.
Nếu xét ra còn dài nữa. mà ngay cả sách giáo khoa còn sai lung tung nữa là ta.
Mệt thế đấy.
Cuối cùng phải kết luận hành trình tối ưu sẽ là hành trình: ?
Có tổng chi phí là: ?
Đường đi là: ?

về phần bài tập:
bắt đầu từ bước tính C112, trong bước này anh Admin lại đặt C12=0 chứ không phải C12=Vô cùng, nên M=101 chứ không phải M=104 => dẫn đến cuối cùng chúng ta còn phải xét tiếp nhánh T112 này.
Mong sao thi không có dạng này nhỉ các anh nhỉ.

Theo lý thuyết của thầy P giảng trên lớp, thì ngay cả các sách chúng ta hiện có trong tay vẫn còn thiếu điều kiện. Nghĩa là, chúng ta còn phải đặt tất cả các cạnh mà có thể khiến hình thành chu trình con đều phải bằng ∞. Mặc dù ngầm định là tính nhánh và cận theo cạnh, chúng ta cũng cần biết cách làm theo đỉnh thì nó như thế nào?

Đề bài thầy trên lớp như vầy:
[You must be registered and logged in to see this image.]
Ở đây, cột trái và hàng đỉnh là hàng ghi chỉ số cho dễ quan sát nha.
Giải:
Không mất tính tổng quát, chọn xuất phát là đỉnh 1. Ta có Cmin = 2.
1) Nếu sang 2:
w = 3
h = 11
f* = ∞

Lý giải cách tính:

2) Nếu sang 3:
w = 14
h = 22
f* = ∞
3) Nếu sang 4:
w = 18
h = 26
f* = ∞
4) Nếu sang 5:
w = 15
h = 13
f* = ∞
Vậy chọn sang 2, đường đi 1 → 2, f* = ∞
5) Nếu sang 3
w = 7
h = 13
f* = ∞

Lý giải cách tính:

6) Nếu sang 4
w = 25
h = 31
f* = ∞
7) Nếu sang 5
w = 23
h = 29
f* = ∞
Vậy chọn sang 3, đường đi 1 → 2 → 3, f* = ∞
8) Nếu sang 4
w = 23
h = 27
f* = ∞
9) Nếu sang 5
w = 11
h = 15
f* = ∞
Vậy chọn sang 5, đường đi 1 → 2 → 3 → 5, f* = ∞
10) Không còn lựa chọn, sang 4
w = 16
h = 18
f* = ∞
11) Không còn lựa chọn, về 1
w = 22
h = 22
f* = 22

Lý giải kết quả:

Đường đi tạm thời là:
1 → 2 → 3 → 5 → 4 → 1
f* tạm thời = 22
12) Quay về 8:
h = 27 > f* loại.
13) Quay về 7:
h = 29 > f* loại.
14) Quay về 6:
h = 31 > f* loại.
15) Quay về 4:
h = 23 > f* loại.
16) Quay về 3:
h = 26 > f* loại.
17) Quay về 2:
h = 22 = f*
18) Nếu sang 2
w = 23
h = 29 > f* loại
19) Nếu sang 4
w = ...
h = ... > f* loại
20) Nếu sang 5
w = ...
h = ... > f* loại
Vậy đường đi tối ưu của bài toán là: 1 → 2 → 3 → 5 → 4 → 1 với f* = 22

thi gặp dạng này (nhánh và cận) làm chắc chết mất, dài dòng lê thê, dễ nhầm lẫn, tốn thời gian

cảm ơn bạn admin 1 lần nữa nhé

vinhct đã viết:thi gặp dạng này (nhánh và cận) làm chắc chết mất, dài dòng lê thê, dễ nhầm lẫn, tốn thời gian

Mình thấy các bạn nên vẽ dạng cây ,giống như ví dụ trong slide thầy đưa .Nó sẽ trực quan và ít bị rối hơn.

mọi người ơi??? gửi slide của thầy lên em xem với càng nhanh càng tốt ạ. em cảm ơn.

mà em hỏi với có hai loại tuần tự nhánh cận và song song nhánh cận đúng không ạ. Mà có thể chỉ rõ cho em về hai cái này được không ạ

Cảm ơn admin về những chia sẻ rất bổ ích đó!!!

Ai co CODE thuat toan tren ko? gui cho minh voi? :(

thanks

cho mình hỏi chút, trường hợp mà bắt đc những 2 số 0 có cùng một chỉ số lớn nhất trong ma trận rút gọn thì xử lý sao nhỉ, bỏ cả 2 cung đó hay chia thành 2 trường hợp để tách

Có anh chị nào có source code của dạng nhánh cận này không> cho mình xin với :)