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
Standard

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