Backtracking in A star

by

your image is like 2d grid map

But your text suggest graph approach which is a bit confusing.

  • For 2D grid map the costs must be different between cells on path

You got too much of cost=100 in there and therefore you can not backtrack the path. You have to increase or decrease cost on each step and fill only cells that are near last filled cells. That can be done by recursion on big maps or by scanning whole map or bounding box for last filled number on small maps.

The backtracking

Can be done by scanning neighbors of start/end cells after A* filling moving always to the smallest/biggest cost

example

In this example start filling from (2,0) until (3,3) is hit and then backtrack from (3,2) cost=8 to the smallest cost (always cost-1 for incremental filling). If you need the path in reverse order then start filling from (3,3) instead …

speedup

Sometimes double filling speed up the process so: Start filling from both ends and stop when they join. To recognize which cell is filled from which point you can use positive and negative values, or some big enough ranges for costs.

More Related Contents:

  1. What should be the algorithm of the below statement?
  2. Finding all possible combinations of numbers to reach a given sum
  3. How do I search for a number in a 2d array sorted left to right and top to bottom?
  4. Generate an integer that is not among four billion given ones
  5. Nearest neighbors in high-dimensional data?
  6. how to calculate binary search complexity
  7. Binary Search in Array
  8. Algorithm to find multiple string matches
  9. Algorithm to find two repeated numbers in an array, without sorting
  10. Fast Algorithm to Quickly Find the Range a Number Belongs to in a Set of Ranges?
  11. O(klogk) time algorithm to find kth smallest element from a binary heap
  12. How does Dijkstra’s Algorithm and A-Star compare?
  13. Print the biggest K elements in a given heap in O(K*log(K))?
  14. Find local minimum in n x n matrix in O(n) time
  15. Breadth First Search and Depth First Search
  16. What is the difference between Linear search and Binary search?
  17. Algorithm to beat Strassen’s Algorithm
  18. HSL to RGB color conversion
  19. What exactly does big Ө notation represent?
  20. Select k random elements from a list whose elements have weights
  21. How are ssl certificates verified?
  22. Find duplicates in an array, without using any extra space
  23. How to delete in a heap data structure?
  24. What are the practical factors to consider when choosing between Depth-First Search (DFS) and Breadth-First Search (BFS)? [closed]
  25. Efficiently reverse the order of the words (not characters) in an array of characters
  26. Painter puzzle – estimation
  27. Approximate string matching algorithms
  28. Generating shuffled range using a PRNG rather than shuffling
  29. Find out which combinations of numbers in a set add up to a given total
  30. Why are hash table expansions usually done by doubling the size?

Leave a Comment