Skip to main content

For a given network of cities, find an optimal path to reach from a given source city to any other destination city using an admissible heuristic.


Objective: For a given network of cities, find an optimal path to reach from a given source city to any other destination city using an admissible heuristic.

Theory:

Heuristics: The heuristic function h(n) tells A* an estimate of the minimum cost from any vertex n to the goal. It’s important to choose a good heuristic function.

The heuristic can be used to control A*’s behavior.

  • At one extreme, if h(n) is 0, then only g(n) plays a role, and A* turns into Dijkstra’s Algorithm, which is guaranteed to find a shortest path.
  • If h(n) is always lower than (or equal to) the cost of moving from n to the goal, then A* is guaranteed to find a shortest path. The lower h(n) is, the more node A* expands, making it slower.
  • If h(n) is exactly equal to the cost of moving from n to the goal, then A* will only follow the best path and never expand anything else, making it very fast. Although you can’t make this happen in all cases, you can make it exact in some special cases. It’s nice to know that given perfect information, A* will behave perfectly.
  • If h(n) is sometimes greater than the cost of moving from n to the goal, then A* is not guaranteed to find a shortest path, but it can run faster.
  • At the other extreme, if h(n) is very high relative to g(n), then only h(n) plays a role, and A* turns into Greedy Best-First-Search.

So we have an interesting situation in that we can decide what we want to get out of A*. With 100% accurate estimates, we’ll get shortest paths really quickly. If we’re too low, then we’ll continue to get shortest paths, but it’ll slow down. If we’re too high, then we give up shortest paths, but A* will run faster.

Procedure:

  1. Put the start node son a list called OPENof unexpanded nodes.
  2. If OPEN is empty exit with failure; no solutions exists.
  3. Remove the first OPEN node n at which f is minimum (break ties arbitrarily), and place it on a list called CLOSEDto be used for expanded nodes.
  4. If nis a goal node, exit successfully with the solution obtained by tracing the path along the pointers from the goal back to s.
  5. Otherwise expand node n, generating all it’s successors with pointers back to n.
  6. For every successor n’on n:a. Calculate f(n’).b. if n’ was neither on OPENnor on CLOSED, add it to OPEN. Attach a pointer from n’back to n. Assign the newly computed f(n’)to node n’.c. if n’ already resided on OPENor CLOSED, compare the newly computed f(n’)with the value previously assigned to n’. If the old value is lower, discard the newly generated node. If the new value is lower, substitute it for the old (n’ now points back to n instead of to its previous predecessor). If the matching node n’ resides on CLOSED, move it back to OPEN.
  7. Go to step 2.
















Conclusion: When h is consistent, the f values of nodes expanded by A* are never decreasing. When A* selected n for expansion it already found the shortest path to it. When h is consistent every node is expanded once.Normally the heuristics we encounter are consistent

–the number of misplaced tiles

–Manhattan distance

–straight-line distance










Labels:

Comments

Post a Comment

Popular posts from this blog

Write a code simulating ARP /RARP protocols

   Write a code simulating ARP /RARP protocols . Aim:        To write a java program for simulating ARP/RARP protocols ALGORITHM: server 1. Create a server socket and bind it to port. 2. Listen for new connection and when a connection arrives, accept it. 3. Send server ‟ s date and time to the client. 4. Read client ‟ s IP address sent by the client. 5. Display the client details. 6. Repeat steps 2-5 until the server is terminated. 7. Close all streams. 8. Close the server socket. 9. Stop. Client 1. Create a client socket and connect it to the server ‟ s port number. 2. Retrieve its own IP address using built-in function. 3. Send its address to the server. 4. Display the date & time sent by the server. 5. Close the input and output streams. 6. Close the client socket. 7. Stop. Program Program for Address Resolutuion Protocol (ARP) using TCP Client: import java.io.*; import java.net.*; impor...
Post a Comment
Read more

Importants Links of Leetcode

  Here are all the important discussion posts which contain brief descriptions about a topic with its problem list. Recursion:- A.   https://leetcode.com/tag/recursion/discuss/1733447/Become-Master-In-Recursion Binary Tree and Binary Search Tree:- A.   https://leetcode.com/tag/binary-tree/discuss/1212004/Binary-Trees-study-guide B.   https://leetcode.com/tag/binary-tree/discuss/1820334/Become-Master-in-Tree C.   https://leetcode.com/tag/binary-tree/discuss/1094690/Views-and-Traversal-of-binary-tree-or-Important-topics-or-Must-Read-%3A- ) Dynamic Programming:- A.   https://leetcode.com/discuss/study-guide/458695/Dynamic-Programming-Patterns B.   https://leetcode.com/tag/dynamic-programming/discuss/1437879/Dynamic-Programming-Patterns C.   https://leetcode.com/tag/dynamic-programming/discuss/662866/DP-for-Beginners-Problems-or-Patterns-or-Sample-Solutions D.   https://leetcode.com/tag/dynamic-programming/discuss/1050391/Must-do-Dynamic-programm...
Post a Comment
Read more

The Future of Web Development: Why Next.js is Going Viral

  Are you ready to level up your web development game? Look no further than Next.js, the latest sensation in the world of web development that's taking the industry by storm. With its powerful features, flexibility, and performance optimizations, Next.js is becoming the go-to framework for building modern web applications. In this blog post, we'll explore why Next.js is going viral and how it's changing the landscape of web development. Supercharged Performance: One of the main reasons why Next.js is making waves is its superior performance capabilities. With built-in optimizations like automatic static site generation (SSG) and server-side rendering (SSR), Next.js allows you to create blazing-fast web applications that load quickly and deliver seamless user experiences. This is especially important in today's fast-paced digital world, where users demand instant gratification and have little patience for slow-loading websites. Flexibility and Scalability: Next.js provid...
Post a Comment
Read more