Traveling Salesman Problem

[group256]

Hi,

I'm supposed to write a code of my TSP assignment using brute force algorithm. Although there are still some darkness about how to do it. I know what is TSP but I don't know how to start it.

Let's say that we have 4 cities(A, B, C, D). Using brute force am I supposed to do ABCDA, ACDBA, ADCBA and ... then save all the total cost for each and decide based on those???

BTW, I'm supposed to read the data from a file that gives the cities coordination.

Please let me know if some more information is needed.

Thanks a lot.

[pecet]

If You have 4 cities, you need 4x4 2d array (f.e. dist[4][4]) to store distance between each city. Another array(f.e. cities[4]) is needed to store city's number. Now, everything you need to do is to calculate all possible permutations of array cities (use std::random_shuffle in loop) and calculate total distance using array dist. At the end choose the shortest route.
And don't use this algorithm for more than ~15 cities;)

[pecet]

Of course you should use std::next_permutation instead of std::random_shuffle. Sorry:)

[moniqueromo]

Hi. I have a similar version to this problem but am quite stuck seeing that my c++ skills are very rusty!

supposed to do something known as the greedy algorithm where a 'salesman' starts at one point and goes to the next 'city' with shortest distance and so on, visiting every city only once and returning to where he started when done.

I have a file(file.txt) to read from that has my numbers. Do i write a function to read these numbers and fill my array??

[pecet]

The answer is: yes, you do :). Yes, you write a function.
You have to create a 2d table with distances between every city (if you have N cities you create NxN table). In every iteration you look for the closet city and mark that city as visited (for example set 'negative distance').

[group256]

Yeah, I actually did manage to do the algorithm even though maybe it wasn't the best, but worked perfectly. What I did was, simply define a function to find distance between 2 cities. Then permute a list of cities (let's say for 4 cities, you permute ABCD, ACBD, ADBC, ....) and each time I called a function to break this into pairs, then find the distance and at the end sum all the values for one permutation. get the rest and find the smallest value. It actually is using Brute Force, although Greedy search is another method by it doesn't always return the optimum answer.

[moniqueromo]

So here's what i came up with. Please don't be too harsh, it's been a while since i took the introductory course and am just taking the intermediate course ><

am i on the right path??

int fillarray(ifstream& fin){
        int distarray [5][5];
		int value = 0;
        while (fin >> value){
			for (int i=0; i <= 5; i++)
				for (int j=0; j<=5; j++)
						distarray [i][j];
		}
		return 0;
}

int main (){
	string name;
	cout << "Enter the name of the file: " << endl;
        cin >> name;
        ifstream fin;
        fin.open("numbers.txt");
        fillarray(fin);
        fin.close();
        return 0;
}

Oh, and my version is i think much simpler and doesn't require permutations (i think). reading from a text file, you are given the distances from planet to planet, so i need an array.

in mine, there is a person visiting a series of planets. They always start at 1, and have other planets 2, 3, 4, 5. They see to which planet is the shortest and go there, setting that as the current planet and it is now visited so they have 3 remaining planets to do the same and always return to 1 at the end. Can't visit one twice and can't skip one!

any help would be really appreciated!!

[pecet]

I dont know structure of your data file, but here's peace of advice. On line #4 you read value, but you never use it. On the other hand there is line #7 which does... what?
What's more you read name of the file from the user in your main function, but numbers.txt is always opened.

[moniqueromo]

Well the data file is a planets.txt that has 5 rows and 5 columns of numbers that are the distances. I somehow have to use that to make an array like you said??

So don't I read the numbers one by one and place them in my array??

i'm sorry if i sound super dumb.. but it's really been nearly 2 years since i took the last c++ class :/

[pecet]

You read numbers, but you _don't_ place them in array (look closer at line #7). At this moment you call value stored in distarray [i][j] (some random value). There is lack of assigment.

[WaltP]

Another suggestion: format your code better. Indents are too deep and not consistent.

[moniqueromo]

I keep flipping through my book but can't seem to find that problem out. I know there is an = sign in there somewhere.. hint??

[pecet]

You have int x; . Now, you want to have value 2 in x. What do you do?
The same story goes with distarray [i][j] and value .

[moniqueromo]

you do int x = 2;

so distarray [j] = [value] ??

[pecet]

That's a bingo! ("inglourious basterds" :) ).
Well, almost. Just remove square brackets from [value] .