Przeszukiwanie przestrzeni stanów 5

Home

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

Przeszukiwanie przestrzeni stanów to podejście, które pozwala rozwiązać bardzo wiele problemów. Należy jednak uważać, ponieważ siłą rzeczy wymaga sprawdzenia wielu ścieżek w drzewie/grafie stanów, co może trwać bardzo długo. W końcu uzyskamy poprawny wynik, ale po co czekać skoro dla niektórych problemów rezultat można uzyskać dużo szybciej. Spójrzmy na to zadanie.

Dana jest liczba N (z przedziału od 1 do 1000000) płytek domina. Każda płytka składa się z 2 połówek. Każda połówka zawiera liczbę z przedziału od 1 do 100. Dwie płytki domina pasują do siebie jeśli na jednej z połówek zawierają tą samą liczbę np.: płytka 1|10 pasuje do kostki 10|3 ale nie pasuje do kostki 4|5. Należy napisać program, który sprawdzi czy zadane płytki można ułożyć w łańcuch np.: 10|1 1|100 100|65 65|78...

Problem ten można rozwiązać w oparciu o strategię przeszukiwania przestrzeni stanów np.:

• Definicji stanu początkowego - zbiór płytek.
• Formuła/Akcje - Wyszukanie wszystkich płytek, które mogą zostać dopasowane do ostatniej płytki w łańcuchu. Dla każdej z nich należy wygenerować nowy stan czyli usunąć ze zbioru i dodać do łańcucha.
• Warunku stopu - pusty zbiór płytek
• Funkcja kosztu - brak.

Podejście to da poprawne rozwiązanie, ale dla dużych wartości liczby klocków N zajmie to niepraktycznie dużo czasu. Czemu? W tym podejściu każda płytka to węzeł grafu, który jest połączony z innymi klockami, do których pasuje. Rozwiązanie problemu to znalezienie ścieżki w grafie, która odwiedzi wszystkie jego węzły, ale każdy węzeł tylko raz. Innymi słowy szukamy ścieżki Hamiltona w grafie (rozwiązania problemu komiwojażera), który jest problemem z klasy NP.

Do problemy można podejść inaczej. Użyjmy modelu, w którym płytki reprezentowane będą jako krawędzie grafu, a nie węzły. W ten sposób otrzymamy graf o małej liczbie węzłów (tyle ile różnych liczb na połówkach płytek) i dużej liczbie krawędzi. Na przykład jeśli zbiór początkowy zawiera 1000 płytek postaci 3|57 to w nowej reprezentacji będziemy mieli 1000 krawędzi łączących węzły 3 i 57.

Przy takiej reprezentacji rozwiązanie problemu to znalezienie ścieżki w grafie, która przejdzie przez każdą krawędź tylko raz czyli znalezienie ścieżki Eulera, a to można zrobić w czasie wielomianowym. Aby w grafie istniała ścieżka Eulera muszą zostać spełnione następujące warunki (stopień węzła to liczba krawędzi wchodzących/ wychodzących do/z tego węzła):

• Graf musi być spójny.
• Co najwyżej dla jednego węzła spełnione jest (stopień wchodzący) - (stopień wychodzący) = 1
• Co najwyżej dla jednego węzła spełnione jest (stopień wychodzący) - (stopień wchodzący) = 1
• Dla wszystkich pozostałych węzłów stopień wchodzący jest taki sam jak stopień wychodzący.

20/05/2013:
Powyższe warunki dotyczą grafu skierowanego. Graf z płytkami jest natomiast grafem nieskierowanym, a więc powyższe warunki jeszcze się uproszczą.

Innymi słowy wśród wszystkich możliwych grafów są takie ich odmiany, dla których problem znalezienia ścieżki Hamiltona można sprowadzić do znalezienia ścieżki Eulera.

Przeszukiwanie przestrzeni stanów może być bardziej intuicyjne, ale zawsze warto zastanowić się dwa razy.

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.