using Octave for solving TSP-like problem with route priorities

[quinyu]

Dear Sirs,
 
  Seeing how useful Sage is in a number of combinatorial problems, I would
like to know if it can be used to solve my problem as well. The problem at
hand is cross-stitching. As you might know, in cross-stitching one
embroiders the pattern onto a suitable cloth (generally this is a so-called
“Aida” cloth, although the quality of the base textile is irrelevant in the
problem posed – it can have some indirect scope in, say, calculating total
yarn usage) with a continuous yarn. The pattern is generated by forming
X-es, between the weave gaps of the base textile. A sample pattern is here,
with a basic floral pattern.



In the attached pattern, dot means a space left empty, while an X means a
place cross-stitched. A multicolour cross-stitch pattern is, for all
purposes, just a sum of its elements, so it can be optimised discretely for
each of the colours involved – but seeing such functionality is not
something I am interested in or expecting at all.
 
  In cross-stitching, the following constraints are observed:
--All X-es are executed in the same order. That is, depending on the
decision of the program or embroiderer, first the \ (top-left to
bottom-right or bottom-right to top-left) stitches are executed, then the /
(bottom-left to top-right or top-right to bottom left), overlapping the
previously laid \. This however does not mean that all such occurrences
(pattern-wide) need to be separated, doing ALL \’s first then ALL /’s
second; only that within the scope of an isolated cross-stitch of the
pattern, there is ordered execution, but one easily might leave half of it
done, then execute the other half somewhere in the middle, instead of
separating the execution of the whole pattern into two strictly oriented
phases. The execution order is relatively highly weighted, one can put a
(say) +10.0 penalty on execution of a stitch in a wrong order (while it is
possible to lead the needle and yarn under the previous stitch on the front
side, it generally adds much to the difficulty of execution, and usually it
comes out looking less neat.) The execution direction of a given sub-stitch
of the X is essentially uninteresting (that is, no penalty for doing a \
stitch from top to bottom instead of bottom to top.) This is the route
priority mentioned in the topic.

--The back side should preferably consist of unit-distance orthogonal steps.
Of course, in case of a pattern more spread and disjoint, it is impossible
to execute them without larger jumps, but these should be minimised, and
preferably these should be also orthogonal. A suggested simple penalty
metric is (distance travelled on backside)^2 – 1. Incidentally, the
preferred execution by human hobbyists appears to give more weight to one
axis over another (say, preferring vertical back side stitches over
horizontal), but this, if any, should be given only very small penalty, on
the scale of 0.025*(total count of back side orthogonal stitches in the
wrong direction) or so.

--The front side is strictly not permitted to have any parts of the cross
double-stitched (the yarn going the same front side subpath twice,
regardless of direction).

--The back side is permitted to have the parts double-stitched (yarn going
the same subpath twice), although this is discouraged. A suggested penalty
metric would be (length of yarn overlapping) * 1.0.
 
>From what I know, there was no research whatsoever on execution of
cross-stitch patterns, neither is there any software that I know of
(commercial or otherwise) that can do any optimisation or planning on the
execution of a cross-stitch pattern. Since the research and functionality on
executing these cross-stitch patterns might prove useful (for hobbyists or
for software companies), I would like to know some suggestions, code or
feedback on it. For a reasonable visual representation, the end solution
should be presented in a “step-by-step” manner, with each step, presenting
the consecutive front-side stitches (subpaths), showing its direction (maybe
with a small arrow?), and showing the incoming and outgoing backside
stitches in a lighter shade. Generally, showing _all_ backside stitches
would result in a rather crowded display which would be a terrible mental
gymnastics to interpret, so it is to be avoided – perhaps a separate summary
output for showing general overlap in the end solution is something that
could prove useful, showing possibly a 0.2 units wide yarn, and colouring
the total overlaps with either a shaded weighted representation or the
common green-yellow-red (“traffic light”) weighted representation. Possible
extensions of the basic cross-stitched execution involve front-side
half-stitches (only \ or / done instead of the full X, this could probably
be relatively easily coded and executed, both in notation as well as
programming), orthogonal stitches on the front side, or other stitches of
varied length and angle – but all these are beyond the scope of my request,
and I believe putting it all in would be a much more challenging task (not
to mention they’d need a more intricate notation, one that I wouldn’t
undertake inventing. But sure enough, if you feel the original constrained
problem is too simple, why not generalise it...)
 
Thank you for your help in advance
Peter Sisak

--
View this message in context: 
http://octave.1599824.n4.nabble.com/using-Octave-for-solving-TSP-like-problem-with-route-priorities-tp4485498p4485498.html
Sent from the Octave - General mailing list archive at Nabble.com.