Treść książki
Przejdź do opcji czytnikaPrzejdź do nawigacjiPrzejdź do informacjiPrzejdź do stopki
diagrampotrafisięliczyćdłużejniż1dzień.
Oszacowanie150*150*150*150=506milionówkombinacji(około2do3dni).
Naszczęściestandardowydiagram,totakijakipowstajepodczaszwykłejgry,tozaledwie30do50
ruchów1warstwy,30*30*30*30kombinacjiliczysięniedłużejniż30minutnakomputerze
1GHzanakomputerze3.8GHzliczysięniedłużejniż10minut.Jesttocenazadokładność
algorytmu.
Takialgorytmzapewniapełnyobrazsytuacjinaplanszy,jeśliistniejechoćby1ścieżkaprowadząca
dosukcesulubporażki,toprogramKalkulatorSzachowy2na2wykryjetąścieżkę.Jesttowięc
algorytmobardzowysokiejużyteczności,awyposażonywfunkcjedecyzyjnektórewyszukują
najatrakcyjniejszeruchywedługpriorytetów,zapewniabardzowysoki,poziomgry,rozumianyjako
nieprzepuszczeniechoćbypojedynczejścieżkisukcesulubporażki.
1.1.2Algorytmdynamiczny
Kolejnyalgorytmtoalgorytmdynamiczny,wktórymzapisujemywpamięcikomputeracałe
drzeworuchów,inastępniejednokrotnielubwielokrotnieprzeszukujemywarstwydrzewawcelu
wyszukaniaodpowiednichkombinacji,np.:czyruch1lub2warstwyspychafiguręKróla
przeciwnikawlewo,wprawo,dogóry,czywdół,jesttoalgorytmprzeznaczonydorozgrywania
końcówekpartiiszachowychizostałwyposażonywwykrywanieruchówkończącychgrę,i
sprawdzaczywystępujeruchprowadzącydosukcesuw1lub3warstwie,doremisuw1lub3
warstwie,iczywystępujeporażkalubremisw2lub4warstwie.
Algorytmdynamicznyzapisujedrzewowszystkichruchówwdynamicznieprzydzielanejpamięci
komputerawodpowiednichstrukturachzewskaźnikami,zużywającproporcjonalnąilośćpamięci
dorzeczywistegopoziomukomplikacjidrzewaruchów.Jesttobardzoszybkialgorytmgdyistnieje
wygenerowanedrzeworuchówwpamięcikomputera,topostawieniediagnozytrwakrócejniż
sekundę,jednakwygenerowaniedrzewawszystkichruchówtrwatylesamoczasucowalgorytmie
statycznym.Pojawiasiępokusaabynieobliczaćkażdejwarstwyodnowaapowykonanymruchuz
pierwszejwarstwydoliczaćtylkoodpowiedniegałęzieczwartejwarstwy,zastanówmysięjakato
jestoszczędnośćczasu,programzamiastliczyćnaprzykład
20+20*20+20*20*20+20*20*20*20=20+400+8000+160000=168420kombinacji
policzytylko
20*20*20*20=160000kombinacji
jestto160000/168420*100%=95%standardowychobliczeńczterechwarstw,czylioszczędność
5%
adla30ruchówpierwszejwarstwy:
30+30*30+30*30*30+30*30*30*30=30+900+27000+810000=837930
kombinacji
policzytylko
30*30*30*30=810000kombinacji
jestto810000/837930*100%=0.966%standardowychobliczeńczterechwarstw,czyli
oszczędność3.4%
imwyższypoziomskomplikowaniadiagramutymmniejszaoszczędność,aczkolwiekprogram
12
