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

About Khuram Ali

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

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

  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!

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

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

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: