Optimizing a breadth-first search
snellman.net
Optimizing a breadth-first search
1–10 of 40 posts
Re: Optimizing a breadth-first search
#2> 100GB of memory would be trivial at work, but this was my home machine with 16GB of RAM. And since Chrome needs 12GB of that, my actual memory budget was more like 4GB. Anything in excess of that would have to go to disk (the spinning rust kind).
I hope this is a joke, although it's a little scary totalling up how much Chrome is chewing right now, with just one window and seven tabs open...
Re: Optimizing a breadth-first search
#3https://en.wikipedia.org/wiki/Iterative_deepening_depth-firs...
Edit: for context, wasn't meant to be "zomg how you so dumb" so much as "everyone should also read, cause is relevant".
Re: Optimizing a breadth-first search
#4https://en.wikipedia.org/wiki/Iterative_deepening_depth-firs... Edit: for context, wasn't meant to be "zomg how you so dumb" so much as "everyone should also read, cause is relevant".
This was my thought too, but I don't want to assume: he cites enough standard but specific sources that he should know the general search algorithms. Also I think that since he doesn't mention standard depth first search at all it perhaps wasn't relevant?
Re: Optimizing a breadth-first search
#5https://en.wikipedia.org/wiki/Iterative_deepening_depth-firs... Edit: for context, wasn't meant to be "zomg how you so dumb" so much as "everyone should also read, cause is relevant".
The article is about optimizing the saved state information of the search, not about optimizing the search itself.
Re: Optimizing a breadth-first search
#6https://en.wikipedia.org/wiki/Iterative_deepening_depth-firs... Edit: for context, wasn't meant to be "zomg how you so dumb" so much as "everyone should also read, cause is relevant".
The article is about optimizing the saved state information of the search, not about optimizing the search itself.
Yet it's also about solving a problem, that goes out of memory. If there is an equal algorithm that doesn't go out of memory isn't this a valid criticism?
The author probably spent some time writing the code, modifying and extending the algorithm. He wrote deduplication code, memory mapping etc. Wouldn't it be interesting to know how iterative deepening performs?
Re: Optimizing a breadth-first search
#7https://en.wikipedia.org/wiki/Iterative_deepening_depth-firs... Edit: for context, wasn't meant to be "zomg how you so dumb" so much as "everyone should also read, cause is relevant".
This was my thought too, but I don't want to assume: he cites enough standard but specific sources that he should know the general search algorithms. Also I think that since he doesn't mention standard depth first search at all it perhaps wasn't relevant?
As mentioned briefly in the introduction, I didn't have good heuristics to use for a scoring function. A totally undirected DFS didn't seem like a great option. The readme links to an existing Python-based solver for the same game [0], which had both BFS and DFS modes. The DFS one was considerably slower on large puzzles even when given the optimal target depth.
Totally happy to believe I'm wrong about that, though :)
Re: Optimizing a breadth-first search
#8https://en.wikipedia.org/wiki/Iterative_deepening_depth-firs... Edit: for context, wasn't meant to be "zomg how you so dumb" so much as "everyone should also read, cause is relevant".
This was my thought too, but I don't want to assume: he cites enough standard but specific sources that he should know the general search algorithms. Also I think that since he doesn't mention standard depth first search at all it perhaps wasn't relevant?
I think it warrants an explanation though. Why not DFS? Too hard to dedupe? What’s the branching factor and the duplication rate? If the algorithm is 50x faster due to lower overhead it might be worth it.
Re: Optimizing a breadth-first search
#9Earlier quoted context omitted.
The article is about optimizing the saved state information of the search, not about optimizing the search itself.
Yet it's also about solving a problem, that goes out of memory. If there is an equal algorithm that doesn't go out of memory isn't this a valid criticism? The author probably spent some time writing the code, modifying and extending the algorithm. He wrote deduplication code, memory mapping etc. Wouldn't it be interesting to know how iterative deepening performs?
Memorization, deduplication and good data structures should help IDDFS and similar algorithms too.
Re: Optimizing a breadth-first search
#10Earlier quoted context omitted.
This was my thought too, but I don't want to assume: he cites enough standard but specific sources that he should know the general search algorithms. Also I think that since he doesn't mention standard depth first search at all it perhaps wasn't relevant?
I think it warrants an explanation though. Why not DFS? Too hard to dedupe? What’s the branching factor and the duplication rate? If the algorithm is 50x faster due to lower overhead it might be worth it.
The problem seems to have many early branches making deep searches much less useful.