Однако, как между информированными, так и неинформированными методами поиска, информированный поиск является более эффективным и экономически эффективным.
Сравнительная таблица
| Основа для сравнения | Информированный поиск | Неинформированный поиск |
|---|---|---|
| основной | Использует знания, чтобы найти шаги к решению. | Нет использования знаний |
| КПД | Высокоэффективен, так как потребляет меньше времени и средств. | Эффективность является посреднической |
| Стоимость | Низкий | Сравнительно высокий |
| Спектакль | Находит решение быстрее | Скорость медленнее, чем информированный поиск |
| Алгоритмы | Поиск в глубину, поиск в ширину и поиск с наименьшей стоимостью | Эвристический поиск в глубину и поиск в ширину и поиск A * |
Определение информированного поиска
Техника информированного поиска использует специфические знания проблемы, чтобы дать ключ к решению проблемы. Этот тип стратегии поиска на самом деле не позволяет алгоритмам спотыкаться о цели и направлении решения. Информированный поиск может быть выгоден с точки зрения стоимости, когда оптимальность достигается при более низких затратах на поиск.
Для поиска оптимальной стоимости пути в графе путем реализации стратегии информированного поиска наиболее многообещающие узлы n вставляются в эвристическую функцию h (n). Затем функция возвращает неотрицательное действительное число, которое является приблизительной стоимостью пути, рассчитанной от узла n до целевого узла.
Здесь наиболее важной частью информированного метода является эвристическая функция, которая облегчает передачу дополнительных знаний о проблеме алгоритму. В результате это помогает найти путь к цели через различные соседние узлы. Существуют различные алгоритмы, основанные на информированном поиске, такие как эвристический поиск в глубину, эвристический поиск в ширину, A * поиск и так далее. Давайте теперь разберемся с эвристическим поиском в глубину.
Эвристическая глубина Первый поиск
Подобно методу поиска в глубину, приведенному ниже, эвристический метод поиска в глубину сначала выбирает путь, но проходит все пути от выбранного пути до выбора другого пути. Тем не менее, он выбирает лучший путь локально. В тех случаях, когда наименьшее эвристическое значение является приоритетом для границы, оно называется лучшим первым поиском.
Другой информированный алгоритм поиска - это поиск A *, который объединяет в себе концепцию с наименьшими затратами и с первыми поисками Этот метод учитывает как стоимость пути, так и эвристическую информацию в процессе поиска и выбора пути, который необходимо расширить. Предполагаемая общая стоимость пути, используемая для каждого пути, находящегося на границе от начала до целевого узла. Поэтому в нем одновременно используются две функции: стоимость (p) - это стоимость обнаруженного пути, а h (p) - это оценочное значение стоимости пути от начального узла до целевого узла.
Определение неинформированного поиска
Неинформированный поиск отличается от информированного поиска тем, что он просто дает определение проблемы, но не является дальнейшим шагом к поиску решения проблемы. Основная цель неинформированного поиска - провести различие между целевым и нецелевым состоянием, и он полностью игнорирует пункт назначения, к которому он направляется в пути, пока не обнаружит цель и не сообщит о преемнике. Эта стратегия также известна как слепой поиск.
В этой категории есть различные алгоритмы поиска, такие как поиск по глубине, поиск по равномерной стоимости, поиск по ширине и так далее. Давайте теперь разберемся в концепции неинформированного поиска с помощью поиска в глубину.
Глубина Первый Поиск
При глубоком первом поиске для добавления и удаления узлов используется стек «первым пришел - первым вышел». Только один узел добавляется или удаляется за один раз, и первый элемент, удаленный с границы стека, будет последним элементом, добавленным в стек. Использование стека на границе приводит к тому, что поиск путей в первую очередь продвигается глубже. Когда выполняется поиск кратчайшего и оптимального пути с использованием поиска в глубину, сначала создается путь, созданный соседними узлами, даже если он не является желаемым. Затем альтернативный путь ищется путем обратного отслеживания.
Другими словами, алгоритм выбирает первую альтернативу в каждом узле, затем возвращается к другой альтернативе, пока не пройдёт все пути от первого выбора. Это также поднимает проблему, когда поиск может прекратиться из-за бесконечных циклов (циклов), присутствующих в графе.
Ключевые различия между информированным и неинформированным поиском
- Прежний метод информированного поиска использует знания, чтобы найти решение. С другой стороны, последняя неосведомленная техника поиска не использует знания. Проще говоря, нет никакой дополнительной информации о решении.
- Эффективность информированного поиска лучше, чем неинформированный поиск.
- Неинформированный поиск требует больше времени и затрат, поскольку не имеет понятия о решении по сравнению с информированным поиском.
- Поиск в глубину, поиск в ширину и поиск с наименьшей стоимостью - это алгоритмы, относящиеся к категории неинформированного поиска. В отличие от этого, информированный поиск охватывает такие алгоритмы, как эвристический поиск в глубину, эвристический поиск в ширину и поиск A *.
Заключение
Информированный поиск обеспечивает направление относительно решения, в то время как при неинформированном поиске не дается никаких предложений относительно решения. Это делает неинформированный поиск более длительным при реализации алгоритма.
