Treść książki
Przejdź do opcji czytnikaPrzejdź do nawigacjiPrzejdź do informacjiPrzejdź do stopki
SamochodyautonomiczneiGrandDARPAChallenge
15
Kiedytorobiły,komputernabieżącowyszukiwałnajlepsządrogęodstar-
tudomety,odsyłającaktualizacjęludziom,którzydziękitemumogliokreślić
priorytetyswoichbadań.Chrisijegozespółzamierzalizaktualizowaćtrasę
przejazduwpojeździeHumveenachwilęprzedstartem.
Wyszukiwanieścieżki
Byćmożekiedybyliściedziećmi,graliściewgrę,wktórejudawałosię,żepod-
łogawsaloniejesttaknaprawdęgorącąlawą.Celemuczestnikówbyłoodna-
lezieniedrogiwpokoju,unikająckontaktuzpodłogą(czylilawą),oileistniała
takamożliwość.Humveemiałprzedsobątosamozadanie,mianowiciemusiał
dotrzećzbieżącejpozycjidonastępnegopunktumapy,ztąróżnicą,żezamiast
lawymusiałomijaćniebezpiecznerejonypustyni.
Niemożemyjednakpowiedziećmupoprostu:znajdźodpowiedniądrogę.
Pamiętajmy,żekiedyVaucansonprojektowałFlecistę,musiałwyposażyćfigu-
ręwinstrukcjeokreślającenajmniejsząnawetczynność,dziękiczemuFlecista
wypracowałwkońcuumiejętnośćgrynaflecie.Wtymprzypadkujestpodob-
nie:kiedyprogramujemykomputer,takbyodnalazłonodpowiedniądrogę,
musimyprzedstawićmujasnąsekwencjękroków,dziękiktórymbędzieon
wstanieodnaleźćjąsamodzielnie.Tekrokiprzypominająprzepiskulinarny,
przyczymtutajmusimywyraźnieopisaćnajdrobniejszynawetdetal.
Gdybyśmymieliopisaćformalnieproces,wramachktóregoodnajdujemy
drogęwwypełnionymlawąsalonie,wyglądałobytoprawdopodobnienastępu-
jąco.Popierwsze,określilibyśmywumyślekosztwykonaniakrokupodanej
powierzchnilubobiektachwsaloniemniejwięcejtak:
Tabela2.1
Typteren
Dywan(lawa)
Stół
Kanapa
Śpiącypieslubkot
„Koszt”jednegokroku
1
0,5(mamabędziezła,alelawatojednakniejest)
0
10
Następniezaplanowalibyśmydrogęprzezsalon,szacując,którakom-
binacjakrokówdoprowadziłabynasnadrugikoniecpokojunajmniejszym
możliwymkosztem.Zauważmy,żeujęliśmyproblemodnalezieniaodpo-
wiedniejdrogiwpojęciachminimalizacjifunkcji(kosztudrogi).Jesttorzecz