高分多線程問題

Question

大家好，有关knight's tour的問題 現在我想用多線程 幷發該如何解決  主要是用到生產者消費者以及工作隊列。要求worker不斷從工作隊列中獲得Path p 然後進行處理 如果不清楚knight's tour的 可以看下我下面的代碼，只要把這段代碼改成幷發執行的 就OK了，時間在26號中午之前。先謝謝了！！
// Find a *single* closed knight's tour 
// (Sequential & iterative version, not optimised)import java.util.*;class Position {

static final int numRows = 3; // number of rows on board
static final int numCols = 10; // number of columns on board

static final Position end1 = new Position(1,2); // possible end positions (start is (0,0) 
static final Position end2 = new Position(2,1); // other possible end position 

private int row; // row number, o<=i<numRows
private int col;  // column number, o<=j<numCols
Position(int row0,int col0) {
row = row0; col = col0;
}

public boolean equals(Object obj) { // compare with another position
if (obj==null) return false;
Position p = (Position) obj;
return (p.row==row && p.col==col);
} Position[]  knightMoves() { //list of knight's possible moves from here
Position[] temp = new Position[8];
int count = 0; // temp[0..count-1] holds results
int[] xStep = {2, 2, -2, -2, 1, 1, -1, -1}; // potential moves are (row+yStep[k],col+xStep[k]) for each index k
int[] yStep = {1, -1, 1, -1, 2, -2, 2, -2}; 
for (int k=0; k<xStep.length; k++) { // check that each potential move stays on board
int x = row+yStep[k];
int y = col+xStep[k];
if (0<=x && x<numCols && 0<=y && y<numRows) {
temp[count] = new Position(x,y); count++;
}
}
Position[]  result = new Position[count];
for (int k=0; k<count; k++)
result[k] = temp[k];
return result;
}

void putPosition() { // print position
System.out.print("("+row+","+col+")");
}
}class Path {  // non-empty path of Position's

private Position start;  // one end position in path (other is (0,0))
private Path next;  // path following start node (may be null) 
private int pathLength;  // length of path

Path(Position start0, Path next0) {
start = start0; next = next0;
if (next==null)
pathLength = 1;
else
pathLength = 1 + next.pathLength;
}

boolean contains(Position p) { // does p occur in this path?
if (start.equals(p)) return true;
else if (next==null) return false;
else return next.contains(p);
}
Position[]  pathMoves() { // new positions to extend path
return start.knightMoves();
} boolean pathComplete() { // does the path cover the entire board?
int tourLength = Position.numRows*Position.numCols;
return pathLength == tourLength;
}

boolean pathClosed() { // is the path (assumed complete) closed?
return start.equals(Position.end1) || start.equals(Position.end2);
}

void putPath() { // print path
start.putPosition();
if (next!=null) {
System.out.print(":");
next.putPath();
}
}

}class KnightsTourSingleItSeq {   
    
    private static void knightsTour() { 
     LinkedList<Path> workQ = new LinkedList<Path>();
     workQ.add(new Path(new Position(0,0), null));
     while (!workQ.isEmpty()) {               
     Path path = workQ.removeLast(); 
     Position[] moves = path.pathMoves();
     for (Position pos : moves) {
     if (!path.contains(pos)) {    
Path newPath = new Path(pos, path);
     if (newPath.pathComplete()) {
     if (newPath.pathClosed()) 
     newPath.putPath();
     System.out.println();
     return;
     }
     else workQ.add(newPath);
     }
     }
     }       
    } public static void main(String[] args) {
long startTime = System.nanoTime();
        knightsTour(); 
long endTime = System.nanoTime();
long time = (endTime-startTime)/1000000;
System.out.println("Running time = " + time);
}
}

Answer 1

静观手头不忙的大牛给你解答吧

Answer 2

这本身只是个算法题目 和多线程没有关系  硬要把它改成多线程 有点为多线程而多线程的意思思路：由生产者去找路径 然后加入到队列中  然后消费者去队列中获取路径 并判断是否正确  lz是这个思路吗？但其实 仔细想想 这只是个生产者找路径的问题   既然生产者已经找到路径了   再让消费者去判断一下不是多次一举吗？

Answer 3

思路是这样，这是我的作业所以先不管实际意义，能实现就好

Answer 4

而且，并发执行的速度肯定比顺序执行的快，这也是作业标准，所以还是有必要多线程的