Thuật Toán Nhánh Cận - Công Nghệ Thông Tin K23

Trang chủ » Thuật Toán Nhánh Cận Giải Bài Toán Người Du Lịch » Thuật Toán Nhánh Cận - Công Nghệ Thông Tin K23

Có thể bạn quan tâm

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ọ.

Từ khóa » Thuật Toán Nhánh Cận Giải Bài Toán Người Du Lịch