|
web
newsgroups
|
|||||||||||||||||||||||
|
|||||||||||||||||||||||
All possible paths in decision tree
Show quote
Hide quote
> I am trying to find all possible routes between two points on a tree I think I need a variant of Djikstra's algorithm but simplified. I hope > using a top to bottom search only. The tree looks like this: > > ' 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 31 32 33 34 35 36 > ' /\ / \ / \ / / / \ / \ > ' 37 38 39 40 41 42 43 44 45 > The problem is that asking for all routes between 1 and 41 should > give: > someone can help because I have spent another day banging my head against a wall with this :-( Arrrggghhhh!! Daniel If I were to implement this, I would design a special class that identified
the two branches from any given node. Public Class BranchNode Public NodeValue As Integer ' The node value itself Public LeftBranch As NodeValue Public RightBranch As NodeValue ' If both LeftBranch and RightBranch are Nothing, this is a Leaf node End Class It would take some work to populate all of the nodes, but once you had it you could traverse all the way down to the leaves using a recursive routine. It would be a lot easier to track and debug than using a string array (at least to me). ----- Tim Patrick Start-to-Finish Visual Basic 2005 Show quoteHide quote >> I am trying to find all possible routes between two points on a tree >> using a top to bottom search only. The tree looks like this: >> >> ' 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 31 32 33 34 35 36 >> ' /\ / \ / \ / / / \ / \ >> ' 37 38 39 40 41 42 43 44 45 >> The problem is that asking for all routes between 1 and 41 should >> give: > I think I need a variant of Djikstra's algorithm but simplified. I > hope someone can help because I have spent another day banging my head > against a wall with this :-( > > Arrrggghhhh!! > > Daniel > Oops, I had typos in the class. Here is the correct class.
Public Class BranchNode Public NodeValue As Integer ' The node value itself Public LeftBranch As BranchNode Public RightBranch As BranchNode ' If both LeftBranch and RightBranch are Nothing, this is a Leaf node End Class ----- Tim Patrick Start-to-Finish Visual Basic 2005 Show quoteHide quote > If I were to implement this, I would design a special class that > identified the two branches from any given node. > > Public Class BranchNode > Public NodeValue As Integer ' The node value itself > Public LeftBranch As NodeValue > Public RightBranch As NodeValue > ' If both LeftBranch and RightBranch are Nothing, this is a Leaf > node > End Class > It would take some work to populate all of the nodes, but once you had > it you could traverse all the way down to the leaves using a recursive > routine. It would be a lot easier to track and debug than using a > string array (at least to me). > > ----- > Tim Patrick > Start-to-Finish Visual Basic 2005 >>> I am trying to find all possible routes between two points on a tree >>> using a top to bottom search only. The tree looks like this: >>> >>> ' 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 31 32 33 34 35 36 >>> ' /\ / \ / \ / / / \ / \ >>> ' 37 38 39 40 41 42 43 44 45 >>> The problem is that asking for all routes between 1 and 41 should >>> give: >> I think I need a variant of Djikstra's algorithm but simplified. I >> hope someone can help because I have spent another day banging my >> head against a wall with this :-( >> >> Arrrggghhhh!! >> >> Daniel >> > If I were to implement this, I would design a special class that Thanks Tim. I'll have a look at it over the weekend and see how I get on. > identified the two branches from any given node. > > Public Class BranchNode > Public NodeValue As Integer ' The node value itself > Public LeftBranch As NodeValue > Public RightBranch As NodeValue > ' If both LeftBranch and RightBranch are Nothing, this is a Leaf > node > End Class Not sure I totally understand what you have said but we'll see! Any other tips you can give? Thanks, Daniel --------------------------------------------------- To contact me you need to clean up my email address. It should be fairly obvious... You might want to read up a little on data structures, a basic computer science
idea. Here is a starting point on Wikipedia. http://en.wikipedia.org/wiki/Data_structures Also, I posted a correction to the class below in another message in this same thread that replaces "NodeValue" in the LeftBranch and RightBranch lines with "BranchNode". Sorry for the mistake. ----- Tim Patrick Start-to-Finish Visual Basic 2005 Show quoteHide quote >> If I were to implement this, I would design a special class that >> identified the two branches from any given node. >> >> Public Class BranchNode >> Public NodeValue As Integer ' The node value itself >> Public LeftBranch As NodeValue >> Public RightBranch As NodeValue >> ' If both LeftBranch and RightBranch are Nothing, this is a Leaf >> node >> End Class > Thanks Tim. I'll have a look at it over the weekend and see how I get > on. > Not sure I totally understand what you have said but we'll see! Any > other > tips you can give? > Thanks, > > Daniel > --------------------------------------------------- > To contact me you need to clean up my email address. It should be > fairly > obvious... 
Other interesting topics
|
|||||||||||||||||||||||
