Читайте также:
|
· Рассмотрим задачу коммивояжера, заключающуюся в том, что он должен посетить всех покупателей, проживающих в различных городах, не превысив при этом установленной сметы. Таким образом, данная задача сводится к нахождению пути, суммарная протяжённость которого не превысит определённой величины.
· Традиционное решение данной задачи заключается в систематическом рассмотрении возможных путей, сравнении их протяжённости с некоторым пределом, пока не будет найден приемлемый вариант или не будут рассмотрены все возможности.
· Данный подход не имеет полиномиального временного решения следовательно, данное решение задачи коммивояжёра является непрактичным, особенно если необходимо посетить много городов.
· Для решения этой задачи за разумное время необходимо найти более быстрый алгоритм. Мы можем получить последовательность задач которая не будет являться алгоритмом в техническом смысле. Говорят, что подобные команды недетерминированы, поэтому мы будем называть такой «алгоритм» недетерминированным алгоритмом. Но время, необходимое на выполнение недетерминированного алгоритма ограниченно кокой-то полиномиальной функцией. При использовании недетерминированного алгоритма появляется возможность решения задачи коммивояжёра за полиномиальное время.
Дата добавления: 2015-07-11; просмотров: 99 | Нарушение авторских прав