Проблема поиска - Search problem

В теория сложности вычислений и теория вычислимости, а проблема поиска это тип вычислительная проблема представлен бинарное отношение. Если р является бинарным отношением такое, что поле (р) ⊆ Γ⁺ и Т это Машина Тьюринга, тогда Т вычисляет р если:

• Если Икс такое, что есть некоторые у такой, что р(Икс, у) тогда Т принимает Икс с выходом z такой, что р(Икс, z) (может быть несколько у, и Т нужно только найти один из них)
• Если Икс такое, что нет у такой, что р(Икс, у) тогда Т отвергает Икс

Интуитивно проблема состоит в том, чтобы найти структуру «y» в объекте «x». An алгоритм считается, что он решает проблему, если существует хотя бы одна соответствующая структура, а затем выводится одно вхождение этой структуры; в противном случае алгоритм останавливается с соответствующим выводом («Элемент не найден» или любое подобное сообщение).

Такие проблемы очень часто возникают в теория графов, например, где поиск в графах структур, таких как соответствие, клики, независимый набор и т. д. представляют интерес.

Обратите внимание, что график частичной функции является бинарным отношением, и если Т вычисляет частичную функцию, тогда существует не более одного возможного выхода.

Отношение р можно рассматривать как задачу поиска, а машину Тьюринга, которая вычисляет р также говорят, чтобы решить эту проблему. Каждой поисковой задаче соответствует проблема решения, а именно

${\displaystyle L(R)=\{x\mid \exists yR(x,y)\}.\,}$

Это определение можно обобщить на п-арные отношения, использующие любую подходящую кодировку, которая позволяет сжать несколько строк в одну строку (например, перечисляя их последовательно с разделителем).

Определение

Проблема поиска определяется:^[1]

• Набор состояния
• А начальное состояние
• А состояние цели или тест цели

логическая функция, которая сообщает нам, является ли данное состояние целевым.

• А функция преемника

отображение состояния на набор новых состояний

Цель

Найдите решение, если вам не дан алгоритм решения проблемы, а только спецификация того, как выглядит решение.^[1]

Метод поиска

• Общий алгоритм поиска: учитывая график, начальные узлы и целевые узлы, постепенно исследуйте пути от начальных узлов.
• Поддерживайте границы изученных путей от начального узла.
• По мере того, как поиск продолжается, граница расширяется до неисследованных узлов, пока не встретится целевой узел.
• Способ расширения границы определяет стратегию поиска.^[1]

   Входные данные: граф, набор начальных узлов, логическая цель процедуры (n), которая проверяет, является ли n целевым узлом. frontier: = {s: s - начальный узел}; пока граница не пуста: выберите и удалите путь  из границы; если цель (nk) return ; для каждого соседа n из nk добавить  к границе; конец пока

Смотрите также

• Оператор неограниченного поиска
• Проблема решения
• Проблема оптимизации
• Проблема подсчета (сложность)
• Функциональная проблема
• Искать игры

Рекомендации

1. Лейтон-Браун, Кевин. "Поиск граф" (PDF). ubc. Получено 7 февраля 2013.

В эту статью включены материалы из задачи поиска по PlanetMath, который находится под лицензией Лицензия Creative Commons Attribution / Share-Alike.