

![0_image_0.png](0_image_0.png)

define a problem domain  In a scheduling domain  for example  those elements might be tasks In graph coloring those elements might be the nodes to be colored The three main components of SWO are Constructor.  Given a sequence of problem elements  the constructor generates a solution using a greedy algorithm  with no backtracking   The sequence determines the order in which decisions are made and can be thought of as a strategy" or recipe" for constructing a new solution This solution" may violate hard constraints

Analyzer. The analyzer assigns a numeric  blame" factor to the problem elements that contribute to flaws in the current solution  For example  if minimizing lateness in a scheduling problem is one of the objectives  then blame would be assigned to late tasks
A key principle behind swo is that solutions can reveal problem structure  By ana lyzing a solution  we can often identify elements of that solution that work well  and elements that work poorly A resource that is used at full capacity for example may represent a bottleneck This information about problem structure is local in that it may only apply to the part of the search space currently under examination  but may be useful in determining where the search should go next

Prioritizer. The prioritizer uses the blame factors assigned by the analyzer to modify the previous sequence of problem elements  Elements that received blame are moved toward the front of the sequence The higher the blame the further the element is moved
The priority sequence plays a key role in SWO As a difficult problem element moves forward in the sequence it is handled sooner by the constructor It also tends to be handled better thus decreasing its blame factor Difficult elements rise rapidly to a place in the ssequence where they are handled well Once there the blame assigned to them drops causing them to slowly sink in the sequence as other parts of the problem that are not handled as well are given increased priority Eventually difficult elements sink back to the point where they are no longer handled well causing them to receive higher blame and to move forward in the sequence again Elements that are always easy to handle sink to the end of the sequence and stay there