Travelling Salesman Program - Video

Anything QL Software or Programming Related.
Post Reply
stevepoole
Super Gold Card
Posts: 712
Joined: Mon Nov 24, 2014 2:03 pm

Travelling Salesman Program - Video

Post by stevepoole »

Hi All,
https://youtu.be/MygBtwbjYqI
https://youtu.be/qghcb1_iZIo
After some technical faults on my video camera, I cobbled together these videos on my smartphone, for you to see the TSP performing.
It represents a five year long programming effort - from Superbasic, through C68, to C++ and javascript.
A challenge to get a QL program running on the latest platforms, and compare it to the top programs so far !
Send me a PM if you want to get the code...

Steve POOLE.
(for the SHRINK TSP team).


Derek_Stewart
Font of All Knowledge
Posts: 3929
Joined: Mon Dec 20, 2010 11:40 am
Location: Sunny Runcorn, Cheshire, UK

Re: Travelling Salesman Program - Video

Post by Derek_Stewart »

Hi Steve,

Nice video, there is quite a difference on the PC version, what spec of PC and operating system are you using?

Have you tried compiling the QL version in Turbo or even programming in assembler?


Regards,

Derek
stevepoole
Super Gold Card
Posts: 712
Joined: Mon Nov 24, 2014 2:03 pm

Re: Travelling Salesman Program - Video

Post by stevepoole »

Hi Derek,
The basic sequence was written using QPC2 and Turbo, on a 2004 Compaq at 2.1Ghz. Pauses were used to reveal how 'nearest points' are located.
Turbo was used as a stepping stone to C68 code.
The Quincy complier was then adopted to convert C68 into C++, still on the Compaq. And we had to devise C++ functions for superbasic keywords...
Finally, using Notepad++, we converted a simplified version of C++ to javascript, this time on an ASUS 1.9Ghz 2014 laptop.
The javascript, generated an html program, which can be distributed as an email attatchment for PCs, tablets and smartphones, using standard browsers.

Way back in 2014, George Gwilt kindly converted the Turbo basic into assembler, which then ran about twice as fast. But the final C++ program is more than a thousand times faster than that assembler was on my SGC... and my Asus is not a top-of-the-range PC !

When we started writing the 'Shrink' TSP, there was very little TSP info on the web, and for a long time you had to have an Apple to see a demo. This is no longer the case. Now we have been able to compare the 'shrink' method to others, and know that it performs very well. (An early Basic listing was printed in a Quanta issue. The final basic program weighs in at over 80Ko).
Regards,
Steve.


stevepoole
Super Gold Card
Posts: 712
Joined: Mon Nov 24, 2014 2:03 pm

Re: Travelling Salesman Program - Video

Post by stevepoole »

Hi All,

Just to give you all an idea of the performance of the 'Shrink' programs in our videos, compare them to those in the link below.

Notice the long time taken by them to solve but several dozen nodes in C++. Then note their acceleration when transcoded into intel assembler : staggering !
I doubt if I will ever learn that language, bit 'shrink' performance would be instantaneous, whereas now it takes just a fraction of a second for 1000 nodes...
I wonder how long it took Marcel to learn intel assembler, when he wrote QPC2, so we could have the QL on PCs...?
Regards,
Steve Poole.

____________________
Traveling Salesman solver in Assembly Language …Traduire cette page
https://www.youtube.com/watch?v=HvE5Ue971Cs

08/10/2009 · Traveling Salesman Problem (TSP) solved by a Hybrid Genetic Algorithm, implemented in Assembly Language. See also my TSP links in http://delicious.com/omadeon/tsp

Auteur : omadeon
Vues : 6,8 K
_________________________


tcat
Super Gold Card
Posts: 633
Joined: Fri Jan 18, 2013 5:27 pm
Location: Prague, Czech Republic

Re: Travelling Salesman Program - Video

Post by tcat »

Hi Steve,

Excellent work.

How do you define optimum, minimal outer polygon circumference, polygon surface minimal? Outer polygon is always closed? At the start, BASIC program draws some polygons, then the routes.

You mentioned earlier with the heuristic algo, you are some 90% close of the optimum.

Tomas


stevepoole
Super Gold Card
Posts: 712
Joined: Mon Nov 24, 2014 2:03 pm

Re: Travelling Salesman Program - Video

Post by stevepoole »

Hi Tomas,
Optimal tour length is calculated using an LKH program. Shrink's percentages quoted are relative to that program.

To get the outer polygon, first the southmost coordinate is found, then the outer nodes going clockwise. But, the C++ code uses 'convex hull' recursive routines.The outer polygon is always closed.

The superbasic program looks at every side of the outer circuit, then locates the 'nearest' node, using a simple triangular bisectrice measure. each succesive circuit is coloured differently, but video compression reduced ink colours from 8 to 4 !

The BASIC program attains 87%+ of optimal. HTML now achieves 96%+, but with no speed optimisation yet. Precision of the C++ output can be selected, varying from 88% up to 98%+, but high precision slows timings.

HTML code is 12Ko, but C++ is 90Ko, because of speed optimisation and 'crossover' checking. It also allows the user to import coordinate files etc...

Regards,
Steve.


stevepoole
Super Gold Card
Posts: 712
Joined: Mon Nov 24, 2014 2:03 pm

Re: Travelling Salesman Program - Video

Post by stevepoole »

Hi Everybody,
Converting the 'SHRINK' Travelling Salesman Program from SuperBasic to C++ and HTML took several years of hard work.....

In December, Laurant Weill and Francois Lionet demonstrated their new 'AOZ' TRANSCODER in Paris. AOZ is a new language, which can read Amiga or Atari BASIC and convert and mix it with javascript code, to run Basic programs at the speed of any PC, tablet or smartphone !

The language will be available on February 1st. See the youtube conference with english subtitles at https:/AOZ.studio

This will be as great a revolution as the coming of the INTERNET itself, as you will not really need to learn C++, javascript or other languages which are very hard to write , test and debug ! Just learn Basic and you will have instant high-speed code running on any device !

It remains to be seen if QL Basics will benefit from the Atarir basic versions.... If so hold on to your hats ... and justhope so ...

Steve Poole.


stevepoole
Super Gold Card
Posts: 712
Joined: Mon Nov 24, 2014 2:03 pm

Re: BASIC to Javascript 'AOZ' transpiler.

Post by stevepoole »

Hi everybody,

In a communication with the AOZ team, they state that the 'AOZ' Basic > javascript 'transpiler' will eventually be operational not only for Atari & Amiga Basic, but also for Visual and Mac Basics, etc. See YouTubevideos : https://AOZ.studio

It is also stated that the 'transpiler' will be able to handle user extensions, which would mean that QL Basics should be fairly compatible after a little tweaking.... as we all know where Atari & Amiga Basic derived from ....

What all this means is that there will no longer ve any need to learn 'bloatware languages' . You will be able to continue to write and develop basic code on your QL platforms, then load them into AOZ to run on any PC, Tablet or smartphone..... staggering ! We should soon witness a revival of the 80's programming boom which went out of the window with early PCs....

Release date was february 1st. QL Forever thanks to the wizards of 'aOZ' !
( If only this program had existed in 2016, it would have saved years of work on the QL 'Travelling Salesman Program'.... )
Steve Poole.


Post Reply