你能混合使用抽象数据类型吗？例如地图的优先队列？

Question

我正在做一个解决数独的项目。它是我大学模块的一部分，虽然我一直在计划我的方法，但我想尝试使用优先级队列来决定接下来在数独中处理哪个单元格。

我应该在优先级队列中存储什么？

我想我可以存储单元格（例如网格[x][y]），但是，这是棘手的部分。我通过可以进入单元格的可能组合的数量计算出某个位置的单元格的优先级。但是我没有办法存储每个单元格有多少组合，所以我在考虑使用地图数据类型将网格位置存储为键，将可能的组合存储为值。然后我要使用这些值的优先级队列，这些值会指向网格位置。

我在 Java 或数据结构方面经验不足，但我真的很喜欢考虑这种方法。非常感谢任何帮助！

Answer 1

由于您尚未发布代码，因此我无法评论这是否是最佳方法。但是你的问题的答案是是.

让我先总结一下你想要实现的（我的理解）：你有几个对象（网格单元或它们的坐标）。您还有一张地图，为这些对象中的每一个分配了优先级。您现在想要建立一个优先级队列，根据地图中的优先级对对象进行排序。

这可以通过向优先级队列提供自定义 Comparator 来实现。比较器接受对象（在我们的例子中是两个网格单元）和 returns 两者中哪个较小（或者在优先级队列的概念中，哪个先出现）。我们的特殊比较器需要访问 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);
    }
}

当您运行这段代码时，您将看到以下输出：

这些是 GridCell ids 从高到低排列的组合。

你能混合使用抽象数据类型吗？例如地图的优先队列？

Can you use a mix of abstract data types? e.g. a priority queue of maps?

java

algorithm

dictionary

priority-queue

abstract-data-type