PROGRAMOWANIE – PRZYKŁADY
IDE C++ WinBGI C# Wpadki

Przykład C#

Problem plecakowy Strategie pakowania Metoda prób i błędów Implementacja metody prób i błędów w C# Drzewo przeszukiwań algorytmu Program w C# Poprzedni przykład Następny przykład Program w C++ Kontakt

Problem plecakowy

Zadaniem programu jest rozwiązanie tzw. problemu pleca­kowego (ang. knapsack problem), a dokła­dniej jednej z jego różnych wersji zwanej dyskre­tnym problemem pleca­kowym (ang. 0-1 knapsack problem). Problem polega na wyborze takiego zestawu przedmiotów z danego zbioru przedmiotów o podanej wadze i wartości, aby suma ich wartości była możliwie jak największa i suma ich wag była nie większa od ładowności plecaka.

Zagadnienie można zobrazować na przykładzie Alibaby, który znalazł w Sezamie skarb i ma wynieść z niego część o jak najwyż­szej wartości. Skarb składa się z przed­miotów, z których każdy ma określoną wagę i wartość. Kłopot Alibaby polega na tym, że może odbyć drogę powrotną tylko raz, a plecak, który ma ze sobą, porwie się, jeśli łączna waga zabranych przed­miotów przekroczy pewien dopuszczalny ciężar. Można spotkać inną wersję przedsta­wienia problemu, w której złodziej rabujący sklep jubilera stoi przed dylematem wyboru jak najwarto­ściowszego łupu o ograni­czonym ciężarze całko­witym. W rzeczy­wistych zastoso­waniach problem plecakowy może dotyczyć nie tylko pakowania plecaka, walizki czy paczki, lecz także samochodu, ciężarówki, samolotu, statku itp.

Strategie pakowania

W praktyce podczas pakowania plecaka postępujemy najczęściej według jednej z następu­jących strategii:

Strategie te opierają się na działaniu zachłannym, które może prowadzić do znale­zienia akcepto­walnego rozwią­zania, lecz nieko­niecznie optymal­nego. Algorytm zachłanny (ang. greedy algorithm) polega na dokony­waniu w każdym kroku wyboru, który wydaje się być w danym momencie najlepszy. Dla każdej z powyż­szych strategii można łatwo podać dane, dla których uzyskane rozwią­zanie nie jest optymalne. Gdyby np. Alibaba wybierał za każdym razem przed­miot o najwyż­szej wartości (pierwsza strategia), to w przy­padku skarbu złożonego z trzech przedmiotów i plecaka o parame­trach:

  Przedmiot  Waga  Wartość
  ------------------------
      1       25      40
      2       42      68
      3       20      56
  ------------------------
  Ładowność plecaka:  50

wyniósłby z Sezamu tylko jeden przedmiot o wadze 42 i wartości 68 zamiast dwóch przedmiotów o łącznym ciężarze 45 i wartości 96. Oczywiście w tym szcze­gólnym przypadku podjęcie najlepszej decyzji nie nastręcza żadnych trudności, generalnie jednak problem plecakowy nie jest łatwy do rozwią­zania.

Metodą zapewniającą znalezienie optymalnego rozwiązania problemu pleca­kowego jest tzw. metoda programo­wania dynami­cznego. Jej nazwa nie odnosi się programo­wania rozumia­nego jako proces projekto­wania i tworzenia programów kompute­rowych, chociaż można ją zapisać w postaci programu dla komputera. Istotą metody jest umiejętne wypeł­nianie tabel wyraża­jących rozwią­zania mniejszych problemów odpowia­dających mniejszej liczbie przedmiotów i mniejszej ładowności plecaka oraz ich zwiększanie aż do uzyskania rozwią­zania całko­witego.

W dalszych rozważaniach zajmiemy się poszukiwaniem optymal­nego rozwią­zania problemu pleca­kowego metodą prób i błędów. Algorytmy o tej własności są nazywane algorytmami z powrotami lub z nawrotami. Charakte­ryzują się one tym, że kolejny krok, który może prowadzić do rozwiązania, jest zapisywany, a gdy później okaże się, że nie prowadzi do rozwiązania, następuje usunięcie jego zapisu i wyco­fanie się do stanu poprzedza­jącego błędną decyzję. Najbardziej naturalnym opisem algorytmów z powrotami jest rekurencja.

