Иногда бывает полезно найти несколько решений одной задачи. Но это не то же самое, что полный перебор, при котором необходимо найти все решения. Например, подумайте о проектировании дома вашей мечты. Вам, чтобы решить, какой проект будет наилучшим, может потребоваться несколько разных набросков поэтажного плана дома, но наброски всех возможных домов вам не нужны. В сущности, разные решения помогают увидеть много разных подходов к поиску окончательного решения, а затем реализовать один из них.
Генерировать разные решения можно несколькими способами, но здесь рассказывается только о двух из них. Первый — это удаление путей, а второй — удаление вершин. Как и следует из названий этих методов, чтобы при генерации разных решений те из них, которые уже найдены не повторялись, некоторые элементы требуется удалять из системы. Помните, что ни один из этих методов не является попыткой найти все решения (и даже не может для этого использоваться). Поиск всех решений — это совсем другая задача, за выполнение которой обычно даже не берутся, потому что она подразумевает исчерпывающий поиск.
При использовании метода генерации нескольких решений, который называется методом удаления путей, из базы данных удаляются все вершины текущего решения, а затем делается попытка найти следующее решение. В сущности, при удалении путей подрезаются ветви дерева.
Чтобы найти несколько решений с помощью удаления путей, необходимо в программе поиска в глубину изменить функцию 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.
В этом случае второе решение — это самый худший из возможных маршрутов, но оптимальное решение все равно найдено. Однако помните, что эти результаты нельзя обобщать: они зависят как от физической организации базы данных, так и от конкретной ситуации.