我正在做一个解决数独的项目。这是我大学模块的一部分,当我一直在计划我的方法时,我想尝试使用优先级队列来决定下一步在数独中使用哪个单元格。
我应该在优先级队列中存储什么?
我想我可以存储单元格(例如网格[x][y](,然而,这是棘手的部分。我通过可以进入单元格的可能组合的数量来计算某个位置单元格的优先级。但我无法存储每个单元格有多少组合,所以我想使用地图数据类型来存储网格位置作为关键字,并将可能的组合作为值。然后我将使用这些值的优先级队列,这些值将指向网格位置。
我对Java或数据结构没有那么多经验,但我真的很喜欢这种方法。任何帮助都将不胜感激!
由于您还没有发布代码,我无法评论这是否是最好的方法。但你的问题的答案是是的。
让我首先总结一下(我理解(你想要实现的目标:你有几个对象(网格单元或它们的坐标(。您还有一个为这些对象中的每个对象指定优先级的贴图。现在,您需要建立一个优先级队列,根据映射中的优先级对对象进行排序。
这可以通过将自定义Comparator
馈送到优先级队列来实现。比较器获取对象(在我们的例子中,是两个网格单元(,并返回两者中哪个较小(或者在优先级队列的概念中,哪个较小(。我们的特殊比较器将需要访问具有组合数量的Map
。一旦有了这种访问权限,比较两个GridCell
就非常容易了。这是指挥官:
class GridCellComparer implements Comparator<GridCell> {
// reference to the map with the number of combinations for each grid cell
Map<GridCell, Integer> combinations;
public GridCellComparer(Map<GridCell, Integer> combinations) {
this.combinations = combinations;
}
// calculate which grid cell comes first
public int compare(GridCell c1, GridCell c2) {
return combinations.get(c2) - combinations.get(c1);
}
}
要使用此比较器,我们需要使用PriorityQueue
的构造函数重载,该重载采用Comparator
。这种过载也会占用初始容量,我们可以将其设置为要添加的细胞数量:
PriorityQueue<GridCell> prio = new PriorityQueue<GridCell>(cells.size(), new GridCellComparer(combinations));
其余部分与任何其他优先级队列一样工作。您可以添加网格单元格等等。下面是一个完整的示例。代码的第一部分生成一些网格单元,并为它们设置一些组合。网格单元内的int n
仅用于在打印时识别它们。
import java.util.Map;
import java.util.HashMap;
import java.util.PriorityQueue;
import java.util.List;
import java.util.ArrayList;
import java.util.Comparator;
public class Example {
public static void main(String []args){
// map with the number of combinations for each cell
Map<GridCell, Integer> combinations = new HashMap<GridCell, Integer>();
// list of grid cells
List<GridCell> cells = new ArrayList<GridCell>();
for(int i = 0; i < 5; ++i)
cells.add(new GridCell(i));
// add number of combinations for each grid cell
combinations.put(cells.get(0), 2);
combinations.put(cells.get(1), 0);
combinations.put(cells.get(2), 6);
combinations.put(cells.get(3), 4);
combinations.put(cells.get(4), 10);
// instantiate the priority queue
PriorityQueue<GridCell> prio = new PriorityQueue<GridCell>(cells.size(), new GridCellComparer(combinations));
prio.addAll(cells);
// retrieve the grid cells in the order imposed by the number of combinations
while(!prio.isEmpty()) {
GridCell topCell = prio.poll();
System.out.println(topCell);
}
}
}
class GridCell{
// number to identify the cell
private int n;
public GridCell(int n) { this.n = n; }
public String toString(){
return Integer.toString(n);
}
}
class GridCellComparer implements Comparator<GridCell> {
// reference to the map with the number of combinations for each grid cell
Map<GridCell, Integer> combinations;
public GridCellComparer(Map<GridCell, Integer> combinations) {
this.combinations = combinations;
}
// calculate which grid cell comes first
public int compare(GridCell c1, GridCell c2) {
return combinations.get(c2) - combinations.get(c1);
}
}
当您运行此代码时,您将看到以下输出:
4
2
3
0
1
这些是从高组合数到低组合数排序的GridCell ID。