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

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

Каждой задаче поиска также соответствует соответствующая проблема решения , а именно:

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

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

Более формально, отношение R можно рассматривать как задачу поиска, и говорят, что машина Тьюринга, вычисляющая R, также решает ее. Более формально, если R — бинарное отношение такое, что поле( R ) ⊆ Γ ⁺ и T — машина Тьюринга , то T вычисляет R , если:

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

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

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

Определение

Проблема поиска часто характеризуется:

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

Цель

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

Метод поиска

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

   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 .