Matematické metody optimalizace

Příkady grafů

• Železniční stanice, tratě mezi nimi

• Města, silnice

• Křižovatky, ulice

• Uzly kanalizace, potrubí

• Místnosti, dveře

• Stavy konečného automatu, přechody

• Stavy systému, přechody

Úloha o koze, vlku a zelí

• Farmář koupil na trhu kozu, vlka a zelí

• Je třeba je převézt přes řeku, v loďce jsou 2 místa

• Na jednom břehu nesmí zůstat samotná koza s vlkem, nebo zelí s kozou

Popis systému

• Systém má 5 komponent: loďka, farmář, koza, vlk, zelí.

• Každá komponenta má dva stavy: levý břeh, pravý břeh

• Farmář a loďka jsou vždy na stejném břehu, stačí uvažovat 4 komponenty

• Celkem je 24=16 stavů

Popis stavů

• FKVZ – nic• FKV – Z• FKZ – V• FVZ – K• FK – VZ• FV – KZ• FZ – VK• F - VKZ

• KVZ – F• KV – FZ• KZ – FV• VZ – FK• K – FVZ• V – FKZ• Z – FVK• Nic – FVKZ

Graf systému

FK - VZ

FVZ - K

FKV - Z

FKZ - V

FKVZ - nic VZ - FK

Z - FVK

V - FKZ

K - FVZ

Nic - FKVZ

Nejkratší cesta v grafu (délka 7)

FK - VZ

FVZ - K

FKV - Z

FKZ - V

FKVZ - nic VZ - FK

Z - FVK

V - FKZ

K - FVZ

Nic - FKVZ

Řešení úlohy

• Farmář přejede s kozou

• Vrátí se• Přejede se zelím• Vrátí se s kozou• Přejede s vlkem• Vrátí se• Přejede s kozou

FK - VZ

FVZ - K

FKV - Z

FKZ - V

FKVZ - nic VZ - FK

Z - FVK

V - FKZ

K - FVZ

Nic - FKVZ

Prohledávání grafu do šířky

FK - VZ

FVZ - K

FKV - Z

FKZ - V

FKVZ - nic VZ - FK

Z - FVK

V - FKZ

K - FVZ

Nic - FKVZ

01

2

3

34

4

6

5

7

Prohledávání grafu do hlouky

FK - VZ

FVZ - K

FKV - Z

FKZ - V

FKVZ - nic VZ - FK

Z - FVK

V - FKZ

K - FVZ

Nic - FKVZ

01

2

3

4

6

5

7

Bludiště

Bludiště prohledané do šířky

0

Bludiště prohledané do šířky

0

1

1

Bludiště prohledané do šířky

0

1

1

2

2

Bludiště prohledané do šířky

0

1

1

3

2

2

Bludiště prohledané do šířky

0

1

1

3

4

2

2

4

Bludiště prohledané do šířky

0

1

1

3

4

5

5

2

2

4

5

Bludiště prohledané do hloubky

0

Bludiště prohledané do hloubky

0

1

Bludiště prohledané do hloubky

0

1

2

Bludiště prohledané do hloubky - backtracking

0

3

1

2

Bludiště prohledané do hloubky

0

3

1

4

2

Bludiště prohledané do hloubky

0

3

1

5

4

2

Bludiště prohledané do hloubky

0

3

1

5

6

4

2

Bludiště prohledané do hloubky

0

3

1

5

6

7

4

2

Bludiště prohledané do hloubky

0

3

1

5

6

7

4

2

8

Úloha o třech cestovatelích

• K divoké africké řece přijdou tři cestovatelé a tři domorodí průvodci z kmene lidojedů

• Přes řeku se dá přejet na loďce, ta má dvě místa, řídit mohou cestovatelé i lidojedi

• Na jednom břehu nesmí zůstat nenulový počet cestovatelů a zároveň více lidojedů než cestovatelů.