Przeszukiwanie przestrzeni stanów 4

Home

Post ten stanowi fragment serii na temat przeszukiwania przestrzeni stanów.

Napisaliśmy już silnik przeszukiwania przestrzeni stanów. Teraz, przy jego pomocy, rozwiążemy problem statków, który stanowił początek naszych rozważań. Zacznijmy od klasy, która będzie przechowywała informacje o bieżącym stanie.

public class ShipsProblemData
{
    public Dictionary<string, Stack<string>> Ports { get; private set; }

    public Stack<string> CurrentPath { get; private set; }

    public ShipsProblemData()
    {
        Ports = new Dictionary<string, Stack<string>>();
        CurrentPath = new Stack<string>();
    }

    public ShipsProblemData Clone()
    {
        var state = new ShipsProblemData();

        foreach (var pair in Ports)
        {
            var stack = new Stack<string>();
            foreach (var target in pair.Value.Reverse())
                stack.Push(target);

            state.Ports[pair.Key] = stack;
        }

        foreach (var item in CurrentPath.Reverse())
            state.CurrentPath.Push(item);

        return state;
    }
}

Właściwość Ports to słownik, którego kluczami są nazwy portów, a wartości to dzienniki modelowane przy pomocy stosu. Właściwość CurrentPath przechowuje natomiast listę odwiedzonych już portów. Metoda Clone ułatwi nam generowanie nowych stanów. Właściwa definicja problemu wygląda tak:

public class ShipsProblem : Problem<ShipsProblemData>
{
    public override ShipsProblemData DataForInitialState
    {
        get
        {
            var data = new ShipsProblemData();

            var port1 = "Gdańsk";
            var port2 = "Szczecin";
            var port3 = "Kołobrzeg";

            data.CurrentPath.Push(port1);

            var book = new Stack<string>();

            book.Push(port2);
            book.Push(port1);
            book.Push(port3);
            book.Push(port2);
            book.Push(port1);
            book.Push(port3);
            data.Ports[port1] = book;

            book = new Stack<string>();

            book.Push(port3);
            book.Push(port1);
            book.Push(port1);
            book.Push(port3);
            book.Push(port1);
            book.Push(port1);
            data.Ports[port2] = book;

            book = new Stack<string>();

            book.Push(port2);
            book.Push(port3);
            book.Push(port2);
            book.Push(port2);
            book.Push(port3);
            book.Push(port2);
            data.Ports[port3] = book;

            return data;
        }
    }

    public override bool IsFinalState(State<ShipsProblemData> state)
    {
        return state.Data.Hosts.All(kvp => !kvp.Value.Any());
    }

    public override IList<State<ShipsProblemData>> Expand(State<MyData> state)
    {
        var newStates = new List<State<ShipsProblemData>>);

        var currentHost = state.Data.CurrentPath.Peek();
        foreach (var host in state.Data.Hosts.Keys)
        {
            if (state.Data.Hosts[host].Count > 0 && state.Data.Hosts[host].Peek() == currentHost)
            {
                var copy = state.Data.Clone();
                copy.Hosts[host].Pop();
                copy.CurrentPath.Push(host);

                newStates.Add(new State<ShipsProblemData> { Data = copy });
            }
        }

        return newStates;
    }
}

Stan początkowy można odczytać z pliku lub bazy danych, ale w naszym przypadku równie dobrze można go zaszyć w kodzie. Stan końcowy możemy wykryć bardzo łatwo, tj. wszystkie dzienniki powinny być puste. Generowanie nowych stanów też jest proste. W każdym kroku musimy znaleźć porty, z których mógł wypłynąć statek i przybić do portu bieżącego czyli takie, których dziennik zawiera na ostatnim miejscu bieżący port. Następnie kopiujemy dane i modyfikujemy je tak aby odpowiadały nowemu stanowi.

Nie pozostaje nic innego jak uruchomić silnik i uzyskać wynik.

var solver = new ProblemSolver<ShipsProblemData>();
var results = solver.SolveProblem(new DFSFringe<ShipsProblemData>(), new ShipsProblem ());

foreach (var res in results)
{
    Console.WriteLine(" ----------- Solution ----------- ");
    foreach (var data in res.ResultData)
        Console.WriteLine(data.CurrentPath.Peek());
    
}

Przeszukiwanie przestrzeni stanów 3

Home

Post ten stanowi fragment serii na temat przeszukiwania przestrzeni stanów.

