2
$\begingroup$

When dealing with a Recursive Backtracking Algorithm what are the ways to speed it up and what computational hardware is involved?

I'm assuming from ignorance that everything is done by the CPU so the only thing that comes to mind to make it faster would be early exits, multithreading or quantum computing.

Is that it? Can a GPU be used or do these only work for mathematical operations?

TLDR: How can you speed up Recursive Backtracking Algorithm via Hardware or via Software.

Edit:

Assume something simple, like having a goal amount and multiple coins, then having to find which combination of coins add up to that goal amount.

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ I think this is too broad. It likely depends on the specific algorithm (and possibly on the distribution of problem instances you are facing). $\endgroup$
    – D.W. ♦
    Jul 18 at 17:26
  • $\begingroup$ Added a specific case for a simple RBA $\endgroup$
    – Daviid
    Jul 19 at 7:00
  • 2
    $\begingroup$ The coin change problem has a reasonably straightforward solution using dynamic programming. $\endgroup$
    – Pseudonym ♦
    Jul 19 at 7:24
  • $\begingroup$ I realize that, that's why I'm asking if there's any way to speed up a process that might take a LONG time, simple as it is. Forget about coins imagine you have 1,000,000 invoices and need a group that adds up to exactly 89,738.76$, worst case scenario it could run for a long time, test all possible groupings and still not find a solution. $\endgroup$
    – Daviid
    Jul 19 at 11:20

1 Answer 1

Reset to default
1
$\begingroup$

I think you pretty much got it there. There really aren't many ways to improve it, our best method is a slow one! (though our human brains instinctively would love to find something better for such a simple problem)

Though I'm imagining, when I think of recursive back-tracking, I think of an algorithm to solve a rubiks cube, or a sudoku puzzle. Which is just brute-forcing the problem, and it'll be slow no matter what. There are millions or billions or pathways to check, to see if we get a solution, and even then we might not get the best one.

However, if you're willing to step away from recursive back-tracking, there are some algorithms that will "smartly" try to find you a good answer really efficiently. Imagine when a human tries to solve a rubiks cube, they don't try every combination possible.

Computerphile has a good video on it: https://www.youtube.com/watch?v=ySN5Wnu88nE

The general idea of it, is you model all of your possible options/choices/moves as a massive decision tree, or graph. You're attempting to find the shortest path from the start, to the solution, but because we don't know how far away from the solution we are, we have a heuristic function, which gives us a guess of how far away we are.

This is the A* algorithm, almost like a Dijkstra, but it involves our heuristic function.

We selectively explore the paths which we guess will find us the solution the quickest. I applied this to a bubble sorting game once, my brute-force would explore 100000 different pathways and give you the BEST solution which takes only 9 steps to solve the game. But my A* algorithm with a good heuristic would explore 100 pathways, and give you a really good solution (but not the best), which took 10 steps. 1000x faster, but not guaranteed to be the best solution.

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ So, assuming you can't multithread (you need the previous iterations) it doesn't matter what kind of CPU we use it'll still be slow? And qubits wouldn't make a difference? $\endgroup$
    – Daviid
    Jul 19 at 12:32
  • 1
    $\begingroup$ Quantum computing is a bit out of my depth on this one to be honest, maybe, maybe not. I can imagine that there might be a way depending on the problem, but I don't think there is a one-size fits all for brute forcing and quantum computer algorithms. It'd definitely be good to post a separate question about quantum computers, as they are such a heavy and deep topic on their own. In terms of CPU speed, yeah, there's a lot of small stuff computers do in the background. $\endgroup$
    – Minko_Minkov
    Jul 19 at 12:35
  • 1
    $\begingroup$ I couldn't edit the last comment, so I'm writing a new one to add on lol: You generally can multithread though (exploring multiple paths at the same time), but other than that, things like solving a rubiks cube is slow no matter the CPU. And another thing, is just heaps of minor optimizations. Do you need 64 bit integers? Do all the numbers you work with fit within 8 bits? You can reduce the sizes of all your numbers, it'll take less time to multiply/add/check. Bitmasking, bit operations in general. But these are all minor optimizations that work for every problem. $\endgroup$
    – Minko_Minkov
    Jul 19 at 12:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.