A* (A Star) Search Algorithm - Computerphile Computerphile English Turkish

A* (A Star) Search Algorithm - ComputerphileYouTube↗ IA↗(long shot)
Education 864.5K views 17.4K likes 426 dislikes 15 Feb 2017 Show Contributors 2

Computerphile 2.6M subscribers N/A YouTube↗

Contributed subtitles

English B. Andrade

Click to Play Video

In the last video, if I remember

Son videoda hatırlarsam

correctly 'cause it was a good month ago now.

doğru çünkü şimdi iyi bir ay önceydi.

I drew a graph out and we

Bir grafik çizdim ve

worked through it with Dijkstra, and at the end

Dijkstra ile birlikte çalıştı ve sonunda

I pointed out a couple of problems.

Birkaç sorun belirttim.

So let's just remind ourselves about

Öyleyse kendimize hatırlatalım

those problems and then when we'll talk about A star

bu sorunlar ve sonra ne zaman bir yıldız hakkında konuşacağız

we can see how it addresses it.

nasıl hitap ettiğini görebiliriz.

The problem is with Dijkstra that it will follow

Sorun Dijkstra'da takip edeceği ile ilgili

the path currently shortest and that -- and

şu anda en kısa yol ve bu - ve

doesn't pay any attention to what

neye dikkat etmez

direction it's going.

So if i'm coming down here to my end goal,

Yani buraya son hedefime geleceksem,

and I'm starting up here, that's fine if

ve ben buradan başlıyorum, eğer iyi

the weights are all the same because it will

ağırlıklar aynıdır çünkü

look at it up here and there, but I'll

şuraya bakın oraya, ama ben

get there quite quick.

Oraya oldukça hızlı.

The problem is of course if you've got

Sorun tabii ki varsa

the map of the UK and it's searching quickly

İngiltere'nin haritası ve hızla arama yapıyor

down all nice motorways when in

Tüm güzel otoyollardan aşağıdayken

fact actually we don't need to go down

aslında aslında aşağı inmemize gerek yok

the motorways because it's a country road drive

otoyollar çünkü köy yolunda

or something like this. Now, course in

ya da böyle bir şey. Şimdi, içeri gir

practice, it wouldn't take very long

pratik, çok uzun sürmez

still because your computer is quite fast

hala bilgisayarınız oldukça hızlı olduğu için

but the whole point of these algorithms

fakat bu algoritmaların tüm amacı

is they're quick and you can imagine if you're

hızlılar mı ve hayal edebilir misin

writing a sat-nav, you don't want it to

sat-nav yazmak, istemezsin

take a long time churning for the roads unnecessarily.

gereksiz yere yollar için uzun zamandır çalkalayın.

The other problem is,

if your graph doesn't look like a map because,

grafiğiniz harita gibi görünmüyorsa,

you know, in some sense the UK road network

bilirsin, bir anlamda İngiltere karayolu ağı

isn't quite sparse but the most of the

oldukça seyrek değil ama çoğu

country doesn't have a road on it. It's

Ülkenin üzerinde yolu yok. Onun

mostly fields and sheep and stuff. But,

çoğunlukla tarlalar, koyunlar ve eşyalar. Fakat,

you know, all houses. If you have a

Bilirsin, bütün evler. Eğer varsa

situation where you've got a quite a

Oldukça iyi bir durumda.

dense network like this, so I guess you

Böyle yoğun bir ağ, bu yüzden sanırım

could say a bit like Manhattan. But also just,

Manhattan gibi biraz söyleyebilirdi. Ama ayrıca sadece

you know, another problem where your

bilirsin, başka bir problem ise

graph structure is different. So if

grafik yapısı farklı. Öyleyse

you're looking through an image or

bir görüntüye bakıyorsunuz veya

something like this. I'm starting up here

bunun gibi bir şey. Buradan başlıyorum

and cross that out. There we are and I'm

ve bunu aşın. İşte biz ve ben

finishing down,

I don't know... here. Let's remember that

Bilmiyorum ... burada. Bunu hatırlayalım

Dijkstra follows the shortest path based

Dijkstra en kısa yolu izler.

on the distance of each of these. Now, if

Bunların her birinin üzerinde. Şimdi eğer

it is just a uniform grid, let's

bu sadece tek tip bir ızgara, hadi

say, we have no interesting information

Diyelim ki ilginç bir bilgimiz yok

to provide for these weights and all

bu ağırlıkları ve hepsini sağlamak için

these weights say one so it's just

bu ağırlıklar bir tane söylüyor, sadece

gonna to flood fill from here. It's gonna

Buradan dolup taşacak. Olacak

go here, and then here and then to

