salesman

Hеy guys, I have a problem solving the traveling salesman algorithm if anyone can help me i would appreciate it...I have this code but I do not know how to solve the algorithm

struct path {
int from_node;
int to_node;
int price;
bool set[MAX_N];
path *next;
};
struct level {
path* list_of_paths
level* new_node
};
define solve it? You can brute force 'relatively small' problems.
there are partial solutions eg greedy algorithm.
the best I ever got was to run greedy from each node in parallel and take the best of those that resolved (some branches can get stuck if its not fully connected).

the code for greedy is very, very easy; I coded it with a 1 line macro (repeated for all the inputs) in excel.

finally, graphs and graph theory protip: you almost never need a pointer driven graph messy data structure. You can almost always do better with tables. Here, for example, a table of (city, city2, cost) is all you need (even for the brute force one, you can do with just this). Sort by cost. pick the cheapest legal entry. If final answer hits all, its done.

I can't prove it but the adapted algorithm I gave you always gives a complete answer as far as I was able to determine. It just does not always give the brute force found best. I could be wrong on that.
Last edited on

Have you looked at this article's algorithm? Writing a c ++ program is difficult for me
>
Have you looked at this article's algorithm? Writing a c ++ program is difficult for me

yes this problem must be hard for someone who started to learn programming one week ago. if you follow my above mentioned link, that says, even for 'naive' solution you have to know another problem "Write a program to print all permutations of a given string". even this one is hard for beginners.
so, my suggestion is learn programming by solving more simple problems.
the most simple 'solution' is literally a vector of {city, city, cost} objects sorted on cost and a for loop to string together the solution with a couple of conditions. If you can do those things, you can do the simple answer, and then work up from there on more complex solutions.
Last edited on
Topic archived. No new replies allowed.