Omezení narušující symetrii - Symmetry-breaking constraints

V oblasti matematiky tzv kombinatorická optimalizace, metoda omezení narušující symetrii lze využít k využití symetrie v mnoha omezení spokojenosti a optimalizační problémy přidáním omezení, která vylučují symetrie a zmenšují velikost vyhledávacího prostoru.

Symetrie v kombinatorickém problému zvětšují velikost vyhledávacího prostoru, a proto se čas ztrácí při návštěvě nových řešení, která jsou symetrická s již navštívenými řešeními. Čas řešení kombinatorického problému lze zkrátit přidáním nových omezení, která se označují jako omezení symetrie, takže některá symetrická řešení jsou z vyhledávacího prostoru vyloučena při zachování existence alespoň jednoho řešení.[1][2]

Symetrie je běžná v mnoha kombinačních problémech v reálném životě. Například některá vozidla v problém s směrováním vozidla mohou být identické. U platného plánu směrování získá každá permutace takových identických vozidel jiný platný plán směrování se stejnou hodnotou objektivní funkce.

Reference

  1. ^ „Publikované klíčové výzkumné práce na téma Symetry Breaking Constraints“. Citovat deník vyžaduje | deník = (Pomoc)
  2. ^ Walsh, Toby (2006). Obecná omezení symetrie. Principy a praxe programování omezení - CP. Přednášky z informatiky. Springer Berlin Heidelberg. 650–664. CiteSeerX  10.1.1.131.2959. doi:10.1007/11889205_46. ISBN  978-3-540-46267-5.