gtoal wrote:

Saiid wrote:

Well, I fixed the blocks themselves, but it doesn't seem to have done much.

Does yours actually work for you? I've never seen a version of it that does anything. The original one never returned, then when you updated it, it returned immediately with an error before it could possibly have had enough time to calculate anything. Without any sort of graphical feedback it's impossible to tell if it has done anything at all.

G

Right now, if you look at it, it calculates the first 30 and draws a graphical representation, but it always gives an error

Saiid

Saiid wrote:

Right now, if you look at it, it calculates the first 30 and draws a graphical representation, but it always gives an error

What I see when I run your code is the initial random route that you're given as a starting point. I'm comparing it side by side with the original project and they're identical.

gtoal wrote:

Saiid wrote:

Right now, if you look at it, it calculates the first 30 and draws a graphical representation, but it always gives an error

What I see when I run your code is the initial random route that you're given as a starting point. I'm comparing it side by side with the original project and they're identical.

Then it's not processing my code correctly. I put my solve code in the place you said to, I don't get why it's not doing anything.
Or is it that my code runs using

replace ... :: list

rather than doing

delete (all v) of [Next City v]

and then adding it all?
EDIT: Found the problem. For some reason, getClosest(); is reporting every closest city to be 2

Saiid

Is anyone considering using an ant colony approach (you send a bunch of virtual “ants” that wander around. The ants wander and leave a trail of pheromone wherever they go. The more pheromone there is in a trail, the more likely it will be walked over. However, the strength of the pheromone trail will decrease over time (this time also takes the ant's walking time into account).

Just had a look at this, and noticed a couple of mistakes in the “Test Solution” script…

I'm assuming that the “Next City” list is meant to show the route from city to city in order of that route.

In that case, the next city after variable “City” is not “item City of Next City”. Rather “item City+1 of Next City” is the next city after “item City of Next City”.

It means you just want to compare the distance between the co-ords for “item (City+1) of Next List” and “item (City) of Next List”, and you should just increase City by one (rather than setting it to “item City of Next City”).

It should also start off City as #Cities (since that's the index of the last city in Next City, which itself is the city you want to start from). –It'll also have to deal with setting City to 1 on the first pass through the loop (rather than adding 1 to it).

Without those fixes, it'll likely not give the correct total distance, and will likely also fail any suggested route other than the original list.


I'd quite like to have a go at this, but I'm kinda busy over the next week with work (presentations & stuff to do for meetings), so I doubt I can realistically do anything worthwhile within the required time.

Maybe I'll give it a go after then, though, and see if I can come up with something decent…

DadOfMrLog wrote:

Just had a look at this, and noticed a couple of mistakes in the “Test Solution” script…

I'm assuming that the “Next City” list is meant to show the route from city to city in order of that route.

In that case, the next city after variable “City” is not “item City of Next City”. Rather “item City+1 of Next City” is the next city after “item City of Next City”.

It means you just want to compare the distance between the co-ords for “item (City+1) of Next List” and “item (City) of Next List”, and you should just increase City by one (rather than setting it to “item City of Next City”).

It should also start off City as #Cities (since that's the index of the last city in Next City, which itself is the city you want to start from).

Without those fixes, it'll likely not give the correct total distance, and will likely also fail any suggested route other than the original list.


I'd quite like to have a go at this, but I'm kinda busy over the next week with work (presentations & stuff to do for meetings), so I doubt I can realistically do anything worthwhile within the required time.

Maybe I'll give it a go after then, though, and see if I can come up with something decent…

Thanks - I definitely had a problem with the traversal of the resulting list (which I worked on yesterday) but I'm not quite sure it is the problem you describe. My intention was that City 1 was the starting point, but after that it was a linked list, eg if city 1 led to city 5, then item 1 of city equals 5. The following city would be whatever the contents of item 5 of city were, not the contents of item 2. I.e. the array is not the cities in order, the array is the exit path from each city. This is not the same as item 1 of city being the first city and item 2 of city being the second city, etc. My intention was that people who were doing iterative improvements to the cycle could swap a couple of pointers rather than have to reorder the entire array…

I'll go over it and check the logic and write up a better description of the interface once I'm sure it works.

Having also tried a few experiments myself, I'm starting to think there may be some help needed for implementations where each city is represented by a clone, which is not too well supported at the moment. (I'm thinking of using the trick that was used in some of the Voronoi projects to find neighbour distances in parallel - not because it's faster than a spatial data structure, but just because it's a trick that fits well with the style of Scratch)

Looking forward to seeing what you come up with!

Graham

gtoal wrote:

Thanks - I definitely had a problem with the traversal of the resulting list (which I worked on yesterday) but I'm not quite sure it is the problem you describe. My intention was that City 1 was the starting point, but after that it was a linked list, eg if city 1 led to city 5, then item 1 of city equals 5. The following city would be whatever the contents of item 5 of city were, not the contents of item 2.

Yeah, as I was writing above, I wondered if you might be looking for something along those lines.

I suspect that's not such a good requirement, since it's not at all intuitive for Scratchers to work with such a list (and they may not understand how to create such a list from whatever they do use).

However, if someone actually does want to work with such a linked list, then they can do that internally as desired, but then easily convert that into a more intuitive ordered city list at the end.

DadOfMrLog wrote:

However, if someone actually does want to work with such a linked list, then they can do that internally as desired, but then easily convert that into a more intuitive ordered city list at the end.

Agreed.

Is this true?: Assuming all cities are connected in a cycle, if at some point in the cycle there is a segment AB and another segment CD, and AB crossed CD, then is it the case that by deleting those two links and reconnecting with either AC and BD or AD and BC, the new path must be shorter or at least not longer than the original?

I didn't read this anywhere, it was just a thought that occurred to me just now, I've no idea if it holds true. It was prompted by me asking myself if TSP solutions were allowed to have crossovers and thinking of TSP art I've seen, which doesn't have crossovers. Which implies that getting rid of crossovers may be a stage in finding a solution?

G

gtoal wrote:

Is this true?: Assuming all cities are connected in a cycle, if at some point in the cycle there is a segment AB and another segment CD, and AB crossed CD, then is it the case that by deleting those two links and reconnecting with either AC and BD or AD and BC, the new path must be shorter or at least not longer than the original?

I didn't read this anywhere, it was just a thought that occurred to me just now, I've no idea if it holds true. It was prompted by me asking myself if TSP solutions were allowed to have crossovers and thinking of TSP art I've seen, which doesn't have crossovers. Which implies that getting rid of crossovers may be a stage in finding a solution?

G

From what I can calculate in my head, yes, it would.

Saiid

Saiid wrote:

From what I can calculate in my head, yes, it would.Saiid

well, so far the ideas I'm mulling over are something like this… (I'm deliberately not looking up algorithms online, I'ld rather reinvent one than just code up someone else's idea…)

