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.