 | Эта статья поднимает множество проблем. Пожалуйста, помогите улучшить его или обсудите эти проблемы на странице обсуждения . ( Узнайте, как и когда удалить эти сообщения-шаблоны ) ( Узнайте, как и когда удалить этот шаблон сообщения )
|
В теории сложности вычислений и теории вычислимости , задача поиска является типом вычислительной задачи представляется бинарным отношением . Если R - бинарное отношение, такое что field ( R ) ⊆ Γ + и T - машина Тьюринга , то T вычисляет R, если:
- Если x таково, что существует некоторый y такой, что R ( x , y ), то T принимает x с выходом z таким образом, что R ( x , z ) (может быть несколько y , и T нужно найти только один из них)
- Если x таково, что не существует y такого, что R ( x , y ), то T отклоняет x
Интуитивно проблема состоит в том, чтобы найти структуру «y» в объекте «x». Алгоритм , как говорят , чтобы решить эту проблему , если по крайней мере одна соответствующая структура существует, и затем одно вхождение этой структуры производится выход; в противном случае алгоритм останавливается с соответствующим выводом («Элемент не найден» или любое подобное сообщение).
Такие проблемы очень часто возникают в теории графов , например, когда поиск в графах структур, таких как конкретное сопоставление , клики , независимое множество и т. Д., Представляет интерес.
Обратите внимание, что график частичной функции является бинарным отношением, и если T вычисляет частичную функцию, то существует не более одного возможного выхода.
Отношение R можно рассматривать как задачу поиска, и говорят, что машина Тьюринга, которая вычисляет R, решает ее. Каждой поисковой задаче соответствует соответствующая проблема решения , а именно:
Это определение может быть обобщено до n -арных отношений с использованием любой подходящей кодировки, которая позволяет сжимать несколько строк в одну строку (например, перечисляя их последовательно с разделителем).
Определение [ править ]
Проблема поиска определяется следующим образом: [1]
- Набор состояний
- Начальное состояние
- Состояние цели или тест цели
- логическая функция, которая сообщает нам, является ли данное состояние целевым.
- Функция преемника
- отображение состояния на набор новых состояний
Цель [ править ]
Найдите решение, если вам не дан алгоритм решения проблемы, а только описание того, как выглядит решение. [1]
Метод поиска [ править ]
- Общий алгоритм поиска: учитывая график, начальные узлы и целевые узлы, постепенно исследуйте пути от начальных узлов.
- Сохраняйте границы изученных путей от начального узла.
- По мере продолжения поиска граница расширяется до неисследованных узлов, пока не будет обнаружен целевой узел.
- Способ расширения границы определяет стратегию поиска. [1]
Вход: график, набор стартовых узлов, Логическая процедура goal (n), которая проверяет, является ли n целевым узлом. frontier: = {s: s - начальный узел}; пока граница не пуста: выбрать и удалить путь <n0, ..., nk> от границы; если цель (nk) return <n0, ..., nk>; для каждого соседа n из nk добавить <n0, ..., nk, n> к границе; конец покаСм. Также [ править ]
- Оператор неограниченного поиска
- Проблема решения
- Проблема оптимизации
- Проблема подсчета (сложность)
- Функциональная проблема
- Искать игры
Ссылки [ править ]
- ^ a b c Лейтон-Браун, Кевин. «Графический поиск» (PDF) . ubc . Проверено 7 февраля 2013 года .
В эту статью включены материалы из задачи поиска на PlanetMath , который находится под лицензией Creative Commons Attribution / Share-Alike License .
