Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <algorithm>
- #include <climits>
- #include <queue>
- #include <cmath>
- #define N 26
- using namespace std;
- typedef struct Priority{
- vector<int> resultat;
- double prior;
- double var_evristic;
- } Priority;
- bool operator < (const Priority &com_ver_1, const Priority &com_ver_2){
- return com_ver_1.prior > com_ver_2.prior;
- }
- class Graf{
- private:
- double **graf;
- vector<int> str;
- double weight_from[N];
- double finish_way;
- public:
- Graf(int start){
- str.push_back(start);
- graf = new double *[N];
- for(int i = 0; i < N; i++)
- graf[i] = new double[N];
- for(int i = 0; i < N; i++){
- for(int j = 0; j < N; j++)
- graf[i][j] = 0;
- }
- }
- ~Graf(){
- for (int i = 0; i < N; i++)
- delete[] graf[i];
- delete[] graf;
- // delete[] weight_from;
- str.clear();
- }
- void matrix(char i, char j, double weight){
- graf[i][j] = weight;
- }
- void Display(){
- for(int i = 0; i < N; i++){
- for(int j = 0; j < N; j++){
- cout << graf[i][j] << " ";
- }
- cout << endl;
- }
- }
- void print_path(int first, int finish){
- bool admissible = 1;
- bool monotonic = 1;
- int i = 0;
- if(str.size() > 1){
- while(str[i] != finish)
- {
- admissible = is_admissible(finish, str[i]) && admissible ? 1 : 0;
- i++;
- monotonic = is_monotonic(finish, str[i-1], str[i]) && monotonic ? 1 : 0;
- }
- admissible = is_admissible(finish, str[i]) && admissible ? 1 : 0;
- for(i = 0; i < str.size() ; i++){
- cout << char(str[i] + 'a');
- cout<<" "<<weight_from[i];}
- if(admissible)
- cout<<endl<<"Heuristic is admissible"<<endl;
- else
- cout<<endl<<"Heuristic is not admissible"<<endl;
- if(monotonic)
- cout<<"Heuristic is monotonic"<<endl;
- else
- cout<<"Heuristic is not monotonic"<<endl;
- }
- else cout << "нет пути";
- }
- double evristic(int i, int j){
- return abs(i - j);
- }
- bool is_admissible( int finish, int ver){
- return finish_way - weight_from[ver] >= evristic(finish, ver);
- }
- bool is_monotonic(int finish, int ver1, int ver2){
- return graf[ver1][ver2] >= evristic(finish, ver1) - evristic(finish, ver2);
- }
- void min_way_A_star(int first, int finish, priority_queue <Priority> &queue, double way){
- vector<int> str1;
- weight_from[0] = 0;
- while(true){
- for(int j = 0; j < N; j++)
- if(graf[first][j] != 0){
- Priority elem;
- elem.var_evristic = evristic(finish, j);
- elem.prior = graf[first][j] + way + elem.var_evristic;
- for(auto i: str1)
- elem.resultat.push_back(i);
- elem.resultat.push_back(j);
- queue.push(elem);
- }
- if(queue.empty())
- break;
- if(!queue.empty()){
- Priority popped;
- popped = queue.top();
- queue.pop();
- first = popped.resultat[popped.resultat.size()-1];
- str1 = popped.resultat;
- way = popped.prior - popped.var_evristic;
- weight_from[first] = popped.prior;
- }
- if(str1[str1.size()-1] == finish){
- for(auto i: str1)
- str.push_back(i);
- break;
- }
- }
- str1.clear();
- finish_way = weight_from[first] + evristic(finish, str.size() - 1);
- }
- };
- int main() {
- char start, the_end, from, to;
- double weight;
- cin>> start >> the_end;
- priority_queue <Priority> queue;
- Graf matr(start - 'a');
- while(cin >> from >> to >> weight){
- matr.matrix(from - 'a', to - 'a', weight);
- }
- // matr.Display();
- matr.min_way_A_star(start - 'a', the_end - 'a', queue, 0);
- matr.print_path(start - 'a', the_end - 'a');
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement