Úkol 2 - problém přelévání vody (water jug problem)

  • CTU Prague, MI-PAA, ZS 2011
  • Autor: Tomáš Borovička (borovto1)

Zadání

  • Základní problém je definován takto: K dispozici jsou dva kbelíky (předem daných obecně rozdílných objemů), vodovodní kohoutek a kanál. Na počátku jsou oba kbelíky prázdné. Vaším úkolem je docílit toho, aby v jednom kbelíku byla voda o předem stanoveném objemu, přičemž můžete pouze nalít plný kbelík z kohoutku, vylít celý obsah kbelíku do kanálu a přelít jeden kbelík do druhého tak, aby druhý kbelík nepřetekl. Problém lze zobecnit tím, že připustíme užití většího počtu kbelíků, aby na počátku řešení byla v kbelících nějaká voda, a že předepíšeme koncový objem vody v každém kbelíku.

Popis problému

Řešení

Vytvořil jsem jedno řešení hrubou silou a několik řešení s využitím heuristiky.

Řešení hrubou silou

Řešení hrubou silou spočívá v prohledávání stavového prostoru do šířky (BFS).

  • Výchozím stavem je stav načtený ze souboru.
  • Hledáme takový stav, který odpovídá požadovanému stavu.

Algoritmus expanduje aktualně zpracovávaný stav do všech stavů, které z něho mohou vzniknout. Tyto stavy přidá do kolekce (množiny). Do kolekce není možné vložit dva stejné stavy, tím je zabráněno vytváření cyklů při prohledávání. Pokud algoritmus najde stav, který je shodný s požadovaným stavem, ukončuje výpočet a vrací nalezený stav. Z nalezeného stavu se rekonstruje cesta, kterou vznikl. Prohledáváním do šířky je zajištěno nalezení nejkratší cesty.

Část zdrojového kódu - řešení hrubou silou

        public ISolution Solve(Instance instance, Methods method)
        {
           ...
 
            states.Add(new Configuration(instance));
 
            while (states.Count > 0)
            {
                var config = states.Get();
                // solution found
                if (instance.IsSolution(config.Volumes))
                {
                    return new Solution()
                               {ID = instance.ID, NumOfNodes = states.NumOfStates - states.Count, Steps = config.Step};
                }
                // expand states
                states.Add(ExpandState(config));
            }
 
            // solution doesn't exists
            return null;
        }
 
 
        public IEnumerable<Configuration> ExpandState(Configuration config)
        {
            var result = new LinkedList<Configuration>();
 
            for (int i = 0; i < config.Count; i++)
            {
                Configuration newConfig = null;
                if ((newConfig = Fill(config, i)) != null) result.AddLast(newConfig);
                if ((newConfig = Empty(config, i)) != null) result.AddLast(newConfig);
 
                for (int j = 0; j < config.Count; j++)
                {
                    if (i == j) continue;
                    if ((newConfig = Pour(config, i, j)) != null) result.AddLast(newConfig);
                }
            }
            return result;
        }

Řešení s využitím heuristiky

Prioritní zpracování stavů podle počtu správně naplněných kbelíků

Heuristika spočívá v prioritním zpracovávání stavů, které mají nejvíce kbelíků naplněných na požadovaný objem. Heuristika je implementována pomocí Compareru, který je předáván prioritní frontě.

Část zdrojového kódu - řešení pomocí heuristiky
        public int Compare(Configuration x, Configuration y)
        {
            var valX = RightVolumes(x.Volumes, x.Instance.Finals);
            var valY = RightVolumes(y.Volumes, y.Instance.Finals);
 
            if (valX > valY) return 1;
            return -1;            
        }
 
        private static int RightVolumes(byte[] volumes, byte[] finals)
        {
            return volumes.Where((t, i) => t == finals[i]).Count();
        }

Prioritní zpracování stavů podle délky ušlé cesty

