Rekurzió Delphi útkereső, Delphi, Delphi komponens Delphi forrás

Rekurzió Delphi: Megtalálni az utat

rekurzió mechanizmus nagyon hatásos, ha a programozás keresési probléma. Egy másik példa, úgy a problémát találni az utat a két város között. Ha több várost köti össze út, akkor nyilvánvaló, hogy eljutni egyik városból a másikba lehet a különböző útvonalakon. A feladat az, hogy megtalálja az összes lehetséges útvonalat.

Ütemterv a városok között is megjelenik, mint egy grafikont - a csúcsok halmaza, azaz város és élek jelölik utak (ábra 12.9.).

Ábra. 12.9. Képviselete az útitervet, mint egy grafikont

A keresési folyamat is képviselteti magát egy sor lépést. Minden lépésben segítségével néhány kiválasztott kritériumok pont, amely elérhető a jelenlegi. Ha a következő kiválasztott pont egybeesik egy előre meghatározott végpont, a útvonalat talál. Ha nem egyeznek meg, mi ezen a ponton még egy lépést. Mivel az aktuális pont lehet csatlakoztatni még sokan mások, szükségünk van valamilyen hivatalos kiválasztási szempont. A legegyszerűbb esetben ki lehet választani a pontot a legalacsonyabb szám.

Tegyük fel például, meg kell találni az összes lehetséges útvonalakat 1 pont 5. pont szerint elfogadott szabály, először válasszon egy pont 2. A következő lépésben azt találjuk, hogy a 2. pontban zsákutca, így megy vissza az 1. pontban, és egy lépést a 3. pont 3 pont - a 4. pontban, a 4 - 6 a 6 pont - a pont 5. egy útvonalat talál. Ezt követően, megyünk vissza a 6. pont, és ellenőrizze, hogy a lépés, hogy egy pont kivételével az esetleges 5. Mivel lehetséges, akkor egy lépést a 7. pontban, majd - a Yeshe 5. Találj másik utat. Így a keresési folyamat egy lépés előre, és visszafordult. Keresés befejeződött, ha az elején a szerelvény mozgása nincs hova mennie.

A keresési algoritmus rekurzív: egy lépést, akkor válassza ki a pontot, és egy lépést hátra, és így tovább addig, amíg el nem érjük a célt.

Így az útvonal keresési feladat lehet tekinteni, mint a feladat választás a következő pont (város) és keresni a többi útvonalon, azaz a. E. Van egy rekurziót.

Graph leírható kétdimenziós tömböt, vagy ahogy mi hívjuk a tar (térkép). Érték térkép tömb elemet [i, j] - közötti távolság városok i és j, ha a város csatlakozik út, vagy nulla, ha a város nem csatlakozik egy egyenes úton. A fenti grafikon tömb kátrány reprezentálható egy táblázatban ábrán látható. 12.10.

Ábra. 12.10. Egy sor tar

A tartalom a táblázatban cella i sorában és j oszlopában megfelel a térkép [i, j].

Amellett, hogy egy sor tar szükségünk van egy sor út (út) és egy sor együtt (az tartalmazza - többek között). Az út utaztunk rekordszámú városokban. Abban az időben a végpont fog tartalmazni több telt el pontot, azaz. E. út leírása.

Az együtt rögzíti igaz, ha a pont számát i szerepel az útvonal. Ez úgy történik, hogy az ne tartalmazza a útvonal szeli át egy pontot (ne járjatok körbe).

Mivel az általunk használt rekurzív eljárást, meg kell, hogy fordítsanak különös figyelmet a feltétele befejezése a rekurzív folyamat. Az eljárást meg kell szüntetnie hívja magát, ha az aktuális pont egybeesik az előre meghatározott végpontot.

Ábra. 12.11 tömbvázlatát mutatja a következő által kialakított útvonalon kiválasztási folyamat, és egy párbeszéd ablak - ábra. 12.12.

Ahhoz, hogy adja meg a tömb képviselő térkép leírását használt stringGridl komponens (az ingatlan táblázatban megadott 12,1), hogy az eredményt (útvonal találat) - Label1 címke mezőben. A kezdő- és végpontját az útvonal meghatározott értékek megadásával a szerkesztési Edit1i Edit2. keresési eljárás indul kattintson a Keresés gombra (Button1). Fields Label2 címke Label3 és Label4 megjelenítéséhez használt magyarázó szöveget.

Ábra. 12.11. Folyamatábra fordulópont kiválasztási eljárás

Ábra. 12.12. A program ablak Directions

12.1 táblázat. Ingatlan értékének stringGrid1 alkatrész

Listing 12.5. Útvonal