SBASIC & C++

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

Re: SBASIC & C++

Post by stevepoole »

Hi,
See the next Quanta magazine to get the Travelling Salesman Program.
Steve.


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

Re: SBASIC & C++

Post by stevepoole »

The Travelling Salesman Program has now been printed in Quanta for all to see.
It runs at n^3*7E-5secs which means it has achieved polynomial time. No doubt this can be greatly improved on, since the published code is the first prototype, and being a long program, was fixed so as to be available rapidly. If you can improve on the program, please do so, as I am short of time, and although I intend to optimise the code, this could take some months at least.
The program was not written optimally, just written to prove it worked...and to get an idea of its speed potential. And even as it stands, it is very fast indeed.
Take a look at the TSP on the internet to get an idea of the challenge.
I will gladly cooperate with anyone interested.
Good luck...
Steve Poole.


EmmBee
Trump Card
Posts: 240
Joined: Fri Jan 13, 2012 5:29 pm
Location: Kent

Re: SBASIC & C++

Post by EmmBee »

Hi Steve,

I certainly would be interested in having a look at your program. Does one have to be a member of Quanta?

Michael


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

Re: SBASIC & C++

Post by stevepoole »

Hi Embee,
Being a member of Quanta certainly helps, as they hold the copyright to the program.
But as the code is 6 ko long, typing it in could be tedious, so I will see if Quanta can put it on their website for members to download.
Otherwise it may be possible to send it via the QlForum private section. I will look into this.
Regards,
Steve.


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

Re: SBASIC & C++

Post by stevepoole »

Hi Embee,

Maybe you know a member of Quanta who could show you a demonstration of the TSP. Copyright remains with Quanta though. There is a demonstration version ready in machine code which will run considerably faster. News on that will appear soon.

The future lies with a fully optimised implementation of the code, being no mean task. I had a hard job getting my program to work at all. This is surely a job for a Professional programmer. But the program is very fast indeed, but slows in function of the number of nodes. This is polynomial time, better than existing programs, according to Wikipedia...?

Steve.


swensont
Forum Moderator
Posts: 252
Joined: Tue Dec 06, 2011 3:30 am
Location: SF Bay Area
Contact:

Re: SBASIC & C++

Post by swensont »

Why would copyright be held by Quanta and not the original author? Does Quanta require that all articles submitted to the Quanta Magazine have the copyrights transferred to Quanta? Unless the original author signs a copyright release form, the copyright stays with them. At least this is how it works in the US and I would assume it works the same in the UK.


User avatar
Mr_Navigator
QL Fanatic
Posts: 782
Joined: Mon Dec 13, 2010 11:17 pm
Location: UK, Essex
Contact:

Re: SBASIC & C++

Post by Mr_Navigator »

swensont wrote:Why would copyright be held by Quanta and not the original author? Does Quanta require that all articles submitted to the Quanta Magazine have the copyrights transferred to Quanta? Unless the original author signs a copyright release form, the copyright stays with them. At least this is how it works in the US and I would assume it works the same in the UK.
QUANTA has copyright to the magazine since it was created by and for QUANTA but unless the copyright to content that was published in the magazine has been assigned to the magazine they do not have copyright over the content. So QUANTA has copyright on the pictorial layout of listings in the magazine but the algorithm and code which produced the listing will still belong to the author. Since QUANTA has not purchased the listing/code, or agreed to publish it with conditions, I don't think there would be anything to stop Steve publishing it anywhere else, however Steve like many others support the magazine and are keen for it to continue and we cannot continue without the support of both members and the QL community, hence there will always be a suggestion to join QUANTA where it is deemed necessary by individuals.

The listings are available in the Members only section here :
http://qlforum.co.uk/viewtopic.php?f=22 ... 686#p10686


-----------------------------------------------------------------------------------
QLick here for the Back 2 the QL Blog http://backtotheql.blogspot.co.uk/
stevepoole
Super Gold Card
Posts: 712
Joined: Mon Nov 24, 2014 2:03 pm

Re: SBASIC & C++

Post by stevepoole »

Hi,
If anyone knows any mathematicians or computer programmers who wish to work on the Travelling Salesman Program published in the last issue of Quanta, I will gladly send them the program as an email attatchment.
The program can probably be greatly optimised by specialists. It already has impressive performance, but for the moment I don't have the qualifications to know all the techniques possible to improve the array handling. This is surely a job for professionals...
TSP is a very active research problem, it is just a question of finding the right contacts.
Steve.


swensont
Forum Moderator
Posts: 252
Joined: Tue Dec 06, 2011 3:30 am
Location: SF Bay Area
Contact:

Re: SBASIC & C++

Post by swensont »

Steve,

I have not looked at the code, but doing a quick read on the Travelling Salesman problem on Wikipedia, I saw that there are a couple of published algorithms for the issue (like Held-Karp). Did you use any of these algorithms or review them?

Tim


User avatar
tofro
Font of All Knowledge
Posts: 2685
Joined: Sun Feb 13, 2011 10:53 pm
Location: SW Germany

Re: SBASIC & C++

Post by tofro »

Steve,

if you want to test your program (or maybe benchmark it against specific data sets or proven optimum solutions) - The University of Heidelberg maintains a database of sample data sets (taken from the "real world") and optimum solutions for download.

http://www.iwr.uni-heidelberg.de/groups ... /TSPLIB95/

Tobias


ʎɐqǝ ɯoɹɟ ǝq oʇ ƃuᴉoƃ ʇou sᴉ pɹɐoqʎǝʞ ʇxǝu ʎɯ 'ɹɐǝp ɥO
Post Reply