CODEWITHSUNDEEP
algorithmpath-findinga-starheuristics
user1940350
user1940350

Reputation: 173

Find the longest path with A*

I'm trying to figure out if I can use A* algorithm to fine the longest path to goal under the assumption of admissibility.

I tried with maximal max(f(n)=g(n)+h(octile-distance)), but it seems wrong to me.

  1. If admissible heuristic is to under estimate the f*, for longest path i had to find heuristic that always over estimate the f*?

  2. According to 1, if i need to over-estimate geographic distance to goal. someone can recommend me for some kind of heuristic ?

  3. Is it optimal finding the longest path with A* like this ?

Upvotes: 1

Views: 1396

Answers (1)

SaiBot
SaiBot

Reputation: 3745

Finding the longest path is NP-Hard, so trying to adapt A* or any other shortest path algorithm to find it will unfortunately not work.

Upvotes: 2

Related Questions