+ 1

can someone help me with a branch and bound code example please?

I would like you to guide me support me or recommend a book / article to know what the code is like of the branch and bound algorithm please

9th Dec 2020, 10:26 PM
~Joker~
~Joker~ - avatar
3 odpowiedzi
+ 3
What I understood is that instead of checking all the solutions of a problem, you discard the ones that cant give you the result you are looking for. In the traveller salesman problem example, you have to calculate the path that goes through different cities (nodes) with the minimum distance. Instead of checking all the possible paths, you start going from each city to the nearest one. Then you check the other paths, and when the distance is greater than the better solution that you have, you move to the next one. If there are 10 cities and path1 is 50km long, and the distance between the first two cities of path2 is 60km, you already know that whatever is the distance to the other cities, path 1 is the better solution.
3rd Feb 2021, 7:20 PM
David
David - avatar
+ 1
I found this video https://m.youtube.com/watch?v=3RBNPc0_Q6g If you don't understand it cause of the pronunciation just turn on the subtitles. The branch and bound part starts at 7:20. Here he uses branch and bound to solve the tsp: https://m.youtube.com/watch?v=1FEP_sNb62k Wikipedia: https://en.m.wikipedia.org/wiki/Branch_and_bound GeeksforGeeks: https://www.geeksforgeeks.org/branch-and-bound-algorithm/
3rd Feb 2021, 7:17 PM
David
David - avatar
0
thanks
4th Feb 2021, 11:17 PM
~Joker~
~Joker~ - avatar