Ú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.

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

Ř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.

        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;
        }

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ě.

        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();
        }

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;
        }

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ě.

    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;
        }
    }

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.

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

• 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ů.

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.

buckets.zip