Hand execution trace of GaborSch's algorithm applied to input {20}

hand_exec.txt

In here, I will write each node as
    [weight]number=expr
and, as a compact notation, multiple nodes with same weight
    [w]n1=e1 [w]n2=e2 [w]n3=e3
are denoted
    [w]n1=e1 n2=e2 n3=e3 

I will trace execution of your algorithm applied to input {20}.

First, I register [0]1 and generate [1]2=1+1
    Registered:
        [0]1
    Generated:
        [1]2=1+1
in generated queue, only [1]2=1+1 exists. then I register it
and generate [2]3=1+2 and [3]4=2^2.
    Registered:
        [0]1  [1]2=1+1
    Generated:
        [2]3=1+2 [3]4=2^2
take first 1 node in generated queue and register if it is new number.
(Generated queue is sorted by weight of each node.)

all new possible calculations with 3 are:
    [3]4=1+3 [4]5=2+3 [5]6=3+3
    [4]6=2*3 [5]9=3*3
    [4]8=2^3 [4]9=3^2 [5]27=3^3
add them without 27 (because it is too large)

    Registered:
        [0]1  [1]2=1+1 [2]3=1+2
    Generated:
        [3]4=2^2 4=1+3
        [4]5=2+3 6=2*3 8=2^3 9=3^2
        [5]6=3+3 9=3^2

step next->
I have encountered [3]4=2^2 and [3]4=1+3, which have same weight and same number.
Let me choose [3]4=2^2...

    Registered:
        [0]1  [1]2=1+1 [2]3=1+2 [3]4=2^2

    New:
        [4]5=1+4  [5]6=2+4  [6]7=3+4  [7]8=4+4
                  [5]8=2*4  [6]12=3*4 [7]16=4*4
                  [5]16=2^4
                  [5]16=4^2

    Generated:
        [3]4=1+3
        [4]5=2+3 5=1+4  6=2*3  8=2^3  9=3^2
        [5]6=3+3 6=2+4  8=2*4  9=3^2  16=2^4  16=4^2
        [6]7=3+4 12=3*4
        [7]8=4+4 16=4*4

step next->
Again, I have encountered [4]5=2+3 and [4]5=1+4.
Let me choose [4]5=2+3...

    Registered:
        [0]1  [1]2=1+1 [2]3=1+2 [3]4=2^2 [4]5=2+3

    New:
        [5]6=1+5 [6]7=2+5  [7]8=3+5  [8]9=4+5  [9]10=5+5
                 [6]10=2*5 [7]15=3*5 [8]20=4*5

    Generated:
        [4]5=1+4  6=2*3  8=2^3  9=3^2
        [5]6=3+3  6=2+4  6=1+5  8=2*4  9=3^2  16=2^4  16=4^2
        [6]7=3+4  7=2+5  10=2*5 12=3*4
        [7]8=4+4  8=3+5  15=3*5 16=4*4
        [8]9=4+5  20=4*5 
        [9]10=5+5

It hits 20, so final result is
2=1+1
3=1+2
4=2^2
5=2+3
20=4*5

...if I chose [4]5=1+4 instead of [4]5=2+3, 3=1+2 were no longer needed.

2=1+1
4=2^2
5=1+4
20=4*5

But, there was no way to determine which was better (think if input was {15}).