Confused pls provide your suggestions!

1

In A * algorithm we choose the node with minimum f ( f = g+h) where g is the distance from start to current node and h is the distance from end to current node.

I implemented A* search in a grid with some obstacles that can traverse up , down ,left , right and at the same time also implemented breadth first search .

I judged the performance of both by finding number of nodes visited by both algorithms and it were same ,no difference was seen.

Now even after applying heuristic in A* search and picking the node with the least f from open list , A* was not efficient as the number of visited nodes was same in both case .

But when i picked node from open list on the basis of minimum h i could see A* performance increased .

Now if h is only sufficient then why f is needed in A* search?

pls someone explain.

2

image
image573×580 7.29 KB

int winner = 0;
        for(int i=0;i<openSet.size();i++){
            if(openSet[i]->f < openSet[winner]->f){
                winner=i;
            }

            
        }

when f is used

3

image
image579×581 6.72 KB

int winner = 0;
for(int i=0;i<openSet.size();i++){
            if(openSet[i]->h < openSet[winner]->h){
                winner=i;
            }

            
        }

when only h is used
red circles are the nodes that are visited

4

It would be better if you share a link to your full code

5

agrupathfinder.azurewebsites.net/ … visit this site here you can easily see the difference in performance of the two algorithms, also if you want the implementation or want to understand the concept behind then you can ask me :grin:

2 Likes
6

Can we always guarantee A* search is efficient always ?

I implemented A* this way , is there any thing wrong ?

function heuristic(a,b){
  var d=abs(a.i - b.i) + abs(a.j - b.j);
  return d;

}

function readyastar(){
  for(let Cell of grid){
    Cell.addNeighbors();
  }
  openSet.push(start);

}


function pathfinder(){
 let currentCell;

 if(openSet.length>0){
  var winner = 0;
  for(var i = 0;i<openSet.length;i++){
    if(openSet[i].f < openSet[winner].f){
      winner = i;
    }
  }

  currentCell = openSet[winner];
  currentCell.m=true;
  if(pathfound){
    return;
  }

  if(currentCell === end){
    pathfound=true;
  }
  
  let index = openSet.indexOf(currentCell);
  openSet.splice(index , 1);
  closedSet.push(currentCell);

  var neighbors = currentCell.neighbors;

  for(let i = 0; i<neighbors.length; i++){
    var neighbor = neighbors[i];

    if(!closedSet.includes(neighbor)){
      var tempG  = currentCell.g + 1;
      if(openSet.includes(neighbor) && tempG<neighbor.g){

      
      neighbor.g = tempG;
      neighbor.h = heuristic(neighbor , end);
      neighbor.f = neighbor.g + neighbor.h ;
      neighbor.previous = currentCell;
    

      }
      else{
      neighbor.g = tempG;
      neighbor.h = heuristic(neighbor , end);
      neighbor.f = neighbor.g + neighbor.h;
      openSet.push(neighbor);
      neighbor.previous = currentCell;
      }

    }
  }     
 }

 else{
  console.log("no solution");
  return;
 }
 path = [];
 var temp = currentCell;
 path.push(temp);
 while(temp.previous){
  path.push(temp.previous);
  temp = temp.previous;
 }

}
7

the efficiency of A* depends on the heuristics. Of course, it may be the case that gready best first search or even a simple dfs scan fewer positions, but those algorithms do not guarantee that it has found the shortest path. The link agru povided is a nice tool to compare algos

8

I was just thinking yesterday of making such a path visualizer web app and here you made it. Awesome work man :ok_hand:

9

Instead of else it should be else if(tempG<neighbor.g) , there are also other improvements that can be made to reduce the time complexity but the main reason your algorithm is visiting all nodes is because of the else part. Do try this and let me know.

10

I made it a few months back, you should definitely try and build one as it showcases both , your development skills and algorithmic knowledge as it is very hard to make it efficient with all the visualization, and the features that you can add and change are limitless, you can check the github repository the link of which is present at the bottom of the site to see the code. :smiley:

11

First i would like to thank u for helping me .
please share your algorithm and optimization it will be really a big help for me.

what i did is

1)select the node from open list with minimum f value

2)pop the node from openSet and push it on closedSet.

3)Now if pathfound is true stop

4)if not then check valid neighbour of the current node that is not in closedSet .

5)if the current node is in openSet and if tempG<neighbor.g then just update neighbor.g value

4)else it is the new cell that is neither in openSet nor in closedSet so just calculate f and push it on openSet .

12

A* has a disadvantage as it guess , it estimates g value correctly but the estimation of h value is guessed using heuristic and sometimes that guess may be incorrect leading it to visit maximum cells.

I say my A* algorithm is correct , just because of incorrect guess of h it is visiting maximum cells.

If we want correct h value than it will be lot more time consuming.

So there is not any highly efficient shortest path algorithm , every algorithm has its disadvantage and if we try to make it efficient the cost increases which is another disadvantage.

13

I understood your code, did you made the change that I told you to made? also do you use discord/telegram/facebook whatsapp? whichever option you are comfortable with share the respective way to connect and we can discuss further. Also you should study dijkstra algorithm first as A* is just a slight modification of that and you can easily find the explanations and code for optimized dijkstra… one such link - Dijkstra on sparse graphs - Algorithms for Competitive Programming

14

yes i changed but i did not see any change.

one last thing i want to ask is if all the values of f are same in openSet then to which shall i give more priority.

my email id - dharewarishab@gmail.com