Archive     Blog     Cast     Forum     RSS     Books!     Poll Results     About     Search     Fan Art     Podcast     More Stuff     Random     Support on Patreon New comics Mon-Fri; reruns Sat-Sun
<   No. 3937   2019-02-26   >

1 Dwalin: Soo where do hobbits live? Oondergroond?
2 Lambert: We live in villages. The best houses are finely furnished shallow burrows, but many live in cottages.
3 Lambert: The village street layout is critical. They need to be arranged so you can visit every house without travelling the same street more than once.
4 Dwalin: Why?
4 Lambert: Otherwise the path won't be Hobbitonian!

 First (1) | Previous (3936) | Next (3938) || Latest Rerun (2608) | Latest New (5242) First 5 | Previous 5 | Next 5 | Latest 5 Fantasy theme: First | Previous | Next | Latest || First 5 | Previous 5 | Next 5 | Latest 5 This strip's permanent URL: http://www.irregularwebcomic.net/3937.html Annotations off: turn on Annotations on: turn off

Yep, it's been 100 strips since the last hobbit pun.

A Hamiltonian path is, in graph theory, a path that connects every vertex of a graph (or every house in a village, as a concrete example), without traversing any edge of the graph (or any street of the village) more than once.

Hamiltonian paths come up in the famous travelling salesman problem: Given a list of cities and the distances between them all, what is the shortest path that visits each city and returns to the starting point? This problem is an optimisation problem of finding a Hamiltonian path that visits the cities, with the extra constraint that the path must be the shortest possible Hamiltonian path. It is a well known problem in the field of computational complexity because it is a classic example of an NP-hard problem - a full explanation of which would require digging deep into the realms of computational complexity theory, but which may be summarised as being a problem that is incredibly difficult to solve as the number of cities increases.

Given that hobbits deal with this sort of problem all the time in their villages, one suspects that while it's a difficult optimisation problem, it's not a very difficult hobbitimisation problem.