Traveling Salesman Problem C++ Code Issue
CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 6 of 6

Thread: Traveling Salesman Problem C++ Code Issue

  1. #1
    Join Date
    Oct 2016
    Posts
    9

    Traveling Salesman Problem C++ Code Issue

    The following code is an algorithm I designed to solve the Traveling Salesman Problem. I am using a Nearest Neighbor Algorithm to find an optimal path and cost of a 5 city tour. When I run the program, the cost calculation is correct. However, the optimal path output is always 154321. This is the output even if I change the distances between the cities in the cost matrix. How do I configure the code to make the optimal path output change when the distances between the cities are changed in the cost matrix?

    Code:
    #include <iostream>
    using namespace std;
    
    //Global definitions
    int costMatrix[5][5];
    int vistedCities[5];
    int numCity = 5;
    int cost = 0;
    
    //Function prototypes
    int tsp(int);
    void minCost(int);
    
    //Main functions
    int main()
    {
    
    	int i;
    	int j;
    
    	//Enter distance between cities
    	cout << "\n\nEnter distance between cities into matrix...\n";
    	for (i = 0; i < numCity; i++)
    	{
    		cout << "\nEnter " << numCity << " elements in Row[" << i + 1 << "]\n";
    		for (j = 0; j < numCity; j++)
    			cin >> costMatrix[i][j];
    	}
    
    	//Display matrix of distances between cities
    	cout << "\nDistances entered into cost matrix:\n";
    	for (i = 0; i < numCity; i++)
    	{
    		cout << endl;
    		for (j = 0; j < numCity; j++)
    		{
    			cout << costMatrix[i][j] << " ";
    		}
    	}
    
    	//Display results
    	cout << "\n\n Optimum Path: \t ";
    	minCost(0);
    	cout << "\n Minimum Cost: \t";
    	cout << cost;
    
    	system("pause");
    	return 0;
    }
    
    //Function to determine minimum cost
    void minCost(int city)
    {
    	int nearestCity;
    	vistedCities[city] = 1;
    
    	cout << city + 1;
    	nearestCity = tsp(city);
    
    	if (nearestCity == 999)
    	{
    		nearestCity = 0;
    		cout << nearestCity + 1;
    		cost = cost + costMatrix[city][nearestCity];
    		return;
    	}
    	minCost(nearestCity);
    }
    
    //Funciton for TSP algorithm
    int tsp(int city1)
    {
    	int counter;
    	int nearestCity = 999;
    	int mini = 999;
    	int temp;
    
    	for (counter = 0; counter < numCity; counter++)
    	{
    		if ((costMatrix[city1][counter] != 0) && (vistedCities[counter] == 0))
    		{
    			if (costMatrix[city1][counter] < mini)
    			{
    				mini = costMatrix[counter][0] + costMatrix[city1][counter];
    			}
    			temp = costMatrix[city1][counter];
    			nearestCity = counter;
    		}
    	}
    	if (mini != 999)
    		cost = cost + temp;
    
    	return nearestCity;
    }

  2. #2
    VictorN's Avatar
    VictorN is offline Super Moderator Power Poster
    Join Date
    Jan 2003
    Location
    Wallisellen (ZH), Switzerland
    Posts
    18,836

    Re: Traveling Salesman Problem C++ Code Issue

    Did you try to debug your code to see where, how, and why goes wrong?
    Victor Nijegorodov

  3. #3
    Join Date
    Oct 2016
    Posts
    9

    Re: Traveling Salesman Problem C++ Code Issue

    Yes, I tried to debug the code, but I honestly could not figure it out. Whenever I change the code to loop through the possible permutations, I get a stack space overflow error message, and the program crashes.

  4. #4
    VictorN's Avatar
    VictorN is offline Super Moderator Power Poster
    Join Date
    Jan 2003
    Location
    Wallisellen (ZH), Switzerland
    Posts
    18,836

    Re: Traveling Salesman Problem C++ Code Issue

    Then try to debug again. Particularly your function void minCost(int city) seems to need being debugged!
    And BTW, why are so sure that the nearestCity will be (and not too late!) exactly 999?
    Victor Nijegorodov

  5. #5
    2kaud's Avatar
    2kaud is offline Super Moderator Power Poster
    Join Date
    Dec 2012
    Location
    England
    Posts
    5,201

    Re: Traveling Salesman Problem C++ Code Issue

    I agree with Victor, in these circumstances you need to use the debugger to trace through the code - line by line if needed - to see what is happening and where the execution deviates from that expected from the program design.

    I get a stack space overflow error message, and the program crashes
    minCost() function is recursive. A stack space overflow error message usually indicates that there is a problem with the recursion terminating condition and that the terminating condition is not being met. In this case recursion only stops when tsp(city) returns 999 ??
    All advice is offered in good faith only. You are ultimately responsible for the effects of your programs and the integrity of the machines they run on. Anything I post, code snippets, advice, etc is licensed as Public Domain https://creativecommons.org/publicdomain/zero/1.0/

    C, C++ Compiler: Microsoft VS2017

  6. #6
    Join Date
    Oct 2016
    Posts
    9

    Re: Traveling Salesman Problem C++ Code Issue

    Thanks for the advice, I am looking into it.

Tags for this Thread

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  


Windows Mobile Development Center


Click Here to Expand Forum to Full Width

This a Codeguru.com survey!


HTML5 Development Center