A* ALGORITHM BASICS FOR PATH FINDING A* , widely used known form of best-first search & path planning algorithm nowadays in mobile robots,games. this is the function for A*, f(n) = g(n) + h(n) g ( n ) is the cost of the path from the start node to n , and h ( n ) is a heuristic function that estimates the cost of the cheapest path from n to the goal This will find cheapest f(n) value in neighbor nodes to archive goal node. check below image A to B path finding with g(n),h(n),f(n) value In the final level check below image Now we will check the Algorithm // A* Search Algorithm 1. Initialize the open list 2. Initialize the closed list put the starting node on the open list (you can leave its f at zero) 3. while the open list is not empty a) find the node with the least f on the open list, call it "q" b) pop q off the open list c) generate q's 8 successors
A hash table is an unordered collection of key-value pairs, where each key is unique.
so next what is Direct-address tables
We shall assume that no two elements have the same key , to represent the dynamic set, we use an array, or direct-address table
here T is the hash table k is the key valueDIRECT -ADDRESS -SEARCH (T, k)
return T [k]
DIRECT -ADDRESS -INSERT (T, x)
T [key[x]] ← x
DIRECT -ADDRESS -DELETE (T, x)
T [key[x]] ← NIL
Each of these operations is fast: only O(1) time is required.
Let have a look in HASH TABLE Collision resolution by chaining
if two elements have the same key we put all the elements that hash to the same slot in a linked list
CHAINED -HASH -INSERT (T, x)
insert x at the head of list T [h(key[x])]
insert x at the head of list T [h(key[x])]
CHAINED -HASH -SEARCH (T, k)
search for an element with key k in list T [h(k)]
CHAINED -HASH -DELETE (T, x)
delete x from the list T [h(key[x])]
Let check Hash functions, in which are the methods to Interpreting keys as natural numbers
k is the key
- The division method : h(k) = k mod m
- The multiplication method : h(k) = m (k A mod 1)
- Universal hashing
Open addressing
all elements are stored in the hash table itself. That is, each table entry contains either an element of the dynamic set or NIL . When searching for an element, we systematically examine table slots until the desired element is found or it is clear that the element is not in the table. There are no lists and no elements stored outside the table, as there are in chaining. Thus, in open addressing, the hash table can “fill up” so that no further insertions can be made
HASH -INSERT (T, k)
i ← 0
repeat j ← h(k, i)
if T [ j ] = NIL
then T [ j ] ← k
return j
else i ← i + 1
until i = m
error “hash table overflow”
HASH -SEARCH (T, k)
i ← 0
repeat j ← h(k, i)
if T [ j ] = k
then return j
i ← i + 1
until T [ j ] = NIL or i = m
if T [ j ] = k
then return j
i ← i + 1
until T [ j ] = NIL or i = m
return NIL
Great bro
ReplyDelete