INF în algoritmi: santinelă, distanță și overflow
Alege o valoare pentru stările inaccesibile fără să o confunzi cu un rezultat valid. Verifică adunările înainte de a actualiza distanțe sau costuri.
În acest material
În mulți algoritmi, INF este numele unei constante folosite pentru „încă inaccesibil” sau „nu există rezultat”. Este o santinelă, adică o valoare specială cu sens convenit de program. Nu este infinitul matematic și nu suportă automat aceleași operații.
Separă valorile valide de absență
Dacă toate costurile valide sunt între 0 și 1000000, poți alege o santinelă mai mare, cu condiția să încapă în tipul folosit și să fie sigură în operațiile efectuate. Limita trebuie dedusă din datele problemei, nu copiată dintr-un alt program.
Dacă un rezultat valid poate fi egal cu santinela, programul nu mai distinge acel rezultat de absență. O alternativă este păstrarea separată a unui indicator care spune dacă starea este accesibilă. Alegerea depinde de simplitatea și limitele modelului.
Nu aduna dintr-o stare inaccesibilă
La actualizarea unui cost, verifică întâi dacă starea sursă este accesibilă. Numai apoi calculezi costul sursei plus costul tranziției. Adunarea INF cu o valoare poate depăși tipul sau poate produce o valoare care este interpretată greșit.
Chiar și două costuri finite pot avea o sumă prea mare. Alegerea lui long long nu înlocuiește estimarea limitei superioare. Dacă nu poți demonstra că adunarea încape, ai nevoie de o verificare explicită înainte de operație.
O stare inaccesibilă nu trebuie folosită ca sursă pentru adunarea unui cost. Verificăm accesibilitatea înainte de tranziție și limita sumei înainte de calcul.Mărește schema ↗
Inițializarea trebuie să reflecte sensul problemei
Pentru distanțe minime, starea de pornire are cost zero, iar stările necunoscute sunt marcate inaccesibile. Inițializarea tuturor cu zero ar afirma că toate sunt deja accesibile gratuit. Aceasta este o eroare de model, nu doar de valoare inițială.
La maximizare, sensul santinelei poate fi invers: o valoare suficient de mică reprezintă o stare imposibilă. Nu reutiliza mecanic aceeași inițializare între minimizare și maximizare.
Testul fără soluție este obligatoriu
Construiește o intrare în care destinația nu poate fi atinsă. Verifică faptul că programul afișează exact mesajul sau valoarea cerută de enunț, nu constanta internă. Testează separat un rezultat valid zero și unul apropiat de limita maximă.
Scrie într-un comentariu de ce santinela nu se confundă cu un rezultat valid. Acea justificare este mai utilă decât un număr foarte mare fără explicație.
Continuă cu drumurile minime, programarea dinamică și tipurile numerice.
Întrebări frecvente
Ce reprezintă INF într-un algoritm de distanțe?
De obicei, este o santinelă numerică pentru o stare încă inaccesibilă. Nu este infinitul matematic: rămâne o valoare a tipului și poate produce overflow în operații.
Cum aleg o valoare sigură pentru INF?
Dedu o limită superioară pentru orice rezultat valid și alege o valoare distinctă, reprezentabilă. Verifică și expresiile în care apare, nu doar valoarea stocată inițial.
Pot aduna direct un cost la o distanță egală cu INF?
Nu fără o verificare. Mai întâi confirmă că starea este accesibilă, apoi că suma încape în tip. Altfel poți transforma o stare imposibilă într-o valoare aparent validă.