C++

Forum

 
translating into c++ langagues.

jimmy5023 (159)
i want to write a function called "greedy" function.
Given

M[5][5] =
{
0,1,3,2,9;
1,0,1,2,4;
3,1,0,1,3;
2,2,1,0,1;
9,4,3,1,0;
}

The matrix M represent the distance between 5 cities, A B C D and E, As you see the diagonal matrix are 0, that is because i assume it takes 0 distance from point A to point A. Also this matrix is symmetric, this is because i assume it takes the same amount of distance from point B to point C as point C to point B.

Now, i want to write a function that connects the "closest" route, not the fastest route, but the closest route. So as you see i modify the matrix to make it simple, as you see from A to B is 1, B to C = 1, C to D = 1, D to E = 1 lastly E to A = 9 (it must be 9 because it's the only route left, oh the rule is u can't pass the same city more than once).
So it will be
1, 1, 1, 1, and 9. It adds up to 13
just to prove my point that it is not the fastest route, i am going to choose the route A->D->E->C->B->back to A which is 2, 1, 3, 1, 1 which adds up to 8.

So here's my approach, i am going to write a double for loop. So i simply need to do a min search for my first row, and i will find b as the fastest.

The thing is i don't know how to write it probably because need to eliminate the route that i used, for example. Since i did a min search for the first row, i am going to do it to the second row, and guess what happens? A to B, B to A = not good. Since the min in second row is B to A as well.

Second i would like to know what if i "MUST" have the connection B to C for example, and use the function to complete the route.

Lastly, you might realize "hmm, jimmy are you solving the TSP", my answer is yea kind of, then you will ask "hmm, but u forgot to check for invalid routes, like if i reach city C where it is between A and B, no matter what route i go i will pass C again to return to A" that don't worry i got it done, and if u want me to post that invalid checking code to help you answer my question i can.
Last edited on
GodPyro (151)
jimmy5023 (159)
No, that algorithm is to find the SHORTEST path, my aim is not to find the shortest path but simply search for the path that is more near to the current city.
king214 (231)
So the traveling sales man problem?

GodPyro (151)
jimmy5023 (159)
NO not the tsp but the rules apply. U can't pass the same city more than once.
jimmy5023 (159)
yes, i know the greedy algorithm, but i am trying to code it my way using the for loop. Anyone have some idea?
GodPyro (151)
Ok. Can you modify your current data structure at all? Say now like once you move from A->B you change 
1
2
3
4
5
6
7
8
 
M[5][5] = 
{
    0,1,3,2,9;
    1,0,1,2,4;
    3,1,0,1,3;
    2,2,1,0,1;
    9,4,3,1,0;
}


to 

1
2
3
4
5
6
7
8
 
M[5][5] = 
{
    0,-1,3,2,9;
    -1,0,1,2,4;
    3,1,0,1,3;
    2,2,1,0,1;
    9,4,3,1,0;
}
Last edited on
jimmy5023 (159)
i do not think so, so you are suggesting that i turn the data to negative then write a if loop if array[i][j]<0 dis regard?

well here's how i store my value, 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
 

struct Path {
  City destination;
  int distance;
};

struct City {
  vector<Path> neightbors;
  ... //other members (fields, methods, ...)

  void addPath(City dest, int dist) {
    Path path = { dest, dist };
    neightbors.push_back(path);
  }
};

int main() {
  City A, B, C;
  A.addPath(B, 1);
  A.addPath(C, 2);
  B.addPath(A, 1);
  B.addPath(C, 3);
  C.addPath(A, 2);
  C.addPath(B, 3);

  ... //do stuff with the cities


  return 0;
}

in this example it's a 3 by 3 but yea you get it.
The reason i do that is because i am actually coding my own version of genetic algorithm TSP.
Last edited on
GodPyro (151)
Hmmmm, Genetic Algorithms now? I thought you wanted a greedy-esk algorithm because you don't want to find the shortest path. What are you using as a fitness function then?
jimmy5023 (159)
ehh nvm ignore my genetic algorithm, let's make it simple the above posot is how i store my values so i don't think u can change the data and make it negative.
GodPyro (151)
Why not have a vector of Cities of which you load up and pop off as your go through it finding the greedy path as you go. Once you have a single item left in the vector you can see what the destination is to the starting City and add that to the length.

jimmy5023 (159)
Oh, i am learning vector right now, so i am not really familiar with vectors. I don't really understand how you "pop off" when i go through.
GodPyro (151)
What I mean is that you remove that item from the vector when you access it,
e.g.
1) Start at A
2) Remove A from the vector
3) Increment distance (distance from A to A is 0)
4) Iterate through vector and find shortest route from A
5) Select B as closest
6) Remove B from vector
7) Increment distance (distance from A to B is 1)
8) Iterate through vector...
etc.
jimmy5023 (159)
This method will still bump into the sitution where A -> B B->A i mentioned in my original post.
GodPyro (151)
How so? A doesn't exist anymore in the vector.
jimmy5023 (159)
Oh that's true, ok i'll try it thanks alot godPyro.
GodPyro (151)
You're welcome :)
Topic archived. No new replies allowed.