Õppetund
Teooria — Teekonnaotsingu algoritmide visualiseerija
Kolm rippmenüü neljast algoritmist on üks ja sama algoritm. Need kõik järjestavad uurimist ootavad ruudud ühe avaldisega f(n) = g(n) + h(n) — seni läbitud maksumus pluss eeldatav järelejäänud maksumus — ning erinevad vaid selle poolest, kumb kahest liidetavast alles jäetakse. Jäta h ära ja saad Dijkstra algoritmi. Eira g-d ja saad Greedy Best-Firsti. Neljas, laiuti otsing, on see, milleks Dijkstra taandub, kui iga samm maksab sama palju.
Mida iga sümbol tähendab
g(n)- odavaima algusest ruuduni n seni leitud teekonna maksumus. Külgsuunas või vertikaalne samm maksab
1; diagonaalne samm maksab√2, sest sammu mõõdetakse pikkusena, mitte ei loeta üheks käiguks. h(n)- hinnang veel ees seisvale maksumusele. Dijkstra algoritmi ja laiuti otsingu puhul pole see mitte lihtsalt kasutamata — see on null, ja just see teeb neist samanäolise avaldise, kust üks liidetav on puudu.
f(n)- järjestamisvõti: vähima väärtusega
fruut on see, mida uuritakse järgmisena. See trükitakse ruudustiku kohale, asendades valemis käesoleva ruudu enda arvud, et algoritmi ääsja tehtud valik oleks nähtav, mitte lihtsalt väidetav. frontier- merevaigukollased ruudud — avastatud, kuid veel uurimata. Laiendatud sõlmed loendab sellest hulgast lahkunud ruute, mis teeb sellest tehtud töö, mitte vastuse kvaliteedi mõõdu.
Kust valem tuleb
- Enne algoritmi valimist lepi kokku, mida tähendab „lühim“. Tee maksumus on selle sammupikkuste summa: külgsuunas või vertikaalse käigu puhul
1, diagonaali puhul√2. Ruute ei loendata; vahemaad liidetakse. - Nüüd tsükkel, mis on kõigi nelja puhul identne: võta rindest üks ruut, märgi see külastatuks ning paku iga läbitav naaber uuendatud väärtusega
gtagasi rindesse. Pane tähele, mida see tsükkel kunagi ei maini — heuristikut, sihi suunda ega seda, millise algoritmi sa valisid. - Nii et ainus otsus, mis jääb teha, on see, milline ruut välja võtta, ja see taandub ühele avaldisele. Järjesta avaldise
g + hjärgi ja saad A*-otsingu. Seah = 0ning järjestamine toimub pelgalt seni läbitud maksumuse järgi — see on Dijkstra algoritm, mis laieneb ringidena väljapoole, sest tal pole aimugi, kus siht asub. Eira selle asemelg-d ja järjestamine toimub pelgalt hinnangu järgi — Greedy Best-First, mis tormab sihi poole ja nõustub mis tahes teekonnaga, mille kaudu kohale jõudis. - Laiuti otsing ei järjesta üldse: esimesena sisse, esimesena välja. Kui suvand Luba diagonaalid on välja lülitatud, maksab iga samm täpselt
1, seega ruutude saabumise järjekord on ühtlasi kasvavagjärjekord — ja seetõttu uurib laiuti otsing täpselt seda sama, mida Dijkstra algoritm. Saad seda kinnitada ilma ruudustikku uuesti genereerimata: vaheta nende kahe vahel ja Laiendatud sõlmed ei liigu paigastki. Lülita diagonaalid sisse ja see argument langeb ära, sest diagonaal maksab1asemel√2ning saabumise järjekord ei vasta enam maksumusele.
Kuidas nähtut lugeda
Prioriteedihinnang asub ruudustiku kohal, kuhu on sisse kantud käesoleva ruudu enda g ja h, nii et saad lugeda järjestust, mis andis viimase valiku. Selle all on kaks loendurit: Laiendatud sõlmed ja Tee pikkus. Merevaigukollane on rinne, indigosinine on juba külastatud. Algoritmi muutmine ei genereeri uut ruudustikku ja just see teebki võrdluse väärtuslikuks — samal neljasuunalisel paigutusel pole Dijkstra algoritmi Laiendatud sõlmed kunagi väiksem kui A*-otsingul ning Greedy Best-Firsti oma on vaid murdosa kumbagi omast.
- Eeldab
- Eeldab sammu maksumusi, mis pole kunagi negatiivsed, ning ruudustikku, mis otsingu ajal ei muutu. Algus on alati ülemine vasak ruut ja siht alumine parem. Ruudu sulgemine on lõplik — tsükkel ei kaalu ühtegi ruutu uuesti — ja see on turvaline vaid seetõttu, et ükski hilisem teekond ei saa saabuda odavamalt, kui iga samm lisab mittenegatiivse hulga.
- Ei kehti, kui
- Laiendatud sõlmed on arv, mis muutub kõige dramaatilisemalt, ning see pole kvaliteedi mõõt. Vali Greedy Best-First: samal ruudustikul uurib see vaid murdosa sellest, mida A*-otsing, ning enamikul paigutustel tagastab see pikema Tee pikkus. Genereeri mõned uued ruudustikud ja jälgi, kuidas kaks loendurit liiguvad vastassuundades. Vähema hulga ruutude uurimine näitab vaid seda, kui kõvasti algoritm töötas, mitte seda, kui hea oli selle vastus.
Õpitee
Loe tööd, mitte sekundeid
Allikad (3)
- Where A*, the f = g + h scoring and the admissibility condition were introduced: P. E. Hart, N. J. Nilsson & B. Raphael, "A Formal Basis for the Heuristic Determination of Minimum Cost Paths." IEEE Transactions on Systems Science and Cybernetics 4, 100–107, 1968.
- And the algorithm A* generalises, for comparison in the dropdown: E. W. Dijkstra, "A note on two problems in connexion with graphs." Numerische Mathematik 1, 269–271, 1959.
- The fourth option in the dropdown, and the wavefront it spreads: E. F. Moore, "The shortest path through a maze." Proceedings of an International Symposium on the Theory of Switching, Part II, 285–292. Harvard University Press, 1959.