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:    • Kỹ thuật Nhánh Cận (Branch and Bound)   Tham khảo cách giải bài toán này bằng kỹ thuật tham ăn: Láng giềng gần nhất (Nearest Neighbor):    • Thuật toán Láng giềng gần nhất (Nearest Ne...   Tham khảo cách giải bài toán này bằng kỹ thuật tham ăn: Xây dựng phương án từ những cạnh có độ dài nhỏ nhất:    • Thuật toán tham ăn giải bài toán TSP (Trav...