buraya ve sonra buraya ve sonra

these three and then to these four, and so on and

bu üç ve sonra bu dört ve benzeri ve

that's not very optimal. Especially

bu çok uygun değil. Özellikle

if we just literally want to go

eğer tam anlamıyla gitmek istiyorsak

straight down here, like this. So we want to

tam burada, böyle. Bu yüzden istiyoruz

build in some kind of idea of, but not

bir tür fikir inşa etmek, ama değil

necessarily the direction we're heading but we are

mutlaka yöneldiğimiz yön ama biz

at least going towards our goal, so we can

en azından hedefimize doğru gidiyoruz.

aim for it. And that's what A star does.

amaç için. Ve bir yıldızın yaptığı budur.

A star is basically a small extension to

Bir yıldız temelde küçük bir uzantısıdır

Dijkstra that builds in a heuristic that

Dijkstra bir sezgisel inşa bu

says we're getting a bit closer.

biraz daha yaklaştığımızı söylüyor.

This is our nice screwed up graph from last time

Bu bizim son zamanların en berbat berbat grafiğimiz.

and this is our nice new fresh graph

ve bu bizim güzel yeni taze grafik

that I've done which is, topologically exactly

yaptığım şey, topolojik olarak tam olarak

the same. I may have traced it. So, we

aynısı. İzlemiş olabilirim. Yani biz

could do Dijkstra on this.

Bu konuda Dijkstra yapabilirdi.

I've got my little cards for my priority queue.

Öncelik sıram için küçük kartlarım var.

I've reminded myself how the end condition is

Son durumun nasıl olduğunu kendime hatırlattım

so I can end it properly.

Böylece düzgün bir şekilde sonlandırabilirim.

That's all fine. What we want to do is extend this

Her şey yolunda. Yapmak istediğimiz bunu uzatmak.

to A star. Now, A star is basically exactly the

Bir yıldıza. Şimdi, bir yıldız temelde tam olarak

same as Dijkstra, except it has an

Dijkstra ile aynı, ancak

additional heuristic that is how far do

ek sezgisel bu ne kadar uzak

we have to go. And, in this case,

gitmeliyiz. Ve bu durumda,

a pretty reasonable heuristic to come up with

gelmek için oldukça makul bir buluşsal

will be literal Euclidean distance

değişmez Öklid mesafesi olacak

of how far we have to go. So, in this case

ne kadar ileri gitmeliyiz. Yani bu durumda

S to E will be that far, C to E will be that far.

S'den E'ye kadar uzak olacak, C'den E'ye kadar uzak olacak.

And so on. I couldn't think of a good way of

Ve bunun gibi. Ben iyi bir yol düşünemiyorum

calculating this without literally just

bu kelimenin tam anlamıyla olmadan sadece hesaplama

measuring it. So I got my, got my...

bunu ölçüyorum. Ben de aldım, aldım ...

dainty 10 meter tape measure,

zarif 10 metre şerit metre,

which is a little bit overkill. But we'll,

Bu biraz overkill. Ama yapacağız

you know, make it work. So this is all a bit odd.

Bilirsin, çalışmasını sağla. Yani bu biraz garip.

I don't use tape measures as much as you can

Mezura olabildiğince fazla kullanmıyorum

imagine 'cause I mostly sit at a desk

hayal et çünkü çoğunlukla masa başında oturuyorum

and do typing. This is a tape measure in

ve yazarak yapın. Bu bir mezura

centimeters and inches. Let's use inches today.

santimetre ve inç Bugün inç kullanalım.

Imperial, woo. So I'm gonna literally

İmparatorluk, ha Yani tam anlamıyla yapacağım

measure the amount of inches from S to E,

S'den E'ye kadar olan inç miktarını ölçmek,

and then A to E, and then I'm just gonna put

ve sonra A'dan E'ye ve sonra sadece koyacağım

this on here now. And this is where

Bu şimdi burada. Ve burası

you fast forward. So, I'm gonna use it,

hızlı ileri sar. Yani kullanacağım

the black pen for this. So let's say this is 10.

Bunun için siyah kalem. Diyelim ki bu 10.

There. This is harder than I thought it would be.

Orada. Bu düşündüğümden daha zor.

I haven't got enough hands.

Yeterince elim yok.

8... 6... I'm rounding up a bit

8 ... 6 ... Biraz yuvarlanıyorum

it's not very accurate. 4... So the green

çok doğru değil. 4 ... Yani yeşil

ones are our step distances from Dijkstra and the

Dijkstra ve Güney

black ones are measured inches.

siyah olanlar inç cinsinden ölçülür.

Also 3, 6, 7. We're getting there. 6 again.

