Settlers of Catan - Longest Path in graph.
Hi Guys.
Maybe some of u know a good implementation to this algorithmic problem. The problem itself seems to sound simple. Find the longest, circle-free path in a graph. That is, taken from "Settlers of Catan", find the longest road of a player.
I dont know how to solve that, and from searching in the web, I fear this problem is NP complete. But I dont want a perfect algorithmic solution, just one that fits into the game.
I would be glad for any hints/solutions/web links etc.
Greetings, Christian.
[533 byte] By [
Cdomscha] at [2007-9-28 14:20:13]
Make all crossings to nodes and all edges will be vertices in a graph. Set all vertices to length/weight 1. Then complement the graph with all other possible direct connections between edges and give those vertices a large length/weight (larger than the number of edges shoudl be enough). And then solve TSP by using an approcimation algorithm (TSP you can find plenty on). At last cut the vertices that are not original edges, and take the longest route.
Example:
.........C--D
......../......\
..A--B........G
./......\....../
E........F--J
.\....../
..H--I
A..J will be nodes
AB, AE ... will be edges with weight 1
Complement with AC, AD ... with weight 10
Say that C and F are taken, they will not be used. The shortest TSP path will be A-B-D-G-J-I-H-E
Cut at B-D and J-I. The 2 remaining sub paths are I-H-E-A-B and D-G-J whereof I-H-E-A-B is longest.
There are probably more efficient ways though. but tsp approxiamtion algorithms exists that are quick.
Gil
What is TSP? Where can on read more about it?
For the time being a really simple algorithm that should solve the problem. It is propably slow as mud, but if it is really for settlers of catan performance shouldn't be a problem.
The algorithm simple creates a list of all possible paths and from that you can get the longest by just counting the elements:
1- repeat the following for all nodes in your graph
2- set currentpath = currentNode // we start with a path consisting of a single node
3- for each neighbouring node do the following:
4- if it does not appear as neighbouring in the current path set currentPath = currentPath + neighbouringNode
5- call 3
Notes:
- the algorithm is meant to be recursive, the change to currentPath is not meant to affect further iterations of the loop started in 3.
- the check in 4 is to avoid running into a loop or turning around and walking back, so if the current node is A and the neighbouring node is B on has to check for the path elements AB and BA
regards
Spieler
Just came to my mind:For settlers of catan you also have to check if their is a foreign village on the rout, because in that case the path element can only be considered for a path end, but it cannot appear in the middle of the path.regardsSpieler
to list all paths is rather expensive even for a small board like catan.
TSP is Travel Salesmans Problem. It is one of the most famous problems which is to make the shortest route to visit all nodes in a graph. Eg, If you wish to visit all major towns in US by driving car, what is the shortest path.
Gil
> to list all paths is rather expensive even for a small
> board like catan.
sure, but if I understood correct we are only talking about the paths, containing streets, and this should be no problem for a normal computer, I'd think.
>
> TSP is Travel Salesmans Problem.
Oh, ok
Thanx
Spieler
> > TSP is Travel Salesmans Problem. While reading the thread again ... where is the relation between TSP and the original problem which was to find the LONGEST path according the settlers of catan rules?regardsSpieler
First thanx for all replies.Then a note to complexity. As one player may only have 13 streets, the resulting graphs shouldnt be that complex. So an algorithm that is very slow/consumes much space whatever is not a problem i guess.Christian
basically you end up doing backtracking or using some heuristic algorithm. for the backtracking approach you check all permuations, out of which you can eliminate many subtrees, since there might be no edges that allow the specific permutation of nodes. however the asymptotical time complexity for the backtracking approach is still O(n!), with n being 13, 13! is still an awfully large number. 6227020800
basically you end up doing backtracking or using some heuristic algorithm. for the backtracking approach you check all permuations, out of which you can eliminate many subtrees, since there might be no edges that allow the specific permutation of nodes. however the asymptotical time complexity for the backtracking approach is still O(n!), with n being 13, 13! is still an awfully large number. 6227020800
Where is this O(n!) comming from?
to get all paths on a SoC borad should scale more or less like
2 * n * 2 * n * n
n being the number of street elements build
You have to start with 2*n different endpoints (there are actually less since, street elements tend to join end points)
from each corner you have 2 ways you can go and you have to do that at most n times (since you have only n street elements, and finally for checking if you have used a street before you need to iterate over your list of streets travelled, which might be up to n.
I am assuming I mist one or two steps, but I certainly can't see where n! is to come from!
BTW: the fact that 13! is a huge number doesn't mean it takes very long to perform the algorithm, it just means it does take much longer to do it for 14 then for 13.
regards
Spieler
i am a misinformed it seems, since i don't know the game settlers of catan. i was thinking the problem would amount to finding a hamiltonian path in a graph. that is a path that visits every vertex once and returns to the starting vertex. this is (one of) the longest path of a graph since all vertices are in it. such a hamiltonian path may not exists, however the n! is coming from the fact that you might have to go back and give up partial solutions. so the path finding is not greedy, that means the algorithm does not get closer to an actual solution each step. however, i guess i completely misunderstood what the specific scenario in the settlers of catan problem was about. also i double posted the reply by using the forward button of my browser. ouch! my apologies
regards,stepan
Have a look at Kruskals algorithm for finding the Minimum spanning treeof an undirected wieghted graph. With a trivial modification can be made to find the maximum spanning tree. (invert the weights associated witheach edge in the graph).matfud
Ignore me. Mistook the question.
I though TSP has never been solved...
The TSP has been solved. The solution is really quite simple...just test
all possible routes. The only problem with it is that it takes rather a
long time to compute. When people say it hasn't been solved they mean that
nobody has yet figured out how to solve it in polynomial time.
matfud
appologies for the sarcasam
You can solve TSP, but in O(n!) time (or other simlar really awful exploding function), which for n=10 is 10!=3628800. Then there are lots of approximate solutions that runs in O(n^3) or on that scale (which for n=100 is 1000000), whereof some can garantue to solve it with maximum a certain percentage larger than the optimal solution. There are many really good algorithms to give approximite results on TSP.
Gil
Still... NP-completeness is really a wonder. I bet people would give a whole lot of money to get the optimal solution to that. :) But if I remembel correctly, they were never able to calculate the optimal Omega of it, so we are still far from the Theta...
I guess it would be helpful to explain a little more what the problem is about.
Like many other games, the first player to reach a specified amount of points wins the game. One of the ways to gain points is by building the longest street. The "board" over which the game is played, is composed by regular hexagonal tiles.
The streets can only be placed over the edges of the tiles (the sides of the hexagon), and can not be placed over other streets. Additionally, streets can not cross each other, and they can not go beyond obstacles like towns and cities which can be constructed over the vertices of the tiles.
The "board" can be represented as a undirected graph. The nodes of the graph will be the vertices of the hexagons, and the arcs of the graph will be the sides of the hexagon. Note however, that most of the time, the vertices from adjacent hexagons will converge in only one node, as well as the sides. For example:
Let ABCDEF and GHIJKL be two of the tiles. If we place the tiles in a way that the CD side of the ABCDEF tile and the LG side of the GHIJKL tile are together, we will end up with the following graph:
N = {a,b,c',h,i,j,k,l',e,f}
A = {(a,b), (b,c'), (c',h), (h,i), (i,j), (j,k), (k,l'), (l',c'), (l',e), (e,f), (f,a)}
Note that the C vertex of the ABCDEF hexagon was merged with the G vertex of the GHIJKL hexagon forming the c' node. In the same way, the D vertex of the ABCDEF hexagon was merged with the L vertex of the GHIJKL hexagon forming the l' node. Note that from each node, only two other nodes can be reached with the exception of the nodes c' and l'. From these nodes three other nodes can be reached.
I hope this description of the problem will clarify some issues.
Dear gilroitto,
Actually I am studying the same problem, which is finding the longest path, but I have my graph with weights already assigned to edges.
http://www.cours.polymtl.ca/inf6100/devoir4/devoir4.html
Can you advice please?
Thanks in advance,
Carlos
Montreal, Canada
Do you know Prof. Godfried Toussaint?
I'm not good at French, but if I understand the assignment correctly it is far easier than the problem in this topic.
Eg, make a dynamic algorithm like this:
Have a set S of all visited points. associate all nodes in S with the path leading to it.
At startpoint, have only startpoint in S.
1. For each node n in S, take all possible paths to neighbour nodes n'.
2. For each node n':i
a) if n':i already in S, and previous path leading to n':i is longer - disregard current path to n':i
b) if n':i already in S, and previous path leading to n':i is shorter - replace with new path to n':i.
3. Repeat from 2.
When all nodes are taken, just look up the longest path to the end node.
This will take O(n*p*p), where p<n, which is O(n^3). You can probably improve it.
Gil
>
here is a nother algorithm (should be quicker)
create a topological sorting S of the nodes v in your graph -> O(n) with modified DFS
initialize camefrom[v] == null for v in V;
initialize distance[v] = 0 for all v in V;
for each v in S in ascending order (from left to right in your image)
for each edge e leaving v do
w = e.target;
if (distance(v) + e.weight) > distance(w)
distance(w) = distance(v) + e.weight;
camefrom(w) = v;
fi
rof
rof (takes O(n+m) )
I think this should be it (much simpler to implement and a lot faster than the previous proposal). Note that this is so easy *only* because there is a perfect topological order in your graph so that for each edge e TopologicalOrder(e.source) < TopologicalOrder(e.target).
Now, all you have to do is verify my little algorithm and translate it into perfect french, done is your homework :-(
Regards, Sebastian
Build your graph out of string. Grab any node and hand the entire graph up off the table. Grab the node that hangs the lowest and let go of the first node. Lift that lowest node above all the others and find the new lowest node. Those two nodes are farthest apart in your graph.
dpza at 2007-7-18 21:15:40 >
> Build your graph out of string. Grab any node and hand
> the entire graph up off the table. Grab the node that
> hangs the lowest and let go of the first node. Lift
> that lowest node above all the others and find the new
> lowest node. Those two nodes are farthest apart in
> your graph.
:))
What's the runtime complexity of this algorithm?
O(knitting+lifting)*Table.getHeight() ?!
Sebastian's algorithm is really good, you cannot get it any better than that. Seems like Sebastian has his theory fresh :) Some student is going to get good grades on his homework :PGil
> Sebastian's algorithm is really good, you cannot get
> it any better than that. Seems like Sebastian has his
> theory fresh :) Some student is going to get good
> grades on his homework :P
thanks :D
Actually my theory is not too fresh (it's about 4 years old), but it's my job being good at this kind of stuff :D (see my profile....)
Hi Guys,Thank you guys, actually it is a nice algorithm, and it is well efficient. Thank you guys,I guess i will have a very good grade, but the most importantis that I had learned something from you.A+Carlos
Dear Sebastian,
Your algorithm is really wonderful and so efficient .But honestly
it seems I need more help ,sorry bothering you ,I am confused about building a topoligical sorting that you mentioned already in the first step also in the second part I lost myself in comparison part.
First I put all distance equals zero then I got w.weight = 16 but in second loop "if (distance(v) + e.weight) > distance(w)"
I had 0 + 12 > 16 . now I have no idea how continue.
Could you please give me more details.
Thank you,
Carlos
Ok I haven't played this game in a long time, but from what i remember, here is my suggestion:
The solutions presented so far approach the problem from a too generic, algorithmic approach. However being as this is a very specific problem, you need a more specific solution. Being that this is a game, you will know when roads are created. Instead of worrying about doing some ridiculously complex traversal of the board/"graph", simply keep track all the roads of each player in some sort of data structure and precalculate the length. Its not like the Catan board is some huge beast... When a new road is built, recalculate the length of the roads for that player. To find longest road, a simply search through the length of the roads.....
I mean its a board game, and people expect you to do travelling salesman and weighted graph traversal blah blah blah...Get Real!! :) Simple problem, simple solution.
> However
> being as this is a very specific problem, you need a
> more specific solution.
Go back and read post #19.
>
> I mean its a board game, and people expect you to do
> travelling salesman and weighted graph traversal blah
> blah blah...Get Real!! :) Simple problem, simple
> solution.
? Strange... the point of OOD is that solutions can
be general, it's called abstraction.
J.Foreman> "Your solution is too general and works for everything".
Johnny> "Sorry sir, I'll try to do a worse job next time."
J.Foreman> "That's my Johnny!"
> sorry bothering you ,I am
> confused about building a topoligical sorting that you
> mentioned already in the first step
use google and you will find hundreds of implementations of topological sorting (maybe use the word ordering or order). this can be computed using a normal depth-first-search (dfs) and using the "completion numbers" for the (inverse) order.
> also in the second
> part I lost myself in comparison part.
> First I put all distance equals zero then I got
> w.weight = 16 but in second loop "if (distance(v) +
> e.weight) > distance(w)"
> I had 0 + 12 > 16 . now I have no idea how continue.
this means you have found a "shorter path" since it cost only 12 to get to w, while you already seem to have found a path that is 16 units long. so all you have to do is *nothing* in this case.
I suggest you draw a very small graph on a piece of paper and do the algorithm by hand. you will realize that the algorithm is very simple and that in the case where the inequality does not hold, you have to do nothing.
> Could you please give me more details.
for the first step.... use google
for the second step, there are no more details, the algorithm I gave you is complete.
Regards, Sebastian
rkippen> Strange... the point of OOD is that solutions can be general, it's called abstraction.
yes, they CAN be general, when they need to be.
If i need to move a brick across a room i'm not going to go out and build a device that can carry an arbitrary amount of bricks across infinite space, i'm going to go pick up the **** brick and move it...
In SoC, when a new section of road is added it either 1) lengthens an existing road or 2) creates a new road..So keeping track of the existing roads and updating when new sections are added to the board seems a perfectly acceptable solution. Unless he wants to change the rules of the game why bother generalizing the solution?
> If i need to move a brick across a room i'm not going
> to go out and build a device that can carry an
> arbitrary amount of bricks across infinite space, i'm
> going to go pick up the **** brick and move it...
>
Good point, but the general solution in this case is not that much more work.
> why bother generalizing the solution?
Another OOD concept - reusing code
Having a geneal solution is useful because it means the code can be used in different applications. Having the code in many applications means that there is a higher chance of finding an error in the code (if there are errors). The code will be tested more heavily, and give a better gauge of its correctness.
Hi Guys,
I am the original creator of this thread, and I was very surprised to see it still active, when I browsed the forums today.
I must say, that the solution of J.Foreman was the best sofar, although it is not a general algorithmic solution. But it is simple, and as far as I can tell, it does the job.
As I stated in my original post, the algorithmic problem seems to be NP-complete. I have no proof for this, but I remeber that I was coming across some refenrences while googling for solutions, that told sth about NP-completeness.
I am still interested in an algorithmic solution, but I am also glad to have a good, working and usable solution for my game.
Greetings, Christian
>
> Another OOD concept - reusing code
>
> Having a geneal solution is useful because it means
> the code can be used in different applications.
> Having the code in many applications means that there
> is a higher chance of finding an error in the code
> (if there are errors). The code will be tested more
> heavily, and give a better gauge of its correctness.
No.
If you do know about future releases then you can design code and implement code for that.
If you do not know about future releases then you are guessing.
- Do not write code that will not be used.
You should never write code that will not be used. In commercial (vs academic) developement that means that you do not write code which you do not know will be used in the current release or has a high probability that it will be used in a future release.
The reason for this is that unless you have psychic powers your ability to predict the future is not any better than any one elses - so your prediction will be wrong (if your predicitions are usually right then you should go make millions gambling.) And the code base will end up with code that is never used, and it is likely that it was not tested in the first place and probably will not be tested in future maintainance releases. It will probably remain until someone is smart enough to realize that it can be ripped out with no impact on existing functionality.
- Do not generalize from a single instance.
Generalizing from a single instance is almost always wrong. If I start with a "horse" I can generalize to an "animal" that "walks". That only works until I have to implement "fish".
Without more than one instance (and I actually prefer at least three) it is impossible to generalize the behavior of objects or systems.
Note again that this applies if you do NOT know what features are needed in future releases.
> >
> > Another OOD concept - reusing code
> >
> No.
>
I think you're missing the point. There is "A", a specific solution that works with specific objects that is specific to a problem. There is "B", a more general solution that can handle more general objects. E.g. I need to multiply a 5 by 5 matrix with a 5 by 8 matrix. Instead of writing code that handles those dimensions, you write a general solution that multiplies an x by y and y by z matrix. I did not mean to imply that your code should have hidden code/functionality that won't be used or tested.
> > >
> > > Another OOD concept - reusing code
> > >
>
> > No.
> >
>
> I think you're missing the point. There is "A", a
> specific solution that works with specific objects
> that is specific to a problem. There is "B", a more
> general solution that can handle more general objects.
> E.g. I need to multiply a 5 by 5 matrix with a 5 by 8
> matrix. Instead of writing code that handles those
> dimensions, you write a general solution that
> multiplies an x by y and y by z matrix. I did not
> mean to imply that your code should have hidden
> code/functionality that won't be used or tested.
>
>
Perhaps we are interpreting the problem differently. The following is the point that you responded to (and then I responded to you.)
Unless he wants to change the rules of the game why bother generalizing the solution?
The way I interpret that question is rather specific. There is a specific solution that meets the needs of the application (the game.) Generalizing that solution, as the poster suggests, does not add any value unless the game is going to be expanded in some known way in the future. Thus if there are future releases that need additional functionality then generalization should be used. If not then it shouldn't.
