时间戳

首页 > 解决方案 > 您可以混合使用抽象数据类型吗？例如地图的优先队列？

java - 您可以混合使用抽象数据类型吗？例如地图的优先队列？

问题描述

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

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

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

我对 Java 或数据结构没有那么丰富的经验，但我真的很喜欢这种方法。任何帮助将不胜感激！

标签： javaalgorithmdictionarypriority-queueabstract-data-type

解决方案

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

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

这可以通过Comparator向优先级队列提供自定义来实现。比较器获取对象（在我们的例子中是两个网格单元）并返回两者中哪个更小（或者在优先级队列的概念中，先出现）。我们的特殊比较器将需要使用Map组合数来访问。一旦有了这个访问权限，比较两个GridCells 就很容易了。这是comaprator：

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。

推荐阅读