unsigned int cost - довжина поточного шляху;
- unsigned int OptCost - довжина оптимального шляху.
Опишемо основні методи клас Guide .
Функції, що дозволяють працювати зі списком аудиторій, що утворюють оптимальний шлях: void addAudiPath (char *) - додавання аудиторії в дорогу, void delAudiPath () - видалення аудиторії з шляху, void copyPath () - копіювання шляху.
Функція void KOMMI (char *), реалізує алгоритм з поверненням приведена в лістингу 2.1.
Лістинг 2.1 - Функція void KOMMI (char *), реалізує алгоритм з поверненням
void KOMMI (char * num1) {/ / алгоритм пошуку (Комівояжера)
FriendAudi * y; * p=audbeg; (p!=NULL && strcmp (p-> number, num1))=p-> next;=p-> firstfr ; (Y!=NULL) {
/ / перевіряємо, чи припустима аудиторія для додавання в дорогу
if (onFloorDop (y)) {
/ / визначаємо вагу ребра, яке хочемо додати
if (p-> number [0] == «L» && y-> number [0] == «L»)
/ / об'єкт названий аудиторією, але фактично не є їй
/ / це просто точка поруч зі сходами, про що говорить буква L
/ / відстань дорівнює 1000> weight=1000; if (p-> number [0] == «S» && y-> number [0] == « S »)> weight=0; {* fr=audbeg; (fr!=NULL && strcmp (fr-> number, y-> number))=fr-> next; (p-> ; x == fr-> x)> weight=abs (p-> y - fr-> y); if (p-> y == fr-> y)> weight=abs ( p-> x - fr-> x); y-> weight=0;
} (cost + y-> weight number, numend)) {(y-> number); ();=cost + y-> weight; ();
} else {* q=audbeg; (q!=NULL && strcmp (q-> number, y-> number))=q-> next; (q-> DOP) {(y-> number);> DOP=false; +=y-> weight; (y-> number); ();> DOP=true; -=y-> weight;
}
}
}
}
y=y-> next;
}
}
Враховуючи сферу застосування, має сенс перед пошуком маршруту обчислювати початкове максимально можливе значення OptCost . Це значення обчислюється у функції void setOptCost (char *, char *) наступним чином: визначається найдовший шлях по другому поверху і визначається максимальне число сходів, необхідних для досягнення шуканої аудиторії.
Крім того, що відсікаються всі часткові рішення, вартість яких перевищує вартість мінімального знайденого рішення, має сенс перевіряти на допустимість кожну переглядається вершину. Ця перевірка здійснюється у функції bool onFloorDop (FriendAudi *).
Допустимість встановлюється згідно з такими правилами:
- Якщо початкова та кінцева аудиторії знаходяться на другому поверсі, а поточна аудиторія - на іншому, то дана аудиторія недоступна для додавання в оптимальний маршрут.
- Якщо початкова та кінцева аудиторії знаход...
