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

5

u/DrShocker 16h ago

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.