Best data structure for DFS on large graphs
miheer.dew at gmail.com
Tue Jul 3 17:08:05 CEST 2012
On Tue, Jul 3, 2012 at 8:10 PM, Tim Chase <python.list at 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 at 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,0,1), o - x
(1,1,0), -> x x -
(2,0,0) ) o - -
More information about the Python-list