Sign in to follow this  
Bru

a problem that requires a sorting algorithm.

Recommended Posts

so i've been doing some algorithm programming questions to see how good i am,but i found myself struggeling with a question that requires some sort of a sorting algorithm. i dont realy know any sorting algorithms and the only solution that came up to my mind is a deformed A* algorithm that i dont think would fit good. the problem is like this : a rich person wants to travel the world,he has a list of countries he wants to visit and the cost of the flight from the current country he is at,to each country. he starts from his home country(marked as 0) and has to visit all the countries in the list and return to his home country in the end. the program must find the cheapest route within -t seconds(which could even be 1 with 200 countries to visit). so i thought about making a list with countries that the person did not visit,and while it's not empty,loop through each country and find the one with the lowest cost from the current country to that country(and then dump that country into a list of countries visited). and keep like that until the list is empty(or 95% of the time given has passed). it sounds simple,but no way it's right, i am not a smart guy,there has to be a hidden problem here i dont see which makes this algorithm not so good. what do you guys think? i dont mind learning a new algorithm if i know which one would fit to this problem. is my algorithm any good?

Share this post


Link to post
Share on other sites
You mean, the traveling salesman problem? This is so-called NP-complete problem, in other words it is assumed that there is no efficient algorithm to solve it. If you want something efficient, look at the various heuristics that can be applied, if not - you can try implementing a naive one - try every combination possible, although that has a exponential running time. (read: really really slow)

Share this post


Link to post
Share on other sites
intresting problem

i dont think that there is realy an other way as to take any posibiliti in to acount

just imagin the last trip cost an exorbitant amount for some reason
it woud conterfy the hole prewius callculation

London - Berlin 100$
London - New York 190$

Berlin - New York 500$
New York - Berlin 150$

Start is London

if you go to berlin in first step wich is the ceaper one you pay in the end more


Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this