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

В теории сложности вычислений и теории вычислимости , задача поиска является типом вычислительной задачи представляется бинарным отношением . Если 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, решает ее. Каждой поисковой задаче соответствует проблема решения , а именно:

${\ Displaystyle L (R) = \ {х \ середина \ существует yR (x, y) \}. \,}$

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

Определение

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

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

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

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

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

Задача

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

Метод поиска

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

   Input: a graph,
       a set of start nodes,
       Boolean procedure goal(n) that tests if n is a goal node.
   frontier := {s : s is a start node};
   while frontier is not empty:
       select and remove path <n0, ..., nk> from frontier;
       if goal(nk)
           return <n0, ..., nk>;
       for every neighbor n of nk
           add <n0, ..., nk, n> to frontier;
   end while

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

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

Ссылки

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