Fwd: Re: TSP implementation question

[Christopher Tensmeyer]

---------- Forwarded message ----------
From: <Rollin...@gmail.com>
Date: Wed, Aug 1, 2012 at 11:22 PM
Subject: Re: Re: TSP implementation question
To: Christopher Tensmeyer <christophe...@gmail.com>


That's interesting. I'd probably have to talk to you in person if I really wanted to understand. So if I'm still deciding on Friday, I'll come talk to you! Thanks for your help, and sure you can post it in google groups.

On , Christopher Tensmeyer <christophe...@gmail.com> wrote:
> The vanilla strategy is to have some kind of priority queue agenda that holds a variable number of partial solutions and when a new bssf is found, the agenda is searched and known sub optimal partial solutions are removed.  Those removed are the ones that count as being pruned.
>
>
> I implemented a DFS as my state-expansion strategy.  My agenda therefore contained one partial state at a time, and did not prune any of those states because I explored them.  By implicitly pruning, I mean that there were branches in the DFS that I skipped based on my bounding function.  Depending on the problem, there were >2^64 possible branches of computation.  On a certain 20 city problem, I actually got through the entire search tree, examining directly several million partial states, leaving about (20! - several million) states that I implicitly pruned.
>
>
> Bottom line, implicit pruning does not count as pruning according to reporting.  So I reported my max size as 1 and states pruned as 0.  As for conditionally handling pruning, if that is not possible to do because of the design of your agenda, so be it.  If you have a variable length agenda, then you can do that.
>
>
> Chris
>
> PS, do I have your permission to post your question and the response to the google group?
>
> On Wed, Aug 1, 2012 at 4:15 PM, Clint Rollins rollin...@gmail.com> wrote:
>
> Hi Chris,
>
> I'm still trying to figure out how to do my state-expansion strategy, and I was curious about what you said about how you did implicit or no cost pruning.  One of the spec requirements says:
>
>
> Your solver must include a mechanism for managing the agenda to
> conditionally (under your control) prune the agenda during execution.
> You will also need a way to report the maximum size of your agenda and
> the number of states that were pruned during the search to collect data
> for the report.
>
> Will implicit pruning comply with this requirement.  Also, if you did implicit pruning, how would you be able to not prune your tree?  We need to show results of both pruning and not pruning.
>
>
>
> Thanks,
>
> Clint
>
>
>
>
>

[Nick Wilson]

Hi Chris,

How, with your DFS implementation, do you manage to store only one partial solution at a time? In another thread, you say, " If you have a pure DFS for your state-expansion strategy, then your agenda works like a stack, holding at most n partial solutions, the current state you are examining, and all ancestor states."

I'm just curious.

-Nick Wilson

--
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.
For more options, visit https://groups.google.com/groups/opt_out.
 
 

[Christopher Tensmeyer]

I forgot to make that correction.  You are right, in theory I stored up to n partial states in a stack like structure.  Because I store the incremental differences between parent and child partial states, it can be viewed as holding a single complete partial state (an oxymoron), or as holding the ability to recreate up to n partial states.

Chris