8125

Методы неинформированного поиска. Поиск в ширину, в глубину, однородной стоимости, ограниченный по глубине поиск

Лекция

Информатика, кибернетика и программирование

Методы не информированного поиска. Поиск в ширину,в глубину, однородной стоимости, ограниченный по глубине поиск. Основная проблема в области поиска - нахождение хорошей стратегии поиска для заданной задачи. Страт...

Русский

2013-02-04

142.53 KB

33 чел.

2

Методы неинформированного поиска. Поиск в ширину, в глубину, однородной стоимости, ограниченный по глубине поиск.

Основная проблема в области поисканахождение хорошей стратегии поиска для заданной задачи.

Стратегии принято оценивать с помощью 4 критериев:

  •  Полнотагарантированное нахождение решения, если оно существует;
  •  Временная сложностьвремя поиска решения конкретной задачи;
  •  Емкостная сложностьзатраты памяти;
  •  Оптимальностьспособность находить наилучшее решение (решение минимальной стоимости).

Стратегии поиска в пространства состояний принято делить на две группы:

  1.  Стратегии неинформированного (слепого) поиска.
  2.  Стратегии информированного поиска (эвристические cтратегии).

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

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

Стратегии неинформированного поиска

Поиск (сначала) в ширину.

Сначала раскрывается вершинакорень в дереве поиска. Затем все вершинынепосредственные потомки корня и т.д. Вершины глубины d раскрываются раньше, чем вершины глубины (d+1). Пока есть хотя бы одна вершина глубины dнельзя раскрывать вершину на глубине d+1. Поиск в ширину может быть реализован алгоритмом General-Search, в котором функция построения очереди помещает вновь сгенерированные вершины в конец очереди.

function Breadth-First-Search(Problem) returns solution or failure

return General-Search(Problem, En-queue-At-End)

Cтратегия помещает вновь сгенерированные вершины в конец очереди.

Поиск в ширину:

гарантирует нахождение решения, если оно существует;

–первым всегда находит решение минимальной глубины.

Однако решение минимальной глубины не всегда имеет минимальную стоимость.

Недостаток поиска в ширинубольшая сложность.

Пусть пространство поиска, в котором каждое состояние может быть раскрыто в b новых состояний. Тогда корень дерева генерирует b потомков, далее b2, затем b3 и так далее.

Следовательно, если решение лежит на глубине d, для нахождения решения потребуется раскрыть 1 + b + bb + bd вершин.

Порядок сложности поискаO(bd).

Оценим временную и емкостную сложность поиска при коэффициенте ветвления b=10 и глубине равной d. Пусть за одну секунду проверяется 1000 вершин (раскрываются и проверяются на достижение цели).

d

Вершины

Время

Память

0

мс

байт

2

,1 с

кбайт

4

с

Мбайт

6

6

18 м

Мбайт

8

8

ч

Гбайт

10

10

дн

Тбайт

12

12

лет

Тбайт

14

14

лет

Тбайт

Поиск по критерию стоимости.

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

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

g(n) –функция стоимости пути в  вершину n.

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

g(n) = depth(n).

Пример: Рассмотрим пути поиска в графе рис. 4.1.

Рис. 4.1.

Найти путь минимальной стоимости из S в G.

S

C

B

A

g(n)=5

g(n)=1

3


 

А также другие работы, которые могут Вас заинтересовать

25726. Сигналы в системах связи. Аналоговые и дискретные сигналы. Параметры сигнала 17 KB
  Аналоговые и дискретные сигналы. Параметры сигнала. Сигнал физический процесс отображающий несущий передаваемое сообщение.
25727. Частотное разделение сигналов 83.9 KB
  ФN спектры gK канальных сигналов занимают соответственно полосы частот 1 2 . Проследим основные этапы образования сигналов а также изменение этих сигналов в процессе передачи Рис. Преобразование спектров в системе с частотным разделением каналов Будем полагать что спектры индивидуальных сигналов конечны.
25728. Системы связи с временным разделением каналов 154.22 KB
  Временное разделение каналов Временное разделение каналов используется для передачи аналоговых и дискретных сообщений однако при этом требуется использовать методы импульсной модуляции. Схема системы передачи сообщений с временным разделением сигналов показана на рисунке 1. Тогда количество вырезанных из аналогового сигнала импульсов в секунду равно Для передачи речи амплитуда одного импульса может быть представлена 1 байтом т. Иными словами общая скорость передачи речи в виде двоичных сигналов 0 и 1 будет равна 8килобита.
25729. CDMA 52.13 KB
  В CDMA Code Division Multiple Access для каждого узла выделяется весь спектр частот и всё время. CDMA использует специальные коды для идентификации соединений. Телефоны CDMA имеют меньшую пиковую мощность излучения и потому возможно менее вредны. [править]Эволюция систем сотовой связи использующих технологию CDMA Технология множественного доступа с кодовым разделением каналов известна давно.
25730. Радиорелейные системы передачи информации. Классификация. Структурная схема РРЛ. Многоканальные РРЛ 2.6 MB
  Под радиосистемой передачи РСП понимают совокупность технических средств обеспечивающих образование типовых каналов передачи групповых трактов и линейного тракта по которому сигналы электросвязи передаются посредством распространения радиоволн в открытом пространстве. Существует множество различных классификаций РСП в зависимости от признаков положенных в их основу.По принадлежности к различным службам: РСП фиксированной службы радиосвязь между фиксированными пунктами; РСП радиовещательной службы передача сигнала для приема...
25731. Многоканальные системы связи. Общие понятия и обобщённая структурная схема многоканальной системы связи 78.86 KB
  Многоканальные системы связи. Общие понятия и обобщённая структурная схема многоканальной системы связи. Многоканальные системы связи это системы связи позволяющие передавать по одной линии связи большое число независимых сообщений т. Для унификации многоканальных систем связи за основной или стандартный канал принимают канал тональной частоты канал ТЧ обеспечивающий передачу сообщений с эффективно передаваемой полосой частот 3003400 Гц соответствующей основному спектру телефонного сигнала.
25732. Спутниковые системы связи. Классификация ИСЗ по особенностям орбиты. Спутниковые службы в системах связи 15.05 KB
  Классификация ИСЗ по особенностям орбиты. Использование ИСЗ позволяет резко повысить дальность радиосвязи тк ретранслятор располагается высоко над Землей. 3 основных вида ИСЗ: ИСЗ на высокой эллиптической орбите ВЭО ИСХ на геостационарной орбите ГЭО ИСЗ на низковысотной орбите НВО ВЭО Спутники типа молния с периодом обращения 12 часов наклоном орбиты 63 градуса высотой апогея над северным полушарием 40 тыс. В области апогея скорость движения ИСЗ замедляется и обеспечивается радиовидимость 68 часов.
25733. Распространение декаметровых волн 37.72 KB
  К диапазону KB декаметровые волны относят радиоволны с длиной волны от 100 до 10м. В отличие от более коротких волн которые распространяются земной волной декаметровые волны распространяются в основном путем отражении от ионосферы. Радиус действия земной волны в диапазоне коротких волн сравнительно невелик и при обычно используемых мощностях передатчиков не превышает нескольких десятков километров. Но короткие волны могут распространяться на многие тысячи километров путем многократных последовательных отражений от ионосферы и Земли и...