CS) Informative Maps on PDA-phones
Chui Pui Ling Page 16
2.3. Path Finding Where is ABC restaurant How to go to the restaurant To find a
route to go to a desired place, the most common way is to read maps. Traditionally, people have to first notice the current location and then the destination on the map for determining the route. It seems to be obvious and trivial on the other hand, it is not as easy for computers to find an optimal route. Finding a route on a map is viewed as finding a path on a graph in computer science. Graph is a set of objects called vertices joined by links called edges. Path finding is a problem to find a path between two vertices. Therefore, each location can be interpreted as a vertex and the road or street between locations can be interpreted as an edge.
2.3.1. Breadth-First Search Breadth-first search is an algorithm aims to expand and examine all nodes of a graph systematically in search of a solution with an uninformed search strategy. The algorithm begins at the root note and explores all the neighboring nodes on of the same level. Then for each of those nearest nodes, it explores their unexplored neighbor nodes until it finds the goal. (Figure 8 [13]) It is complete which guarantees to find a solution if one exists. Moreover, it is optimal technically if the path cost is a non-decreasing function
of the depth of the node, e.g. when the costs of all the arcs are the same. On the other hand, it is memory consuming for holding all the generated nodes and the large number of nodes to be examined would cause a large time complexity. (Complexity - Ob L, where bis the branching factor and L is the level/depth)
CS) Informative Maps on PDA-phones
Chui Pui Ling Page 17
Share with your friends: 
