задача коммивояжера поиск с возвратом

Метод локальных улучшений

в соответствии с некоторой оценкой

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

Метод ветвей и границ

Методы решения труднорешаемых задач

на несколько общих методов улучшения полного перебора.

Способы решения "переборных" задач можно разбить

удовлетворительным. Алгоритмы, дающие такие решения, называются

решение, а некоторое приближение к нему может оказаться

работать за приемлемое время на реальных данных. Во-вторых, не точное

так, что алгоритм, оставаясь в худшем случае экспоненциальным, будет

В таком случае, во-первых, иногда возможно сократить полный перебор

Иногда возникшую NP-полную задачу приходится решать.

Методы решения труднорешаемых задач

ДИСКРЕТНАЯ МАТЕМАТИКА: АЛГОРИТМЫ

КАФЕДРА КОМПЬЮТЕРНЫХ ТЕХНОЛОГИЙ

ФАКУЛЬТЕТ ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ И ПРОГРАММИРОВАНИЯ

ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ, МЕХАНИКИ И ОПТИКИ

САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

Дискретная математика: алгоритмы. Методы решения труднорешаемых задач