Листинг 7.8. Поиск потерянных ключей

#include <ioscreain> #include <stack> #include <string> #include <vector>

using namespace std;

Информация о комнате, struct Roomlnfo {

string from;

string to;

bool skip;

RoomlnfoO { from = ; to = ; skip = false;

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

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

Снова о потерянных ключах

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

. Roominfо(string f. string t) { £гсяп = f.to = t; skip = false;

Ищет ключи, используя поиск в глубину, class Search {

Этот вектор содержит информацию о комнатах.

vector<RoomInfo> rooms ,-

Этот стек применяется для возврата. stack<RoomInfo> btstack;

Возвращает true, если существует путь между

from и to. Возвращает false в противном случае.

bool match(string from, string to);

При заданном from находит любой путь. Возвращает true, если путь найден, и false - в противном случае, bool find(string from, Roominfо &f);

public:

Помещает сведения о комнатах в базу данных.

void addroom(string from, string to)

rooms.push back(Roominfо(from, to));

Показывает пройденный маршрут. void route();

Определяет, есть ли путь между from и to. void findkeys(string from, string to);

Возвращает true, если ключи были найдены, bool keysfoundО {

return !btStack.enpty();

Показывает марщрут. void Search::route() {

stack<RoomInfo> rev; Roomlnfo f;

Меняет порядок стека на обратный для отображения маршрута, while(!btStack.empty()) (

f = btStack.top();

rev.push(f);

btStack.pop-O ;

Отображает маршрут. while( Irev.ertptyO ) {

f = rev. top0 ;

rev.popO;

cout f.from to ;

cout f.to endl;

Возвращает true, если существует путь между

from и to. Возвращает false в противном случае.

bool Search::match(string from, string to)

for (unsigned i=0; i < rooms.sizeO ; i++) { if(rooms[i].from == from &&

rooms[i].to == to && !rooms[i].skip)

rooms[i].skip = true; предотвращает повторное использование return true;