Спонсоры сайта:

Наличие этой страницы в поиске?

Информеры ТИЦ и PR

  Yandex ТИЦ:  
   Google PR:  

Путешественникам, меломанам, бизнесменам, вебмастерам, новости.

Содержание | <<< | >>>

Поиск методом наискорейшего подъема





В задаче организации полета из Нью-Йорка в Лос-Анджелес могут быть два ограничивающих параметра, которые пассажиру хотелось бы свести к минимуму. Первый из них — это количество авиарейсов, необходимых, чтобы добраться до Лос-Анджелеса. А второй — это длина маршрута. Помните, что самый короткий маршрут — это не обязательно тот, который имеет минимальное количество авиарейсов[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 показано как первое решение, так и путь к ложному максимуму.

Рис. 25.7. Пути к решению и на ложный максимум, найденные с помощью наискорейшего подъема

Страница №8

Анализ наискорейшего подъема

Наискорейший подъем дает во многих случаях достаточно хорошие решения, потому что обычно перед тем как решение будет найдено, надо посещать сравнительно мало вершин. Однако у этого метода могут быть такие три недостатка. Во-первых, имеется проблема ложных максимумов, которой мы просто по счастливой случайности смогли избежать во втором решении нашего примера. Именно для того чтобы избежать ложных максимумов, при поиске решения приходится широко использовать возвраты. Вторая проблема связана с "плато" — ситуациями, когда все следующие шаги выглядят одинаково хорошими (или плохими). В таком случае наискорейший подъем будет не лучше, чем поиск в глубину. И последней проблемой является "горный хребет". В таком случае наискорейший подъем проходит плохо, так как алгоритм при возвратах заставляет несколько раз пересекать "горный хребет".

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

----------

[1]Действительно, пересадок может быть мало (например, всего лишь одна), но иногда лучше совершить несколько коротких перелетов, чем два длинных.

[2]Т.е. маршрут с минимальным количеством пересадок.

[3]Т.е. количество проходимых ребер графа.


Содержание | <<< | >>>

C++ исходники. Все примеры - рабочие:

часы:

Dev C++ WinAPI Стрелочные часы Analog Clock

Dev C++ WinAPI Цифровые прозрачные часы. Текст на рабочем столе. Digital transparent clock. Text on desktop

Dev C++ OLE WinApi CALENDAR and DIGITAL CLOCK (15kb). Календарь и цифровые часы

Dev C++ OLE WinAPI Календарь и цифровые часы почти Vista SideBar всего 21kb

плееры:

Microsoft Visual C++ 2008 Direct Show DVD Mini Player 10.5kb

Dev C++ WinAPI Микро медиа плеер 3.5kb

Dev C++ WinAPI Мини медиа плеер 4.5kb

Dev C++ WinAPI Hint Всплывающая подсказка

Dev C++ WinAPI RECT - имитатор кнопки

Dev C++ WinAPI Заполнить ListBox

Dev C++ WinAPI Заполнить, редактировать, сохранить, загрузить ListBox (PlayList)

Dev C++ WinAPI Индикатор уровня

Dev C++ WinAPI MP3 Микро плеер Открыть с помощью...

Dev C++ WinAPI Своя кнопка

изображения:

Dev C++ GDI+ WinAPI Mini FotoResizer (16kb), изменяет размеры всех фото (JPG) до указанного размера в выбраной папке и её подпапках

Dev C++ WinAPI Сохранить BITMAP экрана, десктопа, окна, клиентской области.

Dev C++ WinAPI Изменить размер изображения BMP RESIZE. Загрузка изображений из ФАЙЛА, вывод на экран и сохранение в файл.

Dev C++ WinAPI Загрузка изображений из РЕСУРСОВ и вывод на экран.

Dev C++ GDI+ WinAPI. Преобразовать изображения из одного формата в другой (JPG в BMP, GIF, PNG и обратно ), используя дополнительные библиотеки GDI+. Загрузка изображений из файла и сохранение в файл.

Dev C++ GDI+ WinAPI масштабирование JPG RESIZE

Dev C++ OLE WinAPI. Преобразовать изображения из JPG в BMP, используя дополнительные библиотеки OLE. Загрузка изображений из РЕСУРСОВ и сохранение в файл.

Dev C++ OLE WinAPI преобразовать JPG в BMP, используя дополнительные библиотеки OLE. Загрузка изображений из ФАЙЛА и сохранение в файл.

Dev C++ OLE WinAPI масштабирование BMP RESIZE

разное:

Dev C++ WinAPI Dev C++ Преобразовать цвет точки экрана в HTML код

Dev C++ WinAPI NOTIFYICONDATA WS_EX_TOOLWINDOW Иконка в области уведомлений (notification area, tray, трей). Удалить с панели задач (taskbar).

Dev C++ WinAPI ShellExecute Создать ссылку на WEB сайт

Dev C++ WinAPI ShellExecute Создать окно со ссылкой на WEB сайт

Dev C++ WinAPI CreateProcess ShellExecute WinExec Запуск приложения из приложения

Dev C++ OLE WinAPI Создать регион Regions PopUp Меню Menu

Dev C++ FindFiles. Поиск файлов заданного типа (в примере *.JPG) в папке и её подпапках

библиотеки:

Скачать библиотеку GDI+ для Dev C++

Скачать справочнник с примерами языка C.