DFS, BFS and Priority Queue

[Clint]

For the TSP problem, I know we discussed that a DFS would be better than a BFS because we don't want to search the whole tree before finding a solution, but I can't remember what we concluded about the priority queue.  Is this usually or always preferable over DFS?  Would it be possible for the priority queue to act much like a BFS if the bounds of each state are arranged in a particular way?  Thanks

[Christopher Tensmeyer]

Your agenda has complete liberty to decide the search order.  A pure BFS is a bad choice because you never hit potential solutions until you find an optimal one (like A*), but does good pruning.  A pure DFS will find lots of solutions quickly, but is worse on the pruning.  Prioritizing on a hybrid approach is a sound approach to getting the best of both worlds.  Perhaps you give a higher priority to partial solutions that are close to finishing so you update your bssf more often.  Again, you have to weigh the trade offs based on what your expected inputs are going to be.  When I did mine, my strategy was to use an aggressive pure DFS that was very quick and did implicit (no cost) pruning of the search space, with a quick tight bound function.  But it worked well because all the pieces fitted together in a cohesive strategy.  So decide your strategy-search order preference and bounding function trade offs, and then design specific implementations.

Chris

On Tue, Jul 31, 2012 at 9:32 PM, Clint <rollin...@gmail.com> wrote:

For the TSP problem, I know we discussed that a DFS would be better than a BFS because we don't want to search the whole tree before finding a solution, but I can't remember what we concluded about the priority queue.  Is this usually or always preferable over DFS?  Would it be possible for the priority queue to act much like a BFS if the bounds of each state are arranged in a particular way?  Thanks

--
You received this message because you are subscribed to the Google Groups "BYU CS 312 Summer 2012" group.
To post to this group, send email to byu-cs-3...@googlegroups.com.
To unsubscribe from this group, send email to byu-cs-312-sum...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msg/byu-cs-312-summer/-/48knVHPdEXQJ.
For more options, visit https://groups.google.com/groups/opt_out.