[Haskell-beginners] backtracking search and memory usage

[Dennis Raddle]

thanks, that's some great perspective. I love how computer scientists think
generally like that. I have several specific problems in mind and in those
problems, the backtracking state is always built by adding pieces and never
taking them away,and a full solution always requires the same number of
pieces. So basically there isn't an opportunity for loops to form.

Your advice to narrow the scope and build something that runs before
worrying about performance issues is good advice, advice I would probably
give myself or a younger programmer at times, but a lesson I still need to
learn in other ways.

Mike


On Sat, Mar 15, 2014 at 9:08 AM, Kim-Ee Yeoh <ky3 at atamo.com> wrote:

> Let's look at the requirements for this problem, uncovering some of the
> unspoken ones:
>
> 1. very general problem
> 2. fast, or at least not too slow
> 3. memory-efficient
> 4. correct
>
> Leaving aside performance issues 2 and 3, is it possible that 1 and 4
> alone are enough to deliver plenty of heartburn?
>
> I can think of at least one class of problems: the enumeration and
> application of choices lead to cyclical states. Hence resulting in a list
> of solutions pockmarked with bottoms.
>
> I mean your backtrack function is a correct and succinct description of
> the very notion of backtracking. The devil is in the details of state
> design, including the enumeration and application issues I've described.
>
> By narrowing the scope of the problem so that you first obtain a library
> that correctly solves it, you could then focus on performance issues.
>
>
> -- Kim-Ee
>
>
> On Sat, Mar 15, 2014 at 9:06 AM, Dennis Raddle <dennis.raddle at gmail.com>wrote:
>
>> I want to implement backtracking search, but I wonder if I'm going to
>> immediately run into memory usage problems if I don't use strict evaluation
>> somewhere. I'm very hazy on how to implement strict evaluation. I'm
>> thinking of creating a generic algorithm that looks something like the
>> following.
>>
>> We have the concept of a data construct that can be built step by step.
>> At each step are choices. We are investigating all the choices and finding
>> series of choices that lead to a completed data construct or "solution." We
>> want to generate a list of all solutions.
>>
>> (My Haskell syntax is rusty so there may be errors in the following.)
>>
>>
>> class Construct a where
>>   enumerateChoices :: a -> [b]
>>   applyChoice :: a -> b -> a
>>   isSolution :: a -> Bool
>>
>> backtrack :: Construct a => a -> [a]
>> backtrack c
>>   | isSolution c = [c]
>>   | otherwise =
>>      concat . map (backtrack . applyChoice c) . enumerateChoices $ c
>>
>> So my question is whether this is going to use a lot of memory to run,
>> maybe by holding all partially solved data? Where would strict evaluation
>> go?
>>
>>
>>
>>
>> _______________________________________________
>> Beginners mailing list
>> Beginners at haskell.org
>> http://www.haskell.org/mailman/listinfo/beginners
>>
>>
>
> _______________________________________________
> Beginners mailing list
> Beginners at haskell.org
> http://www.haskell.org/mailman/listinfo/beginners
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/beginners/attachments/20140316/1966e90b/attachment.html>