ROUTING WITH MINIMUM NUMBER OF LANDMARKS

摘要

Routing problem has been studied for decades. In this paper, we focus on one of the routing problems: finding a path from source to destination on road network with the guidance of landmarks. People use landmarks to identify previously visited places and reoriented themselves in the environment. When people give direction instructions for other people, they also like to refer to landmarks. In this sense, we want to find a path such that it visits as many landmarks as possible but also the distance of the path is as short as possible. However, in some situations, the wayfinder may not want to see as many landmarks as possible along the way. For example, the wayfinder drives a car from source to destination. He probably doesn't want to use many landmarks to guide his driving since it's not convenient to switch from one landmark to the other landmark frequently. But he still want to have at least one landmark to be seen at any point along the way. Therefore, the problem becomes: find a path P from s to t such that the driver can see at least one landmark at any point along P and the number of landmarks the driver can stick to is minimized. There are two cases: (a) The same landmark in different road segments counts twice. (b) The same landmark in different road segments counts once. We give the optimal solutions for those two problems by using modified Dijkstra's shortest path algorithm and modified Bellman-Ford algorithm.