Backtracking sökning

Backtracking search , backtracking är en  generell metod för att hitta lösningar på ett problem som kräver en fullständig uppräkning av alla möjliga alternativ i en viss uppsättning M. Som regel låter den dig lösa problem som ställer frågor som: ”Lista alla möjliga alternativ . ..” , ”Hur många sätt ...”, ”Finns det ett sätt ...”, ”Finns ett objekt ...”, etc.

Termen backtracking myntades 1950 av den amerikanske matematikern Derrick Henry Lehmer .

Mindre modifieringar av backtracking-metoden relaterade till datarepresentation eller implementeringsfunktioner har andra namn: branch and bound method , depth-first search , trial and error-metod etc. Backtracking-sökning uppfanns av många forskare nästan samtidigt och oberoende innan dess formella beskrivning.

Beskrivning av metoden

Lösningen av problemet genom metoden för backtracking reduceras till successiv expansion av en partiell lösning. Om i nästa steg en sådan expansion misslyckas, då återgår de till en kortare dellösning och fortsätter sökningen vidare. Denna algoritm låter dig hitta alla lösningar på problemet, om de finns. För att påskynda metoden försöker man organisera beräkningar på ett sådant sätt att man så tidigt som möjligt identifierar uppenbart olämpliga alternativ. Ofta kan detta avsevärt minska tiden för att hitta en lösning.

Med hjälp av

Ett klassiskt exempel på användningen av en bakåtspårningsalgoritm är problemet med åtta drottningar . Dess ordalydelse är som följer: "Arrangera 8 damer på ett standardschackbräde med 64 celler så att ingen av dem attackeras av någon annan." Först placeras en dam på brädet, och sedan försöker de placera varje nästa dam så att den inte blir slagen av de redan etablerade damerna. Om en sådan inställning inte kan göras i nästa steg, går de tillbaka ett steg och försöker placera den tidigare installerade drottningen på en annan plats.

Dessutom låter backtracking-metoden dig lösa många andra uppräkningsproblem. Om du till exempel använder den kan du få alla delmängder , placeringar , permutationer , kombinationer av en given uppsättning M.

Nackdelar

Backtracking-metoden är generisk. Det är ganska enkelt att designa och programmera algoritmer för att lösa problem med denna metod. Men tiden för att hitta en lösning kan vara mycket lång även med små dimensioner av problemet (mängden initiala data), och den är så lång (det kan vara år eller till och med århundraden) att det inte kan vara fråga om praktisk tillämpning . Därför, när man designar sådana algoritmer, är det nödvändigt att teoretiskt uppskatta tiden för deras arbete på specifika data. Det finns även urvalsproblem, för vilka du kan bygga unika, "snabba" algoritmer som gör att du snabbt kan få en lösning även med stora problemdimensioner. Backtracking-metoden är ineffektiv i sådana problem.

Se även

Länkar