4
$\begingroup$

This is a real situation (I hope it's ok that I post this here. If not, please suggest a better home). I have little knowledge of algorithms, but I know I can use one to solve this problem.

I'm looking for an answer, or an online resource that can help, or an algorithm I should research to help me find the route with the least overlap.


I have an enclosed structure with rafters. I want to hang christmas lights inside it, and I'm trying to figure out how to cover all the ceiling beams with lights while minimizing overlap.

Here's a rudimentary schematic of the structure: A rudimentary schematic of the structure

  • The pink circles are places I can hang the lights from
  • The yellow dots are where the lights should be
  • "Start" is the only available electrical outlet
  • Each strand of lights is aprox 234 inches (droop and empty sections have been accounted for)

What is the most efficient path(s) to minimize overlap?

Here's some things to keep in mind:

  • Assume I have an infinite number of lights
  • The beginning of a strand of lights has a male electric connector. The end has a female.
  • The start (male) of one strand must intersect with the end (female) of another strand (for electricity).
  • Multiple strands can start from the same point

Here's the XML of the diagram (you can use this in draw.io):

<?xml version="1.0" encoding="UTF-8"?>
<mxfile userAgent="Mozilla/5.0 (Windows NT 10.0; Win64; x64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/60.0.3112.90 Safari/537.36" version="7.1.3" editor="www.draw.io" type="device"><diagram id="d7d79c46-3ad7-dd0f-4011-e37531a3d72a" name="Page-1">7V1Lk6M4Ev4tc3DE9KEckngf29Xd24fZiImtjdjpo8rINtsYebHq4fn1KwHiIYGLcoNM2XYdClKyBF9+SqVSCZ5Z99vXf6R4t/knDUk8QyB8nVlfZghB2/L4PyE5FBLgglyyTqOwkFWCh+hvIisW0qcoJPtGRUZpzKJdU7ikSUKWrCHDaUpfmtVWNG72usNrogkeljjWpf+JQrbJpb4DKvl3Eq03smcIipJHvPy5TulTUvQ3Q9Yq++TFWyzbKurvNzikLzWR9XVm3aeUsvxo+3pPYgGuhC3/3reO0vK6U5KwPl9w8i884/iJyCvOrosdJBbZ3RBRH8ysxcsmYuRhh5ei9IWrn8s2bBvzM8gPi+ZIyshr5yXB8kY5gwjdEpYeeJXiC34BzaF5+lLpAUo2beo6kEJc6H5dtlzdPz8oIGiHw50eHMg+Ix7e9PCwwRnx8KeHh+OeEY9gengo5qMcPkbwkPPXhAEpx48ZQOD0AIGoiUg5guqIoNEQQdNHxENGEbGmj4jfZlbHQ8SeHiKqH2LYsE7QUVU9EcOITNBXVX0Rs4igCU6+6qgxO/uiCc6+6qgxjMgEZ1911BhGZIKzrzpqWj208RCZ4OyrjhrDiExw9lVHjWFEJjj7qqOm1YsfD5EPECsyjMgHiBYZRmSC8SItvmo0gGZN0GfVIqxmEZmgz6rFWM0iovusnjOXc3INFn6DrHnve5bSn+SexjTlkoQmvOZiFcWxIsJxtE746ZIDQrh8IeCKljj+XBRsozAU3bSCPQDCUPP4NIDtFnzREPDqDnBfeFOyj/7Gj1kFwcQdjRKWXYqzmDlfBLBPjO7z7U1YwzkmK9aCMqMCzj1HN0rW/xYnX+7sgcxc4DQAbvGWnLEA1v1pDrAFLw1i2wFvQdxmIwaBuM1Bd2MBQBg9NzB2//ckNpcXAuq7AqzPvEYx9MtyfrQu/mftcMgSKfM8KeUXVi+oibN+pfSS1Oyi5khqMVXWWGrWVx2+d1noelYTXehAc/DqSxjfnfsXZ6g8aZEP0sFA5iyVvijyvfkFQuw3ILY9z9x8q6+yOMSWd3EQN1nsWuZcGltftnGI3ctjcRNiLzAIsb4O9IOLc8tVhIOW6W40hPV1pdxUvBR4A3VVqVvhsZwJuy0eWnelW3zyZb4qF+54un78nV8F7wbIf58yTMCKJuxuhbdRfMirfifxMxGI1spz9EUpRLvXekHeqShJaLrFca3sGacR5v+5XjB7SkUC7tF6S7zrqvJSoKkWxoTxVcZdoWy9nKa7DU6KVlEu61ipVGVREmZ8EIVA3m1WwlLe2Iq3L3vKoh2CACKMkV1GCUYZzBDsyDKIa9fwQtOwedVlR/xeH39GvC/RYR5wuSv41ahXpQbfKXrOlm9CxfWDT7XbCMmSpphFNKnrL0oiFkng1Hq1Lhr1wmi/i/FBlsQRRwSB36LtjqYMJ6zQYUwxUzBTF4ZObo071oFvWpEBRjfUtoBsbXi3RY2sAYa307YBlGMhBkDr8FZGJhIjU4MVZl/lvA3FcFiJMSOufM8PssZAFk+pfUvin3fbgT+/+Gi3F4rcb/BOCJcxfeL38lb0NMT7TRZpFSf1yGGV2W4tYvxI4kXJ77YqzUgkLwm+ir+yRKbZo4HCXbDpf7dlolijRWydHjs/lUbe0ADe7/JHHFbRq9BEW/xWQ/fbNx8txCS6TnEYcdBqZaHjWUE4FvLum0GwtiFpD4F6j92lS0UdobPB7uproauB3fLPB3uPfbJLhd1Rdotcyxzs+qLpamD3wPnY3iNL7VJhh+p+vEnce+TCXSru6pwKAdKDM6MB3yPl7lKBtzxfAV568yaA75HZd6nAO5YKvEnG90ggvFTg3eCcjL/i1ao6t3LGG5xcr3jBqgLvtTz0MBbu3qgr1o5gWHfy3YS0ogZULX2/ZDSlXPF6Vn1szqAN8q54PavAbrVk9Y4G+xWvZ9UwglG6X/F6VsXdKN+veFWl4u7IBC0DuPvXPKsqiyqTLqZ/xdOqyneT8Uq/xc7co9lnYAGUZ/JmZ7oukvCzeG/cTGyM4/0+Wmbo4JTp4uaWOE1Y8f46sUHfkdwkatXwB9mne62QqU98ZmVe1CzPtcovnITa6+veVM4bCWVSlpIYs+i52XybRooe/hTJX5Xulf0wNdNiT5/SJSm+U2lVa8ZDx9vhilkTprWTsaO8536bxi0DNaNImfr964RppLaBSvBHlg9XlywoY3TblP2rUFI3uxqELKAhacRRIOlDSR9PNJnjrxe6R8lYZnF08bhJ0tqYgK5mZeAHoLH6+h8IvIGYrLc0HJch1B8GERg/FKfFVNF8erKYZ8QheY3YX+J47hRnPyQV5WsqgUq3HqT5L2HsUPBBZIZyEU3Zhq5pguM/aDYq9IcVG/TSpqk6xewjxOxLNI5ZplCpJNDOvl+kVRDMg9pHPhMg/UK7Wez34gk3N/hQq1Zk43ZTW3lKzSneWVfRLm/xZBLK2b9mUR+EXTzd/+lDuC43yEePlqsbITTTstlCh/ih3eQWQke41eJYBV4IPG+gCClUFOXrwTivzY2yft2NgqBPfKKaAgv036kzPT9Qqid4hxpET39ikVacZN0hYOvKXflLsly2+8lf3S51Euw+ZuTh4vQgTOMdmAPgSckPKbGkpJxaVcMpYHg8ikB/U5VbgoIV55wmlX1ax3FOmyRVqkPgjzdJgj4hoOuh9jsYKv0DyBkPax5CNQS4QB0Bp83A/jlp7Su0du1j83Jfkne813oMhvfJHbkx/AjDuQfccIGr02Honec6nM1sqy5gMNDiZkxO9wkgXw+np+SQnG2RDgPFa7DBEIaatzu3HBTYfD3t2h6QW6TldODMa6XyqYMxON8nI+ojcX61Qu/n/GoVBqfb8SCwGoYcwGEtef7E7PmGgOKqBGO4KlpkfkiO90k+u3HcMMfP5plAr2l6Gzy0gmDu+6is4J7otfjHonBWz7jbSWTvk/B3I/uN7JmbAccnu6M+7TrkZkSfLMsb2T+g460u+zz4C572EXaKAfL+DZGTuNonTebG1Y/IVcVD9tUYRX+uese46nunbN6dxFV04+p1cFUENEYhKwSWMbbquy3I5V5c2+vohkjCyrIBrjwJq+MXI99Loq4f4RiDJfqOBXLttre93TgyCkc05Z5IEt1kDckSfQ/AQc4c+jdbMhpP/I6fW31/SNEkUdriLOd49559e/fe1N+958hX7tUOpv/uPXD6i/felzo56K862D2fODrhBX38tPrV9NxmVL9Nb339Pw==</diagram></mxfile> 
$\endgroup$
  • $\begingroup$ This is absolutely on-topic. Welcome to the site! $\endgroup$ – David Richerby Aug 16 '17 at 19:12
  • $\begingroup$ By the way, just above "start", you have a three-way intersection that isn't a hanging point. Is that a mistake in the diagram? (If it's deliberate, it's not possible to hang lights on the line segment heading south from that point to the next intersection.) $\endgroup$ – David Richerby Aug 16 '17 at 19:22
  • $\begingroup$ @DavidRicherby Thanks for the support! In answer to your question, it is deliberate, not a mistake. There is not a hanging spot at the 3-way intersection. What I'll need to do is rely on tension from another hanging spot to wrap around that corner - I wasn't sure how to show that in the diagram. $\endgroup$ – Travis Heeter Aug 16 '17 at 23:54
  • $\begingroup$ Gotcha. Essentially, you have a bent link around that corner -- you'll probably need to pretend that that's not an intersection, and the mathematics and algorithm should work just fine. $\endgroup$ – David Richerby Aug 17 '17 at 0:04
2
$\begingroup$

The problem you're trying to solve is called the route inspection problem (a.k.a. Chinese postman problem, from back in the days when it seemed normal to call something "Chinese" because the first person to study it was Chinese). Good news – there's an efficient algorithm, described in the Wikipedia article.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.