Thuật toán nhánh cận (Branch and Bound) giải bài toán tìm đường đi của người giao hàng (TSP)

Bài toán:
Có một người cần đi giao hàng tại n thành phố.
Xuất phát từ một thành phố nào đó, đi qua các thành phố khác và trở về thành phố ban đầu. Mỗi thành phố chỉ đến một lần.
Khoảng cách từ một thành phố đến các thành phố khác là xác định được.
Giả thiết rằng mỗi thành phố đều có đường đi đến các thành phố còn lại.
Khoảng cách giữa hai thành phố: khoảng cách địa lý/ cước phí / thời gian di chuyển. Ta gọi chung là độ dài.
Tìm một chu trình sao cho tổng độ dài các cạnh là nhỏ nhất.
Thuật toán Nhánh Cận:
Xây dựng cây:
Nút gốc: xuất phát từ một thành phố (bậc 0)
Nút gốc có n-1 nút con (bậc 1), tương ứng với các khả năng đi ra từ thành phố ở bậc 0
Mỗi nút con ở bậc 1 có n-2 nút con (bậc 2), tương ứng với các khả năng đi ra từ thành phố ở bậc 1....
Đến bậc n-2: đã có n-1 cạnh, đi đến thành phố cuối cùng, quay về TP ban đầu sẽ có một phương án
Tính cận dưới:
Nút gốc: CD= n* độ dài cạnh nhỏ nhất
Các nút khác (bậc i):
CD= TGT + (n-i)* độ dài cạnh nhỏ nhất trong số các cạnh chưa sử dụng và TGT là tổng độ dài các cạnh từ thành phố xuất phát đến thành phố đang xét
Tham khảo kỹ thuật nhánh cận tại:

[huynt]

ở dòng 145 i == n - 2 thì phải đi được n-2 cạnh chứ ạ?

[huynt]

sơ đồ khối của thuật toán này như thế nào ạ? thầy chỉ giúp em với ạ😥

[hdgntvmtv]

Thầy ơi em có chỗ chưa hiểu
Đầu tiên là ở hàm Nhanh_Can, dòng 137 và 138, thầy tính tổng gt với cận dưới thì em hiểu rồi, nhưng em thắc mắc ở chỗ là tại sao mình ko đánh dấu da_dung trước khi tính cận dưới? Theo thầy giảng ở đầu video (phút 12) thì lúc tính cận dưới cho nút bậc 1, ví dụ cạnh DA, thì mình ko chọn cạnh nhỏ nhất là cạnh DA nữa vì DA mình đã dùng rồi. Còn trong code thì mình ko đánh dấu da_dung trước khi tính cận thì có chính xác ko ạ? Hay em hiểu sai chỗ nào rồi ạ?
Với lại cho em hỏi tại sao mình ko cần kiểm tra đỉnh cấp 3 vậy thầy? Em xem video giải thuật tham ăn thì thấy thì xét cả chu trình thiếu và đỉnh cấp 3. Còn giải thuật nhánh cận thì ko thấy xét đỉnh cấp 3 ạ
Mong nhận được phản hồi từ thầy ạ

[huynt]

đối với đồ thị có hướng thì giải sao ạ.Mong thầy giải đáp ạ!

[linhkduong]

Em cảm ơn thầy về bài giảng ạ, em mới được tiếp xúc về bài toán này lần đầu tiên nên có nhiều phần em không biết và chưa hiểu rõ lắm nên nhờ thầy giúp đỡ. Phương pháp này theo em là phù hợp khi áp dụng vào bài tập với số lượng ít các điểm, nhưng đối với bài tập mà số lượng các điểm rất lớn (lên tới hàng trăm) thì phương pháp nào là tối ưu nhất ạ thưa thầy?
Chuyên ngành của em không thuộc mảng lập trình hay viết code nên em rất mong thầy hướng dẫn.

Em cảm ơn thầy và chúc thầy nhiều sức khoẻ ạ.

[vyang]

cho em hỏi với ạ, nếu tìm cận trên thì ưu tiên phân nhánh cho nút con nào có cận trên lớn hơn, còn ở bài toán cận dưới thì ko có trường hợp ưu tiên hay sao ạ. Với đoạn tìm cận dưới của bước cuối cùng em vẫn chưa hiểu ạ. Tại sao cận dưới của chu trình DABCED lại ra 20 ạ.

[trieuvidesigner]

em cám ơn thầy, thầy dạy rất là hay ạ, video này đã giúp em hiểu rõ hơn về bài Niên luận 1 sắp tới, Bài Toán Người Giao Hàng. Chúc thầy luôn có nhiều sức khỏe. trong yêu cầu bài Niên luận có yêu cầu thể hiện dưới dạng đồ họa, em không hiểu lắm, thầy có thể hướng dẫn em được không ạ?

[huyvo]

Dạ thầy ơi cho em hỏi, em xem trên các tài liệu khác thì giải thuật này bao gồm thủ tục rút gọn, thủ tục phân nhánh, thủ tục
chọn cạnh phân nhánh, chọn hai cạnh cuối cùng, thầy cho em hỏi sự khác nhau giữa thuật toán của thầy với các thủ tục này như thế nào ạ? Và theo đề thì khoảng cách giữa các thành phố chẳng hạn như từ 1 đến 2 và từ 2 đến 1 có nhất thiết phải giống nhau không ạ?

[batch]

Dạ thưa thầy, em chưa hiểu là dựa trên cơ sở nào để tạo ra được công thức tính cận dưới mà thầy đã sử dụng trong video và thầy có thể chia sẻ rõ hơn ý nghĩa của cận dưới được không ạ, em đọc sách thầy viết môn này và xem video mà vẫn chưa rõ ạ

[huyvongoc]

Thưa thầy, nếu có 1 chi phí (ví dụ từ tp B->C) bằng 0 thì thuật toán trên có đúng không ạ? Mong thầy giải đáp thắc mắc giúp em ạ.

[phambatrung]

rất chuẩn. cảm ơn thầy nhiều.
nhờ thầy giúp em bài này với
cho mảng NxN và dãy 1, 2, ..., N. hãy đưa ra tất cả phương án điền dãy vào mảng mà hàng và cột không có số trùng nhau.

[namquach]

thầy rất nhiệt tình, chúc thầy sức khỏe và chia sẻ những kĩ thuật hay nữa

[huynt]

Mình phải xét hết 5 trường hợp xuất phát là A, B, C, D, E đúng không ạ?

[cuongcong]

thầy ơi, thầy cho em xin code được không
em code theo thầy nó không chạy đc