Какова временная сложность задачи TSP с использованием ветвления и привязки. Это то же самое, что динамическое программирование, которое O (2 ^ n * n ^ 2)
В худшем случае сложность Branch и Bound остается такой же, как и у Brute Force (O(2^n * n^2)), очевидно, потому что в худшем случае у нас никогда не будет возможности обрезать узел. Принимая во внимание, что на практике это работает очень хорошо в зависимости от другого случая задачи коммивояжера. Сложность также зависит от выбора ограничивающей функции, поскольку именно они решают, сколько узлов следует удалить.
(O(2^n * n^2))
Объяснение о отраслевом и связанном подходе для задачи коммивояжера: https://www.geeksforgeeks.org/traveling-salesman-problem-using-branch-and-bound-2/