|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
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 (2205) |
Latest New (4605)|
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.
I think you have discovered a major piece of Middle-earth anthropology - how the Shire kept its idyllic structure of scattered villages. Villages can only grow as long as its Hobbitonian-ness can be checked by brute force - that is, by hobbits wandering round visiting their friends while recording their path. Obviously, a new street cannot be built until this property has been checked, a task which becomes impossible when a village exceeds the optimum size.
LEGO® is a registered trademark of the LEGO Group of companies,
which does not sponsor, authorise, or endorse this site.|
This material is presented in accordance with the LEGO® Fair Play Guidelines.