java-解决滑动拼图难题时的A *算法执行时间很长
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了java-解决滑动拼图难题时的A *算法执行时间很长,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含2407字,纯文字阅读大概需要4分钟。
内容图文
尝试运行24个Tile拼图及以上版本的代码时,代码执行时间很长(大于3分钟)(对于8 Tile Puzzle而言,运行速度非常快).该代码可以在下面找到.
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个拼板拼图及以上版本.如何优化代码以更快地进行计算,是否还有任何导致其花费这么长时间的错误?
如果您对整个代码感兴趣,可以找到here
解决方法:
正如Turing85所提到的,这是一个NP完全问题,因此您不太可能拥有快速的运行时间.
我建议您可以执行以下操作:
>尝试使用different heuristic
>尝试使用bidirectional search
内容总结
以上是互联网集市为您收集整理的java-解决滑动拼图难题时的A *算法执行时间很长全部内容,希望文章能够帮你解决java-解决滑动拼图难题时的A *算法执行时间很长所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。