Tip:
Highlight text to annotate it
X
Så har vi tittat på 2 sökalgoritmer.
Ett, bredd-först sökning, där vi alltid börjar med att expandera
de grundaste vägarna, de kortaste vägarna.
För det andra, billigast-först sökning, där vi alltid expanderar den första vägen
med den lägsta totalkostnaden.
Och jag ska passa på att införa en tredje algoritm, djup-först-sökning,
som på sätt och vis är motsatsen till bredd-först-sökning.
I djup-först sökning, som alltid, expandera den längsta vägen,
den med flest längder på.
Nu, vad jag vill be dig göra är att för var och en av dessa noder i varje träd,
berätta i vilken ordning de har expanderat,
första, andra, tredje, fjärde, femte och så vidare genom att sätta ett nummer i rutan.
Och om några har samma värde, rangordna dem från vänster till höger.
Och jag vill att du ska ställa en fråga eller besvara ännu en fråga:
är dessa sökningar optimala?
Alltså, finner de garanterat den bästa lösningen?
Och för bredd-först-sökning, skulle optimalt innebära att man hittar den kortaste vägen.
Om du tycker det är garanterat att hitta den kortaste vägen, markera här.
För billigast först, skulle det innebära att man hittar vägen med den lägsta ackumulerade kostnaden.
Markera här om du tycker att det är garanterat att göra det.
Och vi gör antagandet att alla kostnader måste vara positiva.
Och för djup-först, skulle billigast, eller optimal, innebära, precis som
i bredd-först-sökning, att hitta kortast möjliga väg i termer av antal längder.
Markera här om du tror att djup-först-sökning alltid kommer att finna det.