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