1) build up pairs of closest points, treat line segments as a virtual point, build bottom-up until cycle formed
2) find nearest points to lines *or*
3) find nearest lines to points (delauney/voronoi may help for one of these. This *might* be possible with graphical trick)
4) look at ABC segment. Find line XY closest to B. if |XBY|+|AC| > |ABC|+|XY| then move B to the other segment.
5) look at places where AB crosses CD. Assuming B connects to C and D connects to A, test uncrossing (AD and BC) and if shorter, uncross.

6) once I have a reasonable starting point from above heuristics, randomly pick pairs of line segments and see if swapping improves.

7) Look at convex hull. Intuitively looks like it might be a possible starting point for refinement. Perhaps make a loop then remove all points from hull and do it again, then join nested hulls by breaking adjoining links.

gtoal wrote:

Saiid wrote:

From what I can calculate in my head, yes, it would.Saiid

well, so far the ideas I'm mulling over are something like this… (I'm deliberately not looking up algorithms online, I'ld rather reinvent one than just code up someone else's idea…)

1) build up pairs of closest points, treat line segments as a virtual point, build bottom-up until cycle formed
2) find nearest points to lines *or*
3) find nearest lines to points (delauney/voronoi may help for one of these. This *might* be possible with graphical trick)
4) look at ABC segment. Find line XY closest to B. if |XBY|+|AC| > |ABC|+|XY| then move B to the other segment.
5) look at places where AB crosses CD. Assuming B connects to C and D connects to A, test uncrossing (AD and BC) and if shorter, uncross.