Ayrıca 3, 6, 7. Oraya geliyoruz. Yine 6.

Alright. That's me doing my workman's... Now:

Peki. İşte benim işçimi yapıyorum ... Şimdi:

we've got exactly the same graph as before but now we

eskisi gibi aynı grafiğe sahibiz ama şimdi

have some measure of the distance to our thing.

Bizim işimize olan uzaklığın bir ölçüsü olsun.

It's not a very good heuristic in

Bu çok iyi bir buluşsal değil

a sense that my measuring is not very

ölçümümün pek olmadığı

accurate and for A star to work really

doğru ve gerçekten bir yıldızın çalışması için

well, you have to have a consistent

peki, tutarlı olmalısın

metric and you have to, not

metrik ve yapmak zorundasın

overestimate how far you've got to go.

ne kadar ileri gitmen gerektiğini küçümseme.

Things like this... But, we'll just

Bunun gibi şeyler ... Ama, biz sadece

hope it works, sort of work itself out....

Umarım işe yarar, işten çıkarsa ...

You know, it can't be any worse than me

Bilirsin, benden daha kötü olamaz.

you know, doing it by hand anyway. So, recall

bilirsin, yine de elle yapıyorsun. Yani hatırla

when we did Dijkstra. What we had was we had

Dijkstra'yı yaptığımızda. Elimizdeydi

some queue here like this. These had the current

Bazı sıra burada böyle. Bunlar akım vardı

distance from the start to these nodes.

bu düğümlere başlangıçtan itibaren mesafe.

And if one of the nodes had a

Ve eğer düğümlerden biri bir

shorter path, it would move up the queue and

kısa yol, sıra yukarı ve

then when we wanted to expand a node we take it

sonra bir düğümü genişletmek istediğimizde onu alırız

off the queue. A star works exactly the

sıra dışı. Bir yıldız tam olarak çalışıyor

same way, except the distance isn't what

aynı şekilde, mesafe hariç ne

we ordered them by anymore. It's a

Artık onları emretti. Bu bir

distance of the path plus how far they

yolun mesafesi artı ne kadar uzak

gitmek zorunda.

so for example. B, the distance is

öyleyse örneğin. B, mesafe

going to be 2 plus 7 which is 9. Alright.

9 artı 9 olacak. 9.

So B will have a value of 9 on this queue.

Böylece B bu sırada 9 değerine sahip olacaktır.

And the idea is that if something has a

Ve fikir şu ki, eğer bir şey varsa

long way to go,

gitmek için uzun yol

it's going to receive a higher weight

daha fazla kilo alacak

and be further down the queue and

ve sırada daha ileride olmak

expanded later. What it will do is

sonra genişledi. Ne yapacak

prioritize nodes, that are going roughly

öncelik sırasına giren düğümler

in the right direction, unless... I mean it will

doğru yönde, sürece ... demek istediğim

still go down really good paths, really

hala çok iyi yollara düşüyorsun, gerçekten

short paths. But not at the expense of

kısa yollar Ama pahasına değil

everything else, it's the idea.

her şey, bu fikir.

OK, so let's run through this just like we did

Tamam, öyleyse bunu geçelim, tıpkı bizim yaptığımız gibi

with Dijkstra and hopefully I won't make

Dijkstra ile ve umarım yapamam

any mistakes. People will very kindly

herhangi bir hata. İnsanlar çok kibar olacak

point them out if I do. Oh look, look. Checkered flag.

yaparsam işaret et. Oh bak, bak. Damalı bayrağı

This is why I don't draw things, because

Bu yüzden bir şeyler çizmiyorum, çünkü

it's not it's never good... Right,

hiç iyi değil ... Doğru,

okay, we're starting at S. I'm not going to

tamam, s ile başlıyoruz.

draw the infinity symbols on because we

sonsuzluk sembollerini çizeriz çünkü

know that all of these nodes start with

tüm bu düğümlerin başladığını biliyorum

a distance of infinity because we

sonsuzluk mesafesi çünkü biz

don't know how far the path is. In Dijkstra,

yolun ne kadar uzakta olduğunu bilmiyorum. Dijkstra'da

we store the distance to each path, and

her yola olan mesafeyi kaydeder ve

we also ordered by that distance. We've

biz de bu mesafeden sipariş verdik. Biz ettik

now got two separate measures we're

şimdi iki ayrı önlem aldık.

measuring in A star: one is the distance

Bir yıldızda ölçme: biri mesafedir

to the node, and one is the distance to

düğüme, ve biri uzaklık

a node and any remaining distance. So, we

bir düğüm ve kalan mesafe. Yani biz

kind of need to have two values on each

