Finding Egyptian fractions with A* search
There's a bug in is_solution:

&gt;&gt;&gt; is_solution((2, 3, 6), 4)
False


even though $$ {1\over2} + {1\over3} + {1\over6} = 1 = {4\over4}. $$

This is because \${1\over3}\$ and \${1\over6}\$ can't be exactly represented as floating-point numbers:

&gt;&gt;&gt; 1/2 + 1/3 + 1/6
0.9999999999999999


The way to solve this is to represent fractions using the fractions.Fraction class:

&gt;&gt;&gt; Fraction(1, 2) + Fraction(1, 3) + Fraction(1, 6) == Fraction(4, 4)
True

The question claims the algorithm is "A*", but that's not true. The A* search algorithm tries to find the least-cost path to an identifiable goal in a directed graph. But here you can't identify the goal (because you're looking for a minimum, you won't know what it is until the search is complete), and you don't care about the cost of the path taken to get there.

It would be better to call the algorithm "best-first search".
You're basically searching over all triples of integers looking for one that happens to add up to your target. This is a waste of time, because after you've picked \$y\$ and \$z\$, say, then you can know that $$ x = {1 \over {4\over n} - {1\over y} - {1\over z}} $$ and all you have to do is compute this and check that it's an integer.

So a (slightly) better strategy looks like this:

from collections import namedtuple
from fractions import Fraction
from itertools import chain, count, takewhile
from math import floor

Triple = namedtuple('Triple', 'x y z')

def egyptian_triples(n):
    """All solutions to 1/x + 1/y + 1/z = 4/n in lexicographic order."""
    tz = Fraction(4, n)
    for z in count(floor(1 / tz) + 1):
        ty = tz - Fraction(1, z)
        for y in range(floor(1 / ty) + 1, z + 1):
            tx = ty - Fraction(1, y)
            if tx.numerator == 1 and tx.denominator &lt;= y:
                yield Triple(tx.denominator, y, z)

def min_egyptian_triple(n):
    """Return the solution to 1/x + 1/y + 1/z = 4/n with minimum x + y + z."""
    triples = egyptian_triples(n)

    # First solution in lexicographic order.
    first = next(triples)
    max_z = sum(first) - 2

    # Return minimum solution.
    return min(chain((first,), takewhile(lambda t: t.z &lt;= max_z, triples)),
               key=sum)


This is substantially faster:

&gt;&gt;&gt; from timeit import timeit
&gt;&gt;&gt; timeit(lambda:main(115), number=1)
(290, (60, 92, 138))
19.941934717004187
&gt;&gt;&gt; timeit(lambda:print(min_egyptian_triple(115)), number=1)
Triple(x=60, y=92, z=138)
0.46365413605235517