×

# 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, 6 months ago

Sort by:

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? Staff · 1 year, 6 months ago

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