Zgodnie z obietnicą dzisiaj napiszę jak zaimplementować klasę Fringe i jakie to może mieć znaczenie. Dla przypomnienia potrzebujemy stworzyć kontener, który będzie przechowywał stany, które musimy jeszcze odwiedzić. Wynika to z tego, że przestrzeń stanów ma strukturę drzewiastą albo w ogólności grafową jeśli możliwe jest wrócenie do już odwiedzonego stanu. Węzły tego drzewa/grafu możemy odwiedzać w różnej kolejności, a co z tym związane w różnej kolejności je produkować. Kolejność ta zależy właśnie od implementacji klasy Fringe.

Zacznijmy od dwóch przykładowych implementacji.

public class DFSFringe<TCustomData> : Fringe<TCustomData>
{
    private readonly Stack<State<TCustomData>> _fringe = new Stack<State<TCustomData>>();

    public override int Count
    {
            get { return _fringe.Count; }
    }

    public override bool IsEmpty
    {
        get { return _fringe.Count == 0; }
    }

    public override State<TCustomData> Next
    {
        get { return _fringe.Pop(); }
    }

    public override void Add(State<TCustomData> s)
    {
        _fringe.Push(s);
    }
}

public class BFSFringe<TCustomData> : Fringe<TCustomData>
{
    private readonly Queue<State<TCustomData>> _fringe = new Queue<State<TCustomData>>();

    public override int Count
    {
            get { return _fringe.Count; }
    }

    public override bool IsEmpty
    {
        get { return _fringe.Count == 0; }
    }

    public override State<TCustomData> Next
    {
        get { return _fringe.Dequeue(); }
    }

    public override void Add(State<TCustomData> s)
    {
        _fringe.Enqueue(s);
    }
}

DFS oraz BFS to skróty od Depth-first search czyli przeszukiwania w głąb oraz Breadth-first search czyli przeszukiwania wszerz. DFSFringe opiera się na stosie, a BFSFringe na kolejce. Ma to ogromne znaczenie.

Zastosowanie stosu powoduje, że rozwijany jest najgłębszy jeszcze nie rozwinięty węzeł - stan, a jego następniki ustawiane są na początku zbioru stanów. Natomiast użycie kolejki powoduje, że rozwijany jest najpłytszy jeszcze nie rozwinięty węzeł, a jego następniki ustawiane są na końcu zbioru stanów.

DFS będzie więc, przeważnie, trzymał mniej stanów w pamięci niż BFS. Przy bardzo szerokich drzewach BFS może być wręcz niepraktyczny z powodu zbyt dużego zapotrzebowania na pamięć. Z drugiej strony, przy bardzo głębokich drzewach,  DFS może tracić czas na przeszukiwanie kolejnych gałęzi podczas gdy rozwiązanie będzie znajdować się dość płytko tj. niedaleko korzenia.

DFSFringe, BFSFringe to zresztą tylko dwa przypadki z wielu. Inne podejścia to min.: przeszukiwanie z równomiernym kosztem (ang. uniform-cost search), przeszukiwanie z ograniczoną głębokością (ang. depth-limited search), iteracyjne pogłębianie (ang. iterative deepening) czy przeszukiwanie zgodnie z zasadą najlepszy wpierw (an.g best-first search).

W kolejnym poście w końcu ;) rozwiążemy problem ze statkami.

Przeszukiwanie przestrzeni stanów 2

Home

Post ten stanowi fragment serii na temat przeszukiwania przestrzeni stanów.

Implementacja przeszukiwania przestrzeni stanów powinna być możliwe ogólna, tak abyśmy mogli zastosować ją również dla innych problemów. Najpierw napiszmy klasę reprezentującą stan. Wygląda ona w następujący sposób:

public class State<TCustomData>
{
    public TCustomData Data { get; set; }

    public double Cost { get; set; }

    public State<TCustomData> Parent { get; internal set; }

    public IList<State<TCustomData>> Children { get; internal set; }
}

TCustomData to dowolna klasa, która przechowuje właściwe dane opisujące stan.

Teraz stwórzmy klasę Problem, która będzie miała trzy zadania: dostarczenie stanu początkowego, produkowanie nowych stanów i określenie kiedy znaleźliśmy stan końcowy. Wszystkie składowe tej klasy są abstrakcyjne, ponieważ ich implementacja zależy od rozwiązywanego problemy.

public abstract class Problem<TCustomData>
{
    public abstract TCustomData DataForInitialState { get; }

