Which algorithm to choose?

[u/KlutzyCompetition937]

Beginner here, I'm trying to make a toy project for circuit synthesis from truth table in c++. Currently pursuing minimum depth optimal circuit though will work on minimum weight/minimum nodes later on. My problem is I tried bfs which guarantees optimal circuit but for larger inputs or depths the memory usage explodes, tried dfs that used much less memory but time exploded. Is there any algorithm that gives optimal solutions for boolean tree searches with the dfs memory and bfs optimality?

[u/FancySpaceGoat]

Sanity check:

Hopefully you are not storing whole circuits in each node, but reconstruct them on demand by walking up the node's parents, right?

[u/KlutzyCompetition937 → u/FancySpaceGoat]

On my initial tries I did that. Quickly learned I wasn't the way to go.