В задаче организации полета из Нью-Йорка в Лос-Анджелес могут быть два ограничивающих параметра, которые пассажиру хотелось бы свести к минимуму. Первый из них — это количество авиарейсов, необходимых, чтобы добраться до Лос-Анджелеса. А второй — это длина маршрута. Помните, что самый короткий маршрут — это не обязательно тот, который имеет минимальное количество авиарейсов[1]. В алгоритме поиска, ищущем в качестве первого решения маршрут с минимальным количеством авиарейсов[2], применяется следующая эвристика. Чем длиннее авиарейс,то тем больше вероятность того, что путешественник окажется ближе к месту назначения. Поэтому количество авиарейсов[3] сводится к минимуму.
На языке искусственного интеллекта это называется наискорейшим подъемом. Алгоритм наискорейшего подъема в качестве следующей выбирает вершину, которая, как ему кажется, ближе всего находится к цели (то есть дальше всего от текущей вершины). Своим названием алгоритм обязан вот чему. Представьте себе, что турист-пешеход на полпути к вершине заблудился в темноте. И хотя вокруг темно, но турист, зная, что его лагерь находится на вершине, может, следуя алгоритму наискорейшего подъема, найти свой лагерь. Просто он должен помнить, что каждый шаг наверх — это шаг в правильном направлении.
Применительно к базе данных авиарейсов, в программе, генерирующей маршруты, эвристику наискорейшего подъема можно использовать следующим образом. Среди авиарейсов, исходящих из текущей вершины, выбирайте самый дальний — в надежде, что он доставит ближе всего к месту назначения. Вот как для этого нужно модифицировать подпрограмму find():
/* Зная пункт отправления (параметр from), найти пункт прибытия
для самого дальнейшего авиарейса (параметр anywhere). */
int find(char *from, char *anywhere)
{
int pos, dist;
pos=dist = 0;
find_pos = 0;
while(find_pos < f_pos) {
if(!strcmp(flight[find_pos].from, from) &&
!flight[find_pos].skip) {
if(flight[find_pos].distance>dist) {
pos = find_pos;
dist = flight[find_pos].distance;
}
}
find_pos++;
}
if(pos) {
strcpy(anywhere, flight[pos].to);
flight[pos].skip = 1;
return flight[pos].distance;
}
return 0;
}
Теперь подпрограмма find() проводит поиск по всей базе данных, отыскивая самый дальний авиарейс из пункта вылета.
Вот вся программа, в которой используется алгоритм наискорейшего подъема:
/* Нискорейший подъем */
#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; /* not found */
}
/* Зная пункт отправления (параметр from), найти пункт прибытия
для самого дальнейшего авиарейса (параметр anywhere). */
int find(char *from, char *anywhere)
{
int pos, dist;
pos=dist = 0;
find_pos = 0;
while(find_pos < f_pos) {
if(!strcmp(flight[find_pos].from, from) &&
!flight[find_pos].skip) {
if(flight[find_pos].distance>dist) {
pos = find_pos;
dist = flight[find_pos].distance;
}
}
find_pos++;
}
if(pos) {
strcpy(anywhere, flight[pos].to);
flight[pos].skip = 1;
return flight[pos].distance;
}
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");
}
В результате выполнения программы получается такое решение:
Нью-Йорк - Денвер - Лос-Анджелес Расстояние в милях равно 2900.
Оно довольно-таки хорошее! В полученном маршруте количество пересадок минимально (только одна), и он достаточно близок к самому короткому маршруту. Более того, программа приближается к решению, не тратя времени и усилий на обширные возвраты.
Однако если бы отсутствовал авиарейс между Денвером и Лос-Анджелесом, то решение не было бы таким хорошим. Это был бы маршрут Нью-Йорк — Денвер — Хьюстон — Лос-Анджелес общей протяженностью 4900 миль! При получении решения пришлось бы делать восхождение на ложный максимум. Как можно легко увидеть, перелет в Хьюстон не приблизит нас к цели, то есть к Лос-Анджелесу. На рис. 25.7 показано как первое решение, так и путь к ложному максимуму.
| Страница №8 |
Наискорейший подъем дает во многих случаях достаточно хорошие решения, потому что обычно перед тем как решение будет найдено, надо посещать сравнительно мало вершин. Однако у этого метода могут быть такие три недостатка. Во-первых, имеется проблема ложных максимумов, которой мы просто по счастливой случайности смогли избежать во втором решении нашего примера. Именно для того чтобы избежать ложных максимумов, при поиске решения приходится широко использовать возвраты. Вторая проблема связана с "плато" — ситуациями, когда все следующие шаги выглядят одинаково хорошими (или плохими). В таком случае наискорейший подъем будет не лучше, чем поиск в глубину. И последней проблемой является "горный хребет". В таком случае наискорейший подъем проходит плохо, так как алгоритм при возвратах заставляет несколько раз пересекать "горный хребет".
Но несмотря на возможные проблемы, наискорейший подъем, как правило, быстрее любого неэвристического метода приводит к решению, которое близко к оптимальному.
[1]Действительно, пересадок может быть мало (например, всего лишь одна), но иногда лучше совершить несколько коротких перелетов, чем два длинных.
[2]Т.е. маршрут с минимальным количеством пересадок.
[3]Т.е. количество проходимых ребер графа.