[Module9 Theory] Black-Box Search Search

עליך להדביק את הפקודה הזאת במסוף שלך:

הסיסמה להתחברות אל

נא לענות על כל השאלות. שגיאה פנימית ל־{} אין סיומת תקפה. {} כבדה מדי.

שאלה 1: Conflict-Ordering Search

Consider seven variables X, Y, Z, A, B, C, D such that:

X, Y, Z have the domain \(\{0, 1\}\) and there are no constraints on these variables.
A, B, C, D have the domain \(\{0, 1, 2\}\) and there is a single constraint: A, B, C, D are all different, implemented using forward checking.

Consider a conflict-ordering search that, by default, considers the variables in the order given above (first X, then Y, ...) and, given a selected variable V, always tries Equal(V, V.min()) on the left branch and NotEqual(V, V.min()) on the right branch.

There are no solutions. How many nodes will be visited by the solver?

Hint: Draw the tree.

שאלה 2: Last-Conflict Search and Conflict-Ordering Search

Select all the true statements:

Conflict-ordering search always generates a strictly smaller search tree than last-conflict search.

In conflict-ordering search, once all the variables have been branched on at least once, the fall-back heuristic will never be used again.

Last-conflict search and conflict-ordering search are value selection heuristics.

In last-conflict search, once all the variables have been branched on at least once, the fall-back heuristic will never be used again.

Last-conflict search and conflict-ordering search can be used with a fall-back heuristic such as Min-Dom.

שאלה 3: First-Fail Principle

Select all variable selection heuristics that are not in the spirit of the first-fail principle:

Select an unfixed variable involved in the largest number of constraints.

Select an unfixed variable involved in the smallest number of constraints.

Select an unfixed variable with the largest domain size.

Select an unfixed variable with the smallest domain size.

Select a value that has the smallest lower-bound propagation impact.

Select a random unfixed variable.

Select an unfixed variable having the lowest propagation activity.

שאלה 4: Search-Tree Size

Consider a model with 10 decision variables X1, X2, ..., X10 and the AllDifferent([X1,X2,...,X10]) constraint. Select all the true statements:

If the variable selection heuristic is static (it selects the leftmost unfixed variable in [X1,X2,...,X10]) and the value selection heuristic is also static (it selects the minimum value of the selected variable on the left branch and removes it on the right branch), then by switching from a forward-checking filtering for AllDifferent to a domain-consistent filtering the number of nodes explored can increase, when searching for the first feasible solution (although it is unlikely with a stronger filtering).

If the variable selection heuristic is a dynamic first-fail Min-Dom but the value selection heuristic is static (it selects the minimum value of the selected variable on the left branch and removes it on the right branch), then by switching from a forward-checking filtering for AllDifferent to a domain-consistent filtering the number of nodes explored can increase, when searching for all the solutions (although it is unlikely with a stronger filtering).

If the variable selection heuristic is a dynamic first-fail Min-Dom but the value selection heuristic is static (it selects the minimum value of the selected variable on the left branch and removes it on the right branch), then by switching from a forward-checking filtering for AllDifferent to a domain-consistent filtering the number of nodes explored never increases, when exploring the complete search tree.

If the variable selection heuristic is static (it selects the leftmost unfixed variable in [X1,X2,...,X10]) and the value selection heuristic is also static (it selects the minimum value of the selected variable on the left branch and removes it on the right branch), then by switching from a forward-checking filtering for AllDifferent to a domain-consistent filtering the number of nodes explored can increase, when searching for all the solutions (although it is unlikely with a stronger filtering).

If the variable selection heuristic is static (it selects the leftmost unfixed variable in [X1,X2,...,X10]) and the value selection heuristic is also static (it selects the minimum value of the selected variable on the left branch and removes it on the right branch), then by switching from a forward-checking filtering for AllDifferent to a domain-consistent filtering the number of nodes explored never increases, when searching for the first feasible solution.

If the variable selection heuristic is static (it selects the leftmost unfixed variable in [X1,X2,...,X10]) and the value selection heuristic is also static (it selects the minimum value of the selected variable on the left branch and removes it on the right branch), then by switching from a forward-checking filtering for AllDifferent to a domain-consistent filtering the number of nodes explored never increases, when exploring the complete search tree.

שאלה 5: Value Selection Heuristics

Select all the true statements:

The value selection heuristic is not important for satisfaction problems.

Once the variable to branch on has been selected, it is important to select as value for the leftmost branch one that has the highest chance to lead to failure, in the spirit of the first-fail principle.

The value selection heuristic should mimic a greedy algorithm in order to find good solutions early.

Phase saving is a learning scheme for the value selection heuristic that tries first the last value that was tried without failing.

Once the variable to branch on has been selected, it is important to select as value for the leftmost branch one that has the highest chance to lead to success.

Selecting a value that has the least impact on the objective bound should lead to a good first solution.

מועד הגשה	אין מועד הגשה
מגבלת הגשות	אין הגבלה

מידע

כניסה