*算法在解决滑动瓦片难题时执行了很长时间

Question

当尝试运行24个Tile字谜和更高版本的代码时，代码会执行很长时间(大于3分钟)(对于8个Tile字谜，它运行得相当快)。代码可以在下面找到。

while (openQueue.isEmpty() == false) {
    State queueHead = openQueue.remove();
    openMap.remove(queueHead.hashCode());
    closedMap.put(queueHead.hashCode(), queueHead);
    State queueHeadState = queueHead;

    if (Constants.debug) {
        System.out.println("Popped State");
        HeuristicSolverUtility.printState(queueHead);   
    }
    // If reached goal state . Termination condition.
    if (queueHead.equals(goalState)) {
        break;
    } else {
        List<Action> listOfPossibleActions = queueHeadState
                .getPossibleActions();
        Iterator<Action> actIter = listOfPossibleActions.iterator();
        while (actIter.hasNext()) {
            // Here it performs Tile UP, DOWN, LEFT and RIGHT operations 
            Action actionOnState = actIter.next();
            StateP newState = actionOnState.applyTo(queueHeadState);
            newState.setHeuristicCost((double) ManhattanDistance
                    .calculate(newState));
            newState.setParent(queueHead);
            newState.setAction(actionOnState);

            if (!closedMap.containsKey(newState.hashCode()) && !openMap.containsKey(newState.hashCode())) {
                openQueue.offer(newState);
                openMap.put(newState.hashCode(), newState);
            } else if (openMap.containsKey(newState.hashCode())) {
                System.out.println("State found in Open Map");
                State stateFetchedFromOpenMap = openMap.get(newState.hashCode());
                if (stateFetchedFromOpenMap.getPathCost() > newState.getPathCost()) {
                    openMap.remove(stateFetchedFromOpenMap.hashCode());
                    openMap.put(newState.hashCode(), newState);
                    openQueue.remove(stateFetchedFromOpenMap);
                    openQueue.add(newState);
                }
            }
        }
    }
}

这是我的哈希码：

    @Override
    public int hashCode() {
        return Arrays.hashCode(allCells);       
    }

这是优先级队列比较器的代码：

public static class HeuristicComparator implements Comparator<State> {
    public int compare(State o1, State o2) {
        Double result;

        result = o1.getKey() - o2.getKey();
        if (result == 0.0) {
            // Ties among minimal f values are resolved in favor of the
            // deepest node in the search tree
            // i.e. the closest node to the goal
            result = (double) (o2.getPathCost() - o1.getPathCost());
        }
        if (result > 0.0) {
            return 1;
        }
        return -1;
    }
}

我不确定为什么我的A*实现花了这么长时间来计算24瓦片以上的拼图。我如何优化我的代码以更快地计算，还有什么bug导致它花了这么长时间吗？

如果您对整个代码感兴趣，可以在here中找到

Answer 1

正如Turing85提到的，这是一个NP完全问题，因此您不太可能拥有快速的运行时。

我建议您可以执行以下操作：

尝试使用different heuristic

• Try来使用bidirectional search

的

Answer 2

我知道这是一个老生常谈的问题，但我也遇到了同样的问题。

显然，Arrays.hashCode(allCells);真的很慢，使用另一个散列代码可以使算法运行得更快。

尝试使用this answer获取替代散列。