Какая реализация карты наиболее подходит для головоломки River Crossing?

Question

Это проект для класса Data Structures, который я беру, поэтому вместо предоставления закодированных ответов я бы предпочел, чтобы вы указали, правильно ли я думаю об этом, или я что-то упускаю. Многие из вас слышали об этой головоломке, но если нет, вот она:

Фермер находится на южном берегу реки со своими владениями: козлом, волком и очень крупной капустой. Фермер хочет добраться до северного берега реки со всем своим имуществом. Река слишком глубокая и широкая, чтобы пройти через нее. Тем не менее, есть небольшая лодка доступна. Лодка настолько мала, что фермер может забрать только одно из своих владений за раз. Важно отметить два других условия.

1. Если козел и волк остались одни на одной стороне ровера, волк съест козу.
2. Если козу и капусту оставить на одной стороне, козочка съест капусту.

Проект требует, чтобы мы создали структуру данных Графика, чтобы помочь фермеру решить, как он должен переместить свое имущество на другую сторону реки.

Моя текущая идея состоит в том, что у меня будет Vertex учебный класс:

public class Vertex {
    private enum Element{ FARMER, SHEEP, WOLF, CABBAGE }
    private Element type;
    private List<Edge> neighbors;

    public Vertex(Element e){
        type = e;
    }
    public List getNeighbors(){
        return this.neighbors;
    }

    public void AddEdge(Vertex destination, int depth){
        neighbors.add(new Edge(destination, depth));
        destination.neighbors.add(new Edge(this, depth));
    }
    private static class Edge {
        public Vertex destination;
        public int depth;

        public Edge(Vertex destination, int depth){
            this.destination = destination;
            this.depth = depth;
        }
    }
}

Я также хочу создать Graph класс, который содержит collection (HashMap, TreeMap или другой тип структуры данных) вершин & ребер в виде поля. Он также будет содержать поле из двух объектов моего Bank класс для представления южной и северной сторон реки.

Как вы можете видеть в Vertex класс, я создал перечисление с именем Element который содержит FARMER, SHEEP, WOLF, CABBAGE, Прочитав JavaDoc относительно реализаций Map, я склоняюсь к использованию EnumMap как тип моей карты. В конце концов мне нужно будет выполнить итерацию по этим данным как в поиске BreadFirst, так и в поиске DepthFirst, но я не могу думать ни о каких причинах, почему одна реализация Map была бы лучше, чем другая, для этой цели.

Я узнал о EnumMap только из чтения JavaDoc, а не из класса, поэтому я хочу убедиться, что я не пропускаю никакой важной информации, которая сделала бы эту идею плохой...

Итак, мой вопрос: имеет ли смысл использовать EnumMap в этом контексте, или другая реализация Map имеет больше смысла?

Если вам нужно больше разъяснений или справочной информации, пожалуйста, дайте мне знать.

Answer 1

Мне кажется, что состояние банка должно идти в вершине, а тип ребра должен быть одним из четырех возможных (три доступных животных или он сам). Хэш-набор будет полезен для обнаружения циклов в графе, но для этого, очевидно, требуется правильный метод equals и hashCode для вашего класса Vertex.

Класс Graph не должен содержать коллекцию ребер. Для этого просто нужна ссылка на исходную вершину, а также любое количество служебных методов.

Что касается EnumMap, каждая вершина может использовать это, чтобы сохранить ребра для следующей вершины.