# properties of heuristics and A*

Let $latex G=(V,E,c)$ be a direct graph with non-negative costs. Also consider a starting vertex $latex s$ and a goal vertex $latex g$. The classic search problem is to find a optimal cost path between $latex s$ and $latex g$. Consider the distance function $latex d:V \times V \to \mathbb R$ induced by the cost $latex c$ (the cost of the minimum cost path). Also, assume the graph $latex G$ is strongly connected. Also let $latex w$ be a real greater or equal to 1.

A heuristic is a function $latex h:V \to \mathbb R$. An heuristic $latex h$ is $latex w-$admissible if $latex h(x) \leq wd(x,g)$ for all $latex x \in v$. A heuristic is $latex w-$consistent if $latex h(g) = 0$ and for all $latex x,y \in V$ such that $latex (x,y) \in E$ we have $latex h(x) \leq wc(x,y) + h(y)$. For $latex w= 1$ we just say…

View original post 1,851 more words

Advertisements

## About Khuram Ali

Programming... Programming and Programming...!!!

Posted on April 27, 2013, in Algorithms, Artificial Intelligence and tagged , , , . Bookmark the permalink. 4 Comments.

• ### Comments 2

1. I do agree with all the ideas you have introduced
to your post. They’re really convincing and can certainly work. Nonetheless, the posts are very quick for beginners. May you please lengthen them a bit from next time? Thanks for the post.

2. You actually make it seem so easy with your presentation but I find this matter to be actually something which I think I
would never understand. It seems too complex and very broad for me.
I’m looking forward for your next post, I’ll try to get the hang of it!