a problem that requires a sorting algorithm.

This topic is 3058 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

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 on other sites
Look up the 'traveling salesman' problem. You might find some solutions there...

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

1. 1
2. 2
Rutin
19
3. 3
4. 4
5. 5

• 14
• 12
• 9
• 12
• 37
• Forum Statistics

• Total Topics
631426
• Total Posts
3000019
×