# 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

Posted on April 27, 2013, in Algorithms, Artificial Intelligence and tagged Algorithms, Artificial Intelligence, heuristics and A*, optimal cost path. Bookmark the permalink. 4 Comments.

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.

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!

Pingback: Large Deviations 5 – Stochastic Processes and Mogulskii’s Theorem | Eventually Almost Everywhere

Pingback: Mixing of the Noisy Voter Model | Eventually Almost Everywhere