I was asked to implement the Traveling Salesperson Problem using Best-First Search with Brand-and-Bound Pruning Algorithm.
Problem: Determine an optimal tour in a weighted, directed graph. The weights are nonnegative numbers.
Inputs: a weighted, directed graph, and n, the number of vertices in the graph. The graph is represented by a two-dimensional array W , which has both its rows and columns indexed from 1 to n, where W [i] [j] is the weight on the edge from the ith vertex to the jth vertex.
Outputs: variable minlength, whose value is the length of an optimal tour, and
variable opttour, whose value is an optimal tour.
Here was the pseudocode I came up with for the main routine:
In addition to this pseudocode, I was tasked with writing the two supporting subroutines: length() and bound(). I ran out of time before getting to these subroutines. However, I am confident function length() is supposed to return the length of the tour u.path , and function bound() returns the bound for a node using the considerations above.