her biri için iki değere sahip olma ihtiyacı

of these things. So I'm going to try and

bunlardan. Yani deneyeceğim ve

keep the colors the same so that we

renkleri aynı tutmak, böylece

don't lose track.

İzini kaybetme.

So anything I draw in green is

Yani yeşil çizdiğim herhangi bir şey

going to be this 'g' cost function which

Bu 'g' maliyet fonksiyonu olacak

is the distance to a current node,

geçerli bir düğüme olan uzaklığı,

so for C that would be 3.

C için bu 3 olur.

And then, in black I'm going to have 3

Ve sonra siyah olarak 3 olacağım

plus 8 which is the sort of combined

artı 8 olan kombine tür

cost; the thing we're actually ordering by.

maliyet; aslında sipariş ettiğimiz şey.

OK, so the path cost to S is 0 and the sort

Tamam, yani S yolunun maliyeti 0 ve sıralama

of distance to go is 10, but it won't

gitmek için mesafe 10, ama olmaz

matter because S is the only thing in

önemli çünkü S içindeki tek şey

our queue. So we'll put S in the queue but everything

bizim sırasımız. Böylece S'yi sıraya koyacağız ama her şey

else have a distance to infinity. So

başka sonsuzluk için bir mesafe var. Yani

let's start expanding some stuff. So A

Hadi bazı şeyleri genişletmeye başlayalım. Yani bir

first. A has... I gotta find A mate. Fast forward.

ilk. Bir ... Bir eş bulmalıyım. Hızlı ileri.

Oh here we are.

Ah işte buradayız.

Why aren't these in alphabetical order?

Neden bunlar alfabetik sırada değil?

I mean, you know... What was I thinking?

Yani, bilirsin ... Ne düşünüyordum?

Right, so A has a distance of 7 and a combined

Doğru, öyleyse A 7 ve toplam değere sahip

distance of 9 plus 7 which is 16. The

9 olan 7 ve 16 olan mesafe.

same for B. Same B, B, B... Again B.

B için aynı Same B, B, B ... Tekrar B.

I mean it's actually at the end.

Yani aslında sonunda.

Unbelievable. So I'm gonna

Inanılmaz. Yani yapacağım

keep seeing it at the top now 'cause I know

Şimdi en üstte görmeye devam et çünkü ben biliyorum

OK, so B has a weight of 2 and a

Tamam, B'nin ağırlığı 2 ve

combined cost of 7 plus 2, which is 9.

9 olan 7 artı 2'nin toplam maliyeti.

So, I'm gonna put that in there. Now, B goes in

Yani onu oraya koyacağım. Şimdi, B giriyor

the queue and goes ahead of A, because

kuyruk ve A'nın önüne gider, çünkü

9 is smaller than 16, right. We're

9 sağ 16, küçüktür. bizler

keeping a track of these green distances.

bu yeşil mesafelerin izini sürmek.

We're not actually using them to see which one

Aslında hangisini görmek için onları kullanmıyoruz

comes next. And then C. C has a path

sırada geliyor. Ve sonra C'nin bir yolu var.

cost of 3 and then a combined weight

3 maliyeti ve ardından birleşik ağırlık

of 11. 8 plus 3. And then that goes in

11 8 artı 3. Ve sonra o giriyor

just above A like this, right. So

A'nın hemen üstünde, böyle. Yani

actually, so far, pretty similar to Dijkstra,

Aslında, şimdiye kadar, Dijkstra'ya oldukça benziyor,

apart all the numbers are changed. So what's next.

ayrı olarak tüm sayılar değiştirilir. Sırada ne var.

We start expanding B. I haven't been

B'yi genişletmeye başlıyoruz.

keeping track of the previous node so

önceki düğümü takip etmek

all of these currently there's the storm

bunların hepsi şu anda fırtına var

in red all are going through S

kırmızı ile hepsi S geçiyor

OK, so B next. We can go to A. A has a

Tamam, sıradaki B. A'ya gidebiliriz.

distance of seven when we deciding

karar verirken yedi mesafe

whether the path to A better via B

B yolu ile A yolunun daha iyi olup olmadığı

we don't care about this heuristic,

Bu buluşsal buluşla ilgilenmiyoruz,

we only care about the actual cost of it,

biz sadece bunun gerçek maliyetini önemsiyoruz,

the path to A, so in this case 2 + 3 is

A yolu, bu durumda 2 + 3

less than 7 just like with Dijkstra

Dijkstra ile olduğu gibi 7'den az

we're going to replace it so A, its new weight

onun yerine A, yeni ağırlığı değiştireceğiz

is going to be 5, and 16 is going to

5 olacak ve 16 olacak

