Tabu Search is a local search procedure with a concept of a tabu list to broaden exploration of the search space by blocking previous moves.
Worsening moves are also accepted if there is no better solution which helps with situations where algorithm gets stuck at a local minimum.
Thanks to these properties of the algorithm, it is a good fit for solving NP problems such as graph coloring.
- https://en.wikipedia.org/wiki/Tabu_search
- https://mat.gsia.cmu.edu/COLOR/instances.html - some instances in the project are included from here
- implemented in C# .NET 5.0