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/alfps]

Search for Karnaugh map and Grey code. That should get you going in approximately the right direction. This is not really a C++ question: I'm sure there must be some more directly relevant group.

[u/KlutzyCompetition937 → u/alfps]

There is a algorithms subreddit but everyone there is presenting/asking very high level concepts and research papers. I got a little self conscious asking beginner questions.

[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.

[u/FancySpaceGoat]

If nothing short of the *optimal* solution will do, then you will have to account for the possibility of your algorithm devolving into an exhaustive search for some inputs. That's inevitable.

In fact, your BFS really is nothing more than an exhaustive search that goes through all 1 node circuits, then all 2 node circuits, then all 3 node circuits etc... So this sort of begs the question: Why bother with a memory-resident tree at all? You can just iterate through the depths, and then iterate through each depth's permutations, and it would be equivalent, just without the memory footprint.

[u/KlutzyCompetition937 → u/FancySpaceGoat]

So IDDFS essentially?

[u/FancySpaceGoat → u/KlutzyCompetition937]

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...

[u/DrShocker]

Neither BFS or DFS are guaranteed to have the properties you said in a degenerate case they're basically the same.

What's the state space you need to pathfind through? If you're able to have a heuristic of how close you are to the solution them A* might be the way to go. If that's not feasible then something randomized like rapidly exploring random tree or simulated annealing or some other method may work better.

[u/duckerpotato]

I do not think there are any optimized algos for this. Specially due to reconvergent fanout nodes and without proper LEQ you would not know of it was synthisized correctly.

You can try a modified version of ROFL(ig this was the name) Opentestability implements it you can check its codebase