5 ms·
People who like this should also check out Robert Bosch's "TSP Art" (TSP stands for Travelling Salesman Problem). While this submission focuses on mazes, Bosch
by xamuel 8y ago
People who like this should also check out Robert Bosch's "TSP Art" (TSP stands for Travelling Salesman Problem). While this submission focuses on mazes, Bosch focuses on non-intersecting paths. The two problems are clearly dual, since a maze's solution is a non-intersecting path, and conversely every non-intersecting path is the solution to a corresponding maze.
http://www2.oberlin.edu/math/faculty/bosch/tspart-page.html http://www2.oberlin.edu/math/faculty/bosch/tspart-page.html
- qxi 8y agoOP's site is from 2005 and Bosch's site mentions the author of, and links back to, the submitted link ;)
- xamuel 8y agoOh, thanks, I explicitly tried to check but somehow missed that!
- adaml_623 8y agoDid you notice the dates on the page? The linked web page predates Bosch's work.
- onychomys 8y agoHis don't really look like mazes, though. There's never any choice involved in the lines. In a maze, you're constantly needing to decide if you should go left or right. His art is just one single line without any branches, as far as I can tell (...and as you'd expect from a TSP algorithm!).
- cr0sh 8y agoDid you miss this part of the post you're responding to (I am modifying it to make it hopefully clearer)? > The two problems are clearly dual > A: since a maze's solution is a non-intersecting path, and > B: conversely every non-intersecting path is the solution to a corresponding maze Focus on "B" - the output of a TSP algorithm "is the solution to a corresponding maze". IOW, the negative space of the TSP algorithms output is the maze itself...
- deleted 8y ago[deleted]
- onychomys 8y agoThat post was edited after I responded to it.
- andjd 8y agoI went to Oberlin, where Bob is a professor. The pair of Campbells soup pictures were gallery framed on the wall of one of the classroom buildings
- deleted 8y ago[deleted]
- flashman 8y ago/u/rhiever also published some code on transforming an image into a travelling salesman path: http://www.randalolson.com/2018/04/11/traveling-salesman-portrait-in-python/ http://www.randalolson.com/2018/04/11/traveling-salesman-por...