Hvordan Reverse grådig algoritme

Omvendt grådig algoritme - også kjent som Rgreedy algoritmer - er ikke "omvendt" av grådige algoritmer. De er også grådig algoritme, men de virker i motsatt retning. Vanligvis er en Rgreedy algoritme løser et problem i den motsatte retning, eller bruker en motsatt løsning enn den klassiske grådig algoritmen løsning. En grådig algoritme er en som tar det som ser ut som den mest fordelaktige skritt på hvert punkt i en prosess. Grådige algoritmer ikke alltid fungerer, men de er nesten alltid den enkleste måten å skrive en algoritme.

Bruksanvisning

1 Start med den grådige algoritmen. Dersom det ikke finnes noen standard grådig algoritme løsning på et problem, problemet med å finne den omvendte algoritmen er et åpent spørsmål. Du kan ikke finne det motsatte av den typiske måten å gjøre noe hvis det ikke er noen typisk måte. Et godt eksempel på en grådig algoritme er "minimum spenntre for en graf" problem. En kurve som er et sett av punkter forbundet med linjer, hvor linjene som er merket med tall. Den minste spenntre er en tilkoblet sett av linjer som forbinder alle punkter.

2 Se etter prosedyren i grådig algoritme som kan reverseres. Vanligvis vil det være prosessen som styrer algoritmen; prosessen som, når utslitt, bevirker at algoritmen for å stoppe. Den klassiske grådig algoritme for å finne det minimale spenntreet er å starte med poeng og ingen forbindelseslinjer. På hvert trinn, legg den minste linjen mellom to punkter. Fortsett prosessen til alle punktene er tilkoblet.

3 Finn noe å reversere hvis du ønsker å bygge en Rgreedy algoritme. Den Rgreedy algoritme for å finne minimum spenntre starter med kartet og alle linjene. På hvert trinn fjerne linjen med den største label som vil forlate punktene tilkoblet. Fortsett denne prosessen til det ikke flere linjer kan fjernes.

4 Sjekk Rgreedy algoritmen for å sørge for at det løser problemet. Det er ikke egentlig en algoritme hvis det ikke løser problemet. Noen ganger snu en kontrollerende prosess kan innføre en situasjon der algoritmen ikke ta opp alle elementer av problemet eller ikke avslutte algoritmen riktig. .

Hint

• I det minste spenntre problem, hvis punktene er byene, kan etikettene være avstandene mellom byene. Hvis punktene representerer transformatorstasjoner for et kabelselskap, kan etikettene være kostnaden for å legge en kabel mellom to transformatorstasjoner. Den minimale spenntreet er et sett med ledninger som er koblet til hverandre og som kobler alle punktene. Begge algoritmer er grådige, men den grådige algoritmen legger linjer og Rgreedy algoritmen trekker linjer.
• Ikke alle grådige algoritmer har en Rgreedy kontrapunkt. Selv om den gjør det, er det ingen grunn til å mistenke at det vil fungere bedre enn den grådige algoritmen. Noen problemer er ikke løsbar ved grådig algoritme. For eksempel å løse Rubiks kube med en grådig algoritme som alltid velger den farten som øker antallet riktige fargene - eller reduserer antall feil farger - er dømt til å mislykkes. Enkelte problemer krever mer globale løsninger.