Domácí úloha číslo 2. : Zobecněný problém kýblů

1) Zadání : K dispozici je 5 kýblů naplněných do počátečních stavů, předem daných obecně rozdílných objemů, vodovodní kohoutek a kanál. Vaším úkolem je docílit toho, aby v kýblech byla voda o předem stanoveném objemu, přičemž můžete pouze naplnit kýbl z kohoutku do plného stavu, vylít celý kýbl do kanálu a přelít kýbl do jiného tak, aby druhý kýbl nepřetekl.  

 

Kýble (objem)

14

10

6

2

8

Počátek

0

0

1

0

0

1 Stav 1-1

12

6

4

1

8

2 Stav 1-2

14

4

5

0

4

3 Stav 1-3

12

6

6

2

4

4 Stav 1-4

0

2

1

2

8

 

Kýble (objem)

15

12

8

4

6

Počátek

0

0

0

0

0

5 Stav 2-1

5

5

5

0

1

6 Stav 2-2

12

1

3

4

5

7 Stav 2-3

11

1

3

4

5

8 Stav 2-4

3

12

4

0

6

9 Stav 2-5

2

0

4

3

6

 

Kýble (objem)

14

10

12

3

8

Počátek

0

0

0

0

0

10 Stav 3-1

13

9

12

2

7

11 Stav 3-2

1

5

5

3

4

12 Stav 3-3

0

9

6

3

1

13 Stav 3-4

12

0

12

0

2

14 Stav 3-5

7

3

7

0

0

15 Stav 3-6

7

0

7

0

7

 

2) Vypracování : Pro řešení zadaného problému jsem jako vhodný programovací jazyk zvolil Borland C++ Builder 5. Zdrojový program i spustitelný soubor jsou přiloženy.

 

3) Rozbor řešení :

Jako heuristickou metodu jsem použil hledání do šířky - prioritní frontu, do které vkládám všechny možné ohodnocené stavy z vybraného stavu, které generuji pro všechny kýble pomocí funkcí: vylít kýbl, naplnit kýbl, přelít kýbl do ostatních  a vždy kontroluji, zda-li generovaný stav již ve frontě není (nekontroluji, ale zda-li tam již nebyl) a zda-li jsem již nedospěl k výsledku. Ohodnocování uzlů jsem rozdělil dle následujících kritérií:

·       vylití plného kýble

·       vylití částečně naplněného kýble

·       naplnění prázdného kýble

·       naplnění částečně naplněného kýble

·       přelití se zbytkem, plného kýble do prázdného kýble

·       přelití se zbytkem, částečně naplněného kýble do prázdného kýble

·       přelití se zbytkem, plného kýble do částečně naplněného kýble

·       přelití se zbytkem, částečně naplněného kýble do částečně naplněného kýble

·       přelití beze zbytku, plného kýble do prázdného kýble

·       přelití beze zbytku, částečně naplněného kýble do prázdného kýble

·       přelití beze zbytku, plného kýble do částečně naplněného kýble

·       přelití beze zbytku, částečně naplněného kýble do částečně naplněného kýble

Vygenerovaný stav pak uložím do prioritní fronty. Prioritní fronta zvýhodňuje při vkládání stavu o stejném ohodnocení později vkládaný stav.

            V programu jsem využil připraveného kódu, který jsem upravil a doplnil funkcemi potřebnými pro prioritní frontu a prohledávání do šířky. Program postupně řeší všechny zadání a navíc generuje soubor reseni.txt (viz. Naměřené hodnoty).

 

4) Naměřené hodnoty :

ZADANI

START

KONEC

Čas

MA_BYT

JSOU

Správně

OPERACI

STAVU

1

1-1

17:50:41

17:51:05

0:00:24

12_6_4_1_8_

12_6_4_1_8_

ANO

16

5134

2

1-2

17:51:07

17:51:11

0:00:04

14_4_5_0_4_

14_4_5_0_4_

ANO

15

2095

3

1-3

17:51:12

17:51:31

0:00:19

12_6_6_2_4_

12_6_6_2_4_

ANO

20

4855

4

1-4

17:51:33

17:51:34

0:00:01

0_2_1_2_8_

0_2_1_2_8_

ANO

5

495

5

2-1

17:51:34

19:25:40

1:34:06

5_5_5_0_1_

5_5_5_0_1_

ANO

66

45284

6

2-2

19:26:20

20:14:27

0:48:07

12_1_3_4_5_

12_1_3_4_5_

ANO

73

33317

7

2-3

20:14:42

20:21:24

0:06:42

11_1_3_4_5_

11_1_3_4_5_

ANO

49

19957

8

2-4

20:21:32

20:21:33

0:00:01

3_12_4_0_6_

3_12_4_0_6_

ANO

7

296

9

2-5

20:21:33

20:29:10

0:07:37

2_0_4_3_6_

2_0_4_3_6_

ANO

50

13083

10

3-1

20:29:22

21:30:24

1:01:02

13_9_12_2_7_

13_9_12_2_7_

ANO

68

40722

11

3-2

21:30:43

22:40:34

1:09:51

1_5_5_3_4_

1_5_5_3_4_

ANO

26

55356

12

3-3

22:40:59

22:46:41

0:05:42

0_9_6_3_1_

0_9_6_3_1_

ANO

47

19855

13

3-4

22:46:50

22:56:12

0:09:22

12_0_12_0_2_

12_0_12_0_2_

ANO

71

24525

14

3-5

22:56:24

23:15:55

0:19:31

7_3_7_0_0_

7_3_7_0_0_

ANO

75

34179

15

3-6

23:16:10

0:20:00

1:03:50

7_0_7_0_7_

7_0_7_0_7_

ANO

38

54099

celkem

 

 

6:26:39

 

 

 

626

353252

 

Poslední sloupec uvádí celkový počet stavů, při nalezení správného řešení. Předposlední sloupec pak počet operací, které jsou popsány v souborech solutionXX.txt, nutných pro dosažení řešení.

 

5) Závěr :

Z naměřených výsledků je jasně patrné, že navržená heuristika vždy dokázala problém vyřešit, což obecně neplatí. Pro lepší,  výsledky by bylo třeba si pohrát s jednotlivými ohodnoceními. Pro každé zadání by ovšem mohlo být optimální nastavení jiné a tak jsem se spokojil pouze s hrubým praktickým odhadem (pro 1. stav), že nejvíce se má ohodnotit naplnění, pak přelévání a nejméně vylévání kýblů.

 

Kyble.cpp – zdrojový soubor

Kyble.exe –  spustitelný soubor

solutionXX.txt  – soubory s řešením jednotlivých zadání