miheer.dew at gmail
Jul 3, 2012, 8:08 AM
Post #5 of 6
(352 views)
Permalink
|
|
Re: Best data structure for DFS on large graphs
[In reply to]
|
|
On Tue, Jul 3, 2012 at 8:10 PM, Tim Chase <python.list [at] tim> 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> 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
--
http://mail.python.org/mailman/listinfo/python-list
|
