I'm working on exploring TSP. So I have to prove the correctness of brute-force algorithm on graphs (pickin up the good permutation from all permutations that exists ~ O(n!)). So I'm learning a lot of books and sites, but I can't find how to prove the correctness. Does the prove exists in books and scientists works? If anyone had the same problem before or know how to solve this problem, can you give me advice please?
the proof for all brute force algorithms are basically the same: let BF be a brute force and X the set of all possible solutions. let us assume our algorithm, BF has returned x in X, than let us assume by contradiction that there exists y in X such that y is a better solution than x. but BF is a brute force algorithm, so he compared x and y, and deduced x is better. contradiction. so x is better than y.
thanks! I proved the algorithm using the similar way. Let we have a list where i have all city-permutations. Let function COST calculate every path's weight. After calculating weight of every path we have array Len, where for i-path from the city-permutation list i-weight exists. MIN function finds the min path length and this path's i-number. Due to the one-to-one correspondence of the list of paths and the array of values, the i-position of the minimum cost corresponds to the i-position of the path. Thus, i is the desired path and the minimum one.