Body: <blockquote>
  <p>Construct a state space with appropriate heuristics and local costs. Show that Greedy Best First search is not complete for the state space. Also illustrate A* is complete and guarantees solution for the same state space.</p>
  </blockquote>
  <p>Here I can not come up with a graphical figure of state space. Somewhere I saw (0,0),(2,2),(4,4),(6,6),(8,8),(10,10) as state space. But how to draw a figure for it?</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2023-06-12T09:05:58.610Z
Comments.Text: Do you know what being complete means? That's the first step to answer your question. Also, your homework problem doesn't tell you to draw the state space, but just to construct it.
Comments.UserDisplayName: nbro
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2023-06-14T13:30:48.707Z
Comments.Text: Actually I am not getting the idea what this question is trying to ask for.
Comments.UserDisplayName: npsulav
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2023-06-15T08:22:41.877Z
Comments.Text: I think you need to describe (not necessarily draw it) a state space with costs in the edges and a heuristic function (that estimates the costs to the goal) in such a way that the greedy BFS will not be able to find any solution and will continue to search forever or maybe get stuck, while A* will find a solution.
Comments.UserDisplayName: nbro
Tags: <search><a-star><best-first-search><completeness><state-space-search>
Title: How do I construct a state space that shows that Greedy Best First Search is not complete while A* is?
UserDisplayName: npsulav
ThreadText: # How do I construct a state space that shows that Greedy Best First Search is not complete while A* is?
  
  (Asked by: username_0 on 2023-06-12)
  
  > Construct a state space with appropriate heuristics and local costs. Show that Greedy Best First search is not complete for the state space. Also illustrate A\* is complete and guarantees solution for the same state space.
  
  Here I can not come up with a graphical figure of state space. Somewhere I saw (0,0),(2,2),(4,4),(6,6),(8,8),(10,10) as state space. But how to draw a figure for it?
  
  **Tags:** search, a-star, best-first-search, completeness, state-space-search
  > **Comments:**
  > **username_1**: Do you know what being complete means? That's the first step to answer your question. Also, your homework problem doesn't tell you to draw the state space, but just to construct it.  
  > **username_0**: Actually I am not getting the idea what this question is trying to ask for.  
  > **username_1**: I think you need to describe (not necessarily draw it) a state space with costs in the edges and a heuristic function (that estimates the costs to the goal) in such a way that the greedy BFS will not be able to find any solution and will continue to search forever or maybe get stuck, while A* will find a solution.  
  
  ---
  
  ## 0 answers
  
  