6) once I have a reasonable starting point from above heuristics, randomly pick pairs of line segments and see if swapping improves.

7) Look at convex hull. Intuitively looks like it might be a possible starting point for refinement. Perhaps make a loop then remove all points from hull and do it again, then join nested hulls by breaking adjoining links.

Sounds reasonable. I was basically trying to do this:

1) run through the list of cities, finding the city closest to each
2) copy the list of cities
3) use the copied city list and the list of closest cities to replace each next city with the city closest to the current city

Saiid

I had a go at this: https://scratch.mit.edu/projects/131906576/

PutneyCat wrote:

I had a go at this: https://scratch.mit.edu/projects/131906576/

Not bad at all! This is the one to beat. About half a minute for the 300 city is quite respectable!

gtoal wrote:

PutneyCat wrote:

I had a go at this: https://scratch.mit.edu/projects/131906576/

Not bad at all! This is the one to beat. About half a minute for the 300 city is quite respectable!

Thanks. BTW as you may have seen I had (independently) had the same thought about crossing lines. It must be right that uncrossing lines makes it shorter. My proof (?): Think of the crossing lines as made up of four lines (each point to crossing point). Then compare the replacement uncrossed lines with those four lines. In the case of each, you're comparing a straight line between two points with a less straight route. If that makes any sense…

well, i have my solution….
it isn't a ‘perfect’ solution, you can adjust the ‘perfectness’ by remixing it.
the key here is that it will lose ‘interest’ after finding a better solution, every time it finds a new solution its interest will reset. when it runs out of interest it will stop and record it as a solution:

when green flag clicked
forever
some code to test a solution
change [intrest v] by (-1)
if <(length) < (best)> then
set [best v] to [length]
set [intrest v] to [100]
end
if <(intrest) = [0]> then
records solution...
stop [all v]
end
end

my original project is here

PutneyCat wrote:

gtoal wrote:

PutneyCat wrote:

I had a go at this: https://scratch.mit.edu/projects/131906576/

Not bad at all! This is the one to beat. About half a minute for the 300 city is quite respectable!

Thanks. BTW as you may have seen I had (independently) had the same thought about crossing lines. It must be right that uncrossing lines makes it shorter. My proof (?): Think of the crossing lines as made up of four lines (each point to crossing point). Then compare the replacement uncrossed lines with those four lines. In the case of each, you're comparing a straight line between two points with a less straight route. If that makes any sense…

It does seem intuitive to me but I suspect a proper proof will involve something to do with triangles :-)

When I set this problem I honestly didn't know if getting an acceptable solution to 300 cities within a reasonable time was going to be possible. Now that you've built a proof of concept I think we can leave this challenge open indefinitely to allow incremental refinements.

G

gtoal wrote:

PutneyCat wrote:

gtoal wrote:

PutneyCat wrote:

I had a go at this: https://scratch.mit.edu/projects/131906576/

Not bad at all! This is the one to beat. About half a minute for the 300 city is quite respectable!

Thanks. BTW as you may have seen I had (independently) had the same thought about crossing lines. It must be right that uncrossing lines makes it shorter. My proof (?): Think of the crossing lines as made up of four lines (each point to crossing point). Then compare the replacement uncrossed lines with those four lines. In the case of each, you're comparing a straight line between two points with a less straight route. If that makes any sense…

It does seem intuitive to me but I suspect a proper proof will involve something to do with triangles :-)

When I set this problem I honestly didn't know if getting an acceptable solution to 300 cities within a reasonable time was going to be possible. Now that you've built a proof of concept I think we can leave this challenge open indefinitely to allow incremental refinements.

G

Yes, good idea to leave open - maybe some prodigy will definitively crack the problem! Scratch is such a wonderful platform that I really think anything is possible. Re crossing lines, the “proof” does sort of involve triangles :-). (Draw the crossed and the uncrossed lines and you get two distinct triangles. In each case one side comes from the uncrossed lines and two come from the crossed.) Thanks again for this enjoyable challenge.