8balls 实现的 DSF BFS 和 A* 搜索任务

Question

我正在尝试使用 dfs、bfs 和 A* 搜索来解决任务，目前我完全是堆栈。任务如下：有 4 个黑球和 4 个白球，将黑、白、黑、白等一一组织起来。也有 2 个空位。需要重新排列球，使 4 个黑球和 4 个白球排成一行。只能移动位于一起的 2 个球。例如，假设 1 - 黑球，0 - 白球

1 0 1 0 _ _ 1 0 1 0

1 0 1 0 0 1 1 - - 0

_ _ 1 0 0 1 1 1 0 0

我无法在脑海中想象和构建图表，非常感谢任何建议

Answer 1

我在Java中写了下面的代码。有 2 个状态 "black, white and empty"。我还描述并添加了球所在的线条。我认为它将按照 DFS 原则工作。有人可以告诉我我是对的吗？代码是否遵循 DFS？

import java.util.ArrayList;
import java.util.List;

public class DepthFirstSearch {

    private List<Vertex> vertexList = new ArrayList<Vertex>(10);

    private Vertex v1 = Vertex.build(1, State.BLACK);
    private Vertex v2 = Vertex.build(2, State.WHITE);
    private Vertex v3 = Vertex.build(3, State.BLACK);
    private Vertex v4 = Vertex.build(4, State.WHITE);
    private Vertex v5 = Vertex.build(5, State.EMPTY);
    private Vertex v6 = Vertex.build(6, State.EMPTY);
    private Vertex v7 = Vertex.build(7, State.BLACK);
    private Vertex v8 = Vertex.build(8, State.WHITE);
    private Vertex v9 = Vertex.build(9, State.BLACK);
    private Vertex v10 = Vertex.build(10, State.WHITE);

    public DepthFirstSearch() {
        v2.setParentVertex(v1);
        v3.setParentVertex(v2);
        v4.setParentVertex(v3);
        v5.setParentVertex(v4);
        v6.setParentVertex(v5);
        v7.setParentVertex(v6);
        v8.setParentVertex(v7);
        v9.setParentVertex(v8);
        v10.setParentVertex(v9);

        v1.setChildVertex(v2);
        v2.setChildVertex(v3);
        v3.setChildVertex(v4);
        v4.setChildVertex(v5);
        v5.setChildVertex(v6);
        v6.setChildVertex(v7);
        v7.setChildVertex(v8);
        v8.setChildVertex(v9);
        v9.setChildVertex(v10);

        vertexList.add(v1);
        vertexList.add(v2);
        vertexList.add(v3);
        vertexList.add(v4);
        vertexList.add(v5);
        vertexList.add(v6);
        vertexList.add(v7);
        vertexList.add(v8);
        vertexList.add(v9);
        vertexList.add(v10);
    }

    private void run() {
        printVertex(v1);

        while (!isFinalResult()) {
            search(v1);
        }
    }

    private void search(Vertex vertex) {
        if (isFirstEmpty(vertex)) {
            State prevState = vertex.getParentVertex().getState();
            Vertex mVertex = null;

            for (Vertex v : vertexList) {
                if (hasPrevState(v, prevState)) {
                    mVertex = v;
                    break;
                }
            }

            State pState = mVertex.getState();
            State cState = mVertex.getChildVertex().getState();

            mVertex.setState(vertex.getState());
            mVertex.getChildVertex().setState(vertex.getChildVertex().getState());

            vertex.setState(pState);
            vertex.getChildVertex().setState(cState);

            findFinal(v1);

            System.out.println("=========================");
            printVertex(v1);
        } else {
            search(vertex.getChildVertex());
        }
    }

    private boolean isFirstEmpty(Vertex vertex) {
        return vertex.getState() == State.EMPTY && vertex.getChildVertex().getState() == State.EMPTY;
    }

    private boolean hasPrevState(Vertex vertex, State state) {
        return !vertex.isFinal() && vertex.getState() == state && vertex.getChildVertex().getState() != State.EMPTY;
    }

    private void findFinal(Vertex vertex) {
        final Vertex childVertex = vertex.getChildVertex();
        if (vertex.isFinal()) {
            findFinal(vertex.getChildVertex());
        } else if (vertex.getState() == State.BLACK && childVertex != null && childVertex.getState() == State.BLACK) {
            vertex.setFinal(true);
            findFinal(vertex.getChildVertex());
        } else {
            return;
        }
    }

    private void printVertex(Vertex vertex) {
        if (vertex != null) {
            System.out.println(vertex);
            printVertex(vertex.getChildVertex());
        }
    }

    private boolean isFinalResult() {
        boolean bResult = v1.getState() == State.BLACK;
        bResult &= v2.getState() == State.BLACK;
        bResult &= v3.getState() == State.BLACK;
        bResult &= v4.getState() == State.BLACK;
        bResult &= v5.getState() == State.WHITE;
        bResult &= v6.getState() == State.WHITE;
        bResult &= v7.getState() == State.WHITE;
        bResult &= v8.getState() == State.WHITE;
        return bResult;
    }

    public static void main(String[] args) {
        DepthFirstSearch search = new DepthFirstSearch();
        search.run();
    }
}

Answer 2

您描述的配置定义了一个状态。您可以将每个状态视为图中的一个顶点。你在两个状态之间有一个优势是有一个简单的移动，你可以应用到第一个状态以达到第二个状态。这是你的图表。

现在求解就是在初始状态对应的顶点和期望状态对应的顶点之间找到一条路径，你可以应用DFS、BFS、A*或任何你喜欢的图算法。

8balls 实现的 DSF BFS 和 A* 搜索任务

DSF BFS and A* search task with 8balls implementation

algorithm

sorting

depth-first-search

breadth-first-search