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 succesiune 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 constata 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ă. Apoi, revenim la punctul 6 și verificăm dacă este posibil un pas în alt punct. Deoarece acest lucru este posibil, facem un pas către punctul 7 și apoi la 5. Se găsește o altă 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ă ca o sarcină de a selecta punctul următor (oraș) și de a căuta restul traseului, adică există o recursivitate.
Graficul poate fi reprezentat de o matrice bidimensională, pe care o numim tar (map). Valoarea map element array [i, j] - este distanța între orașele i și j, în cazul în care orașul conectat drum, sau zero, în cazul în care orașul nu este conectat 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.
În cazul [i] 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 matrice reprezentand carduri de descriere utilizate componente stringGridl (valorile de proprietate prezentate în tabelul 12.1) la ieșire rezultat (traseul gasit) - eticheta câmpului Label 1. punctul de pornire și final al traseului stabilit introducând valori în câmpurile edit1 Edit2 și editare. Procedura de căutare este pornită făcând clic pe butonul Căutare (buton). 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
Articole similare
-
Începutul jocului, istoria wiki-ului, fandom alimentat de wikia
-
Legarea hărților, căi de istorie wiki, fandom alimentat de wikia
Trimiteți-le prietenilor: