1

ですから、私は問題に取り組んできました。基本的な前提は、任意のサイズのグリッドが与えられた場合、「ツアー」の数を計算する必要があるということです。ツアーは、左上のポイント（ポイントx = 1、y = 1を使用）で開始し、左下のポイント（x = 1 y = max、「y」の最大値に関係なく）で終了する実行です。 ）。これに加えて、途中で1つおきのポイントに接触する必要があり、グリッド内の任意のポイントに1回しかアクセスできません。

以下に書いているように、42〜45秒で実行されますが、可能であれば30秒以内で実行されるようにしたいと思います。それで、あなたへの私の質問、それをより速く走らせるために私は何を変えたり、取り除いたりすることができますか？

私はすべてを静的ではなく、クラスをインスタンス化しようとしました（これにより実行時間が数秒長くなりました）。

import java.awt.Point;
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;
import java.util.Date;

public class CodingPuzzle
{
public static List<Point> lAllPoints = new ArrayList<Point>();
public static int iMaxX;
public static int iMaxY;
public static int iCompletePaths = 0;

public static void depthFirstSearch(Point current, Stack<Point> result)
{
    if (result.contains(current))
        return;

    result.push(current);

    if (current.x == 1 && current.y == iMaxY && result.size() == iMaxX*iMaxY)
    {
        // This is a complete path
        iCompletePaths++;
    }
    for (Point p: getPossibleMoves(current))
    {
        depthFirstSearch(p, result);
    }

    // No path was found
    result.pop();
    return;
}

public static List<Point> getPossibleMoves (Point fromPoint)
{
    int iCurrentPointIndex = lAllPoints.indexOf(fromPoint);
    List<Point> lPossibleMoves = new ArrayList<Point>();

    if (fromPoint.x == 1 && fromPoint.y == 1)
    {
        // Top left point
        lPossibleMoves.add(lAllPoints.get(iCurrentPointIndex + 1));
        lPossibleMoves.add(lAllPoints.get(iCurrentPointIndex + iMaxY));
    }

    else if (fromPoint.x == 1 && fromPoint.y == iMaxY)
    {
        // Bottom left point. Should always be the last point. No valid moves.
        // If a path gets here before the end it shouldn't need to continue.
    }

    else if (fromPoint.x == iMaxX && fromPoint.y == 1)
    {
        // Top right point
        lPossibleMoves.add(lAllPoints.get(iCurrentPointIndex - iMaxY));
        lPossibleMoves.add(lAllPoints.get(iCurrentPointIndex + 1));
    }

    else if (fromPoint.x == iMaxX && fromPoint.y == iMaxY)
    {
        // Bottom right point
        lPossibleMoves.add(lAllPoints.get(iCurrentPointIndex - iMaxY));
        lPossibleMoves.add(lAllPoints.get(iCurrentPointIndex - 1));
    }

    else if (fromPoint.x == 1 && fromPoint.y != iMaxY)
    {
        // Any other point on the left side
        lPossibleMoves.add(lAllPoints.get(iCurrentPointIndex - 1));
        lPossibleMoves.add(lAllPoints.get(iCurrentPointIndex + 1));
        lPossibleMoves.add(lAllPoints.get(iCurrentPointIndex + iMaxY));
    }

    else if (fromPoint.x == iMaxX)
    {
        // Any other point on the right side
        lPossibleMoves.add(lAllPoints.get(iCurrentPointIndex - 1));
        lPossibleMoves.add(lAllPoints.get(iCurrentPointIndex + 1));
        lPossibleMoves.add(lAllPoints.get(iCurrentPointIndex - iMaxY));
    }

    else if (fromPoint.y == 1)
    {
        // Any other point on the top
        lPossibleMoves.add(lAllPoints.get(iCurrentPointIndex + 1));
        lPossibleMoves.add(lAllPoints.get(iCurrentPointIndex - iMaxY));
        lPossibleMoves.add(lAllPoints.get(iCurrentPointIndex + iMaxY));
    }

    else if (fromPoint.y == iMaxY && fromPoint.x != 1)
    {
        // Any other point on the bottom
        lPossibleMoves.add(lAllPoints.get(iCurrentPointIndex - 1));
        lPossibleMoves.add(lAllPoints.get(iCurrentPointIndex - iMaxY));
        lPossibleMoves.add(lAllPoints.get(iCurrentPointIndex + iMaxY));
    }

    else
    {
        // Any other point not on an edge.
        lPossibleMoves.add(lAllPoints.get(iCurrentPointIndex + 1));
        lPossibleMoves.add(lAllPoints.get(iCurrentPointIndex - 1));
        lPossibleMoves.add(lAllPoints.get(iCurrentPointIndex - iMaxY));
        lPossibleMoves.add(lAllPoints.get(iCurrentPointIndex + iMaxY));
    }

    return lPossibleMoves;
}

public static void setUpGrid(int x, int y)
{
    iMaxX = x;
    iMaxY = y;
    for (int i = 1; i <= x; i++)
        for (int j = 1; j <= y; j++)
            lAllPoints.add(new Point(i, j));
}

public static void main(String[] args)
{
    Date start = new Date(System.currentTimeMillis());
    setUpGrid(10, 4);
    Stack<Point> sCurrentPoints = new Stack<Point>();
    depthFirstSearch(lAllPoints.get(0), sCurrentPoints);
    Date end = new Date(System.currentTimeMillis());
    long total = end.getTime() - start.getTime();
    System.out.println(iCompletePaths + " paths found in " + total/1000 + " seconds.");
}
4

3 に答える 3

3

カウントを取得するためにコードが実行している作業の量を減らします。

public class CodingPuzzle2 {
    private final int width;
    private final int height;

    public CodingPuzzle2(int width, int height) {
        this.width = width;
        this.height = height;
    }

    public int countPaths(int x, int y) {
        boolean[][] visited = new boolean[width][height];
        int[] count = {0};
        countPaths(x, y, visited, 1,  count);
        return count[0];
    }

    private void countPaths(int x, int y, boolean[][] visited, int depth, int[] count) {
        if (x < 0 || x >= width || y < 0 || y >= height || visited[x][y])
            return;
        visited[x][y] = true;
        try {
            if (x == 0 && y == height - 1) {
                if (depth == width * height)
                    count[0]++;
                return;
            }
            countPaths(x, y + 1, visited, depth+1, count);
            countPaths(x + 1, y, visited, depth+1, count);
            countPaths(x - 1, y, visited, depth+1, count);
            countPaths(x, y - 1, visited, depth+1, count);
        } finally {
            visited[x][y] = false;
        }
    }

    public static void main(String... args) {
        long start = System.nanoTime();
        CodingPuzzle2 cp = new CodingPuzzle2(10,4);
        int count = cp.countPaths(0, 0);
        long time = System.nanoTime() - start;
        System.out.printf("%,d paths found in %.3f seconds.%n", count, time / 1e9);
    }
}

プリント

2,329 paths found in 1.758 seconds.
于 2012-04-16T17:01:03.277 に答える
0

私が最初にすることはあなたのコードをプロファイリングすることです（ピーターがあなたの質問へのコメントで言ったように）。どこで時間を過ごしているかを知らずに「物事を速くする」ことは難しい。しかし、あなたのアルゴリズムはやや非効率的かもしれません。プロファイリングには、OracleJVMに付属しているjvisualvmを使用できます。

グラフのハミルトンパスを解くためのアルゴリズムを調べたいと思うかもしれません。これは事実上あなたがしていることです。ブルートフォースよりも効率的なソリューションがあります。

于 2012-04-16T16:43:56.233 に答える
0

他の人が言うこと。それはあなたがより良いプログラマーになるのを助けるでしょう。

それ以外に、これがあなたが探しているクイックウィンですStack-Deque 、つまりArrayDequeに切り替えます。この1回の変更で、私のJava 7 -serverマシンでは44％高速になりました。

于 2012-04-16T16:50:47.323 に答える