Wordsnakes

Real-world problems related to the Traveling Salesman Problem often introduce considerations that make the situation far more difficult. For example, it is easy to imagine that price considerations may have to be balanced against salesman morale, customer availability, and market conditions if a real salesman were at issue. But even staying with simple cost functions, symmetry and the triangle inequality may not hold.

What carries over are:

1. The desire to estimate bounds (i.e. what is the optimal conceivable solution), because that will tell you whether it is worth struggling for more improvements.

2. Heuristic problem solving techniques.

As an illustration, consider a problem that can be formulated similarly to the Traveling Salesman Problem but requires new analysis.

Given a set of words, a wordsnake is a string containing all the words in the set. The optimal wordsnake is the one of shortest length. For example, given the words “super” and “perfect,” two possible wordsnakes are “superfect” or “perfectsuper.” The first one is shorter, so is better. Your problem is to find an optimal (shortest) wordsnake covering a set of words, given that you are allowed to rearrange the words.

Here are the words:

• subway

• dentist

• wayward

• highway

• terrible

• english

• less

• blessed

• warden

• rib

• stash

• shunt

• hunter

What does this have to do with Traveling Salesman? Well, let’s look at edges between pairs of words, for example, “warden” → “english.” We will consider the cost of this edge to be the number of letters of the target word (“english” in this case) that will be needed in the wordsnake that combines these two in this order (i.e., beyond those letters also included in “warden”). For this edge, the wordsnake would have “wardenglish,” so the cost of this edge is the length of “glish” or 5. Note that the edge “english” → “warden” has a cost of 6 (the full length of “warden”). So symmetry need not hold (though the triangle inequality does).

What would be a good lower bound on the length of the optimal wordsnake? Please pause to consider this before you read on.

I would vote for the following: For each word, consider all edges having that word as target. Find the edge having the smallest cost and add up all such smallest costs. For example, consider “shunt.” The lowest cost edge having “shunt” as a target is “stash” → “shunt” at a cost of 3. So associate 3 with “shunt.” Now just add all the associated costs with each word and you have an approximate lower bound to the cost. (It’s approximate because it’s conceivable that a word could be found in a partly constructed wordsnake. For example, if the words were “shunt,” “stash,” “till,” and “until,” then the wordsnake stashuntill would contain “until” even though the lowest cost edge from any single word to “until” has a cost of two.)

1. How close can you come to this approximate optimal for these words?

Solution to Wordsnakes

1. How close can you come to this approximate optimal for these words?

Order the words as follows (according to their best edges) and see that you come very close to the lower bound.

• subway

• wayward

• warden

• english

• shunt

• hunter

• terrible

• rib

• blessed

• less

• dentist

• stash

• highway

Here is the corresponding wordsnake:

 subwaywardenglishunterriblessedentistashighway