Как я могу показать правильность алгоритма грубой силы TSP?

Question

Я работаю над изучением TSP. Поэтому я должен доказать правильность алгоритма грубой силы на графах (подобрать хорошую перестановку из всех существующих перестановок ~ O (n!)). Поэтому я изучаю много книг и сайтов, но не могу найти, как доказать правильность. Существует ли доказательство в книгах и работах ученых? Если у кого-то была такая же проблема раньше или вы знаете, как решить эту проблему, можете ли вы дать мне совет, пожалуйста?

Answer 1

доказательства для всех алгоритмов грубой силы в основном одинаковы: пусть BF - грубая сила, а X - множество всех возможных решений. давайте предположим, что наш алгоритм BF возвратил x в X, чем предположим от противного, что существует y в X такое, что y - лучшее решение, чем x. но BF - алгоритм грубой силы, поэтому он сравнил x и y, и вывел x лучше. противоречие. так что х лучше чем у.