    public abstract bool IsFinalState(State<TCustomData> state);

    public abstract IList<State<TCustomData>> Expand(State<TCustomData> state);
}

Potrzebujemy jeszcze jednej klasy. Będzie ona odpowiedzialna za przechowywanie stanów, które musimy odwiedzić. Wracając do zadania ze statkiem. W pewnym momencie może być tak, że nie będziemy mogli jednoznacznie powiedzieć skąd przypłynął statek. Możliwości może być wiele i w najgorszym przypadku musimy sprawdzić je wszytskie. Innymi słowy ze stanu A możemy przejść do stanu B, C, D... i gdzieś te stany musimy zapamiętać.

public abstract class Fringe<TCustomData>
{
    public abstract State<TCustomData> Next { get; }

    public abstract int Count { get; }

    public abstract bool IsEmpty { get; }

    public abstract void Add(State<TCustomData> s);

    public void AddRange(IEnumerable<State<TCustomData>> data)
    {
        foreach (var s in data)
            Add(s);
    }
}

Klasa ta jest abstrakcyjna, ponieważ stany możemy odwiedzać w różnej kolejności co może mieć bardzo duże znaczenie, ale o tym później.

Napiszmy jeszcze jedną prostą klasę zanim przejdziemy do właściwego silnika, czyli klasę modelującą rozwiązanie. W tej implementacji rozwiązanie do sekwencja stanów od początkowego aż do końcowego:

public class Result<TCustomData>
{
    private readonly List<TCustomData> _resultData = new List<TCustomData>();

    public IList<TCustomData> ResultData
    {
        get { return _resultData; }
    }
}

Przygotowaliśmy już całą infrastrukturę. Zobaczmy więc silnik. Wbrew pozorom jest on bardzo prosty.

public class ProblemSolver<TCustomData>
{
    public IList<Result<TCustomData>> SolveProblem(Fringe<TCustomData> fringe, Problem<TCustomData> problem)
    {
        var initialState = new State<TCustomData> { Data = problem.DataForInitialState };
        fringe.Add(initialState);

        var res = new List<Result<TCustomData>>();
        while (!fringe.IsEmpty)
        {
            var next = fringe.Next;

            if (problem.IsFinalState(next))
            {
                res.Add(GetSolution(next));
            }
            else
            {
                next.Children = problem.Expand(next);
                foreach (var child in next.Children)
                    child.Parent = next;

                fringe.AddRange(next.Children);
            }
        }

        return res;
    }

    private static Result<TCustomData> GetSolution(State<TCustomData> state)
    {
        var res = new Result<TCustomData>();
        while (state != null)
        {
            res.ResultData.Add(state.Data);
            state = state.Parent;
        }

        return res;
    }
}

Rola silnika sprowadza się do dwóch zadań:

1. Odwiedzanie kolejnych stanów i sprawdzanie czy są rozwiązaniem.
2. Zapamiętywanie kolejno znalezionych rozwiązań.

W kolejnym poście napiszę więcej o możliwych implementacjach klasy Fringe.

Przeszukiwanie przestrzeni stanów

Home

Post ten stanowi fragment serii na temat przeszukiwania przestrzeni stanów.

Zacznijmy od rozwiązania zadania z poprzedniego posta. Poprawna sekwencja portów to:

Gdańsk
Szczecin
Kołobrzeg
Szczecin
Gdańsk
Gdańsk
Kołobrzeg
Kołobrzeg
Szczecin
Gdańsk
Szczecin
Kołobrzeg
Szczecin
Gdańsk
Gdańsk
Kołobrzeg
Kołobrzeg
Szczecin
Gdańsk

Zapewne można do niej dojść stosując algorytm na chłopski rozum czyli:

1. Wiemy, że ostatnim portem był Szczecin.
2. Patrzymy więc na ostatnie wpisy w dziennikach z Gdańska i Kołobrzegu.
3. Okazuje się, że do Szczecina statek przypłynął z Gdańska.
4. Wykreślamy ten wpis.
5. Patrzymy na ostatnie wpisy w dziennikach z Szczecina i Kołobrzegu.
6. Okazuje się, że do Gdańska statek przypłynął z Kołobrzegu.
7. Wykreślamy ten wpis.
8. Patrzymy na ostatnie wpisy w dziennikach z Szczecina i Gdańska.
9. Okazuje się, że do Kołobrzegu statek mógł przypłynąć Szczecina lub Gdańska i musimy rozważyć oba scenariusze.
10. ...

