Ebben az oktatóanyagban megtudhatja, mi az a visszalépés algoritmus. Ezenkívül talál egy példát egy visszalépés megközelítésre.
A visszalépés algoritmus olyan problémamegoldó algoritmus, amely durva erő megközelítést alkalmaz a kívánt kimenet megtalálásához.
A nyers erő megközelítés kipróbálja az összes lehetséges megoldást, és kiválasztja a kívánt / legjobb megoldásokat.
A visszalépés kifejezés arra utal, hogy ha a jelenlegi megoldás nem megfelelő, akkor visszalép, és próbáljon ki más megoldásokat. Így ebben a megközelítésben rekurziót alkalmaznak.
Ezt a megközelítést olyan problémák megoldására használják, amelyek többféle megoldással rendelkeznek. Ha optimális megoldást szeretne, akkor dinamikus programozást kell folytatnia.
Állami űrfa
Az űrállapot fa egy fa, amely a probléma összes lehetséges állapotát (megoldását vagy feloldását) képviseli a gyökértől kezdeti állapotként a levélig, mint terminális állapotig.
Állami űrfa
Visszalépés algoritmus
Backtrack (x), ha az x nem megoldás, adja vissza a false értéket, ha x új megoldás, adja hozzá a megoldások listájához
Példa visszalépés megközelítésre
Probléma: Meg akarja találni az összes lehetséges módot 2 fiú és 1 lány 3 padon való elrendezésére. Megkötés: A lány nem lehet a középső padon.
Megoldás: Összesen 3 van! = 6 lehetőség. Kipróbáljuk az összes lehetőséget és megkapjuk a lehetséges megoldásokat. Rekurzívan kipróbáljuk az összes lehetőséget.
Minden lehetőség a következő:
Minden lehetőség
A következő állapottérfa bemutatja a lehetséges megoldásokat.
Állapotfa az összes megoldással
Visszalépés algoritmus alkalmazások
- Megtalálni az összes hamiltoni utat egy grafikonon.
- Az N királynő problémájának megoldása.
- Labirintus megoldási probléma.
- A Lovag turnéproblémája.
