Recursiunea în Delphi: căutarea căii
Mecanismul recursivității este foarte eficient atunci când se programează sarcini de căutare. Ca un alt exemplu, ia în considerare problema găsirii unei căi între două orașe. Dacă mai multe orașe sunt conectate prin intermediul drumurilor, este evident că este posibil să ajungeți dintr-un oraș în altul prin diferite căi. Sarcina este de a găsi toate căile posibile.
Hărțile de drumuri între orașe pot fi reprezentate sub formă de grafic - un set de vârfuri, adică orașe, și muchii care denotă drumuri (Figura 12.9).
Fig. 12,9. Reprezentarea unei foi de parcurs sub forma unui grafic
Procesul de căutare poate fi reprezentat ca o secvență de pași. La fiecare pas, folosind un anumit criteriu, este selectat un punct care poate fi accesat de cel actual. Dacă următorul punct selectat coincide cu punctul final specificat, traseul este găsit. Dacă nu, atunci facem un alt pas din acest punct. Deoarece punctul actual poate fi conectat cu mai multe altele, este nevoie de un anumit tip de criteriu de selecție formală. În cel mai simplu caz, puteți selecta punctul cu cel mai mic număr.
De exemplu, hai să găsim toate căile posibile de la punctul 1 la punctul 5. Conform regulii acceptate, vom selecta mai întâi punctul 2. În pasul următor, vom afla că punctul 2 este mort-end, așa că revenim la punctul 1 și facem un pas către punctul 3. Din punctul 3 - la punctul 4, de la 4 la 6 și de la punctul 6 la punctul 5. Se găsește o rută. După aceea, revenim la punctul 6 și verificăm dacă este posibil un pas în alt punct decât 5. Deoarece acest lucru este posibil, facem un pas spre punctul 7 și apoi - la 5. Se găsește încă o cale. Astfel, procesul de căutare constă în pași înainte și înapoi. Căutarea se termină dacă nu există unde să meargă de la nodul de pornire.
Algoritmul de căutare are un caracter recursiv: pentru a face un pas, vom selecta un punct și, din nou, vom face un pas și vom continua până vom ajunge la obiectiv.
Astfel, sarcina de a găsi o rută poate fi considerată drept o sarcină de a selecta punctul următor (oraș) și de a căuta restul traseului, adică există o recursiune.
Graficul poate fi reprezentat de o matrice bidimensională, pe care o numim tar (map). Valoarea elementului hărții [i, j] este distanța dintre orașele i și j, dacă orașele sunt conectate printr-un drum sau zero, în cazul în care orașele nu sunt conectate printr-un drum drept. Pentru graficul dat, matricea de gudron poate fi reprezentată sub forma unei tabele, prezentată în Fig. 12.10.
Fig. 12.10. Gamă de gudron
Conținutul celulei de tabelă de la intersecția rândului i și coloanei j corespunde valorii hărții [i, j].
În plus față de gama de gudron, avem nevoie de un șir de drum (rutier) și de o gamă inclusă (include). Pe drum, vom înregistra numerele orașelor pe care le-am trecut. În momentul atingerii punctului final, acesta va conține numărul tuturor punctelor traversate, adică descrierea rutei.
Inclus vom scrie adevărat dacă punctul cu numărul i este inclus în traseu. Acest lucru este făcut pentru a nu include în traseu a trecut deja punctul (nu umbla într-un cerc).
Deoarece folosim o procedură recursivă, trebuie să acordăm o atenție deosebită condiției pentru finalizarea procesului recursiv. Procedura ar trebui să înceteze să se mai numească dacă punctul curent a coincis cu punctul final specificat.
În Fig. 12.11 este o diagramă a algoritmului de procedură pentru selectarea următorului punct al rutei formate, iar caseta de dialog este prezentată în Fig. 12.12.
Pentru a introduce o matrice reprezentând descrierea hărții, utilizați componenta stringGridl (proprietățile sale sunt listate în Tabelul 12.1), iar câmpul etichetei Label1 este utilizat pentru a afișa rezultatul (ruta căutată). Punctele de început și de sfârșit ale rutei sunt specificate prin introducerea valorilor în câmpurile de editare Edit1 și Edit2. Procedura de căutare este pornită făcând clic pe butonul Căutare (Buton1). Câmpurile de etichete Label2, Label3 și Label4 sunt utilizate pentru a scoate text explicativ.
Fig. 12.11. Diagrama bloc a procedurii de selectare a punctului de traseu
Fig. 12.12. Fereastră de program Căutarea căutării
Tabelul 12.1. Valorile proprietăților componentei stringGrid1
Listing 12.5. Căutarea căutării
Trimiteți-le prietenilor: