Unit 2, Topic 4, Tree Search knowitvideos Norwegian English

Unit 2, Topic 4, Tree SearchYouTube↗ IA↗(long shot)
Howto & Style 43.7K views 29 likes 11 dislikes 05 Oct 2011

knowitvideos 11.8K subscribers N/A YouTube↗

Click to Play Video

La oss nå definere en funksjon for å løse problemer.

[Narrator] Now let's define a function for solving problems.

Den kalles et søketre fordi den legger et

It's called Tree Search because it superimposes

søketre over tilstandsrommet.

a search tree over the state space.

Her er hvordan den virker. Den starter med å

Here's how it works: It starts off by

initialisere grensen til å være ruten

initializing the frontier to be the path

bestående av bare initialtilstandene

consisting of only the initial states,

og går deretter inn i en loop

and then it goes into a loop

der den først sjekker om

in which it first checks to see

vi ennå noe igjen i grensen.

do we still have anything left in the frontier?

Hvis nei har vi mislykkes, det finnes ingen løsning.

If not we fail, there can be no solution.

Hvis vi har noe igjen, så kan vi gjøre et valg.

If we do have something, then we make a choice.

Søketre er egentlig en familie av funksjoner

Tree Search is really a family of functions

ikke en enkelt algoritme som

not a single algorithm which

avhanger av hvordan vi gjør det valget,

depends on how we make that choice,

og vi skal se på noen av alternativene senere.

and we'll see some of the options later.

Hvis vi går i gang og gjør et valg ut av en av

If we go ahead and make a choice of one of

rutene på grensen og fjerner

the paths on the frontier and remove that

den ruten fra grensen, finner vi tilstanden

path from the frontier, we find the state

som er ved rutens ende, og hvis den

which is at the end of the path, and if that

tilstanden er riktid, så er vi framme.

state's a go then we're done.

Vi har funnet en rute til målet; ellers

We found a path to the goal; otherwise,

vil vi gjøre det som kalles å bygge på den ruten.

we do what's called expanding that path.

Vi ser på valgene fra den tilstanden

We look at all the actions from that state,

og vi legger dem til ruten

and we add to the path the actions

og resultatet av den tilstanden; så vi får

and the result of that state; so we get

en ny rute som har den gamle ruten, valget

a new path that has the old path, the action

og resultaten av det valget, og vi

and the result of that action, and we

plasserer alle disse rutene tilbake på grensen.

stick all of those paths back onto the frontier.

Nå representerer Søketreet en hel familie

Now Tree Search represents a whole family

av algoritmer, og hvor du finner familielikheten

of algorithms, and where you get the family

er at de alle ser på

resemblance is that they're all looking

grensen, kopierer deler fra den og

at the frontier, copying items off and

ser på de respektive måltester,

and looking to see if their goal tests,

men der du finner ulikhetene er rett her

but where you get the difference is right here,

i valget om hvordan du skal utvide

in the choice of how you're going to expand

det neste punktet på grensen, hvilken

the next item on the frontier, which

rute vi ser på først, og vi skal gå gjennom

path do we look at first, and we'll go through

forskjellige sett med algoritmer som gir

different sets of algorithms that make

forskjellige valg for hvilke ruter vi ser på først.

different choices for which path to look at first.

Den første algoritmen jeg vil se på

The first algorithm I want to consider

er kalt Bredde Først Søk.

is called Breadth-First Search.

Vi kunne ha kalt den korteste-først søk

Now it could be called shortest-first search

fordi det er det den alltid velger

because what it does is always choose

fra grensen der en av rutene ikke har vært

of the frontier one of the paths that hadn't been

valgt ennå, selv om det er den kortest mulige.

considered yet that's the shortest possible.

Så hvordan virker den?

So how does it work?

Vel, vi starter med en rute med

Well we start off with the path of

lengde 0, fra initialtilstanden, og

length 0, starting in the start state, and

der det er den eneste ruten i grensen slik at

that's the only path in the frontier so

det er den korteste, ergo velger vi den,

it's the shortest one so we pick it,

og når vi utvider den, og legger til

and then we expand it, and we add in

alle rutene som resulterer fra

all the paths that result from

å gjennomføre alle mulige valg.

applying all the possible actions.

Så nå har vi fjernet

So now we've removed

renne ruten fra grensen,

this path from the frontier,

men vi har lagt til 3 nye ruter.

but we've added in 3 new paths.

denne og denne.

this one, and this one.

Nå er vi i en posisjon der

Now we're in a position where

vi har 3 ruter på grensen, og

we have 3 paths on the frontier, and

der vi må velge den korteste.

we have to pick the shortest one.

I dette tilfellet er alle 3 rutene

Now in this case all 3 paths

av samme lengde = 1, så vi

have the same length, length 1, so we

velger tilfeldig eller bruker en

break the tie at random or using some

annen teknikk, og la oss anta at

other technique, and let's suppose that

i dette tilfellet velger vi denne ruten

in this case we choose this path

fra Arad til Sibiu.

from Arad to Sibiu.

Nå er spørsmålet jeg vil at du skal besvare

Now the question I want you to answer

at når vi fjerner denne fra grensen,

is once we remove that from the frontier,

hvilke ruter kan vi legge til etterpå?

