Можно ли найти вероятность решения NP-полных задач?
Название охватывает весь вопрос. Можно ли получить функцию, позволяющую с уверенностью сказать, что предложенное решение NP-полной задачи имеет процентную вероятность быть правильным?
1 ответ
Я сомневаюсь. Например, вероятность случайной функции быть оптимальной numberOfOptimalSolutions / searchSpace, Поэтому, если вы знаете ответ на этот вопрос, вы можете вывести число OfOptimalSolutions (о котором IIRC всегда сложнее узнать, чем найти 1 оптимальное решение для полной задачи NP).
В книге "В погоне за коммивояжером" для каждой строительной эвристики в TSP указывается, насколько близко (или далеко) она находится в худшем случае из оптимального решения. В нем также упоминается средний процент правильности для (некоторых) этих алгоритмов, но IIRC, вероятно, основан на выборке и ухудшается по мере масштабирования проблемы.