Metoda prób i błędów

Poszukiwanie optymalnego rozwiązania dyskretnego problemu plecako­wego (0-1 knapsack problem) metodą prób i błędów polega na systema­tycznym podejmo­waniu kolejnych prób dobierania przedmiotów, aż wszystkie dopuszczalne kombi­nacje, w których każdy przedmiot może być pozosta­wiony w Sezamie (0) albo zabrany przez Alibabę (1), zostaną wyczerpane. Jeżeli przedmioty ponume­rujemy kolejnymi liczbami całkowi­tymi od 1 do n, wstępną wersję algorytmu próbującego wykonać kolejny krok dla przedmiotu k możemy sformu­łować następu­jąco:

void Próbuj(int k)
{
    if (k < n) Próbuj(k + 1);
    if (można dołożyć przedmiot k do plecaka)
    {
        zapisz, że Alibaba zabiera przedmiot k;
        if (wartość wynoszonej części skarbu jest wyższa)
            zapamiętaj bieżący zestaw jako optymalny;
        if (k < n) Próbuj(k + 1);
        usuń zapis, że Alibaba zabiera przedmiot k;
    }
}

Metoda zawiera dwa bezpośrednie wywołania rekuren­cyjne samej siebie dotyczące przejścia do nastę­pnego przedmiotu o numerze k+1. Pierwsze przejście odbywa się bez zabie­rania przedmiotu k. Drugie zachodzi wtedy, gdy Alibaba może dołożyć do plecaka przedmiot k. Jeżeli polepsza to wartość wynoszonej części skarbu, bieżący zestaw zgroma­dzonych przedmiotów zostaje zapamię­tany jako optymalny. Na koniec drugiego wywołania dołożony do zestawu przedmiot k jest z niego usuwany, by w później­szych próbach podejmo­wanych po powrocie do niższych od k argumentów można było uzwględnić zestawy bez przedmiotu k (rys.).

Rzecz jasna poszukiwanie optymalnego rozwiązania problemu plecako­wego należy rozpocząć od wywołania metody Próbuj dla argu­mentu 1 przy pustym zestawie przedmiotów do wynie­sienia. Gdy w trakcie działania metody napotkany zostanie bardziej wartościowy zestaw przedmiotów nieprzekra­czający ładowności plecaka, zostaje zapamię­tany zamiast dotychcza­sowego. Ostatni taki zestaw wykryty przed końcem jej wykonania stanowi rozwiązanie optymalne, ponieważ wszystkie dopuszczalne kombi­nacje przedmiotów zostały zanali­zowane.

Implementacja metody prób i błędów w C#

Do utworzonego projektu programu konsolowego o nazwie Plecak, którego zadaniem ma być znajdo­wanie rozwią­zania dyskre­tnego problemu plecako­wego, dodajemy w oddzielnym pliku przestrzeni nazw tego programu klasę Przedmiot zdefinio­waną następu­jąco:

namespace Plecak
{
    class Przedmiot
    {
        public double waga;     // Waga przedmiotu
        public double wartość;  // Wartość przedmiotu
        public bool s;          // Przedmiot w bieżącym zestawie
        public bool sOpt;       // Przedmiot w optymalnym zestawie

        public Przedmiot(double waga, double wartość)
        {
            this.waga = waga;
            this.wartość = wartość;
            s = false;
            sOpt = false;
        }
    }
}

Obiekty tej klasy reprezentują przedmioty o określo­nych wagach i warto­ściach. Dodatkowe dwa pola typu logi­cznego zawierają infor­mację doty­czącą kompleto­wania plecaka. Wartość false oznacza, że przedmiot jest pominięty w zestawie przedmiotów przewi­dzianym do zabrania w plecaku, a wartość true, że jest w nim uwzglę­dniony. Zestaw bieżący jest zawarto­ścią plecaka skomple­towaną w wyniku podejmo­wania do danego momentu kolejnych prób pomijania i zabie­rania przedmiotu. Zestaw optymalny jest najlepszym napotkanym zestawem bieżącym.

W celu uściślenia przedstawionej powyżej metody Próbuj stanowiącej wstępne sformu­łowanie metody prób i błędów wiodącej do optymalnego rozwią­zania problemu plecako­wego użyjemy następu­jących pól programu, w których będą przecho­wywane dane oraz wyniki pośrednie i końcowe:

