11 replies to this topic

[Apprentice123]

About A star Algorithm, I found this example on the Internet:
http://www.webplantm...t<br /> <br /> Game 8puzzle with A* Algorithm.


In function build:

void searchTree::build() {	read();
	makeRoot(initial);
	success = false;
	tree_node* curr;
	heuristic = 1;


	int count = 0;
	while (stack.size() > 0) {
		curr = stack.front();
		stack.erase(stack.begin());
		insert(curr);


		if (curr->distance > count) {
			count = curr->distance;
			cout << "n = " << count << endl;
		}
	}
}

What it shows (court << "n = " << count) is the number of nodes opened?

[haltox]

I think it's the current distance(as in movement count).

[Apprentice123]

haltox said:

I think it's the current distance(as in movement count).

OK. And it has to know the number of movements made?

[haltox]

Usually the a* algorith assigns a base count to each nodes. Then, as it moves, it updates the base count to the actual count. If it meets an already visited node and it took less moves to get there, it updates the move count again to the new lower value.

It proceeds like this for a while and then return a graph with the best path.

[Apprentice123]

haltox said:

Usually the a* algorith assigns a base count to each nodes. Then, as it moves, it updates the base count to the actual count. If it meets an already visited node and it took less moves to get there, it updates the move count again to the new lower value.

It proceeds like this for a while and then return a graph with the best path.

OK. But as I know an node are expanded to count the number of nodes?

[Apprentice123]

Whenever

curr = stack.front()

is a node that was open ?


And whenever pass1 or pass2 or pass3 or pass4 in CheckSuccess function is true a movement is made ?

[haltox]

A* is a recursive algorythm in nature. However, if the map is minimally big, you'd soon get yourself with a stack overflow. Instead, the person who did this code, used a while loop and the standard library stack to kind of replicate the process of the recursive version. When he says

curr = stack.front()

he's unrolling the stack and going to a previous state to continue computation from there.

The checksuccess function returns he is next to his objective.


Note the difference between "the stack", and a stack as a data structure.

[Apprentice123]

haltox said:

A* is a recursive algorythm in nature. However, if the map is minimally big, you'd soon get yourself with a stack overflow. Instead, the person who did this code, used a while loop and the standard library stack to kind of replicate the process of the recursive version. When he says

curr = stack.front()

he's unrolling the stack and going to a previous state to continue computation from there.

The checksuccess function returns he is next to his objective.


Note the difference between "the stack", and a stack as a data structure.

OK. I understood that he ordered the stack dara structure at lower cost of the current nodeto the goal node to do the calculation. But I needed to know how many nodes it opened and how many moves were made during the "game". Its possible to calculate that?

[haltox]

The node next to the goal node should have a count value equal to the number of moves it takes to get there.

[Apprentice123]

haltox said:

The node next to the goal node should have a count value equal to the number of moves it takes to get there.

void searchTree::build() {
    read();    
    makeRoot(initial);    
    success = false;    
    tree_node* curr;    
    heuristic = 1;    
    int count = 0;    
    while (stack.size() > 0) {        
          curr = stack.front();        
          stack.erase(stack.begin());        
          insert(curr);        
          if (curr->distance > count) {            
                   count = curr->distance;            
                   cout << "n = " << count << endl;        
         }    
    }
}

So, the variable count is the number of moviments made the initial state to end state (the movements made during the game)? All nodes are inserted into the stack structure, right? So the number of loops in while is the number of nodes was open?

[haltox]

He won't always visit every nodes. In this case, it stops once it finds the goal. So if it is next to the starting node, he will return immediatly. And then again, he might visit the same node more than once.

[Apprentice123]

haltox said:

He won't always visit every nodes. In this case, it stops once it finds the goal. So if it is next to the starting node, he will return immediatly. And then again, he might visit the same node more than once.

void searchTree::build() {
    read();    
    makeRoot(initial);    
    success = false;    
    tree_node* curr;    
    heuristic = 1;    
    int count = 0;    
    vector<tree_node*> num_open_node;
    int num_nodes = 0;
    bool exist;
    while (stack.size() > 0) {        
          curr = stack.front();
          exist = false;
          for(int i=0; i< num_open_node.size(); i++){
                    if(num_open_node[i] == curr)
                            exist = true
          }
          if(!exist){
               num_open_node.push_back(curr);
               num_nodes += 1;
          }
          stack.erase(stack.begin());        
          insert(curr);        
          if (curr->distance > count) {            
                   count = curr->distance;            
                   cout << "n = " << count << endl;        
         }    
    }
}

I thought about doing this for the number of nodes open, it is correct? My problem is that the program is very slow when you scroll through all the structures: stack and num_open_node. And about the number of moves is correct what I ask in another topic?