Tip:
Highlight text to annotate it
X
Со оглед на неоптималноста на depth-first search
зошто некој би одбрал да го користи?
Одговорот има врска со побарувањата за негово складирање.
Тука имам илустрирано простор на состојба
кој се состои од многу големо, па дури и бесконечно бинарно дрво.
Како што одиме до ниво 1, 2, 3, се до ниво n,
дрвото станува поголемо и поголемо.
Сега, да ја земеме во предвид границата за секој од овие алгоритми за пребарување.
За breadth-first search, знаеме дека границата изгледа така,
па кога ќе се спуштиме до ниво n, ќе ни треба простор од
2 на н-та за поминување на breadth-first search.
За cheapest first, границата ќе биде покомплицирана.
Ќе ја изработи оваа контура на цена,
но ќе има сличен вкупен број на јазли.
Но за depth-first search, како што одиме надолу по дрвото, почнуваме од оваа гранка,
па одиме нагоре, но во секоја точка, нашата граница ќе има само n јазли
наместо 2 на н-та, па така се добиваат значителни заштеди.
Се разбира, ако продолжиме да го следиме истражениот сет,
тогаш заштедата и не е толку голема.
Но без истражениот сет, depth-first search има огромна предност
во однос на просторот кој ќе се заштеди.
Уште едно својтво на алгоритмите кое се зема во предвид
е својството на комплетноста, што начи дека ако некаде има цел,
дали алгоритмот ќе ја најде?
Па, да се префрлиме од големи дрва на бесконечни дрва
и да кажеме дека има некоја цел скриена некаде длабоко во тоа дрво
И прашањето е, дали секој од овие алгоритми е целосен?
Тоа значи, далитие гарантирано че најдат патека до целта?
Чекирајте ги алгоритмите за кои што сметате дека се целосни во оваа смисла.