Takže expandujme uzel v Pitesti.
Musíme jí dolů tímto směrem, pak nahoru
a poté dosáhneme cesty, kterou už jsme viděli předtím
a pokračujeme tímto směrem.
Nyní dorazíme do Bukurešti, což je náš cíl
a hodnota h se změní na 0,
protože jsme v cíli a hodnota g bude 418.
Vložením cesty na hranici nekončíme,
pouze ji sem vložíme, netestujeme cíl,
ale pak se vrátíme zpět k hranici,
a ukáže se, že cesta s hodnotou 418 je na hranici nejlevnější.
Takže nyní provedeme test cíle
a nalezli jsme cestu k cíli
a je to ve skutečnosti nejkratší možná cesta.
V tomto případě byl algoritmus A* schopen nalézt cestu s nejnižší cenou.
A nyní otázka, nad kterou se budete muset zamyslet,
protože jsme ji ještě nevysvětlili, zní:
Bude se algoritmus A* vždy chovat tímto způsobem?
Odpovězte ano, pokud si myslíte, že algoritmus A* vždy nalezne cestu s nejnižší cenou,
odpovězte ne, pokud si myslíte, že toto chování závisí na konkrétním zadaném problému
nebo odpovězte ne, pokud si myslíte, že toto chování závisí na konkrétní heuristické odhadovací funkci h.
Så lad os udvide noden til Pitesti.
Vi bliver nødt til at gå ned denne vej, op,
så når vi en sti, vi har set før,
og vi går i denne retning.
Nu når vi Bukarest, som er målet,
og værdien for h vil her være 0
fordi vi er ved målet, og værdien af g beregnes til 418.
Igen, så stopper vi ikke bare her fordi vi har føjet en sti til grænsen,
vi har tilføjet den, vi udfører ikke måltesten som det næste,
men, nu går vi tilbage til grænsen,
og det viser sig at 418 er den laveste omkostning for stierne på grænsen.
Så nu fjerner vi den, foretager måltesten,
og nu har vi fundet vores sti til målet,
og den er faktisk den kortest mulige sti.
I dette tilfælde var A* altså i stand til at finde stien med den laveste omkostning.
Nu er det spørgsmål som man må overveje,
for vi har ikke forklaret dette endnu,
om A* altid vil være i stand til det.
Svar ja, hvis du mener A* altid vil finde den billigste sti,
og svar nej, hvis du mener det afhænger af det konkrete, givne problem,
eller svar nej, hvis du mener det afhænger af den konkrete heuristiske estimeringsfunktion, h.
Erweitern wir also den Knoten bei Pitesti.
Wir müssen hier nach unten gehen, hoch,
und erreichen einen Pfad den wir schon kennen,
und dann gehen wir hier entlang.
Wir erreichen nun Bukarest, das Ziel,
mit dem h-Wert 0,
da wir im Ziel sind, und dem g-Wert von 418.
Wie vorhin halten wir hier nicht an weil wir einen Pfad auf die Grenze legen,
wir speichern ihn, wenden aber nicht den Zieltest an,
sondern gehen zurück zur Grenze,
und es stellt sich heraus dass 418 der niedrigste Wert an der Grenze ist.
Jetzt nehmen wir ihn heraus, wenden den Zieltest an,
und haben unseren Weg zum Ziel gefunden,
und es ist tatsächlich der kürzestmögliche Pfad.
In diesem Fall war A* in der Lage den billigsten Pfad zu finden.
Die Frage über die Sie jetzt nachdenken sollen,
weil wir das noch nicht erklärt haben,
ist ob A* das immer schaffen würde.
Antworten Sie mit Ja, wenn Sie glauben A* fände immer den billigsten Pfad [oben],
oder antworten Sie mit Nein, wenn Sie glauben es hängt vom Problem ab [mitte],
oder antworten Sie mit Nein, wenn Sie glauben, es hängt von der heuristischen Schätzfunktion h ab [unten].
So let's expand the node at Pitesti.
We have to go down this direction, up,
then we reach a path we've seen before,
and we go in this direction.
Now we reach Bucharest, which is the goal,
and the h value is going to be 0
because we're at the goal, and the g value works out to 418.
Again, we don't stop here just because we put a path onto the front tier,
we put it there, we don't apply the goal test next,
but, now we go back to the front tier,
and it turns out that this 418 is the lowest-cost path on the front tier.
So now we pull it off, do the goal test,
and now we found our path to the goal,
and it is, in fact, the shortest possible path.
In this case, A-star was able to find the lowest-cost path.
Now the question that you'll have to think about,
because we haven't explained it yet,
is whether A-star will always do this.
Answer yes if you think A-star will always find the shortest cost path,
or answer no if you think it depends on the particular problem given,
or answer no if you think it depends on the particular heuristic estimate function, h.
Maintenant agrandissons le noeud à Pitesti.
Nous devons aller dans cette direction vers le bas, en haut,
puis nous atteignons un chemin que nous avons vu auparavant,
et nous allons dans cette direction.
Maintenant nous atteignons Bucharest qui est l'objectif,
et la valeur de h va être 0
car nous sommes à l'objectif, et il apparaît que la valeur de g est 418.
Encore une fois, nous ne nous arrêtons pas ici juste parce que nous avons mis un chemin dans le tiers de devant,
nous le mettons ici, nous n'appliquons pas le test d'objectif,
mais nous retournons maintenant vers le tiers de devant,
et il apparaît que ce 418 est le chemin de moindre coût sur le tiers de devant.
Donc maintenant nous l'enlevons, effectuons le test d'objectif,
et nous avons maintenant trouvé notre chemin vers l'objectif,
et il s'agit en fait du plus petit chemin possible.
Dans ce cas, A-étoile a été capable de trouver le chemin de moindre coût.
Maintenant la question à laquelle vous allez devoir réfléchir,
pour la simple raison que nous ne l'avons pas expliquée pour l'instant,
est de savoir si A-étoile aura toujours ce comportement.
Répondez oui si vous pensez que A-étoile va toujours trouver le chemin de moindre coût,
ou répondez non si vous pensez que cela dépend du type de problème donné,
ou répondez non si vous pensez que cela dépend du type de la fonction heuristique d'estimation h.
אז בואו נרחיב את הקודקוד בפיטשט.
נצטרך ללכת לאורך הכיוון הזה, למעלה,
ואז נגיע למסלול שכבר ראינו,
ונלך במסלול הזה.
עכשיו נגיע לבוקרשט, שהיא המטרה,
והערך h הולך להיות 0
בגלל שאנחנו במטרה, והערך g יוצא 418.
שוב, אנחנו לא עוצרים פה רק בגלל שהוספנו מסלול לחזית.
נשים אותו שם, עוד לא ניישם את בדיקת המטרה,
אלא נחזור אל החזית,
ומסתבר שהמסלול 418 הוא המסלול בעל הערך הנמוך ביותר בחזית.
אז עכשיו אנחנו לוקחים אותו ומבצעים את בדיקת המטרה,
ועכשיו מצאנו את המסלול שלנו אל המטרה,
וזהו, למעשה, המסלול הקצר ביותר האפשרי.
במקרה הזה, A* היה יכול למצוא את המסלול בעל העלות הנמוכה ביותר.
עכשיו השאלה שעליה תצטרכו לחשוב,
בגלל שעדין לא הסברנו אותה
היא האם A* תמיד יעשה זאת?
ענו "כן" אם אתם חושבים ש A* תמיד ימצא את המסלול בעל העלות הנמוכה ביותר,
או שענו "לא" אם אתם חושבים שזה תלוי בבעיה הספציפית שתינתן,
או שענו "לא" אם אתם חושבים שזה תלוי במשוואה ההאוריסטית הספציפית להערכת המרחק h.
Proširimo čvor u Pitesti.
Moramo ići ovim smjerom, prema gore,
i doći ćemo do putanje koju smo prije vidjeli,
i idemo u ovom smjeru.
Sada dolazimo do Bukurešta, koji jeste cilj,
i h vrijednost će biti 0
jer smo na cilju, a g vrijednost radi za 418.
Opet, ne stajemo ovdje samo zato što smo stavili putanju u prvi red,
stavili smo ga tamo, ne primjenjujemo Cilj Testa sljedeći,
No, sada se vraćamo na prednji red,
i ispada da je 418 doista put sa najnižim troškovima.
Dakle, sada smo došli do toga, uradit ćemo Cilj Test,
i sada smo pronašli svoj put do cilja,
i to je, zapravo, najkraći mogući put.
U ovom slučaju, A-Star je bio u mogućnosti pronaći put s najnižim troškovima.
Slijedi pitanje o kojem ćete morati razmisliti,
jer to još nismo objasnili,
jHoće li A-Star uvijek moći ovo učiniti.
Odgovorite potvrdno ako mislite da će A-Star uvijek pronaći najkraći put s najnižim troškovima,
ili odgovorite ne, ako mislite da to ovisi o određenom datom problemu,
ili odgovorite ne, ako mislite da to ovisi o pojedinoj heurističkoj funkciji procjene, h.
Quindi espandiamo il nodo di Pitesti.
Dobbiamo andare su questa direzione, su,
e arriviamo ad un percorso che abbiamo già visto,
e andiamo in questa direzione.
Ora si arriva a Bucarest, che è il goal,
e il valore di h è 0
perché siamo al goal, e il valore g è 418.
Di nuovo, non ci fermiamo qui solo perché abbiamo messo un percorso sulla frontiera,
adesso lo mettiamo qui, non facciamo il test goal,
ora torniamo sulla frontiera,
e si scopre che questo 418 è il percorso a minor costo nella forntiera.
Quindi lo tiriamo fuori, facciamo il test goal,
e abbiamo trovato il nostro percorso verso il goal,
che è, infatti, l'itinerario più corto.
In questo caso, A star è riuscito a trovare il percorso a minor costo.
Ora la domanda a cui dovrete pensare,
perché non l'abbiamo ancora spiegata,
è se A star ci riuscirà sempre.
Rispondete sì se pensate che A star troverà sempre il percorso più breve,
o rispondete no se pensate che dipenda dal tipo di problema,
o rispondete no se pensate che dipenda dal tipo di funzione euristica di stima h.
ピテシュのノードを展開しましょう
この経路を進んで行きます
すると先ほど見た経路に出るので
こちらの方向へ進みます
ゴールのブカレストに着きましたね
ゴールにいるので
hの値はゼロになります
そしてgの値は418です
フロンティアに他の経路を追加するので
ここで止まりません
この場合はゴール検査を適用しないのです
ではフロンティアに戻りましょう
するとこの418がフロンティアでの
最短経路だという事が分かりますね
そこは除いてゴール検査をします
ゴールへの経路が見つかりました
これが考え得る限りの最短距離の経路です
A*で最短経路を発見できました
ではクイズです 考えてみましょう
まだ説明はしていなかったのですが
A*は常にこれを行います
A*が常に最短経路を
見つけると思ったら“イエス”
問題によると思う場合は“ノー”
ヒューリスティック関数hによると思えば
“ノー”と答えて下さい
Да го истражиме јазолот кај Питешти.
Треба да одиме во оваа насока,
тогаш стигнуваме до пат кој веќе сме го виделе
и одиме во оваа насока.
Сега стигнуваме до Букурешт, нашата цел,
и вредноста на h ќе биде 0
зашто сме на целта, а вредноста на g е 418.
Не запираме тука само зашто сме го ставиле патот на границата,
го оставаме тука, не го правиме тестот за целта
туку одиме назад на границата,
и испаѓа дека 418 е патот со најмала цена на границата.
Сега ја тестираме целта,
го најдовме патот до целта,
кој е најкраткиот можен пат.
Во овој случај, А-ѕвезда беше во можност да го најде патот со најмала цена.
Прашањето за кое ќе треба да размислите,
бидејќи се уште не сме го објасниле,
е дали А-ѕвезда секогаш ќе го прави ова.
Одговорете „да“ ако мислите дека А-ѕвезда секогаш ќе го најде патот со најмала цена,
или одговорете „не“ ако мислите дека зависи од конкретниот проблем,
одговорете „не“ и ако мислите дека зависи од конкретната хеуристичка функција за проценка, h.
Så la oss utvide noden i Pitesti.
Vi må gå ned i denne retningen, opp,
så når vi en rute vi har sett før,
og går i denne retningen.
Så når vi Bukurest, som er målet,
og h-verdien vil være 0
fordi vi er ved målet, og g-verdien viser seg å være 418.
Igjen, vi stopper ikke her bare fordi vi festet en rute til frontlaget,
vi satte den der, men vi tar ikke måltesten ennå,
men går nå tilbake til frontlaget,
og det viser seg at disse 418 er den laveste-kostnadsruten på frontlaget.
Så vi tar den av, gjør måltesten,
og nå har vi funnet ruten til målet,
og den er, faktisk, den kortest mulige ruten.
I dette tilfellet var A-stjerne i stand til å finne den laveste korstnadsruten.
Nå til spørsmålet du skal tenke på,
fordi vi ikke har forklart det ennå,
om A-stjerne alltid vil gjøre dette.
Svar ja dersom du tror at A-stjerne alltid finner den korteste kostnadsruten,
og svar nei dersom du tror at det avhenger av oppgaven som er gitt,
eller svar nei dersom du tror det avhenger av den spesielle heuristiske estimatfunksjonen, h.
Rozszerzmy węzeł w Pitesti.
Idziemy tędy w dół, w górę,
i dochodzimy do ścieżki, którą już znamy.
Idąc w tym kierunku
dochodzimy do Bukaresztu, który jest celem.
Jego wartość h wynosi 0,
ponieważ jesteśmy u celu, a wartość g wychodzi 418.
Jak poprzednio nie kończymy tutaj tylko dlatego, że dodaliśmy ścieżkę do granicy,
ale dodajemy tą ścieżkę, nie wykonujemy testu celu
i wracamy do granicy;
okazuje się, że 418 jest najmniejszym kosztem ścieżek w granicy.
Usuwamy więc tą ścieżkę, robimy test celu
i w ten sposób znajdujemy ścieżkę do celu,
która okazuje się faktycznie być najkrótszą z możliwych.
W tym przypadku A* był w stanie znaleźć ścieżkę o najmniejszym koszcie.
Pytanie, nad którym musicie się zastanowić,
ponieważ tego jeszcze nie wyjaśniliśmy,
jest takie, czy A* zawsze tego dokona.
Odpowiedzcie TAK jeśli myślicie, że A* zawsze znajdzie ścieżkę o najmniejszym koszcie
albo NIE jeśli myślicie, że będzie to zależeć od konkretnego przypadku
albo NIE jeśli myślicie, że będzie to zależeć od konkretnej heurystyki estymacji funkcji h.
Давайте раскроем путь в Питешти.
Мы должны пойти вниз в этом направлении, потом вверх,
тогда мы достигнем путь, который видели ранее,
или же мы пойдем в этом направлении.
Здесь мы достигнем Бухарест - нашу цель,
где значение для h будет равно 0
потому что мы достигли цели, а значение для g - 418.
Как и раньше, мы не останавливаемся здесь лишь потому, что добавили путь к границе,
мы добавляем его здесь, но не проводим проверку цели,
мы возвращаемся назад к границе,
что в итоге даёт 418, и делает этот путь путём с самой низкой оценкой.
И теперь после проверки цели
мы находим наш путь,
который на самом деле является кратчайшим путём.
В этом случае A-Star поиск позволил найти путь и с наименьшими затратами.
А теперь вопрос над которым вам нужно будет подумать,
потому что мы этого ещё не касались.
Всегда ли A-Star поиск будет приводить к такому результату?
Выберите ответ "да" (yes) если вы думаете что A-Star поиск будет всегда находить кратчайший путь,
или ответ "нет" (no) если вы полагаете что это зависит от поставленной задачи,
или ответ "нет" если по вашему мнению это зависит от определенной эвристической оценки функции h.
Rozšírme uzol v Pitesti.
Musíme ísť týmto smerom, nahor,
dostávame sa na cestu, ktorú už poznáme.
a pokračujeme týmto smerom
prichádzajúc do cieľa v Bukurešti.
Jeho H-hodnota je 0,
pretože sme v cieli a G-hodnota vychádza na 418.
Rovnako ako predtým tu neskončíme preto, že sme cestu práve pridali k hranici,
pridáme ju tu, ale nevykonáme test cieľa,
ale vrátime sa do hranice
a vidíme, že 418 sú najmenšie náklady spomedzi ciest na hranici.
Takže teraz vykonáme test cieľa
a týmto spôsobom nachádzame našu cestu k cieľu,
ktorá je skutočne najkratšou možnou cestou.
V tomto prípade, bol A* algoritmus schopný nájsť cestu s najnižšími nákladmi.
Otázka, nad ktorou sa budete musieť zamyslieť,
pretože sme ju ešte nevysvetlili,
je, či to A* dokáže zakaždým.
Odpovedzte áno, ak si myslíte, že A* vždy nájde cestu s najnižšími nákladmi,
alebo odpovedzte nie, ak si myslíte, že to záleží od konkrétneho prípadu,
alebo odpovedzte nie, ak si myslíte, že to bude závisieť od konkrétneho tvaru funkcie heuristického odhadu, H.
Hajde dakle da proširimo čvor u Pitesti.
Moramo da idemo dole ovim pravcem, gore,
onda dolazimo do puta koji smo već videli pre
i onda idemo ovim pravcem.
Sada stižemo u Bukurešt, koji je cilj,
i vrednost h će biti 0
zato što smo u cilju, a vrednost g će biti 418.
Ponovo, mi se ne zaustavljamo ovde samo zato što smo stavili put na granicu
stavimo ga ovde, ne primenjujemo test cilja sledeće,
ali, sada se vraćamo nazad do granice
i ispostavlja se da je 418 najjeftiniji put na granici.
Sada ga mi sklanjamo, uradimo test cilja,
i sada smo našli put do cilja,
i to je, u stvari, najkraći mogući put.
U ovom slučaju, A-star je bio u mogućnosti da nađe najjeftiniji put.
Sada, pitanje o kome ćete morati da razmislite,
zato što ga još nismo objasnili,
je da li će A-star uvek da uradi to.
Odgovorite sa da ukoliko mislite da će A-star uvek naći najjeftiniji put,
ili odgovorite sa ne ukoliko mislite da to zavisi od datog pojedinačnog problema,
ili odgovorite sa ne ukoliko mislite da to zavisi od posebne heurističke funkcije procene, h.
Så låt oss expandera noden vid Pitesti.
Vi måste i denna riktning, uppåt,
då når vi en stig vi har sett förut,
och vi går i denna riktning.
Nu når vi Bukarest, som är målet,
och H-värdet kommer att vara 0
eftersom vi är i mål, och D-värdet utvärderas till 418.
Återigen, vi stannar inte här bara för att vi satte en stig på frontlinjen,
vi lägger det där, vi tillämpar inte måltestet härnäst,
utan, nu går vi tillbaka till frontlinjen,
och det visar sig att denna 418 är den billigaste vägen på frontlinjen.
Så nu har vi klarat av det, gör måltestet,
och nu har vi hittat vår stig till målet,
och det är i själva verket den kortast möjliga vägen.
I detta fall kunde A-stjärna-algoritmen hitta den billigaste vägen.
Nu är frågan som du måste tänka på,
eftersom vi inte har förklarat det ännu,
är om A-stjärna kommer alltid att göra detta.
Svara ja om du tror att A-stjärna alltid kommer att finna kortaste vägen med lägst kostnad,
eller svara nej om du tror att det beror på det givna problemet,
eller svara nej om du tror att det beror på valet av heuristisk funktion, H.
కాబట్టి Pitesti వద్ద నోడ్ విస్తరించేందుకు చేసుకుందాం.
మేము, అప్, ఈ దిశలో క్రిందికి వెళ్ళు ఉంటుంది
అప్పుడు మేము, మేము ముందు చూసిన చేసిన ఒక మార్గం చేరుకోవడానికి
మరియు మేము ఈ దిశలో వెళ్ళండి.
ఇప్పుడు మేము లక్ష్యం ఇది బుకారెస్ట్,, చేరుకోవడానికి
మరియు H విలువ 0 అవతరిస్తుంది
మేము లక్ష్యం వద్ద చేస్తున్నాం, మరియు గ్రా విలువ 418 వరకు బయటకు పనిచేస్తుంది కాబట్టి.
మేము ముందు టైర్ లోకి ఒక మార్గం పుట్ కేవలం ఎందుకంటే మళ్ళీ, మేము, ఇక్కడ ఆపండి లేదు
మేము అక్కడ అది తెలుపుము, మేము, తదుపరి లక్ష్యం పరీక్ష వర్తించదు
కానీ, ఇప్పుడు మేము, టైర్ ముందు తిరిగి వెళ్ళు
మరియు ఈ 418 టైర్ ముందు భాగంలో అత్యల్ప-ఖర్చు మార్గం అని బయటకు వస్తాడు.
కాబట్టి ఇప్పుడు మనం,, ఇది ఆఫ్ తగ్గింపు లక్ష్యం పరీక్ష చేయండి
ఇప్పుడు మేము, లక్ష్యం మా పథం కనుగొనబడలేదు
మరియు ఇది, నిజానికి, చిన్నదైన సాధ్యం మార్గం ఉంది.
ఈ సందర్భంలో, ఒక నటుడు అత్యల్ప-ఖర్చు మార్గం కనుగొనేందుకు చేయగలిగాడు.
ఇప్పుడు మీరు ఆలోచించడం ఉంటుంది అని ప్రశ్న,
మేము, ఇంకా అది వివరించారు కాదు ఎందుకంటే
ఒక నటుడు ఎల్లప్పుడూ చేస్తాను అని ఉంది.
మీరు ఒక నటుడు ఎల్లప్పుడూ చిన్నదైన ఖర్చు మార్గం కనుగొంటారు అనుకుంటే, అవును సమాధానం
మీరు ఇచ్చిన ప్రత్యేక సమస్య మీద ఆధారపడి ఉంటుంది అనుకుంటే లేదా, ఏ సమాధానం
మీరు నిర్దిష్ట శోధన అంచనా ఫంక్షన్, హెచ్ ఆధారపడి ఉంటుంది అనుకుంటే లేదా సమాధానం లేదు
Şimdi Piteşti düğümünü açalım.
Bu yöne doğru, aşağıya gideriz,
ve önceden gördüğümüz bir yolla karşılaşırız;
daha sonra bu yöne gideriz,
ve hedefimiz olan Bükreş'e ulaşırız.
Burada h değeri 0 olacak,
çünkü hedefin üzerindeyiz, ve g değeri de 418 olacak.
Burada yine sınıra bir yol eklediğimizden henüz durmayız,
yolu sınıra koyarız ve hedef sınamasını uygulamayız,
ama sınıra yeniden bakarız,
ve 418'in sınırdaki en düşük değer olduğunu görürüz.
Bundan sonra bunu çıkarırız,
hedef sınamasını yaparız ve hedefe yolumuzu bulmuş oluruz.
Bu yol gerçekten olabilecek en kısa yoldur.
Bu durumda, A-Yıldız en düşük maliyetli yolu bulabildi.
Üzerinde düşünmeniz gereken soru ise,
henüz bunu açıklamadığımızdan,
A-Yıldız'ın bunu her zaman yapıp yapamayacağı.
A-Yıldız'ın her zaman en düşük maliyetli yolu bulabileceğini düşünüyorsanız evet deyin,
veya sonucun verilen probleme bağlı olacağını düşünüyorsanız hayır deyin,
ya da sonucun kullanılan sezgisel fonksiyon olan h'ye bağlı olacağını düşünüyorsanız hayır deyin.
现在来扩展Pitesti节点
从下边这里往上
然后我们到达了一条已有的路径
然后朝这个方向
现在我们到达了目的地Bucharest
h的值应该是0
因为我们已经到达目的地了,得到g的值是418
但还没有结束,因为现在只是延伸了一条路径到边界上
还不是测试目标达成没有的时候
现在我们回到边界
发现418是边界上最小的消耗
现在可以进行目标测试了
发现这确实是一条到达目标的路径
事实上它还是最短的路径
在这个情况,A*可以找到消耗最小消耗的路径
现在你们要思考的问题是
(我们还没有解释过)
是A*搜索总能找到最小消耗的路径吗
回答yes,如果你认为A*搜索总能找到最小消耗路径
或者no,如果你认为这和特定的问题相关
或者你觉得这和特定的启发式估计函数h相关