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

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

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

  Yandex ТИЦ:  
   Google PR:  

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

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

Поиск "оптимального" решения





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

Перед тем как закончить изучение хорошо проработанного примера с маршрутами, проанализируйте программу, которая находит оптимальный маршрут при следующем ограничении: общее расстояние должно быть минимальным. Эта программа с помошью удаления путей генерирует разные решения, а с помощью поиска с использованием частичного пути минимальной стоимости получает путь с минимальным общим расстоянием. При нахождении самого короткого пути применяют такой принцип: из двух решений, старого и нового, сохраняется лишь то, которое короче. А когда новые решения больше не генерируются, то остается только оптимальное.

Чтобы реализовать этот алгоритм, необходимо серьезно изменить функцию route() и создать еще один стек. В новом стеке будет храниться текущее решение, а в конце работы — оптимальное. Этот стек называется solution (решение), а вот и сама измененная функция route():

/* Найти кратчайшее расстояние. */
int route(void)
{
  int dist, t;
  static int old_dist = 32000;

  if(!tos) return 0;  /* все сделано */
  t = 0;
  dist = 0;
  while(t < tos) {
    dist += bt_stack[t].dist;
    t++;
  }

  /* Если короче, то найти новое решение */
  if(dist<old_dist && dist) {
    t = 0;
    old_dist = dist;
    stos = 0; /* удалить старый маршрут из стека solution */
    while(t < tos) {
      spush(bt_stack[t].from, bt_stack[t].to, bt_stack[t].dist);
      t++;
    }
  }
  return dist;
}

Далее приводится вся программа. Обратите внимание на изменения в функции main() и на то, что в программу введена функция spush(), которая помещает вершины нового решения в стек решений (solution).

/* Поиск оптимального решения методом поиска частичного пути
   минимальной стоимости; некоторые маршруты удаляются.
*/
#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;     /* вершина стека */
int stos = 0;    /* вершина стека solution */

struct stack {
  char from[20];
  char to[20];
  int dist;
} ;

struct stack bt_stack[MAX]; /* стек, используемый для поиска */
struct stack solution[MAX]; /* хранит временные решения */

void setup(void);
int route(void);
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);
void spush(char *from, char *to, int dist);
int find(char *from, char *anywhere);
int match(char *from, char *to);

int main(void)
{
  char from[20], to[20];
  int t, d;

  setup();

  printf("From? ");
  gets(from);
  printf("To? ");
  gets(to);
  do {
    isflight(from, to);
    d = route();
    tos = 0;  /* возврат в исходное состояние стека,
                 используемого для поиска с возвратом */
  } while(d != 0);  /* пока алгоритм может новые решения */

  t = 0;
  printf("Оптимальное решение:\n");
  while(t < stos) {
    printf("%s to ", solution[t].from);
    d += solution[t].dist;
    t++;
  }
  printf("%s\n", to);
  printf("Расстояние в милях равно %d.\n", d);

  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");
}

/* Найти кратчайшее расстояние. */
int route(void)
{
  int dist, t;
  static int old_dist=32000;

  if(!tos) return 0;  /* все сделано */
  t = 0;
  dist = 0;
  while(t < tos) {
    dist += bt_stack[t].dist;
    t++;
  }

  /* Если короче, заменить новым решением */
  if(dist<old_dist && dist) {
    t = 0;
    old_dist = dist;
    stos = 0; /* удалить старый маршрут из стека solution */
    while(t < tos)  {
      spush(bt_stack[t].from, bt_stack[t].to, bt_stack[t].dist);
      t++;
    }
  }
  return dist;
}

/* Если между двумя городами (параметры from и to) имеется авиарейс,
   то возвращается расстояние между ними,
   а в противном случае возвращается 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");
}

/* Cтек решений (solution) */
void spush(char *from, char *to, int dist)
{
  if(stos < MAX) {
    strcpy(solution[stos].from, from);
    strcpy(solution[stos].to, to);
    solution[stos].dist = dist;
    stos++;
  }
  else printf("Стек для кратчайших маршрутов заполнен.\n");
}

В последнем методе есть один недостаток: обход по всем маршрутам продолжается вплоть до их листьев. Будь этот метод более совершенным, обход по маршруту немедленно прекращался бы тогда, когда длина найденной части маршрута достигала бы текущего минимума (или превосходила его). С учетом этого обстоятельства данную программу можно значительно улучшить.


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

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.