Re: Best data structure for DFS on large graphs

On Tue, Jul 3, 2012 at 8:10 PM, Tim Chase <python.list@tim.thechases.com> wrote:
> On 07/03/12 08:39, Miheer Dewaskar wrote:
>> On Tue, Jul 3, 2012 at 4:53 PM, Stefan Behnel <stefan_ml@behnel.de> wrote:
>>>
>>> Miheer Dewaskar, 03.07.2012 13:11:
>>>> I am not sure,but if there are large number of states Dictionaries wont
>>>> help much right?
>>>
>>> Dicts are fast for lookup, not for searching.
>>>
>> What do you mean by searching in the context of Dicts?
>
> It took me a while to parse Stefan's post, and I *think* he means
> that key-indexing (direct lookup) is fast O(1), and that by
> "searching" he means something like "find all keys/values matching
> property $FOO" such as between a range.
>
> One of the important things you omit is how you define "large". Is
> this a couple thousand? Hundreds of thousands? Millions?

I want it to be a generic Game solver.So the number of states depends
on the game.
For a simple tic-tac-toe the upper bound is 3^9 states.But for more
complex games it could be much larger.
I would like to assume that the number of states can grow arbitrarily large.

> Also, what sort of information are you keeping in the state? Just
> available transitions? Or do you want additional metadata? If it's
> just transition mappings (A->B) rather than complex objects, I'd try
> using a dict first, and if it's too large, I'd reach for the
> "anydbm" module to store them to disk.

The state just has 'state data'.The transitions are obtained by
functions analyzing the state.
So that I should not be able to identify between two same states that
have been reached by different means.

For example in the tic-tac-toe game the states can be a 3x3 box of integers

0 -> unoccupied
1 -> x
2-> o

( (2,0,1), o - x
(1,1,0), -> x x -
(2,0,0) ) o - -



--
Miheer Dewaskar