3 ms·
A dynamic programming approach would work. Basically, try everything.
by eschneider 3y ago
A dynamic programming approach would work. Basically, try everything.
- CyberDildonics 3y agoWhat do you mean by that exactly and why would it be 'dynamic programming' ?
- Shorel 3y ago"Dynamic programming" is jargon from competitive programming. It sounds a lot more sophisticated than it is. In reality, it is nothing more than memoization of function calls into an array.
- CyberDildonics 3y agoMemoization is just caching so I'm not sure how that would make any difference here.
- jazpy 3y agoDifferent sets of moves can lead to the same state, so if you can cache that a given state will not lead to a solution you can stop exploring that branch when you encounter it again.
- CyberDildonics 3y agoIs that 'dynamic programming' or is that just keeping a set of explored states?
- 317070 3y ago> In reality, it is nothing more than memoization of function calls into an array. No, it's the next step after memoization. Recursion is the slowest approach of implementing many algorithms, as it will duplicate a lot of computation of subproblems. It solves a lot of subproblems many times. Memoization is a cheap fix, it will not solve subproblems multiple times. It stores subproblems it has already solved, along with the solution. But it has an increasingly large state, keeping solutions of subproblems in memory which are actually no longer needed. Dynamic programming is a manipulation on algorithms relying on memoization. It takes such an algorithm, and it makes the state as small as possible. So solutions of subproblems are discarded when they are no longer needed. Like in memoization, dynamic programming will keep around previous subproblem solutions. But it will only keep the ones around it still needs in the future, and discard what is no longer needed. This often requires a change in representation of that state and in the order in which the subproblems are solved. But it will run much faster than recursion, on less memory than memoized approaches.
- CyberDildonics 3y agoKeeping the intermediate results of computations is just called programming. They go into a variable or a data structure like a vector or a hash map.
- 317070 3y agoThat tends to blow up your memory. And even if you have huge amounts of memory available, using a big cache will slow down your program enormously.
- CyberDildonics 3y agoYou: Dynamic programming means saving the results of computations Me: That's just normal programming, there is no reason to use a term that someone made up in the 60s to as intentionally nonsensical. You: That will blow up your memory and slow down your program! What are you talking about here? All I said was that what you described was normal programming. I didn't come up with anything different, we're still talking about whatever you wrote. Somehow now storing data, something that happens in every program ever made, 'blows up memory'.
- 317070 3y agoBut there is a difference between memoization and dynamic programming. Memoization or otherwise indiscriminately storing the results of computations will blow up your memory use on many problems, where a dynamic programming approach would not. Dynamic programming does not mean saving the results of computations, it is about saving the _minimal_ number of results, without having to recompute already solved subproblems later on. I agree that the name chosen is nonsensical, but the concept is very much a real thing. And a quite important one at that.
- Shorel 3y agoYep, it has a nonsensical name, that's the point I wanted to convey. Actual "dynamic programming" would be self-modifying code, or something just as sophisticated, IMO. Or Prolog =) What about "memoization optimized backtracking"?