[Date Index]
[Thread Index]
[Author Index]
using Mathematica for solving TSP-like problem with route priorities
*To*: mathgroup at smc.vnet.net
*Subject*: [mg125617] using Mathematica for solving TSP-like problem with route priorities
*From*: Peter Sisak <p-kun80 at hotmail.com>
*Date*: Thu, 22 Mar 2012 05:49:03 -0500 (EST)
*Delivered-to*: l-mathgroup@mail-archive0.wolfram.com
Dear Mathgroup,
Seeing Mathematica's capabilities in a number of
combinatorial/optimization problems, I would like to know if someone
could solve my problem as well (unfortunately, I'm completely
unfamiliar with the magic needed.) 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 =E2=80=93 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.
..X...X..
..XX.XX..
XX.X.X.XX
.XX.X.XX.
...XXX...
.XX.X.XX.
XX.X.X.XX
..XX.XX..
..X...X..
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:
a.. 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
\=E2=80=99s first then all /=E2=80=99s 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.
b.. 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 =E2=80=93 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.
c.. 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).
d.. 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.
e.. The desired start/end points are not specified. It needs to be
found by the solver.
>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 =E2=80=93 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 (=E2=80=9Ctraffic
light=E2=80=9D) 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 =E2=80=93 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
Prev by Date:
**Re: new functional operator**
Next by Date:
**Re: new functional operator**
Previous by thread:
**Re: Exporting a formula to Excel via copypaste**
Next by thread:
**Re: using Mathematica for solving TSP-like problem with route priorities**
| |