Искусственный интеллект

11 Итж> Моею 15 Ростов Рис. 6. 2. Задача нахождения маршрута из Иванова в Москву: а — порядок монотонного поиска в ширину. Каждая вершина помечена ценой пути, ведущим в нее из начальной вершины (снаружи вершины) и номером ее получения в процессе поиска (внутри вершины). На последнем шаге монотонного поиска в ширину найдена целевая вершина с ценой пути, равным 10; б— пространство состояний, иллюстрирующее цену действий, соответствующую участкам пути между городами 141 6. Стратегии поиска 6.2.3. Поиск в глубину Рис. 6.3. Стратегия поиска в глубину При поиске в глубину, начиная с корневой вершины (корневая вершина находится на уровне 1), рассматриваются все инцидентные ей вершины уровня 2, начиная слева направо. Если удается найти среди них все целевые вершины, то на этом поиск прекращается. Если среди них не удается найти все целевые вершины, а максимальная глубина дерева еще не достигнута, то берется самая левая вершина уровня 2 и рассматриваются все инцидентные ей вершины уровня 3 слева направо. Если после этого все целевые вершины все еще не найдены, то берется самая левая вершина из уровня 3. Затем снова рассмат-риваются все иниидентные ей вершины уровня 3 слева направо и так до тех пор, пока либо не будут найдены все целевые вершины, либо достигнута максимальная глубина дерева, на которой в соответствии с рассматриваемой процедурой просмотрены все вершины, инцидентные самой левой вершине предыдущего уровня, и все целевые все еще не найдены. В последнем случае осуществляется подъем по дереву на один уровень вверх, выбор на этом уровне самой левой вершины, инцидентные которой вершины следующего уровня еще не рассмотрены, и поиск дальше среди целевых вершин по тому же принципу. И так до тех пор, пока все вершины дерева не будут рассмотрены. На рис. 6.3 показана последовательность поиска в глубину для дерева с тремя уровнями и степенью ветвления 2. Вершины на этом рисунке пронумерованы в соответствии с последовательностью их просмотра.