Vypracovane-zkouskove-otazky - teorie

3) Popište princip neinformovaného prohledávání grafů. Uveďte a stručně popište vybranou metodu neinformovaného prohledávání grafu.

Metody neinformovaného prohledávání

• systematické, ale mechanické prohledávání;

• prohledávání do hloubky nebo do šířky.

4) Popište princip informovaného prohledávání grafů. Uveďte a stručně popište vybranou metodu informovaného prohledávání grafu.

• Metody informovaného prohledávání

  • dána nezáporná hodnotící funkce f

  • gradientní algoritmus

    • prosté řazení uzlů v zásobníku podle f

  • paprskové prohledávání

    • hladiny uzlů, vždy zařazujeme k nejperspektivnějích

Informované prohledávání

• Dijkstrův algoritmus

  • uspořádané prohledávání, viz hledání nejkratší cesty

• Algoritmus A

  • modifikovaná hodnotící funkce

  • f(i) = g(i) + h(i)

  • problém: obvykle přesně neznáme, nutno nahradit odhady

5) Charakterizujte úlohu o hledání minimální kostry grafu, stručně popište princip jejího řešení.

Najít kostru s minimálním součtem ohodnocených hran

1)Seřadíme hrany podle hodnocení neklesajícím způsobem

2)Podle takto získaného pořadí zkoumáme postupně hrany. Hranu přidáme do kostry, pokud netvoří s dříve zařazenými hranami kružnici (první dvě hrany přidáme vždy). Algoritmus končí,jakmile zařazené hrany utvoří kostru.

= najdeme si nejméně ohodnocené hrany a ty od nejmenší po největší zařazujeme, ale musíme si dát pozor, aby netvořily ten uzavřený okruh.

• Minimální délky větví síťového propojení počítačů

• Kostra: souvislý graf s minimálním počtem hran

• Princip: přidáváme hrany podle ohodnocení tak, aby netvořily kružnici

6) Charakterizujte úlohu o hledání nejkratší cesty v grafu, stručně popište princip jejího řešení.

• Nalezení nejkratší cesty mezi dvěma místy

• Síť cest

• Některé cesty nemusí existovat

• Postup řešení

  • vypočteme délku tras od počátku do všech uzlů, do nichž se lze dostat z uzlu aktuálního;

    1. Začneme u uzlu, ve kterém chceme začínat, tam je počáteční délka rovna nule)

  • přesuneme se do uzlu, který je nejblíže počátku a v němž jsme ještě nebyli; a má pro nás nejkratší délku (hodnoty jednotlivých uzlů sčítáme – např. do uzlu C je vzdálenost od A = 1, přes B = 5+2 = 7, přes D= 5+7 = 12… Tedy do uzlu C půjdeme nejkratší cestou a to je A-C, a takto pokračujeme i u ostatních uzlů až k tomu konečnému).

  • algoritmus končí, jakmile se dostaneme do cílového místa.

7) Charakterizujte úlohu o hledání maximálního toku v síti, stručně popište princip jejího řešení.

7) Charakterizujte úlohu o hledání maximálního toku v síti, stručně popište princip jejího řešení.

• Proputnost produktovodů

• Ford Fulkersonova věta

Maximální tok v síti je roven jejímu minimálnímu řezu

Algoritmus k nalezení maximálního toku v síti

• Nasycená cesta

  • Vpřed – nelze zvýšit průtok

  • Vzad – průtok lze snížit