CLOSE
YouTube // poprhythm
YouTube // poprhythm

Solving the Traveling Salesman Problem

YouTube // poprhythm
YouTube // poprhythm

The Traveling Salesman Problem (TSP for short) is a classic problem in computer science. Wikipedia succinctly states the problem like so:

Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city exactly once and returns to the origin city?

First formalized in 1930, the TSP has been studied and fiddled with ever since. There are lots of ways to try solving the problem, but the devil is in the details. Most of us start with a simple assumption: Let's pick a starting city, then just start walking around the map, choosing the nearest city every time. Rinse, repeat. This algorithm is called "Greedy," and while it does a reasonable job for very short routes, it often fails to make the overall route the shortest, because it doesn't consider the entire route. (It "greedily" chooses the optimal choice in each leg of the route, at the possible expense of the larger route.)

Take a look at this video, illustrating several algorithms for solving the TSP, and compare the complexity of the solutions. Computers are rad.

Read more about this video from its creator, James "poprhythm" Kolpack. For a lot more on this problem and why it matters, check out this lecture.

[h/t: Kottke.]

nextArticle.image_alt|e
iStock
arrow
Big Questions
Why Are the Keys On a QWERTY Keyboard Laid Out As They Are?
iStock
iStock

Why are the keys on a QWERTY keyboard laid out as they are?

C Stuart Hardwick:

What is commonly called QWERTY (more properly, the Sholes layout) was designed by Christopher Lathan Sholes, then modified through a series of business relationships. Sholes's original keyboard was alphabetical and modeled after a printing telegraph machine. The alphabetical layout was easy to learn, but not easy to type on.

For one thing, all practical typing machines of the day relied on mechanical levers, and adjacent letters could jam if struck with rapidity. There has long been a myth that Sholes designed the QWERTY layout to slow typists down in order to prevent this. Nothing could be further from the truth, but Sholes’s first customers were telegraphers. Over several years, he adapted the piano-like alphabetical keyboard into
a four-row keyboard designed to aid telegraphers in their transcription duties.

This new layout mostly spread out commonly struck keys, but also placed easily confused telegraph semaphores together. This layout was sufficient to permit telegraph transcription to keep up with transmissions and created a growing market.

During this time, Sholes teamed up with several other inventors to form a typewriter company with assignment of all related patents. An association with Remington led to increased sales, at which time another company acquired the shift platen patent that permits a typewriter to type in mixed case, and they seem to have made a few essentially random changes in order to avoid the original typewriter company patents.

So that’s it then, right? QWERTY is crap?

Well, no. QWERTY was based mostly on the needs of telegraphers in transcribing Morse code, and Morse had been scientifically designed to make transmission of English language messages as efficient as possible. The result is that the QWERTY arrangement is pretty good—efficiency-wise.

In the 1930s, John Dvorak used modern time-motion study techniques to design his own keyboard, and around it had grown up a whole cult following and mythology. But the fact is, it’s much ado about nothing. Careful scientific studies in the 1950s, '70s, and '80s have shown that choice between the Sholes and Dvorak layout makes no material difference in typing speed. Practice and effort are what yields rapid typing, and studies of professional typists have shown that however well we may perform on timed trials, few typists ever exceed 35 words per minute in their daily work.

So relax. Take an online typing course, practice a little, and relax.

This post originally appeared on Quora. Click here to view.

arrow
Afternoon Map
Monthly Internet Costs in Every Country

Thanks to the internet, people around the world can conduct global research, trade tips, and find faraway friends without ever leaving their couch. Not everyone pays the same price for these digital privileges, though, according to new data visualizations spotted by Thrillist.

To compare internet user prices in each country, cost information site HowMuch.net created a series of maps. The data comes courtesy of English market research consultancy BDRC and Cable.co.uk, which teamed up to analyze 3351 broadband packages in 196 nations between August 18, 2017 and October 12, 2017.

In the U.S., for example, the average cost for internet service is $66 per month. That’s substantially more than what browsers pay in neighboring Mexico ($27) and Canada ($55). Still, we don’t have it bad compared to either Namibia or Burkina Faso, where users shell out a staggering $464 and $924, respectively, for monthly broadband access. In fact, internet in the U.S. is far cheaper than what residents in 113 countries pay, including those in Saudi Arabia ($84), Indonesia ($72), and Greenland ($84).

On average, internet costs in Asia and Russia tend to be among the lowest, while access is prohibitively expensive in sub-Saharan Africa and in certain parts of Oceania. As for the world’s cheapest internet, you’ll find it in Ukraine and Iran.

Check out the maps below for more broadband insights, or view HowMuch.net’s full findings here.

Map of Internet costs in each country created by information site HowMuch.net.
HowMuch.net

Map of Internet costs in each country created by information site HowMuch.net.
HowMuch.net

Map of Internet costs in each country created by information site HowMuch.net.
HowMuch.net

Map of Internet costs in each country created by information site HowMuch.net.
HowMuch.net

Map of Internet costs in each country created by information site HowMuch.net.
HowMuch.net

[h/t Thrillist]

SECTIONS

arrow
LIVE SMARTER
More from mental floss studios