个人中心
文章发布
退出
作者热门文章
- html - 出于某种原因，IE8 对我的 Sass 文件中继承的 html5 CSS 不友好？
- JMeter 在响应断言中使用 span 标签的问题
- html - 在 :hover and :active? 上具有不同效果的 CSS 动画
- html - 相对于居中的 html 内容固定的 CSS 重复背景？
26
4
我正在寻找 8-puzzle 的解决方案使用 A* 算法 的问题。我找到了 this互联网上的项目。请查看文件 - proj1 和 EightPuzzle。 proj1 包含程序的入口点(main() 函数)，EightPuzzle 描述了拼图的特定状态。每个状态都是 8 拼图的一个对象。
感觉逻辑上没什么问题。但它会永远循环我尝试过的这两个输入:{8,2,7,5,1,6,3,0,4} 和 {3,1,6, 8,4,5,7,2,0}。它们都是有效的输入状态。代码有什么问题？
注意
PriorityQueue。 compareTo()函数在 EightPuzzle 类中实现。proj1 类的 main() 函数中的 p1d 的值来更改程序的输入。<{0,5,7,6,8,1,2,4,3}。花了大约 10 秒 并给出了 26 步 的结果。但是小程序在 0.0001 秒 内给出了 24 步 的结果，A*。f_n 为 11 或 12。他们似乎永远不会减少。所以一段时间后，PriorityQueue(openset) 中的所有状态都具有 11 或 12 的启发式。因此没有太多选择，可以扩展到哪个节点。因为最小的是11，最大的是12，这正常吗？while(openset.size() > 0){
EightPuzzle x = openset.peek();
if(x.mapEquals(goal))
{
Stack<EightPuzzle> toDisplay = reconstruct(x);
System.out.println("Printing solution... ");
System.out.println(start.toString());
print(toDisplay);
return;
}
closedset.add(openset.poll());
LinkedList <EightPuzzle> neighbor = x.getChildren();
while(neighbor.size() > 0)
{
EightPuzzle y = neighbor.removeFirst();
if(closedset.contains(y)){
continue;
}
if(!closedset.contains(y)){
openset.add(y);
}
}
}
EDIT4
我找到了这个无限循环的原因。看我的回答。但是执行起来大概需要25-30秒，这是相当长的时间。 A* 应该比这快得多。小程序在 0.003 秒 内完成此操作。 我将奖励改进性能的赏金。
为了快速引用，我粘贴了两个没有注释的类:
import java.util.*;
public class EightPuzzle implements Comparable <Object> {
int[] puzzle = new int[9];
int h_n= 0;
int hueristic_type = 0;
int g_n = 0;
int f_n = 0;
EightPuzzle parent = null;
public EightPuzzle(int[] p, int h_type, int cost)
{
this.puzzle = p;
this.hueristic_type = h_type;
this.h_n = (h_type == 1) ? h1(p) : h2(p);
this.g_n = cost;
this.f_n = h_n + g_n;
}
public int getF_n()
{
return f_n;
}
public void setParent(EightPuzzle input)
{
this.parent = input;
}
public EightPuzzle getParent()
{
return this.parent;
}
public int inversions()
{
/*
* Definition: For any other configuration besides the goal,
* whenever a tile with a greater number on it precedes a
* tile with a smaller number, the two tiles are said to be inverted
*/
int inversion = 0;
for(int i = 0; i < this.puzzle.length; i++ )
{
for(int j = 0; j < i; j++)
{
if(this.puzzle[i] != 0 && this.puzzle[j] != 0)
{
if(this.puzzle[i] < this.puzzle[j])
inversion++;
}
}
}
return inversion;
}
public int h1(int[] list)
// h1 = the number of misplaced tiles
{
int gn = 0;
for(int i = 0; i < list.length; i++)
{
if(list[i] != i && list[i] != 0)
gn++;
}
return gn;
}
public LinkedList<EightPuzzle> getChildren()
{
LinkedList<EightPuzzle> children = new LinkedList<EightPuzzle>();
int loc = 0;
int temparray[] = new int[this.puzzle.length];
EightPuzzle rightP, upP, downP, leftP;
while(this.puzzle[loc] != 0)
{
loc++;
}
if(loc % 3 == 0){
temparray = this.puzzle.clone();
temparray[loc] = temparray[loc + 1];
temparray[loc + 1] = 0;
rightP = new EightPuzzle(temparray, this.hueristic_type, this.g_n + 1);
rightP.setParent(this);
children.add(rightP);
}else if(loc % 3 == 1){
//add one child swaps with right
temparray = this.puzzle.clone();
temparray[loc] = temparray[loc + 1];
temparray[loc + 1] = 0;
rightP = new EightPuzzle(temparray, this.hueristic_type, this.g_n + 1);
rightP.setParent(this);
children.add(rightP);
//add one child swaps with left
temparray = this.puzzle.clone();
temparray[loc] = temparray[loc - 1];
temparray[loc - 1] = 0;
leftP = new EightPuzzle(temparray, this.hueristic_type, this.g_n + 1);
leftP.setParent(this);
children.add(leftP);
}else if(loc % 3 == 2){
// add one child swaps with left
temparray = this.puzzle.clone();
temparray[loc] = temparray[loc - 1];
temparray[loc - 1] = 0;
leftP = new EightPuzzle(temparray, this.hueristic_type, this.g_n + 1);
leftP.setParent(this);
children.add(leftP);
}
if(loc / 3 == 0){
//add one child swaps with lower
temparray = this.puzzle.clone();
temparray[loc] = temparray[loc + 3];
temparray[loc + 3] = 0;
downP = new EightPuzzle(temparray, this.hueristic_type, this.g_n + 1);
downP.setParent(this);
children.add(downP);
}else if(loc / 3 == 1 ){
//add one child, swap with upper
temparray = this.puzzle.clone();
temparray[loc] = temparray[loc - 3];
temparray[loc - 3] = 0;
upP = new EightPuzzle(temparray, this.hueristic_type, this.g_n + 1);
upP.setParent(this);
children.add(upP);
//add one child, swap with lower
temparray = this.puzzle.clone();
temparray[loc] = temparray[loc + 3];
temparray[loc + 3] = 0;
downP = new EightPuzzle(temparray, this.hueristic_type, this.g_n + 1);
downP.setParent(this);
children.add(downP);
}else if (loc / 3 == 2 ){
//add one child, swap with upper
temparray = this.puzzle.clone();
temparray[loc] = temparray[loc - 3];
temparray[loc - 3] = 0;
upP = new EightPuzzle(temparray, this.hueristic_type, this.g_n + 1);
upP.setParent(this);
children.add(upP);
}
return children;
}
public int h2(int[] list)
// h2 = the sum of the distances of the tiles from their goal positions
// for each item find its goal position
// calculate how many positions it needs to move to get into that position
{
int gn = 0;
int row = 0;
int col = 0;
for(int i = 0; i < list.length; i++)
{
if(list[i] != 0)
{
row = list[i] / 3;
col = list[i] % 3;
row = Math.abs(row - (i / 3));
col = Math.abs(col - (i % 3));
gn += row;
gn += col;
}
}
return gn;
}
public String toString()
{
String x = "";
for(int i = 0; i < this.puzzle.length; i++){
x += puzzle[i] + " ";
if((i + 1) % 3 == 0)
x += "\n";
}
return x;
}
public int compareTo(Object input) {
if (this.f_n < ((EightPuzzle) input).getF_n())
return -1;
else if (this.f_n > ((EightPuzzle) input).getF_n())
return 1;
return 0;
}
public boolean equals(EightPuzzle test){
if(this.f_n != test.getF_n())
return false;
for(int i = 0 ; i < this.puzzle.length; i++)
{
if(this.puzzle[i] != test.puzzle[i])
return false;
}
return true;
}
public boolean mapEquals(EightPuzzle test){
for(int i = 0 ; i < this.puzzle.length; i++)
{
if(this.puzzle[i] != test.puzzle[i])
return false;
}
return true;
}
}
import java.util.*;
public class proj1 {
/**
* @param args
*/
public static void main(String[] args) {
int[] p1d = {1, 4, 2, 3, 0, 5, 6, 7, 8};
int hueristic = 2;
EightPuzzle start = new EightPuzzle(p1d, hueristic, 0);
int[] win = { 0, 1, 2,
3, 4, 5,
6, 7, 8};
EightPuzzle goal = new EightPuzzle(win, hueristic, 0);
astar(start, goal);
}
public static void astar(EightPuzzle start, EightPuzzle goal)
{
if(start.inversions() % 2 == 1)
{
System.out.println("Unsolvable");
return;
}
// function A*(start,goal)
// closedset := the empty set // The set of nodes already evaluated.
LinkedList<EightPuzzle> closedset = new LinkedList<EightPuzzle>();
// openset := set containing the initial node // The set of tentative nodes to be evaluated. priority queue
PriorityQueue<EightPuzzle> openset = new PriorityQueue<EightPuzzle>();
openset.add(start);
while(openset.size() > 0){
// x := the node in openset having the lowest f_score[] value
EightPuzzle x = openset.peek();
// if x = goal
if(x.mapEquals(goal))
{
// return reconstruct_path(came_from, came_from[goal])
Stack<EightPuzzle> toDisplay = reconstruct(x);
System.out.println("Printing solution... ");
System.out.println(start.toString());
print(toDisplay);
return;
}
// remove x from openset
// add x to closedset
closedset.add(openset.poll());
LinkedList <EightPuzzle> neighbor = x.getChildren();
// foreach y in neighbor_nodes(x)
while(neighbor.size() > 0)
{
EightPuzzle y = neighbor.removeFirst();
// if y in closedset
if(closedset.contains(y)){
// continue
continue;
}
// tentative_g_score := g_score[x] + dist_between(x,y)
//
// if y not in openset
if(!closedset.contains(y)){
// add y to openset
openset.add(y);
//
}
//
}
//
}
}
public static void print(Stack<EightPuzzle> x)
{
while(!x.isEmpty())
{
EightPuzzle temp = x.pop();
System.out.println(temp.toString());
}
}
public static Stack<EightPuzzle> reconstruct(EightPuzzle winner)
{
Stack<EightPuzzle> correctOutput = new Stack<EightPuzzle>();
while(winner.getParent() != null)
{
correctOutput.add(winner);
winner = winner.getParent();
}
return correctOutput;
}
}
最佳答案
这是一个建议。对于您的示例，我的计时器报告 0 毫秒。对于此处给出的更难的拼图，需要 31 步才能完成，需要 96 毫秒。
HashSet 对于闭集比您的链表更有意义。它具有 O(1) 时间插入和成员资格测试，其中您的链接列表需要的时间与列表的长度成正比，列表的长度在不断增长。
您正在使用额外的数据结构和代码，使您的程序比需要的更复杂和更慢。多思考，少编码，学习别人好的代码来克服这个问题。我的并不完美(没有任何代码是完美的)，但它是一个起点。
我使用从每个图 block 的当前位置到其目标的曼哈顿距离的最大值作为启发式。启发式的选择不会影响解决方案中的步骤数，但会极大地影响运行时间。例如，h=0 将产生强力广度优先搜索。
请注意，为了让 A* 提供最佳解决方案，启发式永远不会高估达到目标的实际最小步数。如果这样做，找到的解决方案可能不是最短的。我不肯定“反转”启发式具有此属性。
package eightpuzzle;
import java.util.Arrays;
import java.util.Comparator;
import java.util.HashSet;
import java.util.PriorityQueue;
public class EightPuzzle {
// Tiles for successfully completed puzzle.
static final byte [] goalTiles = { 0, 1, 2, 3, 4, 5, 6, 7, 8 };
// A* priority queue.
final PriorityQueue <State> queue = new PriorityQueue<State>(100, new Comparator<State>() {
@Override
public int compare(State a, State b) {
return a.priority() - b.priority();
}
});
// The closed state set.
final HashSet <State> closed = new HashSet <State>();
// State of the puzzle including its priority and chain to start state.
class State {
final byte [] tiles; // Tiles left to right, top to bottom.
final int spaceIndex; // Index of space (zero) in tiles
final int g; // Number of moves from start.
final int h; // Heuristic value (difference from goal)
final State prev; // Previous state in solution chain.
// A* priority function (often called F in books).
int priority() {
return g + h;
}
// Build a start state.
State(byte [] initial) {
tiles = initial;
spaceIndex = index(tiles, 0);
g = 0;
h = heuristic(tiles);
prev = null;
}
// Build a successor to prev by sliding tile from given index.
State(State prev, int slideFromIndex) {
tiles = Arrays.copyOf(prev.tiles, prev.tiles.length);
tiles[prev.spaceIndex] = tiles[slideFromIndex];
tiles[slideFromIndex] = 0;
spaceIndex = slideFromIndex;
g = prev.g + 1;
h = heuristic(tiles);
this.prev = prev;
}
// Return true iif this is the goal state.
boolean isGoal() {
return Arrays.equals(tiles, goalTiles);
}
// Successor states due to south, north, west, and east moves.
State moveS() { return spaceIndex > 2 ? new State(this, spaceIndex - 3) : null; }
State moveN() { return spaceIndex < 6 ? new State(this, spaceIndex + 3) : null; }
State moveE() { return spaceIndex % 3 > 0 ? new State(this, spaceIndex - 1) : null; }
State moveW() { return spaceIndex % 3 < 2 ? new State(this, spaceIndex + 1) : null; }
// Print this state.
void print() {
System.out.println("p = " + priority() + " = g+h = " + g + "+" + h);
for (int i = 0; i < 9; i += 3)
System.out.println(tiles[i] + " " + tiles[i+1] + " " + tiles[i+2]);
}
// Print the solution chain with start state first.
void printAll() {
if (prev != null) prev.printAll();
System.out.println();
print();
}
@Override
public boolean equals(Object obj) {
if (obj instanceof State) {
State other = (State)obj;
return Arrays.equals(tiles, other.tiles);
}
return false;
}
@Override
public int hashCode() {
return Arrays.hashCode(tiles);
}
}
// Add a valid (non-null and not closed) successor to the A* queue.
void addSuccessor(State successor) {
if (successor != null && !closed.contains(successor))
queue.add(successor);
}
// Run the solver.
void solve(byte [] initial) {
queue.clear();
closed.clear();
// Click the stopwatch.
long start = System.currentTimeMillis();
// Add initial state to queue.
queue.add(new State(initial));
while (!queue.isEmpty()) {
// Get the lowest priority state.
State state = queue.poll();
// If it's the goal, we're done.
if (state.isGoal()) {
long elapsed = System.currentTimeMillis() - start;
state.printAll();
System.out.println("elapsed (ms) = " + elapsed);
return;
}
// Make sure we don't revisit this state.
closed.add(state);
// Add successors to the queue.
addSuccessor(state.moveS());
addSuccessor(state.moveN());
addSuccessor(state.moveW());
addSuccessor(state.moveE());
}
}
// Return the index of val in given byte array or -1 if none found.
static int index(byte [] a, int val) {
for (int i = 0; i < a.length; i++)
if (a[i] == val) return i;
return -1;
}
// Return the Manhatten distance between tiles with indices a and b.
static int manhattanDistance(int a, int b) {
return Math.abs(a / 3 - b / 3) + Math.abs(a % 3 - b % 3);
}
// For our A* heuristic, we just use max of Manhatten distances of all tiles.
static int heuristic(byte [] tiles) {
int h = 0;
for (int i = 0; i < tiles.length; i++)
if (tiles[i] != 0)
h = Math.max(h, manhattanDistance(i, tiles[i]));
return h;
}
public static void main(String[] args) {
// This is a harder puzzle than the SO example
byte [] initial = { 8, 0, 6, 5, 4, 7, 2, 3, 1 };
// This is taken from the SO example.
//byte [] initial = { 1, 4, 2, 3, 0, 5, 6, 7, 8 };
new EightPuzzle().solve(initial);
}
}
关于java - 8-Puzzle Solution 无限执行，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/13053455/
26
4
0
以下是来自Interviewstreet的问题我没有从他们的网站上得到任何帮助，所以在这里提问。我对算法/解决方案不感兴趣，但我不理解他们作为第二个输入示例给出的解决方案。任何人都可以帮助我理解问题陈
根据我的理解，创建一个可解决的滑动拼图必须遵循以下规则: A. If the grid width is odd, then the number of inversions in a solvabl
我编写了一系列函数来尝试解决 N 难题/8 难题。 我对自己处理拼图的能力感到非常满意，但在如何迭代和找到最佳路径方面苦苦挣扎。我的技能也不是 OOP，所以功能很简单。 这个想法显然是为了减少 her
我有些摩尔斯电码丢失了字母之间的空格，我的挑战是找出消息中所说的内容。到目前为止，由于可能存在大量的组合，我有点迷失了。 这是关于我收到的消息的所有信息。 输出将为英语 总是会有有意义的翻译 这是示例
如果我知道，变量 a,b,c,d,e 有多少可能的组合: a+b+c+d+e = 500 并且它们都是整数且 >= 0，所以我知道它们是有限的。 最佳答案 @Torlack、@Jason Cohen:
检查 n 的数组是否整数包含 3 个可以形成三角形的数字(即两个数字中任何一个的总和大于第三个)。 显然，这可以在 O(n) 中完成。时间。 (明显的 O(n log n) 解决方案是对数组进行排序，
我有兴趣实现 14-15 puzzle : 我正在创建一个值 0 - 15 按递增顺序排列的数组: S = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13
Closed. This question is off-topic。它当前不接受答案。 想要改善这个问题吗？ Update the question，所以它是用于堆栈溢出的on-topic。 已关闭
所以，我对数独游戏的生成做了大量的阅读。据我所知，获得所需难度的数独谜题的标准方法是生成一个谜题，然后对其进行评分，然后重复，直到获得可接受的评分。这可以通过使用一些更复杂的求解模式(XY-wing、
如何混合两个ARGB像素？ 例 在这里，A是（带有Alpha的红色），而B是（带有Alpha的蓝色）。 最佳答案 取自获得图像的同一Wikipedia文章： 转换为介于0到255之间的值： rOut
Closed. This question is off-topic。它当前不接受答案。 想改善这个问题吗？ Update the question，所以它是on-topic，用于堆栈溢出。 已关闭8
Joel 在他的 Guerrilla Guide to Interviewing 中提到计算一个字节中设置位的数量是一个编程问题。 ，并谈到了一种利用查找表中出现的模式的方法。在我发现这种模式后不久，
我在做一些回顾时遇到了这个报告的面试问题(以下引用是我找到的关于这个问题的所有信息): Given a function for a fair coin, write a function for a
我遇到了这个问题：说给定两个权重1和3，您可以权衡1,2（乘以3-1），3,4（乘以3 + 1）（使用平衡的两面）。现在找到最小的砝码数量，以便可以测量1到1000。 答案是1,3,9,27 ...
Locked. This question and its answers are locked因为该问题是题外话，但具有历史意义。它当前不接受新的答案或互动。 我使用这些规则制作了最终的笑声发生器。
左边是布局的正常状态。右边是布局的展开状态。 我的问题是我不知道如何让粉色框在它们的单元格中居中，并且随着布局向任何方向增长，粉色框之间的绿线连接起来。 只有这两个 View 的 AutoSizing
考虑以下代码: template struct S { }; template struct B; template class C> struct B> { void f() { } };
问题: 编写一个程序来删除出现在“所有”字符串中的片段，其中一个片段是 3 个或更多个连续的单词。 示例: 输入: s1 = "正在下雨，我想开车回家。"; s2 = "下雨了，我想去滑雪。"; s3
请检查以下程序。 #include struct st { int a ; } fn () { struct st obj ; obj.a = 10 ; return obj ; } int
我一直在研究这个 Prolog 逻辑问题。它得到了不正确的结果，运行程序本身需要一段时间，这是我更关心的。逻辑问题如下: Alex, Bret, Chris, Derek, Eddie, Fred,
我是一名优秀的程序员,十分优秀！