static List<Przedmiot> skarb;   // Lista wszystkich przedmiotów
static double cMax;             // Dopuszczalna ładowność plecaka
static double c = 0;            // Ciężar bieżącego zestawu
static double v = 0;            // Wartość bieżącego zestawu
static double cOpt = 0;         // Ciężar optymalnego zestawu
static double vOpt = 0;         // Wartość optymalnego zestawu

Elementy listy generycznej skarb reprezen­tującej zestaw wszystkich przedmiotów mają indeksy od zera wzwyż, a ich liczbę określa właści­wość Count. Numery przedmiotów są więc o 1 wyższe od indeksów elementów listy, w których są przecho­wywane wagi, wartości i infor­macja o zakwalifi­kowaniu tych przedmiotów do zestawu bieżącego i opty­malnego. Przyjmując nadal, że argu­mentem metody Próbuj jest numer przedmiotu, względem którego ma być podjęta decyzja, czy ma on być zapako­wany do plecaka, czy nie, jej uściśloną wersję możemy sformu­łować następu­jąco:

static void Próbuj(int k)
{
    if (k < skarb.Count) Próbuj(k + 1);
    c += skarb[k - 1].waga;
    if (c <= cMax)
    {
        v += skarb[k - 1].wartość;
        skarb[k - 1].s = true;
        if (v > vOpt)           // Zapamiętaj bieżący zestaw
        {                       // jako optymalny
            cOpt = c;
            vOpt = v;
            foreach (Przedmiot p in skarb)
                p.sOpt = p.s;
        }
        if (k < skarb.Count) Próbuj(k + 1);
        skarb[k - 1].s = false;
        v -= skarb[k - 1].wartość;
    }
    c -= skarb[k - 1].waga;
}

Na początku, gdy liczba wszystkich przedmiotów, ich wagi i wartości oraz dopuszczalna ładowność plecaka jest znana, zestawy bieżący i optymalny przedmiotów wybranych do zabrania są puste (konstru­ktor klasy Przedmiot inicjali­zuje pola ssOpt obiektu wartością false), a ich ciężary i wartości określone przez zmienne ccOpt oraz vvOpt są równe zero. W celu znale­zienia rozwią­zania problemu metodą prób i błędów wystarczy wykonać instrukcję:

Próbuj(1);

Drzewo przeszukiwań algorytmu

Działanie algorytmu z powrotami można prześledzić na przyto­czonym powyżej przykła­dzie problemu pleca­kowego dla trzech przedmiotów o wagach 25, 42 i 20, warto­ściach 40, 68 i 56 oraz ładowności plecaka wynoszącej 50 jednostek. Prosta analiza prowadzi do przedsta­wionego na poniższym rysunku binarnego drzewa przeszu­kiwań.

W wierzchołkach drzewa są wpisane numery przedmiotów występujące w roli argumentów kolejnych wywołań metody Próbuj. Czerwona linia zakończona strzałką wskazuje kierunek wędrówki po wierzchołkach wzdłuż krawędzi drzewa. Lewe krawędzie odpowia­dają przejściu do nastę­pnego przedmiotu bez zabie­rania przedmiotu określonego w wierz­chołku, a prawe – przejściu po zabraniu go. Obcięcie ostatniej krawędzi oznacza, że wędrówka wzdłuż niej nie ma sensu ze względu na przekro­czenie dopuszczalnej ładowności plecaka. Etykiety pod wierzchołkami opisują rozpatry­wany bieżący zestaw przedmiotów (łączny ciężar, wartość i skład). Gwiazdka oznacza, że jest on dotąd najlepszy i jako taki zostaje zapamiętany jako optymalny. Ostatnia na drodze gwiazdka określa rozwiązanie optymalne problemu pleca­kowego.

Dla większej liczby przedmiotów drzewo przeszukiwań może być bardzo rozbudo­wane, co może wpłynąć negaty­wnie na złożoność czasową algorytmu. Nie oznacza to jednak, że zawsze tak jest. Często podczas kolejnych prób binarne drzewo przeszukiwań jest stopniowo obcinane ze względu na przekro­czenie ładowności plecaka, przez co ich liczba redukuje się i algorytm daje się wykonać w rozsądnym czasie.

Program w C#

