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

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

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

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

• 1 Определение
• 2 Цель
• 3 Метод поиска
• 4 См. Также
• 5 Ссылки

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

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

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

• A функцией-преемником

отображением из состояния к набору новых состояний

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

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

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

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

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