be 5 + 9, so 14, right? And this now,

5 + 9, yani 14 olmalı, değil mi? Ve şimdi,

this path is going through B, not..

bu yol B'den geçiyor, değil ..

Do you think I can turn this into a B?

Bunu bir B'ye dönüştürebileceğimi mi düşünüyorsun?

Oh yes, there we go, look at that.

Oh evet, işte başlıyoruz, şuna bir bakın.

So it stays below C, it's not a big deal.

Bu yüzden C'nin altında kalır, önemli bir şey değil.

OK, D... Let's find in my shuffled list.

Tamam D ... Karışık listemde bulalım.

If you're implement this, don't shuffle it because

Bunu uygularsan, karıştırmayın çünkü

it'll be a lot harder to find in memory

bellekte bulmak çok daha zor olacak

Right, there we are. B has a path length of 2

Doğru, işte buradayız. B yol uzunluğu 2

D has a path length of 4, so that's a path length of 6

D, 4 yol uzunluğuna sahiptir, bu yüzden 6 yol uzunluğu

and D has got a distance of 8 to the end so

ve D'nin sonuna kadar 8'lik bir mesafe var.

actually you can see here that D is

aslında burada D olduğunu görebilirsiniz

traveling forward in this direction, but is actually

Bu yönde ilerlemek, ama aslında

getting further away than B so these

B den daha uzaklaşmak, böylece

going to be quite heavily penalized

oldukça ağır bir şekilde cezalandırılacak

that's our hope so D is not going to be

Bu bizim umudumuz, yani D olmayacak

expanded for a while we're going to look

genişletilmiş bir süre bakacağız

there until it's a last resort

Son çare olana kadar orada

So 8 + 4 is 12, and that path goes through...

Yani 8 + 4 12, ve o yol geçiyor ...

You know what, I'm just gonna leave the lids off.

Biliyor musun, sadece kapakları kapalı bırakacağım.

And that goes through B. So put that in.

Ve bu B'den geçer. Öyleyse onu içine koy.

And that goes above A because A is a terrible one,

Ve bu A'nın üstüne çıkar çünkü A berbat bir şeydir,

remember there's a fallen tree on that one,

Unutma, bunda düşmüş bir ağaç var.

but it still could be back and then

ama yine de geri olabilirdi

finally H. Now, H has a path length of 1 which is

Sonunda H. Şimdi H, 1 olan bir yol uzunluğuna sahiptir.

nice and quick, B has a path length of 2 so

güzel ve hızlı, B 2 yol uzunluğuna sahiptir

the total path cost is 3 and the

toplam yol maliyeti 3

actual heuristic cost is 3 plus 6 which

gerçek sezgisel maliyet 3 artı 6 olan

is 9, that's 9 in here, 9 is looking

9, buradaki 9, 9

pretty good right now.

şu an oldukça iyi.

Now H goes straight above everything

Şimdi H doğruca her şeyin üstünde gider

like this, right?

böyle, değil mi?

B is about to pop out so that's good.

B ortaya çıkmak üzere, yani bu iyi.

So B is finished, and we put B on our finished pack.

Böylece B bitti ve B'yi bitmiş paketimize koyduk.

Huh, finished stack... Finished list?

Huh, yığın bitti ... Liste bitti mi?

Finished data structure over here.

Burada bitmiş veri yapısı var.

Next up is H, right? Now,

Sıradaki H, değil mi? Şimdi,

last time we didn't expand H next,

son seferinde H'yi genişletmedik,

we expanded C next in Dijkstra because

Dijkstra'da C'yi genişlettik çünkü

they had the same rough paths cost which

aynı zor yollara sahiplerdi ki

is 3 and C was already in the list so

3 ve C zaten listede idi

now we already started to move a little bit

şimdi çoktan biraz hareket etmeye başladık

faster with A star which is good because

çünkü daha iyi olan bir yıldız

it means my example is working so H comes off

bu benim örneğimin çalıştığı anlamına geliyor, yani H çıkıyor

and let's see where we can go

ve bakalım nereye gidebiliriz

we could go to F, so that's easy, I'll find F

F'ye gidebiliriz, bu yüzden kolay, F'i bulacağım

F has a past of 3 + 3

F 3 + 3 geçmişe sahip

which is 6 and it has a distance to go

6 olan ve gitmek için bir mesafe vardır

of 6, so that's a total heuristic cost of 12

6, bu yüzden toplam 12 sezgisel maliyet

and it's going through H. Right, this goes in

ve H’den geçiyor.

and it will come in behind D here with a

ve burada D ardına gelecek

path cost also of 12, right, in general

yol maliyeti de genel olarak 12, doğru,

if there's a conflict will just put the first on in

Bir çatışma varsa, ilk giren

you know, depends on your implementation

bilirsin, uygulamana bağlı

G has a path cost of 3 from H plus another

G, H artı birinden 3 yol maliyetine sahiptir

2 so that's 5 and then plus another 3 is 8.

2 böylece 5 ve sonra artı 3, 8 olur.

Ok, we're done with H

Tamam, H ile işimiz bitti

G goes in right to the top which is good

G doğruca yukarı doğru gider

news for us, for our nice elegant search.

güzel ve şık aramamız için bizden haberler.

So we're going to expand G, so where's E?

Öyleyse G'yi genişleteceğiz, E nerede?

But I'm not gonna go off half-cocked this time

Ama bu sefer yarı yarıya kapalı gitmeyeceğim

and finish my algorithm here. G has a path

ve algoritmamı burada bitirin. G'nin yolu var

length of 5 and so E has a path length

5 ve E'nin uzunluğu bir yol uzunluğuna sahiptir

7

see now I've drawn this checkered flag and

şimdi bak bu damalı bayrağını çizdim ve

it's in the way of my numbers, thanks for

sayılarımın yolunda, teşekkürler

the suggestion there. Right, E has a

öneri var. Doğru, E bir

heuristic cost of zero because we're at

sıfır sezgisel maliyet, çünkü biz

the goal so actually 7 is the final

hedef şu ki aslında 7 final

value that we get given here and this

burada ve burada verdiğimiz değer

goes through G and we're going to

G içinden geçiyor ve biz gidiyoruz

put E in, so E goes in here

E'yi içeri sok, böylece E buraya girer.

G is not really on the stack anymore.

G artık yığında değil.

G can't expand anywhere else, we've already

G başka hiçbir yerde genişleyemez, biz zaten

been to H and so the next iteration of the

H oldu ve böylece bir sonraki yineleme

algorithm starts, right? We popping off the

algoritma başlar değil mi? Patlıyoruz

we're about to expand it and we realize

genişletmek üzereyiz ve fark ediyoruz

that's where we're going and we finished

oraya gidiyoruz ve bittik

bizim algoritmamız

ok so then just like before we trace

tamam öyleyse izlemeden önceki gibi

back through so E goes to G and then...

Böylece E, G'ye gider ve sonra ...

Where's my G? There it is. And G goes to H,

G nerede? İşte burada. Ve G, H'ye gider.

and then H goes to B,

ve sonra H, B'ye gider,

and B goes to S, and S is the start, alright?

ve B S'ye gidiyor ve S başlangıç, tamam mı?

So we've got our path, S-B-H-G-E

Demek yolumuza girdik SBHGE

Now in this case it's exactly the same path

Şimdi bu durumda tam olarak aynı yol

as Dijkstra because

Dijkstra olarak

I picked a fairly reasonable heuristic, right?

Oldukça makul bir buluşsal yöntem seçtim, değil mi?

Plus or minus a bit of my dodgy measuring

Artı veya eksi tehlikeli ölçümümden biraz

But you can see we didn't bother to expand

Ama görebiliyorsun ki genişlemek için uğraşmadık.

C or L or even consider I and J many fewer

C veya L, hatta I ve J'yi daha az düşünün

nodes got put in the stack...In both terms

düğümler yığına kondu ... Her iki durumda da

of the amount of computation we did and

yaptığımız hesaplama miktarının ve

the memory footprint was reduced and we

hafıza ayak izi azaldı ve biz

still obtained the same result.

hala aynı sonucu elde etti.

So there were one or two comments on the last

Sonuncusu hakkında bir iki yorum vardı.

video about not expanding those but

bunları genişletmemekle ilgili video

you're saying that on A star you

bunu bir yıldızda söylüyorsun

definitely don't have to expand those,

kesinlikle onları genişletmek zorunda değilsin

No. The comments on the video were

Hayır. Videodaki yorumlar

because basically I forgot to wait

çünkü temelde beklemeyi unuttum

until E was expanded to finish, I got

E bitinceye kadar genişledi, anladım

overexcited and as soon as I saw E,

fazla heyecanlı ve E'yi görür görmez

I declared it over when we went and got

Giderken ve aldığımızda bunu ilan ettim.

coffee and yeah and that's not right

kahve ve evet ve bu doğru değil

because technically speaking there could

çünkü teknik olarak konuşursak

have been a path from say, F to E, that

D’den F’ye E’ye giden bir yol

was super-sneaky and really quick, right?

süper sinsi ve gerçekten hızlı oldu, değil mi?

I'm sorry, super-sneaky is not a technical

Üzgünüm, süper sinsi bir teknik değil

