Thread: Logic problems

  1. #1
    Registered User
    Join Date
    Sep 2007
    Posts
    100

    Logic problems

    Hey,

    I am trying to design a recursive method to figure out a certain problem. I know what I have to do but I am not really sure how to go around implementing it. Here it is:

    The user inputs n locations, say 4, and the distance between each location. For example

    Code:
    4
    9   6   10
    11   10
    4
    The first line is the number of locations there are, in this case 4. The next three lines are the distance between locations. Line 2 corresponds to the distance of location 1 to loc. 2, 3, and 4 - so between 1 and 2 there is a distance of 9, between 1 and 3 there is a distance of 6, and between 1 and 4 there is a distance of 10. Line 3 corresponds to the distance between 2 - 3 and 2 - 4, and line 4 is the distance between 3 - 4.

    Now my goal is to find the shortest possible route between all four locations, starting with location 1 and ending back at location 1, hitting all of the locations inbetween. For example, it may look like "1 3 2 4 1" which would mean start at loc 1, travel to loc 3, from 3 travel to 2, from 2 travel to 4, and from 4 back to one.

    Here is what I know I must do: find the sum of every combination and then compare the sums to see which one is the smallest. My problem is that I am not sure how to code this - how do I put together every possible combination?

    Code:
    1 -> 2 -> 3 -> 4 -> 1
    1 -> 3 -> 4 -> 2 -> 1
    1 -> 4 -> 2 -> 3 -> 1
    1 -> 2 -> 4 -> 3 ->1
    etc
    etc
    I am using lists and sets if that is of any help. I think I know how to do this if I was able to use two dimensional arrays and n was a constant, but I can't quite figure it out recursively using sets and lists.

  2. #2
    Registered User
    Join Date
    Apr 2006
    Posts
    2,149
    This is done by Dijkstra's algorithm IIRC. It uses a stack to find the shortest route. Look it up.

    The actual implementation of the graph can be done in a number of ways. The simplest is to use a multimap, but there are other alternatives.
    It is too clear and so it is hard to see.
    A dunce once searched for fire with a lighted lantern.
    Had he known what fire was,
    He could have cooked his rice much sooner.

  3. #3
    Registered User
    Join Date
    Sep 2007
    Posts
    100
    I've been reading through articles I have found on Google, but the code is not making much sense to me. Does anyone know of any good tutorials that talk about Dijkstra's algorithm in terms of C++ lists and sets, not graphs?

  4. #4
    Registered User
    Join Date
    Apr 2006
    Posts
    2,149
    You need to figure out how to implement a graph using lists and sets.

    It's very easy with a multimap, since a graph is just a mapping of vertexes to edges, and edges are just a value and destination pair.

    If you can't use a multimap, you can implement one youself.
    It is too clear and so it is hard to see.
    A dunce once searched for fire with a lighted lantern.
    Had he known what fire was,
    He could have cooked his rice much sooner.

  5. #5
    Registered User
    Join Date
    Sep 2007
    Posts
    100
    I asked about this also in another forum and here is what one person had to say:

    Actually, Dijkstra's algorithm gives you the shortest paths between a given node and all the other nodes. It doesn't give you any path that visits all the nodes. What you are asking for is a solution of the traveling salesman problem, which is an infamous NP-complete problem. Nobody knows whether an efficient algorithm exists. If there are only 4 locations, you can just check all 6 orderings of locations 2, 3, and 4, but that's not going to work if you have many locations. (With 10 locations, there are already more than 360,000 orderings, and after that, each new location increases the number of orderings by at least a factor of 10.)

    You should ask yourself why you need the absolute shortest path. If you can settle for one that's not quite optimal, there may be algorithms that find short paths without guaranteeing that they find the shortest one. If I remember correctly, this is true at least when the locations are points on a plane and the distance is just normal distance, but beyond that, I don't know.

    In any case, this is a graph problem, so all relevant examples and code you're likely to encounter will use the language of graphs.
    What about something along these lines?

    Code:
    // int n = number of places the user has entered
    possibleCombinations = factorial(n);
    
    for(int i = 0; i < possibleCombinations; i++)
    {
      for(int x = 0; x < n; x++)
      {
        // some code here
      }
    }
    So if there were 5 places, 5! is 160 so the first loop would execute 160 times for 160 total possible combinations, and the inside loop would execute 5 times for each time the out loop executed, since each combination has 5 places. Now my problem still is how do I put together all of these combinations?

  6. #6
    Registered User
    Join Date
    Sep 2007
    Posts
    100
    I found an article through Google talking about the traveling salesman problem, and it mentioned using std::next_permutation() This seems to be exactly what I need?

  7. #7
    Officially An Architect brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,396
    Quote Originally Posted by Beowolf View Post
    I found an article through Google talking about the traveling salesman problem, and it mentioned using std::next_permutation() This seems to be exactly what I need?
    Sure. For each permutation, you have to check if it is a valid path.

    std::next_permutation() will keep permuting forever. When it eventually comes back to the order you started with, you know you're done.

  8. #8
    Registered User
    Join Date
    Jan 2005
    Posts
    7,366
    It will actually return false when it realizes it has come back to the order you started with, you just have to keep checking the return value.

  9. #9
    Registered User
    Join Date
    Apr 2006
    Posts
    2,149
    Yeah, the other forum poster was right, I did not read your post carefully enough.

    next_permutation will work if you disallow revisiting each destination. Sometimes though, the least path may involve doubling back.
    It is too clear and so it is hard to see.
    A dunce once searched for fire with a lighted lantern.
    Had he known what fire was,
    He could have cooked his rice much sooner.

  10. #10
    Registered User
    Join Date
    Sep 2007
    Posts
    100
    For my assignment I have to calculate the best route using a recursive method. I've been playing around with next_permutation() and do not see how I could implement it into a recursive method - is it even possible? Is there anywhere I can see the actual code that next_permutation calls?

  11. #11
    Registered User
    Join Date
    Sep 2007
    Posts
    100
    Update: I found this recursive method for permutations, which seems to do what I need, but I don't understand the code:

    Code:
    // recvperm.cpp : Defines the entry point for the console application.
    //
    
    #include "stdafx.h"
    
    
    #include <string>
    #include <iostream>
    
    using namespace std;
    
    
    void string_permutation( std::string& orig, std::string& perm )
    {
    	if( orig.empty() )
    	{
    		std::cout<<perm<<std::endl;
    		return;
    	}
    
    	for(int i=0;i<orig.size();++i)
    	{
    		std::string orig2 = orig;
    
    		orig2.erase(i,1);
    
    		std::string perm2 = perm;
    		
    		perm2 += orig.at(i);
    
    		string_permutation(orig2,perm2);
    
    	} 
    }
    
    int main()
    {
      
    	std::string orig="ABCDE";
    	std::string perm;  
    
    	string_permutation(orig,perm);
    
    	cout<<"Complete!"<<endl;
    
    	system("pause");
    
    	return 0;
    }
    How does this look to you? And what is "stdafx.h"?

  12. #12
    Registered User
    Join Date
    Oct 2005
    Posts
    271
    As far as I know, "stdafx.h" is a header file automatically generated when you use Visual C++. And as far as I can see from the code, you can just get rid of that line if you want to.

  13. #13
    Registered User
    Join Date
    Sep 2007
    Posts
    100
    Thanks, that fixed it.

    I've been working to convert that method from using strings to lists and sets. Originally I had a ton of errors, but now I've managed to fix a few of them. However, I seem to be stuck now. Here is my code:

    Code:
    #include <string>
    #include <iostream>
    #include <set>
    #include <list>
    
    using namespace std;
    
    
    void string_permutation(set<int>& orig, list<int>& perm )
    { // line 10
    	if( orig.empty() )
    	{
    		list<int>::iterator theIterator;
            for(theIterator = perm.begin(); theIterator != perm.end(); theIterator++)
            {
                cout << *theIterator << "\n";
            }
    		return;
    	}
    
    	for(int i = 0; i < orig.size(); i++) // line 21
    	{
    		list<int> orig2 = orig;
    
    		orig2.erase(i,1); // line 25
    
    		list<int> perm2 = perm;
    		
    		perm2.push_front(orig.find(i)); // line 29
    
    		string_permutation(orig2,perm2); // line 31
    
    	} 
    }
    
    int main()
    {
      
    	int myInts[] = {1, 3, 2, 4};
        set<int> orig(myInts, myInts+4);
    	list<int> perm;  
    
    	string_permutation(orig, perm);
    
    	system("Pause");
    
    	return 0;
    }
    And the compiler errors:
    Code:
    21 permutation.cpp [Warning] comparison between signed and unsigned integer expressions 
    23 permutation.cpp conversion from `std::set<int, std::less<int>, std::allocator<int> >' to non-scalar type `std::list<int, std::allocator<int> >' requested 
    25 permutation.cpp invalid conversion from `int' to `std::_List_node_base*' 
    25 permutation.cpp   initializing argument 1 of `std::_List_iterator<_Tp>::_List_iterator(std::_List_node_base*) [with _Tp = int]' 
    25 permutation.cpp invalid conversion from `int' to `std::_List_node_base*' 
    25 permutation.cpp   initializing argument 1 of `std::_List_iterator<_Tp>::_List_iterator(std::_List_node_base*) [with _Tp = int]' 
    29 permutation.cpp no matching function for call to `std::list<int, std::allocator<int> >::push_front(std::_Rb_tree_const_iterator<int>)' 
     note C:\Applications\Dev-Cpp\include\c++\3.4.2\bits\stl_list.h:753 candidates are: void std::list<_Tp, _Alloc>::push_front(const _Tp&) [with _Tp = int, _Alloc = std::allocator<int>] 
    31 permutation.cpp invalid initialization of reference of type 'std::set<int, std::less<int>, std::allocator<int> >&' from expression of type 'std::list<int, std::allocator<int> >' 
    10 permutation.cpp in passing argument 1 of `void string_permutation(std::set<int, std::less<int>, std::allocator<int> >&, std::list<int, std::allocator<int> >&)'

  14. #14
    Registered User
    Join Date
    Oct 2005
    Posts
    271
    First, fix line 23. You're trying to dump a set into a list. Furthermore, you're trying to pass that on as an argument to a function which isn't defined for that argument.
    Last, you're lists aren't defined to have pointers/iterators as elements.

  15. #15
    Registered User
    Join Date
    Sep 2007
    Posts
    100
    I fixed line 23.

    Last, you're lists aren't defined to have pointers/iterators as elements.
    Sorry, what does this mean? The only place I use pointers/iterators is at line 13 and 14 (the for loop inside of if orig.empty()) and that compilers fine.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. No clue how to make a code to solve problems!
    By ctnzn in forum C Programming
    Replies: 8
    Last Post: 10-16-2008, 02:59 AM
  2. Logic Problems
    By mike_g in forum C Programming
    Replies: 3
    Last Post: 08-06-2008, 10:19 AM
  3. Actors, cues, event based logic.
    By Shamino in forum Game Programming
    Replies: 2
    Last Post: 04-27-2006, 10:58 PM
  4. Circular Logic
    By DavidP in forum A Brief History of Cprogramming.com
    Replies: 1
    Last Post: 10-15-2001, 08:10 PM