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

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

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

  Yandex ТИЦ:  
   Google PR:  

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

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

Поиск нескольких решений





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

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

Удаление путей

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

Чтобы найти несколько решений с помощью удаления путей, необходимо в программе поиска в глубину изменить функцию main():

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

  setup();

  printf("Пункт вылета: ");
  gets(from);
  printf("Пункт прибытия: ");
  gets(to);
  do {
    isflight(from, to);
    route(to);
    tos = 0;  /* сброс стека, используемого при поиске с возвратом */
  } while(getchar() != 'q'); /* для выхода вводится символ 'q' */

  return 0;
}

У каждого авиарейса, входящего в цепочку, ведущую к решению, будет помечено его поле skip. Следовательно, такие авиарейсы больше не будут найдены функцией find(), все авиарейсы, имеющиеся в решении, будут эффективно удалены. Перед поиском следующего решения нужно только сбрасывать переменную tos, ведь именно это на самом деле и очищает стек, используемый при поиске с возвратом. Метод удаления путей обнаруживает следующие решения:

Нью-Йорк - Чикаго - Денвер - Лос-Анджелес
Расстояние в милях равно 3000.
Нью-Йорк - Торонто - Лос-Анджелес
Расстояние в милях равно 2600.
Нью-Йорк - Денвер - Лос-Анджелес
Расстояние в милях равно 2900.

При поиске было найдено три наилучших решения. Однако этот результат нельзя обобщать, так как он зависит от размещения информации в базе данных и от конкретной ситуации.

Удаление вершин

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

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

  setup();

  printf("From? ");
  gets(from);
  printf("To? ");
  gets(to);
  do {
    isflight(from,to);
    route(to);
    clearmarkers(); /* возврат базы данных в исходное состояние */
    if(tos > 0) pop(c1,c2,&d);
    retract(c1,c2);  /* удаление последней вершины из базы данных */
    tos = 0;  /* сброс стека, используемого для поиска с возвратом */
  } while(getchar() != 'q'); /* для выхода вводится символ 'q' */

  return 0;
}

/* Сбросить поле skip, т.е. заново активизировать все вершины. */
void clearmarkers()
{
  int t;

  for(t=0; t < f_pos; ++t) flight[t].skip = 0;
}

/* Удаление записи из базы данных. */
void retract(char *from, char *to)
{
  int t;

  for(t=0; t < f_pos; t++)
    if(!strcmp(flight[t].from, from) &&
      !strcmp(flight[t].to, to)) {
        strcpy(flight[t].from,"");
        return;

    }
}

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

/* Поиск несольких решений методом поиска в глубину;
   некоторые вершины удаляются */
#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; /* index for searching flight db */

int tos = 0;      /* вершина стека */
struct stack {
  char from[20];
  char to[20];
  int dist;
} ;
struct stack bt_stack[MAX]; /* стек, используемый для посика
                               с возвратом */

void retract(char *from, char *to);
void clearmarkers(void);
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], c1[20], c2[20];
  int d;

  setup();

  printf("From? ");
  gets(from);
  printf("To? ");
  gets(to);
  do {
    isflight(from,to);
    route(to);
    clearmarkers(); /* возврат базы данных в исходное состояние */
    if(tos > 0) pop(c1,c2,&d);
    retract(c1,c2);  /* удаление последней вершины из базы данных */
    tos = 0;  /* сброс стека, используемого для поиска с возвратом */
  } while(getchar() != 'q'); /* для выхода вводится символ 'q' */

  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");
}
/* Сбросить поле skip, т.е. заново активизировать все вершины. */
void clearmarkers()
{
  int t;

  for(t=0; t < f_pos; ++t) flight[t].skip = 0;
}

/* Удаление записи из базы данных. */
void retract(char *from, char *to)
{
  int t;

  for(t=0; t < f_pos; t++)
    if(!strcmp(flight[t].from, from) &&
      !strcmp(flight[t].to, to)) {
        strcpy(flight[t].from,"");
        return;

    }
}

/* Показать маршрут и общее расстояние. */
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);
}

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

С помощью этого метода получаются такие решения:

Нью-Йорк - Чикаго - Денвер - Лос-Анджелес
Расстояние в милях равно 3000.
Нью-Йорк - Чикаго - Денвер - Хьюстон - Лос-Анджелес
Расстояние в милях равно 5000.
Нью-Йорк - Торонто - Лос-Анджелес
Расстояние в милях равно 2600.

В этом случае второе решение — это самый худший из возможных маршрутов, но оптимальное решение все равно найдено. Однако помните, что эти результаты нельзя обобщать: они зависят как от физической организации базы данных, так и от конкретной ситуации.


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

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.