Suboptimal solution given by A* search

Question

I don't understand how the following graph gives a suboptimal solution with A* search.

enter image description here

The graph above was given as an example where A* search gives a suboptimal solution, i.e the heuristic is admissible but not consistent. Each node has a heuristic value corresponding to it and the weight of traversing a node is given. I don't understand how A* search will expand the nodes.

Only A* with "graph search" will return a suboptimal solution. See http://stackoverflow.com/questions/10680180/graph-search-vs-tree-search/15281447#15281447. — ziggystar, Sep 13 '14 at 14:39
Imho the pseudoimplementation of the "A* graph" is a really bad one but it can be the only reason for a subopt solution. — Demplo, Sep 13 '14 at 14:56

score 6 · Answer 1 · answered Aug 29 '16 at 08:11

The heuristic h(n) is not consistent.

Let me first define when a heuristic function is said to be consistent.

h(n) is consistent if  
– for every node n
– for every successor n' due to legal action a 
– h(n) <= c(n,a,n') + h(n')

Here clearly 'A' is a successor to node 'B' but h(B) > h(A) + c(A,a,B)

Therefore the heuristic function is not consistent/monotone, and so A* need not give an optimal solution.

score 0 · Answer 2 · answered Sep 13 '14 at 14:45

0

Honestly I don't see how A* could return a sub-optimal solution with the given heuristic. This is for a simple reason: the given heuristic is admissible (and even monotone/consistent).

h(s) <= h*(s) for each s in the graph

You can check this yourself comparing the h value in each node to the cost of shortest path to g.

Given the optimality property of A* I don't see how it could return a sub-optimal solution, which should be S -> A -> G of course.

The only way it could return a suboptimal solution is if it would stop once an action from a node in the frontier leading to the goal is found (so to have a path to the goal), but this would not be A*.

answered Sep 13 '14 at 14:45

Demplo

511
6
18

The heuristic is not monotone. It decreases from B to A. – ziggystar Sep 13 '14 at 15:14
True, not only there. Still is admissible and should guarantee optimality. – Demplo Sep 13 '14 at 15:33
Sorry, I'm a bit confused today. :) – ziggystar Sep 13 '14 at 16:02
Your comment was actually relevant. The heuristic is not consistent. – Demplo Sep 13 '14 at 16:26
But it is possible to have a situation where A* search gives a suboptimal solution if the heuristic is admissible but not consistent right? Could you provide me with some example of that? – eejs Sep 13 '14 at 16:30
Afaik it is NOT possible: admissibility leads to optimality, both in terms of cost of the solution and of nodes expanded. – Demplo Sep 13 '14 at 16:34
2

@Crackej If the heuristic is not monotone, then you need to reopen nodes, as you can later encounter them on a cheaper path. – ziggystar Sep 13 '14 at 18:50
Ofc, this is why I said that the pseudocode implementation of the link was a bad one ;) – Demplo Sep 13 '14 at 19:12

S. M. Hejazi Hoseini · Answer 3 · 2023-02-12T07:45:06.213

In graph search, we don't expand the already discovered nodes.

f(node) = cost to node from that path + h(node)

At first step:

fringe = {S} - explored = {}

S is discarded from the fringe and A and B are added.

fringe = {A, B} - explored = {S}

Then f(A) = 5 and f(B) = 7. So we discard A from the fringe and add G.

fringe = {G, B} - explored = {S, A}

Then f(G) = 8 and f(B) = 7 so we discard B from the fringe but don't add A since we already explored it.

fringe = {G} - explored = {S, A, B}

Finally we have only G left in the fringe So we discard G from the fringe and we have reached our goal.

The path would be S->A->G. If this was a tree search problem, then we would find the answer S->B->A->G since we would reconsider the A node.

Suboptimal solution given by A* search

3 Answers3