term you see in the literature, and if

edebiyatta gördüğünüz terim ve eğer

that had happened we have to wait until

Bu olana kadar beklemeliydik

E bubbles to the top of our priority

E önceliğimizin üstüne kabarcıklar

queue to be able to know for sure that we've got

elimizde olduğundan emin olmak için sıraya gir

the shortest path. In this case it was

en kısa yol. Bu durumda öyleydi

very straightforward, E went straight to

çok basit, E doğruca gitti

the top, but you can never guarantee and a

üst, ama asla garanti edemez ve bir

different graph will have a different

farklı grafik farklı olacak

so the actual stopping criterion for

yani gerçek durma kriteri

both Dijkstra and A star is when your goal

Amacınız Dijkstra ve A Yıldızları

node gets to the top of your priority queue.

düğüm öncelik sıranızın başına gelir.

But yeah that was good that people pointed that out

Ama evet, insanların bunu işaret etmesi iyi oldu

because it completed the video with a

çünkü videoyu bir

bit of extra comments. To wrap up you can

Ekstra yorumlar biraz. Sarmak için yapabilirsiniz

imagine now that we've seen a video on

şimdi bir video izlediğimizi hayal edin

how that works in terms of GPS positions

GPS pozisyonları açısından nasıl çalışır?

and we've seen a couple of videos on

ve birkaç video izledik

pathfinding and there's lots of videos on data

yol bulma ve verilerde çok video var

structures in this you can imagine now

buradaki yapıları şimdi hayal edebiliyorum

that you might start to think i can

Yapabileceğimi düşünmeye başlayabilirsin

actually not see how that might be

aslında bunun nasıl olabileceğini görmüyorum

implemented I could see you know the

uygulanmış seni tanıyorum

parts of the system that have to work together

sistemin birlikte çalışması gereken kısımları

we've got a map that stored in the

depoda bir haritamız var

we've got nodes that we're trying to get

elde etmeye çalıştığımız düğümlerimiz var

to and from, that we've got an algorithm

ve bir algoritmamız var

that will find a way through

Bu bir yolunu bulur

Now, you can imagine also that it's

Şimdi bunun da olduğunu hayal edebilirsiniz

unrealistic to expect a small sat-nav

küçük bir sat-nav beklemek gerçekçi değil

to completely compute its way through the

tamamen üzerinden yolunu hesaplamak için

UK but if you saw "I what the best path

İngiltere'yi görürseniz ama "En iyi yol ne?"

from Land's End to John O'Groats" you

Land's End'den John O'Groats'a. "

might melt your sat-nav unless you do

sat-nav'unuzu eritebilirseniz,

something a little bit smarter so you

biraz daha akıllı bir şey yani sen

can imagine they might precompute some

bazılarını hesaplayabileceklerini hayal edebiliyorum

of these things but they know the

Bunların arasında ama onlar biliyor

shortest way of getting from Nottingham

Nottingham'dan en kısa yoldan

into London is via the M1 or

Londra’ya M1 veya

something like this

böyle bir şey

to sort of hard code some of it in some sense

bazı kodları bir şekilde sert kodlamak için

Dürüst olmak gerekirse

I don't work for a sat-nav company, I don't

Sat-nav bir şirket için çalışmıyorum

know what their proprietary algorithms

kendi özel algoritmalarının ne olduğunu bilmek

are, but you can see this is the kind of

öyle, ama görebildiğin gibi

thing we're doing we're trying to find a

Yaptığımız şey bulmaya çalışıyoruz.

nice elegant way of getting from A to B

b den A almanın güzel zarif yolu

and there's lots of pathfinding algorithms

ve çok fazla yol bulma algoritması var

and you could come up with lots of

ve çok fazla gelebilirsin

interesting heuristics, not just euclidean distance

ilginç sezgisel tarama, sadece öklid mesafesi

Also of course they're going to

Ayrıca tabii ki gidiyorlar

have a GPS to measure up in your dating

randevunuzda ölçmek için bir GPS’iniz var

that I mean yet although i would say VPS

Demek istediğim henüz VPS diyebildiğim halde

often has an accuracy of possibles few

çoğu zaman birkaç kesinliğin doğruluğu vardır

meters so it was shoddy measuring tape

metre böylece ayakkabılı ölçüm bandı

is actually pinpoint precision compared

aslında karşılaştırıldığında kesin olan kesin

to that still have maps are carefully

Bunun için hala haritalar dikkatlice

crafted would be exact known positions

hazırlanmış tam olarak bilinen pozisyonlar olurdu

of all these junctions and they know how

Tüm bu kavşaklar ve onlar nasıl biliyor

long it takes to travel out the

