Forum Announcement
22/04/2018 - The Online Chat isn't working via the normal link.
You can connect via IRC, or using another web client - https://kiwiirc.com/client/chat.qlforum.co.uk/#qlforum

SBASIC & C++

Anything QL Software or Programming Related.
stevepoole
Trump Card
Posts: 160
Joined: Mon Nov 24, 2014 2:03 pm

Re: SBASIC & C++

Postby stevepoole » Tue Feb 10, 2015 9:17 am

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


stevepoole
Trump Card
Posts: 160
Joined: Mon Nov 24, 2014 2:03 pm

Re: SBASIC & C++

Postby stevepoole » Sun Apr 19, 2015 9:30 am

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
Bent Pin Expansion Port
Posts: 79
Joined: Fri Jan 13, 2012 5:29 pm
Location: Kent

Re: SBASIC & C++

Postby EmmBee » Mon Apr 20, 2015 2:05 pm

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
Trump Card
Posts: 160
Joined: Mon Nov 24, 2014 2:03 pm

Re: SBASIC & C++

Postby stevepoole » Tue Apr 21, 2015 9:18 am

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
Trump Card
Posts: 160
Joined: Mon Nov 24, 2014 2:03 pm

Re: SBASIC & C++

Postby stevepoole » Mon Apr 27, 2015 7:05 am

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: 115
Joined: Tue Dec 06, 2011 3:30 am
Location: SF Bay Area
Contact:

Re: SBASIC & C++

Postby swensont » Mon Apr 27, 2015 8:19 pm

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++

Postby Mr_Navigator » Tue Apr 28, 2015 10:04 am

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&t=1281&p=10686#p10686


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

Re: SBASIC & C++

Postby stevepoole » Thu May 14, 2015 10:05 pm

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: 115
Joined: Tue Dec 06, 2011 3:30 am
Location: SF Bay Area
Contact:

Re: SBASIC & C++

Postby swensont » Fri May 15, 2015 9:14 pm

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
QL Wafer Drive
Posts: 1339
Joined: Sun Feb 13, 2011 10:53 pm
Location: SW Germany

Re: SBASIC & C++

Postby tofro » Fri May 15, 2015 11:16 pm

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



Return to “Software & Programming”

Who is online

Users browsing this forum: No registered users and 2 guests