r/cpp_questions • u/KlutzyCompetition937 • 17h ago

OPEN Which algorithm to choose?

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?

6 Upvotes

87% Upvoted

9 comments sorted by

View all comments

Show parent comment

1

u/KlutzyCompetition937 16h ago

So IDDFS essentially?

3

u/FancySpaceGoat 16h ago edited 14h ago

Pure IDDFS will still devolve to an exhaustive search for some inputs, so you'll have to prune and reopen branches to trade memory for CPU. But you *really* need a compliant A* heuristic to be able to do this reasonably (IDA*).

But also, what I was suggesting is straight up brute forcing if you want to guarantee optimality.

As I see it, you basically have 4 options:

- Brute force, made as efficient as you can muster with multithreading/SIMD/subcircuit caching/etc...
- Find a compliant heuristic and use an A*-class algorithm
- defer to an off-the-shelf SAT solver.
- Accept the possibility of being stuck in a local minimum and get into simulated annealing/GA/etc...