what paths are we going to add next?

Vis meg gjennom å merke de byene

So show me by checking off the cities

som avslutter rutene, hvilke ruter

that ends the paths, which paths

skal da legges til grensen?

are going to be added to the frontier?

Similar videos:

Qué son los SWAPS
canaloie24
55.4K views 259 likes 4 dislikes 24 Nov 2011100% match

CEOS Chatter
Fernando Garcia
1.3K views 2 likes 1 dislikes 14 Mar 2012100% match

Mr. Peabody & Sherman
TheCaptionedInternet
43.6K views 74 likes 9 dislikes 03 Mar 2014100% match

Instrucciones para llorar, de Julio Cortázar
Inés Andrés
5.9K views 10 likes 0 dislikes 10 Jan 2012100% match

Recomendación kuentalibros - pizarra digital y niños con discapacidad auditiva
anitamc20
933 views 1 likes 0 dislikes 21 Dec 2012100% match

(ENG/CHI SUB) 140216 SM True Thailand Facebook EXO
Baby Xiumin
783 views 10 likes 0 dislikes 16 Feb 2014100% match

[ENG SUB] 110811Mnet Wide Super Junior Interview Part 1/3
yingxuan0806
80.6K views 567 likes 7 dislikes 18 Sep 2011100% match

TED & TEDx explained
Kyo young Chu
1.1K views 7 likes 0 dislikes 02 Apr 2012100% match

Unit 2, Topic 23, A-Star Search

138K views 392 likes 60 dislikes 05 Oct 201171% match

YouTube CHANNEL MEMBERSHIP Shameless Self Promotion (part 2)
PooDot StinkPants
532 views 155 likes 2 dislikes 17 Mar 202063% match

🧢Cisterna🚽no carga agua💦( ARREGLALO TÚ )
That, Dad fix it
108.1K views 1.2K likes 93 dislikes 01 Mar 201963% match

"Цветущая веточка" из холодного фарфора
Юлия Машинская
1.2K views 98 likes 0 dislikes 25 Jan 202162% match

🧢Eliminar oxido de piezas de metal (NO TE LO IMAGINAS)
That, Dad fix it
483K views 9.6K likes 1.1K dislikes 15 Mar 202061% match

MKS Gen L - Optical Endstop
Ed's 3d Tech
8.1K views 107 likes 4 dislikes 12 May 201861% match

Göra vinter - Lär dig svenska
Learn Swedish with Marie!
6K views 441 likes 2 dislikes 18 Nov 202061% match

Linear Search
CS50
24.3K views 74 likes 4 dislikes 07 Oct 201561% match

Prebeardy (Official Music Video)
nigahiga
6M views 214.7K likes 1.9K dislikes 12 Nov 201661% match

#24 The Universe Is Basically Playful
Her 86m2
113.4K views 5.3K likes 81 dislikes 03 Dec 202061% match

Bois ceci et ton Vag@ sera très sucré et très bon!
L'ART DU TEINT PARFAIT,ELIXIR DEMARIE LEONIE COACH
134.2K views 0 likes 0 dislikes 02 Sep 201960% match

Intertool XT-9007 torque wrench how to use
Practice makes perfect
1K views 32 likes 0 dislikes 13 Dec 201960% match

comment toujours garder sa peau juste jeune et belle naturellement !
L'ART DU TEINT PARFAIT,ELIXIR DEMARIE LEONIE COACH
106.3K views 0 likes 0 dislikes 17 Aug 201960% match

Best budget gym gloves unboxing and review | kobo gym gloves review
Utopian Days
2.2K views 55 likes 6 dislikes 29 Oct 202060% match

POLPETTONE DI CARNE PER NATALE E CAPODANNO OTTIMO AL FORNO
Carlo Gaiano
905K views 21.6K likes -1 dislikes 10 Dec 201960% match

КЕТО РЕЦЕПТ, от которого вы обалдеете! ПЕЛЬМЕНИ по Итальянски | ТиЛи
Тикунова Лиза
1.2K views 130 likes 0 dislikes 19 Jan 202160% match

Sesi.13 - Cara Planting Moss Aquascape - Planted Aquascape - Bucephalandra - Moss Ricardia - Weeping
Queen Art Aquatic Design
12.2K views 0 likes 0 dislikes 16 Jan 202160% match

0 views 0 likes -1 dislikes 04 Jun 202660% match

Discover INDIA a Journey from the NORTH to the SOUTH (4K Video) Subtitles Available in 30 Languages
FairDinkum Adventure
21.6K views 143 likes 30 dislikes 25 Jul 202060% match

JUSTICE LEAGUE: "Batman's New Toy" Reveal Trailer (2017) Blockbuster Action Movie HD
MovieGasm‍․com
791.1K views 4.7K likes 359 dislikes 06 Oct 201760% match

Wrinkles on Nose Bridge I Best Skin Care, 2021 Challenge I Anti Aging, Face massage
Health City
5.2K views 264 likes 4 dislikes 22 Dec 202060% match

BMW M4 Competition, M440i, and M340i
Marlboro “Marlboro Car Videos” M2C
1.8K views 17 likes 3 dislikes 02 Dec 202060% match

Settings Privacy About Contact Donate