Обход графа с помощью алгоритма A * - PullRequest
Новая
       18

Обход графа с помощью алгоритма A *

3 голосов
/ 03 мая 2011

Привет, я AI Student и собираюсь попробовать мою домашнюю работу - реализацию алгоритма A * для обхода графа. Я использую коды C ++, и то, что я сделал на данный момент, ниже кода, который является только классом Graph + insertge и функциями вершин. но теперь я запутался в том, как определить функцию стоимости (f = h (n) + g (n)) ...

также мне поможет любая ссылка на код или объяснение того, как A * работает для графов. то, что я нашел в Google, было о поиске пути через *, и это не имеет ничего общего с графом обхода. 

#include <iostream>
using namespace std;

class Graph;
class node {
    friend class Graph;
private:
    char data;
    int cost;
    node *next;
    node *vlist;
    bool goal;
    bool visited;
public:
    node(char d,int c, bool g){
        cost = c;
        goal = g;
        next = NULL;
        data = d;
        vlist = NULL;
        visited = false;
    }
};

class Graph {
private:
    node *Headnodes;
    char n;
public:
    Graph ()
    {
        Headnodes = NULL;
    }
    void InsertVertex(char n, int c, bool g);
    void InsertEdge(char n, char m, int c);
    void PrintVertices();
    void Expand(char n);
};

/////////////////
//  INSERTION  //
/////////////////
void Graph::InsertVertex(char n, int c, bool g){
    node *temp = new node(n,c,g);
    if(Headnodes==NULL)
    {
        Headnodes=temp;
        return;
    }

    node *t=Headnodes;
    while(t->vlist!=NULL)
        t=t->vlist;
    t->vlist=temp;
}

void Graph::InsertEdge(char n, char m, int c){
    int temp_cost = 0;
    if(Headnodes==NULL)
        return;

    node *x=Headnodes;
    while(x!=NULL){
        if(x->data==m)
            temp_cost = (x->cost+c);
        x = x->vlist;
    }
    node *t=Headnodes;
    node *temp=new node(m,temp_cost,false);

    while(t!=NULL){
        if(t->data==n){
            node *s=t;
            while(s->next!=NULL)
                s=s->next;
            s->next=temp;
        }
        t=t->vlist;
    }
}

int min_cost = 1000;
bool enough = false;
void Graph::PrintVertices(){
    node *t=Headnodes;
    while(t!=NULL){
        cout<<t->data<<"\t";
        t=t->vlist;
    }
}

void Graph::Expand(char n){
    cout << n << "\t";
    char temp_min;
    node *t=Headnodes;
    while(t!=NULL){
        if(t->data==n && t->visited == false){
            t->visited = true;
            if (t->goal)
                return;
            while(t->next!=NULL){
                if (t->next->cost <= min_cost){
                    min_cost=t->next->cost;
                    temp_min = t->next->data;
                }
                t = t->next;
            }
        }
        t=t->vlist;
    }
    Expand(temp_min);
}

int main(){
    Graph g;
    g.InsertVertex('A',5,false);
    g.InsertVertex('B',1,false);
    g.InsertVertex('C',9,false);
    g.InsertVertex('D',5,false);
    g.InsertVertex('E',1,false);
    g.InsertVertex('F',3,false);
    g.InsertVertex('G',2,false);
    g.InsertVertex('J',1,false);
    g.InsertVertex('K',0,true);

    g.InsertEdge('A','B',2);
    g.InsertEdge('A','C',1);
    g.InsertEdge('B','A',2);
    g.InsertEdge('B','D',1);
    g.InsertEdge('B','E',1);
    g.InsertEdge('C','A',1);
    g.InsertEdge('C','F',1);
    g.InsertEdge('C','G',1);
    g.InsertEdge('E','J',3);
    g.InsertEdge('E','K',3);

    g.PrintVertices();

    cout<<"\n\n";
    g.Expand('A');

    return 0;
}

1 Ответ

5 голосов
/ 03 мая 2011

Имеется только алгоритм поиска по графику.

Вы забыли суть алгоритма A *, то есть стоимость h (n) , полученную в результате эвристического вычисления..

Вы должны реализовать метод, h (n) , который будет рассчитывать, исходя из вашей эврититики, возможную стоимость от фактического пути до конечного пути, и это значение будетиспользуется для расчета стоимости ходьбы:

f '(n) = g (n) + h' (n) , где g (n) ужеЗнайте, что стоимость, в вашем случае, x-> cost .

g (n) - это общая стоимость дистанции, которую потребовалось, чтобы добраться от начальной позиции до текущего местоположения..

h '(n) - это расчетная стоимость расстояния от текущей позиции до цели / состояния цели.Эвристическая функция используется для создания этой оценки того, как далеко нужно достичь целевого состояния.

f '(n) - сумма g (n) и h' (n).Это текущий расчетный кратчайший путь.f (n) - истинный кратчайший путь, который не обнаруживается до завершения алгоритма A *.

Итак, что вам нужно сделать:

  • Реализация методаheuristic_cost (actual_node, final_node);
  • Используйте это значение вместе с фактической стоимостью, как в предыдущем уравнении, например: min_cost = t-> next-> cost + heuristic_cost (t-> next, final_node);

Мне действительно нравится здесь объяснение: http://www.policyalmanac.org/games/aStarTutorial.htm, чище, чем объяснение в Википедии.

...