При поиске в глубину каждая из цепочек, которые могут привести к решению, проверяется до своего листа, а лишь затем начинается проверка следующей цепочки (т.е. пути). Чтобы более точно представить себе, как работает такой поиск, проанализируйте следующее дерево. Целью является вершина F.
| Страница №4 |
При поиске в глубину вершины графа обходятся в порядке ABDBEBACF. Если вы знакомы с деревьями, то увидите, что в этом виде поиска используется разновидность обхода неориентированного дерева. То есть путь продолжается налево до тех пор, пока не будет достигнут лист или не будет найдена цель. Если лист достигнут, то путь поворачивает назад, поднимается на один уровень вверх, затем продолжается направо, потом снова влево, пока не встретится цель или очередной лист. А вся эта процедура продолжается до тех пор, пока не будет найдена цель или не проверена последняя вершина области поиска.
Как видите, поиск в глубину, — это такой метод поиска цели, который в наихудшем случае вырождается в исчерпывающий поиск. В нашем примере это случится тогда, когда целью является вершина G.
В С-программе, предназначенной для выбора маршрута из Нью-Йорка в Лос-Анджелес, используется база данных с информацией об авиарейсах компании XYZ Airlines. Каждая запись этой базы содержит сведения о городе-пункте вылета и городе-пункте прибытия, о расстоянии между ними, а также флаг, который помогает при поиске с возвратом (вы скоро увидите, каким именно образом). Вся эта информация хранится в следующей структуре:
#define MAX 100
/* структура базы данных авиарейсов */
struct FL {
char from[20];
char to[20];
int distance;
char skip; /* используется при поиске с возвратом */
};
struct FL flight[MAX]; /* массив структур БД */
int f_pos = 0; /* количество записей в БД авиарейсов */
int find_pos = 0; /* индекс для поиска в БД авиарейсов */
Отдельные записи вводятся в базу данных с помощью функции assert_flight(), а всю информацию об авиарейсах инициализирует функция setup(). Индекс последней записи базы данных сохраняется в глобальной переменной f_pos. Вот код нужных нам функций:
void setup(void)
{
assert_flight("Нью-Йорк", "Чикаго", 1000);
assert_flight("Чикаго", "Денвер", 1000);
assert_flight("Нью-Йорк", "Торонто", 800);
assert_flight("Нью-Йорк", "Денвер", 1900);
assert_flight("Торонто", "Калгари", 1500);
assert_flight("Торонто", "Лос-Анжелес", 1800);
assert_flight("Торонто", "Чикаго", 500);
assert_flight("Денвер", "Урбана", 1000);
assert_flight("Денвер", "Хьюстон", 1500);
assert_flight("Хьюстон", "Лос-Анжелес", 1500);
assert_flight("Денвер", "Лос-Анжелес", 1000);
}
/* Запись данных в базу. */
void assert_flight(char *from, char *to, int dist)
{
if(f_pos < MAX) {
strcpy(flight[f_pos].from, from);
strcpy(flight[f_pos].to, to);
flight[f_pos].distance = dist;
flight[f_pos].skip = 0;
f_pos++;
}
else printf("База данных авиаресов переполнена.\n");
}
Чтобы следовать духу науки об искусственном интеллекте (ИИ), считайте, что в базе данных содержатся "факты". Создаваемая программа будет с помощью этих "фактов" приближаться к решению. По этой причине многие исследователи искусственного интеллекта называют базы данных "базами знаний". В данной главе эти понятия используются как взаимозаменяемые.
Для написания кода, выполняющего поиск маршрута из Нью-Йорка в Лос-Анджелес, потребуется несколько вспомогательных функций. Во-первых, нужна подпрограмма для определения того, имеется ли авиарейс между двумя городами или нет. Эта функция называется match(); она возвращает расстояние между двумя городами, если такой авиарейс есть и ноль, если такого рейса нет. Вот эта функция:
/* Если между двумя городами имеется авиарейс, то возвращается
расстояние между ними, а в противном случае возвращается 0. */
int match(char *from, char *to)
{
register int t;
for(t=f_pos-1; t > -1; t--)
if(!strcmp(flight[t].from, from) &&
!strcmp(flight[t].to, to)) return flight[t].distance;
return 0; /* не найден */
}
Другой необходимой подпрограммой является find(). Эта функция ищет в базе данных какой-либо авиарейс из указанного города. Если авиарейс с каким-либо другим городом найден, то возвращаются название этого города и расстояние до него от первого города, в противном же случае возвращается нуль. Вот текст подпрограммы find():
/* Зная пункт отправления (параметр from), найти пункт прибытия
(параметр anywhere). */
int find(char *from, char *anywhere)
{
find_pos = 0;
while(find_pos < f_pos) {
if(!strcmp(flight[find_pos].from, from) &&
!flight[find_pos].skip) {
strcpy(anywhere, flight[find_pos].to);
flight[find_pos].skip = 1; /* активизировать */
return flight[find_pos].distance;
}
find_pos++;
}
return 0;
}
Как видите, если поле skip (пропустить) имеет значение 1, то авиарейс между городами не выбирается. Кроме того, когда авиарейс найден, то его поле skip отмечается как активное — таким образом реализуется поиск с возвратом из тупиков.
Поиск с возвратом — это очень важная часть многих методов, используемых в системах искусственного интеллекта. Он выполняется с помощью рекурсивных подпрограмм и с помощью специального стека для поиска с возвратом. Почти во всех ситуациях, связанных с возвратом к предыдущему состоянию, используется нечто, похожее на стек, — то есть нечто, работающее по принципу "последним пришел — первым вышел". При проходе по пути все встретившиеся на нем вершины помещаются в стек. При достижении листа, наоборот, происходит как бы остановка без возможности повторного пуска (в глубину) и из стека извлекается последняя помещенная туда вершина и исследуется новый путь, который начинается с этой вершины. Этот процесс продолжается до тех пор, пока не будет найдена цель или не будут исследованы все пути. Далее представлены функции push() и pop() (означают соответственно "поместить в стек, положить в стек, сохранить в стеке" и "выталкивать из стека, снимать со стека, вынимать из стека, считывать из стека"), которые управляют стеком, используемым для поиска с возвратом. Массив, в котором хранятся значения, заталкиваемые в стек, представлен глобальной переменной bt_stack, а указатель на вершину стека — глобальной переменной tos. Именно эти переменные используют данные функции при обращении к стеку.
/* Подпрограмма обращения к стеку */
void push(char *from, char *to, int dist)
{
if(tos < MAX) {
strcpy(bt_stack[tos].from, from);
strcpy(bt_stack[tos].to, to);
bt_stack[tos].dist = dist;
tos++;
}
else printf("Стек заполнен.\n");
}
void pop(char *from, char *to, int *dist)
{
if(tos > 0) {
tos--;
strcpy(from, bt_stack[tos].from);
strcpy(to, bt_stack[tos].to);
*dist = bt_stack[tos].dist;
}
else printf("Стек пуст.\n");
}
Теперь, когда написаны необходимые вспомогательные подпрограммы, проанализируйте следующий код. Он определяет функцию isflight() — главную подпрограмму для поиска маршрута из Нью-Йорка в Лос-Анджелес.
/* Определить, имеется ли маршрут между из города, на который указывает
параметр from (из) в город, на который указывает параметр to (в). */
void isflight(char *from, char *to)
{
int d, dist;
char anywhere[20];
/* посмотреть, является ли городом-пунктом прибытия */
if(d=match(from, to)) {
push(from, to, d);
return;
}
/* проверить другой авиарейс */
if(dist=find(from, anywhere)) {
push(from, to, dist);
isflight(anywhere, to);
}
else if(tos > 0) {
/* поиск с возвратом */
pop(from, to, &dist);
isflight(from, to);
}
}
Эта подпрограмма работает следующим образом. Во-первых, функция match() проверяет базу данных — нет ли в ней авиарейса между городами, на которые указывают параметры from и to. Если такой авиарейс имеется, то цель поиска достигнута — данные по авиарейсу помещаются в стек и функция возвращает управление. В противном случае функция find() проверяет, нет ли авиарейса между городом, на который указывает from, и каким-нибудь другим городом. Если есть, то соответствующие данные помещаются в стек и рекурсивно вызывается isflight(). В противном случае выполняется поиск с возвратом. Предыдущая вершина удаляется из стека, и рекурсивно вызывается isflight(). Этот процесс повторяется до тех пор, пока не будет найдена цель. Поле skip используется при поиске с возвратом, чтобы не проверялись повторно одни и те же авиарейсы.
Поэтому если подпрограмму вызвать с такими параметрами, как "Денвер" и "Хьюстон", то первое условие оператора if будет истинным и isflight() завершит свою работу. Предположим теперь, что isflight() вызывается с параметрами "Чикаго" и "Хьюстон". В таком случае первое условие оператора if не будет истинным, так как авиарейса между этими городами нет. Поэтому второе условие оператора if проверяет наличие авиарейса из Чикаго в какой-либо другой город. В нашем примере из Чикаго имеется авиарейс в Денвер, поэтому isflight() рекурсивно вызывается с параметрами "Денвер" и "Хьюстон". И опять проверяется первое условие. Оно выполнено: на этот раз авиарейс найден! Наконец, все рекурсивные вызовы можно завершить, и isflight() заканчивает свою работу. Проанализируйте — используемая здесь функция isflight() ведет в базе знаний поиск в глубину.
Важно понять, что isflight() на самом деле не возвращает решение — она его генерирует. При выходе из функции isflight() в стеке, используемом для поиска с возвратом, находится готовый маршрут между Чикаго и Хьюстоном, то есть собственно решение. В действительности успешное или неудачное выполнение isflight() определяется состоянием стека. Пустой стек указывает на неудачу; в противном же случае в стеке будет находиться решение. Поэтому для завершения всей программы нужна еще одна функция. Эта функция называется route(), именно она выводит как путь, так и общее расстояние. Рассмотрим эту функцию:
/* Вывести маршрут и общее расстояние. */
void route(char *to)
{
int dist, t;
dist = 0;
t = 0;
while(t < tos) {
printf("%s to ", bt_stack[t].from);
dist += bt_stack[t].dist;
t++;
}
printf("%s\n", to);
printf("Расстояние в милях равно %d.\n", dist);
}
Далле следует вся программа, использующая поиск в глубину:
/* Поиск в глубину. */
#include <stdio.h>
#include <string.h>
#define MAX 100
/* структура базы данных авиарейсов */
struct FL {
char from[20];
char to[20];
int distance;
char skip; /* используется при поиске с возвратом */
};
struct FL flight[MAX]; /* массив структур БД */
int f_pos = 0; /* количество записей в БД авиарейсов */
int find_pos = 0; /* индекс для поиска в БД авиарейсов */
int tos = 0; /* вершина стека */
struct stack {
char from[20];
char to[20];
int dist;
} ;
struct stack bt_stack[MAX]; /* стек, используемый для посика
с возвратом */
void setup(void), route(char *to);
void assert_flight(char *from, char *to, int dist);
void push(char *from, char *to, int dist);
void pop(char *from, char *to, int *dist);
void isflight(char *from, char *to);
int find(char *from, char *anywhere);
int match(char *from, char *to);
int main(void)
{
char from[20], to[20];
setup();
printf("Пункт вылета: ");
gets(from);
printf("Пункт прибытия: ");
gets(to);
isflight(from,to);
route(to);
return 0;
}
/* Инициализация базы данных авиаресов. */
void setup(void)
{
assert_flight("Нью-Йорк", "Чикаго", 1000);
assert_flight("Чикаго", "Денвер", 1000);
assert_flight("Нью-Йорк", "Торонто", 800);
assert_flight("Нью-Йорк", "Денвер", 1900);
assert_flight("Торонто", "Калгари", 1500);
assert_flight("Торонто", "Лос-Анжелес", 1800);
assert_flight("Торонто", "Чикаго", 500);
assert_flight("Денвер", "Урбана", 1000);
assert_flight("Денвер", "Хьюстон", 1500);
assert_flight("Хьюстон", "Лос-Анжелес", 1500);
assert_flight("Денвер", "Лос-Анжелес", 1000);
}
/* Запомнить данные в базе. */
void assert_flight(char *from, char *to, int dist)
{
if(f_pos < MAX) {
strcpy(flight[f_pos].from, from);
strcpy(flight[f_pos].to, to);
flight[f_pos].distance = dist;
flight[f_pos].skip = 0;
f_pos++;
}
else printf("База данных авиарейсов заполнена.\n");
}
/* Показать маршрут и общее расстояние. */
void route(char *to)
{
int dist, t;
dist = 0;
t = 0;
while(t < tos) {
printf("%s to ", bt_stack[t].from);
dist += bt_stack[t].dist;
t++;
}
printf("%s\n", to);
printf("Расстояние в милях равно %d.\n", dist);
}
/* Если между двумя городами имеется авиарейс, то возвращается
расстояние между ними, а в противном случае возвращается 0. */
int match(char *from, char *to)
{
register int t;
for(t=f_pos-1; t > -1; t--)
if(!strcmp(flight[t].from, from) &&
!strcmp(flight[t].to, to)) return flight[t].distance;
return 0; /* не найден */
}
/* Зная пункт отправления (параметр from), найти пункт прибытия
(параметр anywhere). */
int find(char *from, char *anywhere)
{
find_pos = 0;
while(find_pos < f_pos) {
if(!strcmp(flight[find_pos].from,from) &&
!flight[find_pos].skip) {
strcpy(anywhere,flight[find_pos].to);
flight[find_pos].skip = 1; /* активизировать */
return flight[find_pos].distance;
}
find_pos++;
}
return 0;
}
/* Определить, имеется ли маршрут между из города, на который указывает
параметр from (из) в город, на который указывает параметр to (в). */
void isflight(char *from, char *to)
{
int d, dist;
char anywhere[20];
/* является ли пунктом прибытия */
if(d=match(from, to)) {
push(from, to, d);
return;
}
/* проверить другой авиарейс */
if(dist=find(from, anywhere)) {
push(from, to, dist);
isflight(anywhere, to);
}
else if(tos > 0) {
/* поиск с возвратом */
pop(from, to, &dist);
isflight(from, to);
}
}
/* Подпрограммы обращения к стеку */
void push(char *from, char *to, int dist)
{
if(tos < MAX) {
strcpy(bt_stack[tos].from,from);
strcpy(bt_stack[tos].to,to);
bt_stack[tos].dist = dist;
tos++;
}
else printf("Стек заполнен.\n");
}
void pop(char *from, char *to, int *dist)
{
if(tos > 0) {
tos--;
strcpy(from,bt_stack[tos].from);
strcpy(to,bt_stack[tos].to);
*dist = bt_stack[tos].dist;
}
else printf("Стек пуст.\n");
}
Обратите внимание, что main() подсказывает ввести пункт вылета и пункт прибытия. Это означает, что программу можно использовать для определения маршрутов между любыми двумя городами. Однако в оставшейся части главы при анализе программы подразумевается, что вылет осуществляется из Нью-Йорка, а в качестве пункта назначения выбран Лос-Анджелес.
Если выбраны Нью-Йорк и Лос-Анджелес, то получится такое решение:
Нью-Йорк - Чикаго - Денвер - Лос-Анджелес Расстояние в милях равно 3000.
Цепочка, ведущая к решению и являющаяся собственно маршрутом, показана на рис. 25.5.
| Страница №5 |
На рис. 25.5 видно, что это действительно первое решение, которое можно найти с помощью поиска в глубину. Найденное нами решение не оптимально (оптимальное решение в данном случае — это маршрут Нью-Йорк — Торонто — Лос-Анджелес с расстоянием в 2600 миль), но плохим его тоже назвать нельзя.
Итак, с помощью поиска в глубину нам удалось найти достаточно хорошее решение. Кроме того, благодаря такому поиску именно в этой задаче было с первой попытки найдено решение без возврата, что уже считается очень хорошим показателем. Но то, что для достижения оптимального решения при поиске в глубину приходится пройти почти все вершины, — вот это уже не совсем хороший признак.
Обратите внимание, что если изучается особенно длинная ветвь, на конце которой нет решения, то эффективность поиска в глубину может оказаться весьма низкой. Тогда при рассматриваемом способе поиска теряется очень много времени, причем не только на изучение этой цепи, но и на возвращение по ней, чтобы можно было двигаться дальше к цели.