seyahat etmek uzun sürüyor

roundabout and they know how long it

dolambaçlı ve ne kadar süreceğini biliyorlar

takes because of traffic and think about

trafik yüzünden alır ve düşün

this they're going to be doing a lot

bu çok yapacaklar

smarter or albums and i'm doing but this

daha akıllı ya da albümler ve bunu yapıyorum ama

is a start and you can see you could

bir başlangıç ve görebildiğini görebiliyorsun

build this up into a really good system

Bunu gerçekten iyi bir sisteme dönüştür

Similar videos:

Dijkstra's Algorithm - Computerphile
Computerphile
1.1M views 23.1K likes 392 dislikes 04 Jan 201741% match

Maze Solving - Computerphile
Computerphile
1M views 21.8K likes 295 dislikes 24 Feb 201741% match

SHA: Secure Hashing Algorithm - Computerphile
Computerphile
874.6K views 14.8K likes 394 dislikes 11 Apr 201734% match

Finding the Edges (Sobel Operator) - Computerphile
Computerphile
359.3K views 6.9K likes 50 dislikes 04 Nov 201534% match

Password Cracking - Computerphile
Computerphile
3M views 60.3K likes 1K dislikes 13 Jul 201629% match

How to Choose a Password - Computerphile
Computerphile
1M views 21.1K likes 235 dislikes 20 Jul 201628% match

Hill Climbing Algorithm & Artificial Intelligence - Computerphile
Computerphile
355K views 7.7K likes 165 dislikes 09 Sep 201428% match

Slow Loris Attack - Computerphile
Computerphile
962.6K views 31.1K likes 265 dislikes 09 Nov 201628% match

Mac or PC? - Computerphile
Computerphile
587.9K views 9.7K likes 314 dislikes 21 May 201427% match

YouTube's Secret Algorithm - Computerphile
Computerphile
318.7K views 6.3K likes 165 dislikes 24 Apr 201427% match

TOR Hidden Services - Computerphile
Computerphile
859.3K views 16.2K likes 242 dislikes 09 Jun 201727% match

Resizing Images - Computerphile
Computerphile
360.9K views 8.5K likes 115 dislikes 02 Sep 201626% match

What is Bootstrapping? - Computerphile
Computerphile
375.1K views 5.5K likes 287 dislikes 19 Mar 201426% match

Onion Routing - Computerphile
Computerphile
1.1M views 24.4K likes 255 dislikes 31 May 201726% match

Cookie Stealing - Computerphile
Computerphile
992.7K views 17.2K likes 210 dislikes 01 Jun 201626% match

Buffer Overflow Attack - Computerphile
Computerphile
1.5M views 32.2K likes 320 dislikes 02 Mar 201625% match

PDF, What is it FOR? - Computerphile
Computerphile
409K views 12K likes 144 dislikes 16 Sep 201624% match

Deep Dream (Google) - Computerphile
Computerphile
618.9K views 13K likes 127 dislikes 26 Aug 201624% match

Why C is so Influential - Computerphile
Computerphile
1.6M views 22.5K likes 1.6K dislikes 25 Aug 201724% match

End to End Encryption (E2EE) - Computerphile
Computerphile
450.6K views 11.2K likes 168 dislikes 30 Mar 201724% match

Where HTML beats C? - Computerphile
Computerphile
551.2K views 11K likes 1.3K dislikes 27 May 201623% match

How Blurs & Filters Work - Computerphile
Computerphile
423.4K views 8.8K likes 120 dislikes 02 Oct 201523% match

Lambda Calculus - Computerphile
Computerphile
803.9K views 19.5K likes 567 dislikes 27 Jan 201723% match

Secrets Hidden in Images (Steganography) - Computerphile
Computerphile
1.1M views 22K likes 242 dislikes 04 Aug 201523% match

Internationalis(z)ing Code - Computerphile
Computerphile
911.6K views 32.5K likes 495 dislikes 04 Aug 201422% match

Wana Decrypt0r (Wanacry Ransomware) - Computerphile
Computerphile
1.4M views 30.1K likes 640 dislikes 15 May 201722% match

Parsing Explained - Computerphile
Computerphile
134.2K views 3.6K likes 45 dislikes 13 Nov 201922% match

What on Earth is Recursion? - Computerphile
Computerphile
565.8K views 16.8K likes 123 dislikes 16 May 201422% match

Where GREP Came From - Computerphile
Computerphile
644.1K views 23.4K likes 152 dislikes 06 Jul 201822% match

Program Correctness - Computerphile
Computerphile
48.8K views 2K likes 253 dislikes 27 Nov 202022% match

Settings Privacy About Contact Donate