[gameprogrammer] Re: Let's play... Name That Algorithm! :)
- From: Bob Pendleton <bob@xxxxxxxxxxxxx>
- To: gameprogrammer@xxxxxxxxxxxxx
- Date: Tue, 18 Aug 2009 09:59:14 -0500
On Tue, Aug 18, 2009 at 9:45 AM, Mike Gillissie<Niyoto@xxxxxxxxxx> wrote:
> Hi Bob!
>
> Your note on memoization looks very interesting, especially considering the
> approach I'm currently using. I just need to identify which problems are
> being repeated - something keeps flashing in my mind as I think of this, so
> I need to get back to pencil and paper and work my way through this.
>
> My main concern with caching results, though, is that size of the entire
> resultset can be astounding - it might not be feasible to add search and
> storage to the approach...
Yep, it is a classic space/speed trade off. And, yes, the space needed
can become huge. OTOH, if you only cache a small percentage of the
cases you can still get a significant speed up. I've tried to use it
many times. Some times the results are wonderful, other times it was a
total failure because there were so many results.
Bob Pendleton
>
> -Mike
>
> ----- Original Message ----- From: "Bob Pendleton" <bob@xxxxxxxxxxxxx>
> To: <gameprogrammer@xxxxxxxxxxxxx>
> Sent: Tuesday, August 18, 2009 9:15 AM
> Subject: [gameprogrammer] Re: Let's play... Name That Algorithm! :)
>
>
> Yeah, this is the right solution. The problem is called finding the
> transitive closure on a set.
>
> I don't know if it applies in this case, but in a lot of problems like
> this you find your self solving the same sub problem over and over.
> That means you can save a lot of time by remembering the solutions to
> previously solved problems. This is called memoization
> (http://en.wikipedia.org/wiki/Memoization). For example, if you are
> about to add "b" to the processing list, first look up "b" and see if
> you have already come up with its compatibility list, if so, add the
> whole results. That way you avoid resolving the problem for "b". This
> technique works really well for recursive solutions to problems
> because each recursive call can just check its arguments to see if
> that combination has already been solved and each function call can
> add its arguments and the final value for that call to the set of
> remembered solutions.
>
> Bob Pendleton
>
> On Mon, Aug 17, 2009 at 10:41 PM, Kevin
> Jenkins<gameprogrammer@xxxxxxxxxx> wrote:
>>
>> This is equivalent to determining if a set of vertices is connected by
>> edges, while adding additional vertices to check, and also checking if the
>> vertice is connected to itself. The most efficient way to do so is add
>> single vertices at a time, and compare the new vertice to the existing
>> ones.
>>
>> Then returning the combination set of the maximum fully connected graphs.
>>
>> 1. Add all vertices (in your case, indices) to a processing list.
>> 2. Pop the first vertex from the processing list.
>> 3. For each additional vertex, if that vertex connects to all vertices in
>> the working list, add it to the working list. Else add it to a next-round
>> processing list.
>> 4. Add the working list to the completed list (list of lists)
>> 5. Swap the processing and next-round processing list.
>> 6. Goto 2
>>
>> So now you have the set of maximum sized fully connected meshes. Since you
>> appear to also want the combination set, just do a combination set process
>> on the completed list. For example, 0,1,2 would return 0-1, 0-2, 1-2. This
>> is different from your example output, which I believe is incorrect.
>>
>> Mike Gillissie wrote:
>>>
>>> I did just an excellent job of not completing my first attempt at an
>>> email
>>> - hopefully my second attempt came though to completion... ;)
>>> The Karnaugh Map thingie looks pretty interesting, though admittedly I'm
>>> going to have to take a closer look at its scalability to 5000-ish values
>>> (squared-ish)... thanks for sharing! :)
>>> My ultimate goal is to determine all combinations of mutually compatible
>>> units based on the truth table.
>>> From Vince's example,
>>> 0 1 2 3
>>> 0 [1, 1, 0, 1]
>>> 1 [1, 1, 1, 1]
>>> 2 [0, 1, 1, 0]
>>> 3 [1, 1, 0, 1]
>>> In this case, starting with element 0, I'm currently building a tree
>>> using a recursive function. I see that 0 and 1 are compatible - I recurse
>>> down one level and see if 0-1 is compatible with 3 (the next compatible
>>> element to 0) - since all three are mutually compatible (0-1, 0-3 and
>>> 1-3)
>>> my first "stored" combination is 0-1-3.
>>> From 1, I look at 1-2. I recurse down to see if 1-2-3 is compatible - I
>>> find that it's not since 2-3 are not compatible. So I end up storing the
>>> combinations 1-2 and 1-3.
>>> Finally, since 2-3 is not compatible, I end up storing 2 and 3 as
>>> separate "combinations" (albeit combinations of 1 element).
>>> My final set from the Vince-List:
>>> 0-1-3
>>> 1-2
>>> 1-3
>>> 2
>>> 3
>>> My code actually eliminates the "south-west" portion of the matrix, since
>>> I will only compare against higher-value indexes from my starting point.
>>> Well said, Mike... yeesh... ;)
>>> 0 1 2 3
>>> 0 [*, 1, 0, 1]
>>> 1 [*, *, 1, 1]
>>> 2 [*, *, *, 0]
>>> 3 [*, *, *, *]
>>> While slightly complicating my indexing, it more than doubles my
>>> capacity.
>>> Looking at this, even considering a 5000x5000 truth table (stored as a
>>> 4999+4998+4997...3+2+1 one-dimensional array), it just looks like
>>> something
>>> that a more experienced algorithmagician must have solved nicely in the
>>> past... ;)
>>> My apologies for the half-email that I started this with - Outlook
>>> Express
>>> probably does a send when you hit some combination of
>>> Control/Shift/Enter,
>>> or if you're trying to impress your betters... =/
>>> Thanks guys! :)
>>> -Mike
>>>
>>> ----- Original Message -----
>>> *From:* Alan Wolfe <mailto:alan.wolfe@xxxxxxxxx>
>>> *To:* gameprogrammer@xxxxxxxxxxxxx
>>> <mailto:gameprogrammer@xxxxxxxxxxxxx>
>>> *Sent:* Monday, August 17, 2009 8:24 PM
>>> *Subject:* [gameprogrammer] Re: Let's play... Name That Algorithm! :)
>>>
>>> I'm not sure 100% what you are trying to achieve but Karnaugh maps
>>> might help you
>>> http://en.wikipedia.org/wiki/Karnaugh_map
>>> they let you take an array of bools and simplify it into groups.
>>> They are used on 2d arrays mostly to take boolean output and try
>>> to come up with the simplified boolean equation to make that
>>> output, but i think they could work for what you want too, and
>>> they deffinately work on both 1d and 3d arrays (and higher) as well :P
>>> On Mon, Aug 17, 2009 at 5:13 PM, Vince <uberneen@xxxxxxxxx
>>> <mailto:uberneen@xxxxxxxxx>> wrote:
>>>
>>>
>>>
>>> --- On Mon, 8/17/09, Mike Gillissie <Niyoto@xxxxxxxxxx> wrote:
>>>
>>> > From: Mike Gillissie <Niyoto@xxxxxxxxxx>
>>> > Subject: [gameprogrammer] Let's play... Name That Algorithm! :)
>>> > To: gameprogrammer@xxxxxxxxxxxxx
>>> <mailto:gameprogrammer@xxxxxxxxxxxxx>
>>> > Date: Monday, August 17, 2009, 11:57 PM
>>> >
>>> >
>>> >
>>> >
>>> >
>>> >
>>> >
>>> > Hi folks!
>>> > > I'm in the middle of a
>>> > situation - I have a problem
>>> > I'm trying to solve, and it looks like the sort of
>>> > problem that has a very nice
>>> > algorithm named after some fine studious person. Here's
>>> > the skinny:
>>> > > At this point in my code I
>>> > have a square boolean
>>> > array that's used to indicate
>>> > "compatibilities" - so if I have 5 units and I
>>> > calculate each one's compatibility with each other unit
>>> > (as either a Yes or a
>>> > No), I might have values something like:
>>> > > compat[0][1]=true;
>>> >
>>> > compat[0][1]=true;
>>> >
>>> > compat[0][1]=true;
>>> >
>>> > compat[0][1]=true;
>>> >
>>> >
>>>
>>> I'm looking three redundant statements here.
>>> If I'm reading your description correctly, compat might look
>>> more like this: (adjust 0, 1 for true, false if you please)
>>> 0 1 2 3
>>> 0 [1, 1, 0, 1]
>>> 1 [1, 1, 1, 1]
>>> 2 [0, 1, 1, 0]
>>> 3 [1, 1, 0, 1]
>>>
>>> If you're testing to see if something along X is compatible
>>> with something along Y, you could
>>> #define OPTION1 0
>>> #define OPTION2 1
>>> and so on, then you could check with any pair like so :
>>> iscompat = compat[OPTION1][OPTION2]
>>>
>>> Is that what you're after?
>>>
>>> Vince~
>>>
>>>
>>>
>>>
>>>
>>>
>>> ---------------------
>>> To unsubscribe go to http://gameprogrammer.com/mailinglist.html
>>>
>>>
>>>
>>
>> ---------------------
>> To unsubscribe go to http://gameprogrammer.com/mailinglist.html
>>
>>
>>
>
>
>
> --
> +-----------------------------------------------------------
> + Bob Pendleton: writer and programmer
> + email: Bob@xxxxxxxxxxxxx
> + web: www.TheGrumpyProgrammer.com
>
> ---------------------
> To unsubscribe go to http://gameprogrammer.com/mailinglist.html
>
>
>
>
>
> ---------------------
> To unsubscribe go to http://gameprogrammer.com/mailinglist.html
>
>
>
--
+-----------------------------------------------------------
+ Bob Pendleton: writer and programmer
+ email: Bob@xxxxxxxxxxxxx
+ web: www.TheGrumpyProgrammer.com
---------------------
To unsubscribe go to http://gameprogrammer.com/mailinglist.html
Other related posts:
