- Задачи распознавания свойств
- Класс задач распознавания свойств (ЗРС) – множество проблем, решением которых является ответ «Да» или «Нет».
- ГАМИЛЬТОНОВ ЦИКЛ (ГЦ).
- Задан граф G = (V, E).
- Спрашивается, содержит ли G гамильтонов цикл?
- Opt задаче max{f(x) : x D} соответствует ЗРС:
- « ли решение x D: f(x) Q?», где Q – заданное число.
- КОММИВОЯЖЕР (КМ). Дано:
- N – список городов;
- cij – расстояния между городами i,j N; B R.
- ли гамильтонов контур, длина которого B?
- Под общей (массовой) задачей (проблемой) P понимается некоторый общий вопрос, требующий ответа.
- Общая задача, как правило, содержит некоторые параметры. В задаче КМ, например, это расстояния между городами.
- Если все параметры общей задачи принимают конкретные значения, то такую задачу называют индивидуальной.
- Количество символов в стандартном (двоичном)
- представлении данных инд. задачи XP наз. длиной входа
- и обозначим L(X).
- наз. трудоемкостью алг. A.
- , где d – целое положительное число
- Алг., трудоемкость которого не ограничена полиномом от длины входа, наз. экспоненциальным.
- Пусть алг. A решает проблему P и tA(X) количество элементарных операций, выполняемых алгоритмом A при решении инд. задачи XP. Тогда функция
- Алг. A наз.
Do'stlaringiz bilan baham: |