The Traveling Salesman's Problem: Part 6 of Ann's Visit to G'Raph

The traveling salesman problem is a route planning problem. The goal is to find the shortest path through a graph that visits each node exactly one time and returns to the starting node. The problem is also a classic example of a class of computational difficult problems, called NP-hard. There are no known efficient solutions (polynomial time) for solving NP-hard problems, and it has yet to be determined whether or not such a solution even exists.

Ann looked at the depressed scholar in the corner. "You have been working on the same problem for twenty-five years?" she asked.

"I am so close," he answered.

Behind her, Florence and Edgar had stopped arguing. They peeked their heads around the stack of books.

"Oh. I see you met Geoffrey," said Edgar. "Never mind him."

"I want to hear more about this problem," stated Ann. "What do you mean by shortest path?"

Geoffrey did not answer. He was hunched over his paper and mumbling to himself.

Ann turned back to Edgar and Florence. "You just told me about a shortest path algorithm,” she said.

"This is different," explained Florence. "The traveling salesman problem is a particularly difficult path planning problem. The goal is to find the shortest path through a graph that visits each node exactly once and returns to the starting node."

"Here are two example paths through G'Raph's school neighborhood," offered Edgar, drawing a crude sketch on a nearby blackboard.

Path 1

Path 2

"Both paths cross each node exactly once. Path 1 has a distance of 55 meters, and path 2 has a distance of 66 meters," he explained.

"That seems simple enough," commented Ann. "There is really no algorithm to solve it? Why not try all possible orderings of nodes? For each ordering, you could compute the total distance traveled if you visited the nodes in that order."

"There is no known efficient algorithm to solve it," explained Edgar. "No polynomial solution at least. The method you suggested would work, but it is factorial. You have to look at N! different orderings. For the 5 nodes in our simple example, there are 5! = 120 different permutations."

"Polynomial solution?" asked Ann.

"An algorithm where the running time scales polynomially with the size of the problem -- O(N^k) for some fixed value of k. For example linear algorithms O(N), quadratic algorithms O(N^2), and cubic algorithms O(N^3) are all polynomial. But the algorithm you suggested is O(N!); it scales as the factorial of N." Edgar explained.

Florence shrugged. "No one actually knows if there is an efficient solution or not. At least no one has found an efficient solution yet. There are good approximations and reasonable heuristics, of course, but no polynomial time algorithm."

"I played with it for a while," offered Edgar. "I never made much progress."

"Geoffrey has been working on it for twenty-five years?" asked Ann.

Both scholars nodded. "Ever since he met that man, Geoffrey has been unnaturally obsessed with this problem. He does not think about anything else. In the past, he would work on 3 or 4 different problems at the same time. It is as though he is under some sort of spell." Edgar explained.

Edgar's words sent a shiver through Ann. A vague memory floated through the back of her mind, but she was unable to latch onto it.

"Has anyone else met that man?" Ann asked.

Edgar shrugged. "I do not think so. Geoffrey said that he was probably a visiting salesman."

"He was selling questions," Geoffrey said quietly. Ann jumped at the sudden statement. Even though she had spoken to him only a minute ago, she had forgotten he was there.

"What did he look like?" asked Ann. The undefined memory continued nag at the back of her mind. She was miss a connection.

"Dark cloak and a large wooden staff that was covered with mathematical symbols," answered Geoffrey. "Never did see his face though."

"You only saw him that on time? Twenty-five years ago?" she confirmed. Why should an event from twenty-five years ago strike any memories with her?

"Three times," answered Geoffrey. "The first time was twenty-five years ago. Then, I saw him again ten years later. I was about to give up on the problem, but he found me and asked if I had solved it. That question rekindled the fire. I knew I could find a solution."

"And the third time?" asked Ann. She could feel a pit of fear building inside her, but she was not sure why.

"This morning," mumbled Geoffrey. "As I walked by the school, I saw him talking to some girl. He stopped for a moment and waved with his staff. I still have not found a solution yet, so I kept walking. I know I can find one. I am so close."

Ann did not wait for the rest of the story, she ran out the door and toward the school.

To be continued in Part 7: Panicked Depth First Search…

Follow Ann's Visit to G'Raph from the beginning with Part 1: The City of G'Raph.