Pełny program konsolowy w języku C# znajdujący optymalne rozwiązanie dyskre­tnego problemu pleca­kowego metodą prób i błędów jest przedsta­wiony na poniższym listingu. W programie przyjęto wewnętrzną nume­rację przedmiotów od 0 wzwyż zgodną z natu­ralną indeksacją elementów listy klasy genery­cznej List, co wymusiło niewielką modyfi­kację omówionej powyżej metody Próbuj i instrukcji inicju­jącej wyszuki­wanie rozwią­zania.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.IO;

namespace Plecak
{
    class Program
    {
        static void Main(string[] args)
        {
            Console.Write("Nazwa pliku: ");
            try
            {
                using (StreamReader plik = new StreamReader(Console.ReadLine().Trim()))
                    Dane(plik);
                Próbuj(0);
                Wynik();
            }
            catch (Exception e)
            {
                Console.WriteLine(e.Message);
            }
        }

        static void Dane(StreamReader plik)
        {
            int n = int.Parse(plik.ReadLine().Trim());
            if (n <= 0)
                throw new Exception("Niewłaściwa liczba przedmiotów.");
            skarb = new List<Przedmiot>(n);
            Nagłówek(null);
            for (int k = 1; k <= n; k++)
            {
                string s = plik.ReadLine().Trim();
                int p = s.IndexOf(' ');
                double waga = double.Parse(s.Substring(0, p));
                double wartość = double.Parse(s.Substring(p + 1));
                if (waga <= 0 || wartość <= 0)
                    throw new Exception("Wartość powinna być dodatnia.");
                skarb.Add(new Przedmiot(waga, wartość));
                Console.WriteLine("{0,5} {1,10:F2} {2,10:F2}", k, waga, wartość);
            }
            cMax = double.Parse(plik.ReadLine().Trim());
            if (cMax <= 0)
                throw new Exception("Niewłaściwa ładowność plecaka.");
            Console.WriteLine("---------------------------");
            Console.WriteLine("Ładowność plecaka:{0,9:F2}\n", cMax);
        }

        static void Nagłówek(string s)
        {
            if (s != null) Console.WriteLine(s);
            Console.WriteLine("---------------------------");
            Console.WriteLine("Przedmiot   Waga    Wartość");
            Console.WriteLine("---------------------------");
        }

        static void Wynik()
        {
            Nagłówek("Zestaw optymalny");
            int k = 0;
            foreach (Przedmiot p in skarb)
            {
                k++;
                if (p.sOpt)
                    Console.WriteLine("{0,5} {1,10:F2} {2,10:F2}", k, p.waga, p.wartość);
            }
            Console.WriteLine("---------------------------");
            Console.WriteLine("Optimum:{0,8:F2} {1,10:F2}\n", cOpt, vOpt);
        }

        static void Próbuj(int k)
        {
            if (k < skarb.Count - 1) Próbuj(k + 1);
            c += skarb[k].waga;
            if (c <= cMax)
            {
                v += skarb[k].wartość;
                skarb[k].s = true;
                if (v > vOpt)           // Zapamiętaj zestaw
                {
                    cOpt = c;
                    vOpt = v;
                    foreach (Przedmiot p in skarb)
                        p.sOpt = p.s;
                }
                if (k < skarb.Count - 1) Próbuj(k + 1);
                skarb[k].s = false;
                v -= skarb[k].wartość;
            }
            c -= skarb[k].waga;
        }

        static List<Przedmiot> skarb;   // Lista wszystkich przedmiotów
        static double cMax;             // Dopuszczalna ładowność plecaka
        static double c = 0;            // Ciężar bieżącego zestawu
        static double v = 0;            // Wartość bieżącego zestawu
        static double cOpt = 0;         // Ciężar optymalnego zestawu
        static double vOpt = 0;         // Wartość optymalnego zestawu
    }
}

Program rozpoczyna działanie od wczytania danych z pliku teksto­wego o nazwie podanej z klawia­tury. Przyjęto, że w pierwszym wierszu pliku podana jest liczba przedmiotów, w następnych wierszach po dwie liczby określa­jące wagę i wartość kolejnego przedmiotu, a w ostatnim wierszu pojemność plecaka. Na poniższym rysunku przedsta­wiony jest wynik wykonania programu dla przykła­dowych danych zawartych w pliku Dane1.txt.


Opracowanie przykładu: kwiecień 2020