Heuristika spočívá v prioritním zpracovávání stavů, kterých byo dosaženo nejkratší cestou. Heuristika je implementována pomocí Compareru, který je předáván prioritní frontě.

    public class PathLengthComparer : IComparer<Configuration>
    {
 
        public int Compare(Configuration x, Configuration y)
        {
            var valX = x.Step;
            var valY = y.Step;
 
            if (valX < valY) return 1;
            return -1;
        }

Prioritní zpracování stavů podle rozdílu sum objemů kbelíků

Heuristika spočívá v prioritním zpracovávání stavů, které mají nejmenší rozdíl v sumě objemů kbelíků oproti požadovanému objemu. Heuristika je implementována pomocí Compareru, který je předáván prioritní frontě.

Část zdrojového kódu - řešení pomocí heuristiky
    public class SumVolumeComparer : IComparer<Configuration>
    {
 
        public int Compare(Configuration x, Configuration y)
        {
            var valX = Sum(x.Volumes, x.Instance.Finals);
            var valY = Sum(y.Volumes, y.Instance.Finals);
 
            if (valX < valY) return 1;
            return -1;
        }
 
        private static int Sum(byte[] volumes, byte[] finals)
        {
            var sumDiff = Math.Abs(volumes.Sum(i => i) - finals.Sum(i => i));
            return sumDiff;
        }
    }

Kombinování heuristik

Další možností je kombinování heuristik. Zkoušel jsem kombinovat následující heuristiky:

  • Prioritní zpracování stavů podle počtu správně naplněných kbelíků + Prioritní zpracování stavů podle délky ušlé cesty
  • Prioritní zpracování stavů podle počtu správně naplněných kbelíků + Prioritní zpracování stavů podle rozdílu sum objemů kbelíků

A to následujícím způsobem - pokud mají stavy podle první heuristiky shodnou prioritu, použiji druhou heuristiku.

Výsledky měření

  • Metrikou měření je počet prošlých stavů, který intuitivněji vyjadřuje kvalitu heuristiky lépe než výpočetní čas.

Tabulka naměřených hodnot

  • BFS - Hrubá síla, prohledávání do šířky.
  • Heuristika 1 - Prioritní zpracování stavů podle počtu správně naplněných kbelíků.
  • Heuristika 2 - Prioritní zpracování stavů podle délky ušlé cesty.
  • Heuristika 3 - Prioritní zpracování stavů podle rozdílu sum objemů kbelíků.
  • Heuristika 4 - Prioritní zpracování stavů podle počtu správně naplněných kbelíků + Prioritní zpracování stavů podle délky ušlé cesty.
  • Heuristika 5 - Prioritní zpracování stavů podle počtu správně naplněných kbelíků + Prioritní zpracování stavů podle rozdílu sum objemů kbelíků.
BFS Huristika 1 Huristika 2 Huristika 3 Huristika 4 Huristika 5
ID Nodes OperationsNodesOperationsNodesOperationsNodesOperationsNodesOperationsNodesOperations
11 8992 10 155 22 8992 10 2159 12 155 22 155 22
12 8055 8 74 12 8331 8 410 8 74 12 74 12
13 8063 8 40 9 8139 8 91 8 40 9 40 9
14 179 3 10 3 165 3 13 3 10 3 10 3
21 49350 16 525 45 49344 16 8264 196 525 45 525 45
22 40020 12 169 32 41962 12 2248 14 169 32 169 32
23 31387 11 334 37 32481 11 1483 13 334 37 334 37
24 790 5 23 6 1678 5 117 6 23 6 23 6
25 4722 7 146 20 4294 7 420 7 146 20 146 20
31 59199 14 423 41 59199 14 7748 621 423 41 423 41
32 58703 12 176 24 56961 12 2369 12 176 24 176 24
33 43770 10 59 11 46503 10 1770 12 59 11 59 11
34 1008 5 13 5 1010 5 179 6 13 5 13 5
35 7459 7 83 9 6916 7 403 7 83 9 83 9
36 27532 9 146 12 26062 9 1463 12 146 12 146 12

Délka cesty v závislosti na zvoleném algoritmu

Počet navštívených uzlů v závislosti na zvoleném algoritmu

Závěr

Ukazuje se, že s vzužitím jednoduché heuristiky můžeme značně redukovat počet projítých stavů. Na druhou stranu může heuristika najít výrazně hořší řešení než optimální. Jako nejlepší se ukázala heuristika s prioritním zpracováváním stavů podle počtu správně naplněných kbelíků, které s minimálním počtem prošlých stavů, dosahovalo relativně slušného výsledku. Také heuristika s prioritním zpracování stavů podle rozdílu sum objemů kbelíků měla ve většině instancích dobré výsledky, v několika však měla výsledek velmi špatný. Jako bezvýznamné se ukázalo kombinování výše zmíněných heuristik, jelikož nezlepšilo výsledek.

Source code

References

school/fit/mipaa/ukol2.txt · Last modified: 2018-06-21 19:48 (external edit)
CC Attribution-Noncommercial-Share Alike 4.0 International
Driven by DokuWiki Recent changes RSS feed Valid CSS Valid XHTML 1.0