И.А. Едыгаров,
(КГТУ им. А.Н. Туполева, г. Казань)
Не стоит объяснять, насколько часто приходиться решать NP-полные задачи [I], главная из которых задача коммивояжера. Эта задача всегда служит полигоном для испытания каких-либо новых методов оптимизации.
Пусть мы решаем оптимизационную задачу, то есть ищем объект с наибольшей или наименьшей стоимостью среди множества объектов, на которых задана функция стоимости. Обозначим оптимальное решение как С*. А решение, которое дает нам алгоритм как С.
Мы будем говорить, что алгоритм решает задачу с ошибкой не более чем в р(n) раз, если
mах(С / С*, С* / C) ≤ р(п)
Заметим, что поскольку максимум из двух взаимно обратных величин не меньше 1, то
р(п)≥ 1
Здесь и далее под п мы будем понимать длину входа, то есть длину соответствующей входу битовой строки.
Иногда удобнее использовать относительную ошибку, которая определяется как |С - С*| / С*.
Мы будем говорить, что алгоритм имеет ошибку не более ε(n), если
|С - С*| / С* ≤ ε(n)
Легко проверить, что ε(n) может быть ограничена сверху через функцию р(п), а именно ε(n) ≤ р(п) - 1. В самом деле, для задач на минимум это неравенство превращается в равенство. Для задач на максимум ε(n) = (р(п) - 1) / р(п) (далее нужно вспомнить, что р(п) ≥ 1).
Для многих задач известны приближенные алгоритмы, решающие задачу с ошибкой не более чем в некоторое фиксированное число раз (независимо от длины входа). В других случаях такие алгоритмы неизвестны, и приходится довольствоваться алгоритмами, в которых оценка ошибки растет с ростом п.
Для некоторых задач можно улучшать качество приближения (уменьшать относительную ошибку) ценой увеличения времени работы. Схемой приближения для данной оптимизационной задачи называется алгоритм, который, помимо условия задачи получает положительное число е, и дает решение с относительной ошибкой не более ε.
Схема приближения называется полиномиальной, если для любого фиксированного ε > 0 время ее работы не превосходит некоторою полинома от n. Схема приближения называется полностью полиномиальной, если время ее работы ограничено некоторым полиномом от п и от 1/ ε.
В настоящее время для решения переборных задач, в частности задачи коммивояжера, применяются следующие методы:
• Метод ветвей и границ и его модификация алгоритм Литтла состоит в отбрасывании заведомо неоптимальных решений целыми классами в соответствии с некоторой оценкой. Удовлетворительных теоретических оценок алгоритма Литтла и ему подобных нет, но практика показывает, что на современных машинах они позволяют решать задачу коммивояжера с количеством вершин ~ 100. Кроме того, алгоритмы типа ветвей и границ являются эффективными эвристическими процедурами. Если нет возможности доводить их до конца.
• Метод локальных улучшений состоит в поиске более оптимального решения в окрестности некоторого текущего решения. Если такое решение удается найти, оно само становится текущим решением, если нет - поиск заканчивается.
• Приближенные и эвристические методы состоят в применении эвристик для выбора элементов решения. В этих методах для выбора элементов решения используются те или иные, кажущиеся естественными рекомендательные правила выбора, эвристики. Часто такие правила комбинируются с условием жадности выбора: сделанный выбор в дальнейшем не пересматривается. Более мощной разновидностью такого подхода является сокращенный поиск, в котором дерево вариантов, как по методу ветвей и границ, искусственно сокращается исходя из некоторых правил, правдоподобных, но формально не обоснованных.
• Псевдополиномиальные алгоритмы представляют собой подкласс динамического программирования разработанном Беллманом. У таких алгоритмов экспоненциальная зависимость времени работы (и памяти компьютера) от длины входа, однако существует полиномиальная зависимость от некоторого числа (чисел) на входе задачи. Такие алгоритмы очень полезны, т.к. позволяют точно решать задачи с маленькими числами и приближенно - для больших чисел, каким-либо образом преобразованных в маленькие.
• Метод случайного поиска состоит в представлении выбора последовательностью случайных выборов. Суть в том, что обычно выбор решения можно представить последовательностью выборов. Если делать эти выборы с помощью какого-либо случайного механизма, то решение находится очень быстро, так что можно находить решение многократно и запоминать «рекорд», т.е. наилучшее из встретившихся решений Этот наивный подход существенно улучшается, когда удается учесть в случайном механизме перспективность тех или иных выборов, комбинировать случайный поиск с эвристическим методом и методом локального поиска. По описанию такие методы применяются при составлении расписаний в крупных авиакомпаниях.
Список литературы
1. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М.: Мир, 1982.
2. Джон Э. Хопкрофт, Раджив Мотвани, Джеффри Д. Ульман. Введение в теорию автоматов, языков и вычислении. М: «Вильяме», 2002. 527 с.
Ахо А., Хопкрофт Дж., Ульман Дж. Структуры данных и алгоритмы. М: Издательский дом «Вильяме», 2001.
|
