Úloha 2.1

Mějte dánu situaci podle níže uvedeného obrázku:

Pomocí heuristického prohledávání a A* algoritmu s různými typy ryze heuristické funkce

určete přibližně optimální cestu z místa S do místa G.

1. z hlediska spotřeby pohonných hmot, tj. nejkratší cestu,
2. z hlediska potřeby času (nejrychlejší cestu),

když víte, že jednotlivé úseky cesty můžete projet průměrnými rychlostmi podle následující tabulky:

Jako odhad členu

použijte skutečně projetou vzdálenost, resp. skutečně spotřebovaný čas, pro odhad ryze heuristické funkce

použijte následující možnosti:

1. rovnou 0
2. rovnou vzdálenosti nalezené v mapě, tj. podle výše uvedeného obrázku
3. rovnou odhadu vzdálenosti vzdušnou čarou podle obrázku:
   
   
4. rovnou přibližnému odhadu času potřebnému k dojetí do cíle G pro případ ad b)

Řešení:

ad i) f0 = 0 f1 = 36 f2 = 11 f3 = 11 + 31 = 42 f4 = 43 + 13 = 55 f5 = 43 + 19 = 61 f6 = 55 + 43 = 98	ad ii) f0 = 0 f1 = 36 + 36 = 72 f2 = 11 + 11 = 22 f3 = 11 + 31 + 31 = 73 f4 = 11 + 31 + 13 + 13 = 68 f5 = 11 + 31 + 19 + 19 = 80 f6 = 11 + 31 + 13 + 43 + 43 = 141
ad iii) f0 = 0 f1 = 36 + 26 = 62 f2 = 11 + 47 = 58 f3 = 11 + 31 + 14 = 56 f4 = 11 + 31 + 13 + 26 = 81 f5 = 11 + 31 + 19 = 61	ad iv) f0 = 0 f1 = 20 + 20 = 40 f2 = 20 + 50 = 70 f3 = 20 + 10 + 20 = 50 f4 = 20 + 20 + 0 = 40

1. obecný graf
2. stromový graf

pro nalezení správného řešení (včetně všech ostatních) následující úlohy:
Máte k dispozici dva kameninové neprůhledné džbány - jeden o objemu čtyři litry a druhý o objemu tři litry (při naplnění po okraj). Vaším úkolem je naplnit větší (tj. čtyřlitrový) džbán přesně dvěma litry vody.

Přípustná pravidla:

1. _ -> 4   (naplnění 4-litrového džbánu)
2. _ -> 3   (naplnění 3-litrového džbánu)
3. 4 -> 3   (přelití vody z 4-litrového do 3-litrového džbánu)
4. 3 -> 4   (přelití vody z 3-litrového do 4-litrového džbánu)
5. 4 -> _   (vylití vody ze 4-litrového džbánu)
6. 3 -> _   (vylití vody z 3-litrového džbánu)

Žádná jiná pravidla nejsou přípustná. Vodu z nádoby lze buď vylít anebo přelít (i částečně) z jedné nádoby do druhé. Obě činnosti nelze provést najednou. Pokud se přelévá z jedné do druhé nádoby, musí být buď jedna nádoba úplně vyprázdněna anebo druhá nádoba úplně vyprázdněna.

Řešení:

• ad a)
  
• ad b)
  
  Poznámka 1: Znakem "#" jsou označeny uzly, které se už vyskytly.
  Poznámka 2: Číslo u každé hrany označuje použité pravidlo.

Mějte dány osmibitové řetězce reprezentující hodnoty spolehlivostní funkce podle uvedeného schématu:

0

1

1

0

0

1

0

1

7

6

5

4

3

2

1

0

V první generaci máte dány hodnotové řetězce (genotypy) o struktuře:

1 0 0 1 1 1 1 1

1 0 1 0 1 1 0 0

0 0 0 1 0 1 1 1

0 1 0 1 1 0 1 0

Určete hodnoty bitových řetězců (genotypů) pro čtvrtou generaci uzlů, když víte, že při aplikaci genetického algoritmu na první generaci dojde ke křížení nultého a prvního bitu v sousedních párech genotypů a mutaci čtvrtého bitu v druhém a čtvrtém řetězci (počítáno zleva), v druhé generaci dojde ke křížení čtveřic bitů 0-3 opět v sousedních párech genotypů a mutaci nultého bitu v prvním a třetím genotypu a konečně ve třetí generaci dojde ke křížení nultého a prvního bitu v levé dvojici genotypů, čtvrtého a pátého bitu v pravé dvojici genotypů a mutaci šestého bitu ve druhém genotypu a druhého bitu v třetím genotypu.

Řešení: