Backtracking si Algoritmi de cautare (30, 31, 32, 34) (total 28) Flashcards
Cum se mai numeste metoda Backtracking?
metoda cautarii cu revenire, deoarece găsirea soluţiilor este rezultatului unui proces de căutare sistematică, cu încercari repetate şi reveniri în caz de nereuşită
Care este justificarea utilizării metodei Backtracking în contextul modularizării?
poate optimiza procesul de căutare, evitând căile care nu duc la o soluţie.
Care sunt câteva exemple de probleme rezolvate prin Backtracking?
- găsirea unei căi de ieşire dintr-un labirint;
- plasarea pe o tablă de şah a opt dame care nu se atacă între ele;
- găsirea unui traseu care acoperă tabla de şah, generat adoptând săritura calului fără a trece de două ori prin aceeaşi poziţie.
Ce este o regula euristica; justificati utilizarea acestei metode in cazul algoritmilor de cautare
O regulă euristică oferă o metodă de rezolvare a problemelor, sau o metodă de căutare. Nu este garantat ca gaseste cea mai buna solutie, dar poate reduce timpul de cautare.
Metodele de acest tip pot fi folosite pentru reducerea mărimii arborilor de căutare în cazurile arborilor foarte mari.
Câteva dintre avantajele strategiei de căutare înapoi
- atunci când sunt necesare sau când toate posibilităţile au fost explorate, sistemul recurge la întrebări adresate utilizatorului;
- arborele de căutare este adesea mai puţin adânc decât cel aferent strategiei de căutare înainte;
- procesul de raţionare este interactiv.
