Оглавление
Проблема поиска
-
Определение задачи поиска
- Задача поиска в математике – это бинарное отношение, которое представляет собой поиск структуры “y” в объекте “x”.
- Алгоритм решает задачу, если находит хотя бы одну соответствующую структуру, и останавливается с выводом “не найден” в противном случае.
-
Обобщение задачи поиска
- Определение задачи поиска может быть обобщено на n-арные отношения с помощью подходящей кодировки.
-
Машина Тьюринга как решение задачи поиска
- Машина Тьюринга, вычисляющая бинарное отношение R, считается решением задачи поиска.
- Если x удовлетворяет условию R (x, y), то машина Тьюринга принимает x с выводом z, удовлетворяющим R (x, z).
- Если x не удовлетворяет условию R (x, y), машина Тьюринга отвергает x.
-
Примеры задач поиска
- Задачи поиска часто возникают в теории графов и комбинаторной оптимизации для поиска определенных структур.
-
Характеристики задачи поиска
- Задача поиска включает в себя набор состояний, начальное состояние, целевое состояние или целевой тест, функцию-преемницу и цель.
- Метод поиска – это общий алгоритм, который исследует пути от начальных узлов, расширяя границы по мере продвижения.
-
Связанные понятия
- В статье упоминаются оператор неограниченного поиска, задача решения, задача оптимизации, задача подсчета и функциональная проблема.
- Также упоминаются поисковые игры.
-
Рекомендации
- Статья основана на материалах из поисковой задачи на PlanetMath и доступна под лицензией Creative Commons Attribution/Share-Alike.