[gameprogrammer] Re: Let's play... Name That Algorithm! :)
- From: Bob Pendleton <bob@xxxxxxxxxxxxx>
- To: gameprogrammer@xxxxxxxxxxxxx
- Date: Tue, 18 Aug 2009 08:15:45 -0500
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
Other related posts:
