a problem that requires a sorting algorithm.
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?
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)
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
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
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement