Доказательство сходимости алгоритмов комбинаторной оптимизации с использованием подклассов разрешимых задач

摘要

На примере задачи коммивояжера с использованием подклассов разрешимых задач доказана сходимость методов, основанных на распознавании структуры входной информации. Показано, что сходимость последовательности решений, построенных методом структурно-алфавитного поиска для задачи коммивояжера приближается к нулю, а сходимость метода ближайшего соседа и "жадного" алгоритма зависит от структуры входных данных.