Dla dużej liczby portów jest to zadanie karkołomne. Ja przy takich problemach stosuję przeszukiwanie przestrzeni stanów (ang. State space search), w skrócie PPS. Podejście to pozwala rozwiązać wiele problemów algorytmicznych, które pozornie wydają się bardzo trudne, w prosty sposób. Między innymi stosowane jest w uczeniu maszyn, warto więc je znać.

PPS zakłada, że problem reprezentujemy przy pomocy:

• Definicji stanu początkowego.
• Formuły, która powie nam jakie stany można odwiedzić, z bieżącego stanu. Albo inaczej zbioru akcji, które powodują zmianę stanu.
• Warunku stopu, który powie nam czy znaleźliśmy rozwiązanie.
• Opcjonalnie funkcji kosztu, która pozwala nam wybrać lepsze, bardziej optymalne rozwiązanie.

Na tej podstawie PPS znajduje sekwencję akcji prowadzących od stanu początkowego do rozwiązania. Dla opisanego przeze mnie problemy wygląda to tak:

• Definicji stanu początkowego - port końcowy + stan dzienników.
• Formuła/Akcje - Znalezienie listy portów, z których statek mógł przypłynąć do bieżącego portu. Wybranie portu oznacza dodanie go do listy już odwiedzonych portów oraz wykreślenie odpowiedniego wpisu z dziennika.
• Warunku stopu - Wszystkie dzienniki są puste.
• Funkcja kosztu - brak.

Stan to para składająca się z aktualnej listy odwiedzonych portów oraz aktualnego stanu dzienników. Mając definicję problemu możemy przejść do implementacji o czym napiszę w kolejnym poście.

Zadanie do pogłówkowania

Home

Post ten stanowi pierwszy z serii, w której opisze podejście do rozwiązywania pewnej klasy problemów. W ostatnim czasie po raz kolejny zastosowałem to podejście do rozwiązania problemu, jaki napotkałem, i dlatego postanowiłem o tym napisać. Na początek proponuję zastanowić się nad takim zadaniem.

Treść zadania:

Załóżmy, że statek podróżuje pomiędzy pewną liczną N portów. Za każdym razem kiedy zawinie do portu jest to odnotowywane przez kapitanat w dzienniku. Kapitanat zapisuje również informacje o kolejnym docelowym porcie podróży.

Mając zbiór dzienników ze wszystkich portów, oraz port końcowy należy odtworzyć trasę podróży statku. Statek może wielokrotnie odwiedzać ten sam port. Statek może również wypłynąć z portu A i do niego wrócić.

Niestety dzienniki są prowadzone niechlujnie i nie możemy polegać na datach wpisów. Wpisy są natomiast ułożone chronologicznie w ramach dziennika, czyli jeśli wpis A jest wcześniej w danym dzienniku niż wpis B to znaczy, że statek najpierw odpłynął do A, wrócił po jakimś czasie i popłynął do B.

Przykład 1:

Rozważmy przypadek z 3 portami Szczecin, Gdańsk oraz Kołobrzeg. Portem końcowym jest Szczecin. Dzienniki dla pewnego statku wyglądają w następujący sposób:

Szczecin	Gdańsk	Kołobrzeg
Gdańsk	Kołobrzeg	Gdańsk
Kołobrzeg	Kołobrzeg	Szczecin
	Szczecin	Gdańsk

Z dziennika dla Szczecina możemy odczytać, że statek najpierw odpłynął do Gdańska potem wrócił i odpłynął do Kołobrzegu itd.

Rozwiązanie 1:

Rozwiązaniem jest następująca trasa:

Szczecin
Gdańsk
Kołobrzeg
Gdańsk
Kołobrzeg
Szczecin
Kołobrzeg
Gdańsk
Szczecin

Teraz w ramach ćwiczeń, zanim opiszę swoje podejście, proponuję rozwiązać problem dla poniższych danych. Port końcowy to Gdańsk.

Przykład 2:

Gdańsk	Szczecin	Kołobrzeg
Szczecin	Kołobrzeg	Szczecin
Gdańsk	Gdańsk	Kołobrzeg
Kołobrzeg	Gdańsk	Szczecin
Szczecin	Kołobrzeg	Szczecin
Gdańsk	Gdańsk	Kołobrzeg
Kołobrzeg	Gdańsk	Szczecin