Menu

Commit [282446]  Maximize  Restore  History

Course Timetabling: Limited-Depth Search (Suggestion Selection)

- when doing a limited-depth backtracking, but no suggestion is found
- only do a random assignment with >1 conflicts when Suggestion.AllowUnassignments is true (defaults to false)
- while this somewhat limits the Suggestion's ability to converge the search towards a complete solution, allowing unassignments (>1 conflicts) causes the Hill Climber to diverge from a local optima
- this is because the number of assigned variables is not included in the objective function that is being minimized
- other search algorithms (such as Great Deluge or Simulated Annealing) can also suffer from accepting a move that decreases the number of assigned variables, especially when it is not possible to find a complete solution eventually (i.e., no complete solution can be found)

tomas-muller tomas-muller 2024-11-08

changed src/org/cpsolver/coursett/neighbourhoods/Suggestion.java
src/org/cpsolver/coursett/neighbourhoods/Suggestion.java Diff Switch to side-by-side view
Loading...
Want the latest updates on software, tech news, and AI?
Get latest updates about software, tech news, and AI from SourceForge directly in your inbox once a month.