Waste less time on Facebook — follow Brilliant.

Junction Tree Algorithm

Algorithm Overview

Start at position 1 and count the number of paths that lead from it. Store as an array in the first set of arrays such that the format is ({set} [ junction number, 1/ n amount of junctions]) : {1}[1, 1/2], {2}[2, 1/2]. Go down junction {1}[1, 1/2] and check for another junction at the end. If no junction at the end, then assign value of 0 to {1}[1, 1/2] and a value of 1 to {2}[2, 1/2].

At position 2, count paths just as at 1and assign to array of 2nd set such that they are: {2}[1, 1/n]...{2}[n, 1/n]. Go down {2}[1, 1/3]. If no junction then assign 0 to {2}[1, 1/3] and value to the remaining two junctions by:

\(\frac{1}{n}=\frac{1}{n+1} + \frac{1}{n(n-1)}\)

(-1 from the denominators) Go down path {2}[2, 1/3] (which now has a value of 1/2) and check for a junction. If found, then store as the 3rd set of junctions(position 3): {3}[1, 1/n)....{3[n, 1/n]. Go back to two and down the junction {2}[3, 1/3] and again check for junctions. Second junction found and so assigns the 4th set like the other sets. From here, the algorithm goes down both 4th set junctions to realise that no junctions were found and so assigns a value of 0 to {2}[3, 1/3].

This means that it must go back to position 2 and change junction {2}[2, 1/3] to 1 by default. It can then move along {2}[2, 1/3] to 3. At 3 the set has already been established and so it checks {3}[1, 1/2] and realises that there are no solutions. It assigns a value of 0 to {3}[1, 1/2] and a value of 1 to {3}[2, 1/2] and goes down it. It then solves the puzzle and the algorithm stops.

The solution to the problem is the junctions that have the value of 1 assigned to them: S -> {1}[2, 1/2] -> {2}[2, 1/3] -> {3}[2, 1/2] -> F

Note by Jack Barker
1 year, 8 months ago

No vote yet
1 vote


Sort by:

Top Newest

Hey @Jack Barker , it would be great to flesh this out with background on what kind of problems the algorithm was developed to solve. Can you start a wiki? Josh Silverman Staff · 1 year, 8 months ago

Log in to reply

@Josh Silverman Yeah sure. Sorry for being a little vague with this note. It's just something that i'm working on Jack Barker · 1 year, 8 months ago

Log in to reply

Can you add a little more background on what the problem is or what the algorithm is supposed to be doing? Agnishom Chattopadhyay · 1 year, 8 months ago

Log in to reply


Problem Loading...

Note Loading...

Set Loading...