Алгоритм поиска, который пытается найти маршрут с минимальным числом пересадок, использует эвристику, утверждающую, что чем больше длина очередного рейса, тем выше вероятность того, что пассажир стал ближе к пункту назначения; следовательно, количество пересадок минимизируется. На языке искусственного интеллекта это пример поиска экстремума (hill climbing).
Алгоритм поиска экстремума выбирает в качестве следующего шага узел, который кажется самым близко расположенным от цели (т. е. находящийся дальше других от текущей позиции). Он извлекает имя узла так же, как действует путешественник, застигнутый темнотой при восхождении на гору. Предполагая, что лагерь находится на вершине горы, даже в темноте путешественник знает, что каждый шаг, ведущий наверх, делает его ближе к цели.
Работая только с информацией, содержащейся в базе данных рейсов, нужно включить в программу формирования маршрута эвристику поиска экстремума следующим образом: выбрать соединяющий рейс, пункт назначения которого дальше всех остальных от текущей позиции, в надежде, что он ближе всего к конечному пункту назначения. Для этого в программе поиска в глубину (см. листинг 7.1) следует заменить метод find о новой версией, приведенной далее.
// Версия поиска методом "восхождения на гору".
// При заданном from находит самый длинный рейс.
// Возврашает true, если он найден,
// и false — в противном случае.
bool Search::find(string from, Flightlnfo &f)
{
int pos = -1; int dist = 0;
for(unsighed i=0; i < flights.size(); i++) {
if(flights[i].from == from && !flights[i].skip) { // Использует самый длинный рейс, if(flights[i].distance > dist) { pos = i;
dist = flights[i].distance;
}
}
}
if(pos != -1) { f = flights[pos];
flights[pos].skip = true; // предотвращает повторное использование return true;
}
return false;
)
Метод find о теперь просматривает всю базу данных в поисках рейса в самый удаленный от места отправления пункт назначения.
Для большей ясности в листинге 7.3 приведена полностью программа, реализующая применение эвристического метода поиска экстремума или "восхождения на гору".
рисгинг 7.3. Нахождение маршрута.при помощи метода эвристического поиска Экстремума ;
¦include <ioscream>
¦include <stack>
¦include <string>
¦include <vector>
using namespace std; /
// Информация о рейсе, struct Flightlnfo (
string from; // пункт отправления
string to; // пункт назначения
int distance; // расстояние между from и to
bool skip; // используется при возврате или откате
Flightlnfo() { from - "" ; to = ""; distance = 0; skip = false;
}
Flightlnfo(string f, string t, int d) { from = f ; to = t; distance = d; skip = false;
}
};
// Эта версия находит маршрут
//с помощью эвристики поиска экстремума.
class Search {
// Этот вектор содержит•информацию о рейсе.
vector<PlightInfo> flights;
// Этот стек используется при откате. stack<FlightInfo> btStack;
// Если есть рейс между from и to,
// запоминает расстояние в переменной dist.
// Возвращает true, если рейс существует, и
// false — в противном случае.
bool match(string from, string to, int fcdist);
// Версия поиска экстремума или метода восхождения на гору.
// При заданном from ищет самый длинный рейс из from.
// Возвращает true, если рейс найден,
//и false — в противном случае.
bool find(string from, Flightlnfo &f);
public:
// Помещает рейсы в базу данных.
void addflight(string from, string to, int dist) { flights.push_back(Flightlnfo(from, to, dist));
}
// Показывает маршрут и общую длину, void route();
// Определяет, есть ли маршрут между from и to. void findroute(string from, string to);
// Возвращает true, если маршрут найден, tool routefound()
return btStack.size() != 0;
J
);
// Показывает маршрут и общую длину.
void Search::route()
{
stack<FlightInfo> rev; irit dist = 0; Flightlnfo f;
// Меняет порядок стека на противоположный для вывода маршрута. . While (! btStack. empty ()) { f = btStack.top(); rev.push(f); btStack.pop();
}
// Отображает маршрут, while(!rev.empty ()) {
f = rev.top();
rev.popO ;
cout « f.from « " to "; dist += f.distance;
}
cout « f.to « endl;
cout « "Distance is " « dist « endl;
}
If Если есть рейс между from и to,
Н запоминает длину рейса в disc
II Возвращает true, если рейс существует,
If и false — в противном случае.
Search::match(string from, string to, int &dist)
for(unsigned i=0; i < flights.size(); i++) { if(flights[i].from == from &&
flights[i].to == to && !flights[i].skip)
{
flights[i].skip = true; // предотвращает повторное использование dist = flights[i].distance; return true;
}
}
return false; //не найден
}
// Версия "восхождения на гору".
// При заданном from находит самый длинный рейс из from.
// Возврашает true, если он найден.
//и false — в противном случае.
bool Search::find(string from, Flightlnfo &f)
{
int pos = -1; int dist = 0;
for(unsigned i=0; i < flights.size(); i++) {
if(flights[i].from == from && !flights[i].skip) { // Использует самый длинный рейс, if(flights[i].distance > dist) { pos = i;
dist = flights[i].distance;
}
}
}
if(pos != -1) { f = flights[pos];
flights[pos].skip = true; // предотвращает повторное использование return true;
}
return false;
)
// Определяет, есть ли маршрут между from и to. void Search::findroute(string from, string to) {
int dist; Flightlnfo f;
// Проверяет, достигнут ли пункт назначения, if (match (from, to, dist)) {
btStack.push(Flightlnfo(from, to, dist));
return;
}
// Пробует другой рейс. If(find(from, f)) {
btStack.push(Flightlnfo(from, to, f.distance));
findroute(f.to, to);
}
else if(!btStack.empty()) {
// Возвращается и проверяет другой рейс.
f = btStack.top();
btStack.pop();
findroute(f.from, f.to);
}
>
int main() { char to[40], from[40]; Search ob;
// Добавляет сведения о рейсах в базу, ob.addflight("New York", "Chicago", 900); ob.addflight("Chicago", "Denver", 1000); ob.addflight("New York", "Toronto", 500); ob.addflight("New York", "Denver", 1800); ob.addflight("Toronto", "Calgary", 1700); ob.addflight("Toronto", "Los Angeles". 2500);
ob.addflight("Toronto", "Chicago", 500); ob.addflight("Denver", "Urbana", 1000) ; ob.addflight("Denver", "Houston", 1000); ob.addflight("Houston", "Los Angeles", 1500); ob.addflight("Denver", "Los Angeles", 1000);
// Получает названия пунктов отправления и назначения, cout « "From? ";
cin.getline(from, 40); cout « "To? ";
cin.getline(to. 40);.
// Проверяет, есть ли маршрут между from и to. ob.findroute(from, to);
// Если маршрут существует, отображает его. if(ob.routefound())
ob.route () ,-return 0;
}
Выполнение программы приводит к следующему решению: From? New York То? Los Angeles
New York to Denver to Los Angeles Distance is 2800
Очень хорошее решение! Маршрут содержит минимальное число пересадок (только одну) и является самым коротким. Таким образом, найден наилучший возможный маршрут.
Но если бы не существовало рейса между Денвером и Лос-Анджелесом, Ре~ шение не было бы таким хорошим. Пришлось бы лететь из Нью-Йорка в Денвер, потом в Хьюстон и наконец в Лос-Анджелес, преодолевая расстояние в 4300 миль! В этом случае решение "взбирается на ложную вершину", потому что перелет в Хьюстон не приближает нас к Лос-АнджелесУ-На рис. 7.10 показаны найденное решение и ложная вершина.
|
