properties of heuristics and A*

combinatoricsandai

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.

  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:

WordPress.com Logo

You are commenting using your WordPress.com 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 )

Google+ photo

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

Connecting to %s

%d bloggers like this: