Solution Test

[Joshua Lepinski]

What is meant by solution test in the project 7 write up. I understand feasability test but since we are just generating all better solutions than bssf to get the best one. is there such a thing as a solution test?

[Joshua Lepinski]

I might also need some clarification on this " This does not include states pruned by comparison with the BSSF" when are we to prune if it's is a valid solution, and it's not compared to the BSSF?

[Paul Felt]

The solution test is how you know when you have a complete solution. This tells you WHEN you can update your BSSF. Obviously you aren't going to try to update your BSSF after adding only one edge. So when DO you update it? How do you know you have encountered a complete solution?

--Paul

On Aug 1, 2012, at 9:17 PM, Joshua Lepinski <joshual...@gmail.com> wrote:

What is meant by solution test in the project 7 write up. I understand feasability test but since we are just generating all better solutions than bssf to get the best one. is there such a thing as a solution test?

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

[Paul Felt]

Report "pruned states" as the number of states that you added to you agenda, then removed from the agenda later after updating your BSSF pruning the agenda. We've referred to this in class as "explicit pruning."

What you should NOT report are the number of states that you never added to the agenda in the first place, because when you considered adding them to the agenda they were not promising compared to the BSSF. We've referred to this in class as "implicit pruning."

--
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/-/dU6ZV6AZuTkJ.

[Joshua Lepinski]

I may not really see clearly what an agenda is because the way I've done it I only keep n items in at a time since I did a DFS and matrix aproach. in this case do I ever have an agenda?

[Joshua Lepinski]

I wouldn't think that I have one because I'm only ever going to have the path I'm going down and i'm never going to know if it's higher than my bssf without comparing them. So do I just put zero's on my pruned list?

[Christopher Tensmeyer]

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.  Should a computational path find a new bssf, then all states on the agenda are ancestor problems of that bssf and cannot be pruned.

Given the top partial solution on your stack, you may decide not to explore some of it's possible child states because of your bounding function and bssf.  That decision to not explore those computational sub-trees is what we mean by implicit pruning.  The number of such states is not reported.  If they were, they would need to be displayed in scientific notation for the largeness of them.  It is okay to report a 0 for number of pruned states if that is part of your strategy.

Chris

--
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.