#include <iostream> #include <stack> #include <string> #include <vector>
using namespace std; // Информация о рейсах.
Flightlnfo(string f, string t, int d) { - from = f ;
to = t;
distance = d;
skip = false;
}
};
// Ищет множественные решения с помощью удаления узлов, class Search {
// Этот вектор солержит информацию о рейсах.
vector<FlightInfo> flights;
// Этот стек используется для возврата или отката. Stack<FlightInfo> btStack;
If Если есть рейс между from и to,
// запоминает расстояние в dist.
// Возвращает true, если рейс существует,
II и false — в противном случае.
bool match(string from, string to, int fcdist);
11 Для заданного from находит любой рейс. 11 Возвращает true, если рейс найден, II и false — в противном случае, bool find(string from, Flightlnfo &f);
gtruct Flightlnfo { string from; // пункт отправления string to; // пункт назначения int distance; // расстояние между from и to bool skip; // используется при возврате'
FlightlnfoO { from = ""; to = ""; distance = 0; skip = false;
>
public:
// Помещает рейсы в базу данных.
void addflight(string from, string to, int dist) { flights.push_back(FlightInfo(from, to, dist));
}
// Показывает маршрут и общую длину, void route();
// Определяет, есть ли маршрут между from и to. void findroute(string from, string to);
// Возвращает true, если маршрут был найден, bool routefoundO {
return btStack.size() != 0;
}
// Возвращает рейс из вершины стека. Flightlnfo getTOSO { return btStack.top();
}
// Переустанавливает все поля skip, void resetAilskip();
// Удаляет рейс.
void remove(Flightlnfo f) ;
};
// Показывает маршрут и его длину.
void Search::route()
{
stack<Fl ight Info rev; int dist = 0; Flightlnfo f;
// Меняет порядок стека на противоположный для отображения маршрута.
While(!btStack. empty()) { f = btStack.top(); rev.push(f) ; btStack.pop() ;
}
// Отображает маршрут, while(!rev.empty()) {
f = rev. top() ;
rev.pop() ;
cout « f.from « " to "; dist += f.distance;
)
cout « f.to « endl;
cout « "Distance is " « dist « endl;
}
// Если есть рейс между from и to,
// запоминает расстояние Б dist.
// Возвращает true, если рейс существует,
// и false — в противном случае.
bool 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; //не найден
}
11 Для заданного from находит любой рейс. 11 Возвращает true, если рейс найден,
//и false — в противном случае.
bool Search::find(string from, Flightlnfo &f)
{
for(unsigned i=0; i < flights.size(); i++) {
if(flights[i].from == from && !flights[i].skip) ( f = flights[i];
flights[i].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(FlightInfo(from, to, dist)); ,
return;
}
// Пробует другой рейс, if(find(frbm, f)) {
btStack.push(FlightInfo(from, to, f.distance));
findroute(f.to, to);
}
else if(!btStack.empty()) {
// Возвращается на шаг назад и пробует другой рейс. •
f = btStack.top();
btStack.pop();
findroute(f.from, f.to);
}
ц Переустанавливает все поля skip. void Search::resetAilskip() {
for(unsigned i=0; i< flights.size(); i++) flights[i].skip = false;
}
// Удаляет рейс
void Search::remove(Flightlnfo f) {
for(unsigned i=0; i< flights.size(); i++) if(flights[i].from == f.from && flights[i].to == f.to) flights[i].from = "";
)
// Версия для удаления узлов, int main () {
charto[40], from[40];
Search ob;
Flightlnfo f;
// Добавляет рейсы в базу данных, ob.addflight("New York", "Chicago", 900); ob. addf 1 ight (" Chi cago", " 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);
I/ Получает пункты отправления и назначения. cout « "From? ";
oin.getline(from, 40); cout « "To? ";
cin.getline(to, 40);
// Находит множественные решения. for(;;) {
// Проверяет, есть ли рейс.
ob.f indroute(from, t о),-
// Если не найден ни один новый маршрут, завершается, if(!ob.routefound()) break;
// Сохраняет рейс на вершине стека (on top-of-stack). f = ob.getTOSO;
ob.rouceO; // отображает текущий маршрут.
ob.resetAilskip(); // переустанавливает поля skip
// Удаляет из базы данных последний рейс //из предыдущего решения, ob.remove(f);
)
return 0;
}
Программа находит следующие решения:
From? New York To? Los Angeles
New york to Chicago to Denver to Los Angeles Distance is 2900
New York to Chicago to Denver to Houston to Los Angeles Distance is 4400
New York to Toronto to Los Angeles Distance is 3000
В данном случае второе решение — это наихудший из возможных маршрУ" тов, но найдены и два достаточно хороших решения. Обратите внимание на то, что множество решений, найденных методом удаления узла, отличается от набора маршрутов, найденных методом удаления пути. Разные подходы» генерирующие множественные решения, часто дают различные результаты.
|
