Trajectories of Search - Mapping Scientific Frontiers: The Quest for Knowledge Visualization - page 143

documents according to the likelihood that users would visit one document from
another via hyperlinks (Pirolli et al. 1996 ). In the following examples, we first
introduce a travel planning problem in the real world and then discuss real-world
navigation strategies in a virtual world.

4.1.1 Traveling Salesman Problem

The traveling salesman problem (TSP) is a classic example in algorithms. Given a
finite number of cities along with the cost of travel between each pair of them, the
salesman must find the cheapest way of visiting all the cities and returning to the
starting point. The TSP problem belongs to a class of hard problems. No known
algorithms have the complexity of polynomial or faster. Therefore, the total number
of cities in a TSP indicates the hallmark of the strength of a TSP solution. The size
of solved TSP examples has been steadily increasing. The largest number of cities in
a TSP solution is 15,112. Alexander Schrijver gave a good survey on this topic in his
paper “On the history of combinatorial optimization (till 1960)” (Schrijver 2001 ).
In an 1832 manual for the successful traveling salesman, the problem was
formulated without using mathematics. The manual suggested five tours through
Germany. Martin Groetschel ( 1977 ) published a 120-German-city TSP solution in
1977. The largest TSP solution to date is a traveling salesman problem through
15,112 cities in Germany, exceeding the 13,509-city tour through the United States
solved in 1998. The computation was carried out on a network of 110 processors
located at Rice University and at Princeton University. The optimal tour is equivalent
to a trip of approximately 66,000 km through Germany. It was proved to be the
optimal solution in April 2001. Figure 4.1 shows three famous traveling salesman
tours in Germany. Note that the projections of the map and the city data do not quite
match.
There are three reasons why I include examples of the traveling salesman
problem in a topic about mapping knowledge structures in scientific frontiers. First,
the traveling salesman problem represents one of the most common tasks we do
with a map as a journey planner. In the abstract world, an equivalent question would
be “what is the shortest path that will link up all the necessary publications to help
me understand a research subject matter?” In fact, Henry Small at ISI extracted such
pathways that can do precisely a virtual tour of a scientist through intellectual cities
in scientific literature (Small 2000 ). A topic in subsequent discussion will focus
on users' search patterns in a visual-spatial environment on computer. The second
reason is that in addition to geographic locations and thematic overlays in thematic
maps, there is another dimension worth noting: actions and events. The structure of
knowledge acquires more meaning in the context of such activities. The third reason
is related to the concept of trailblazing, which leads to the following examples.
Transitions from real-world navigation to virtual-world navigation are made by
studying how people navigation in virtual environments that replicate some common
navigation cues found in the real world. Darken and Sibert ( 1996 ) noted that