Het ontwerpen van algoritmes

Algoritmen zijn de grondslag en het kader vormt van alle computerprogramma's. Zij zijn de volgorde van precieze instructies gegeven aan een computer voor het bereiken van een gewenste output. Algoritmen zijn computerprogramma's wat de geest is voor het menselijk lichaam. Veel algoritmische ontwerppatronen of paradigma's bestaan zoals greedy algoritmen, verdeel-en-heers algoritmen, dynamisch programmeren algoritmen en backtracking algoritmen. Elke klasse van algoritmen heeft zijn eigen unieke ontwerp-structuur.

Wat die u nodig hebt

• Papier
• Pen

• Potlood
• Gum

• Greedy algoritmen zijn algoritmen waarmee beslissingen op basis van de beschikbare informatie zonder een vooruitziende blik. Ze werken het beste in optimalisatieproblemen en eenvoudig te implementeren zijn. De algemene stappen voor hun ontwerp zijn:

  1. Een collectie (lijst, reeks, etc) van kandidaten (C) maken

  2. Vind een Subset (S) uit de collectie van candidates(C)

  3. Geef de criteria waaraan S moet voldoen.

  4. Als het voldoet aan die criteria (haalbaar), ga je gang tot S optimaliseren

  5. Optimaliseren S betekent selecteren te minimaliseren of maximaliseren, afhankelijk van het specifieke probleem. Daarbij kunnen we de grootste of kleinste oplossing selecteren.

• Verdeel-en-heers algoritmen volgen een top-down-benadering in algoritme ontwerp. Ze sub verdeelt het probleem in kleinere problemen en tenslotte Monteer de oplossingen voor de problemen van de component. De algemene stappen voor hun ontwerp zijn:

  1. Definieer het probleem

  2. Een exemplaar maken van het probleem

  3. Casu verdelen in kleinere sub exemplaren van het zelfde probleem

  4. Elk van de sub instanties op eigen oplossen

  5. Integreren en de oplossingen van de sub exemplaren teneinde een oplossing voor het oorspronkelijke exemplaar te combineren.

• Dynamische programmering algoritmen zijn een variant van het verdeel-en-heers algoritme. Terwijl de verdeel-en-heers algoritmen die recursieve een top-down-benadering volgen voor het oplossen van optimalisatieproblemen, volgt dynamisch programmeren een bottom-up techniek. De algemene stappen voor hun ontwerp zijn:

  1. Definieer het probleem

  2. Instanties maken van het probleem

  3. Bouwen van een lijst met alle sub exemplaren

  4. Beginnen met de kleinste sub exemplaren

  5. Ga verder met het vergroten van sub aanleg toe te voegen resultaten van posten al berekend

  6. Zich blijven ontwikkelen tot het laatste sub aanleg. De uiteindelijke verkregen oplossing is de oplossing voor het probleem in eerste instantie gedefinieerd.

  Deze methode is iteratieve terwijl de verdeel-en-heers-benadering recursief is.

• De backtracking algoritme wordt systematisch gezocht naar een oplossing van beschikbare opties, in de veronderstelling dat er een oplossing bestaat. De algemene stappen voor hun ontwerp zijn:

  1. Beginnen met een lege vector

  2. Laat de oplossing worden vertegenwoordigd door vectoren (Vi... VM)

  3. Traverse van de vectoren, uitbreiding van de gedeeltelijke vectoren met een nieuwe waarde

  4. Als een vector een deeloplossing vertegenwoordigen kan Backtrack

  5. De afsluitende waarde verwijderen uit de vector

  6. Gaat u verder met het uitbreiden van de vector met alternatieve waarden

  7. Herhaal de procedure totdat een oplossing wordt gevonden.

• Proberen te vinden van het type algoritme dat best uw probleem oplost voordat u algoritme ontwerp begint.

• Algoritme ontwerp is verslavend maar een mooie ervaring. Begin niet hebt u andere urgente dingen te doen snel.