基于递归的Java城市网络资源分配问题及代码修复

问题背景 #

给定城市网络，需为至多numCities个城市分配资源，确保所有城市自身有资源或邻接城市有资源。城市以String为键存入HashMap，邻接城市存为对应Set；numCities为最大可分配城市数，supplyLocations存储已分配资源的城市。尝试用递归求解，但两种实现均存在问题：第一种维护未覆盖城市集合的方案始终返回false；第二种通过硬检查覆盖状态的方案存在逻辑错误，比如numCities为1时错误返回true。

第一种实现（维护未覆盖集合） #

代码 #

public static boolean allocate(HashSet<String> to_visit, HashMap<String, HashSet<String>> roadNetwork, int numCities, HashSet<String> supplyLocations) {
    if (to_visit.size() == 0) { 
        return true; 
    }
    if (numCities == 0) { 
        return false; 
    }
    else { 
        for (String city : roadNetwork.keySet()) {
            Set<String> cities_and_neighbors = new HashSet<String>();
            cities_and_neighbors.add(city); 
            if (roadNetwork.get(city) != null) {
                cities_and_neighbors.addAll(roadNetwork.get(city)); 
            }
            for (String adjacent_city : cities_and_neighbors) { 
                supplyLocations.add(adjacent_city);
                
                HashSet<String> added_city = new HashSet<String>();
                added_city.add(adjacent_city); 
                if (roadNetwork.get(adjacent_city) != null) {
                    added_city.addAll(roadNetwork.get(adjacent_city)); 
                    to_visit.removeAll(added_city);
                }
                
                if (allocate(to_visit, roadNetwork, numCities-1, supplyLocations) == true) {
                    return true; 
                }
                
                to_visit.addAll(added_city);
                supplyLocations.remove(adjacent_city); 
            }
        }
    }
    return false; 
}

public static boolean allocateResources(HashMap<String, HashSet<String>> roadNetwork, int numCities, HashSet<String> supplyLocations) {
    HashSet<String> to_visit = new HashSet<String>(); 
    for (String city : roadNetwork.keySet()) { 
        to_visit.add(city); 
    }
    boolean can_allocate = allocate(to_visit, roadNetwork, numCities, supplyLocations); 
    return can_allocate; 
}

问题分析 #

• 错误的分配逻辑：代码遍历当前城市的邻接集合，将所有邻接城市也加入supplyLocations，但需求是选择单个城市分配资源，而非批量分配，这直接偏离核心需求，导致递归分支全部无效。
• 未覆盖集合修改混乱：每次处理邻接城市时，错误地移除该城市及其邻接区域，且循环重复处理同一批城市，导致to_visit被反复篡改，最终所有递归路径都失败，返回false。

第二种实现（硬检查覆盖状态） #

代码 #

public static boolean allocateResources(Map<String, HashSet<String>> roadNetwork, int numCities, Set<String> supplyLocations) {
    if (all_covered(roadNetwork, supplyLocations) == true && supplyLocations.size() <= numCities) {
        return true;
    }
    
    if (numCities == 0) {
        return true;
    }
    for (String city : roadNetwork.keySet()) {
        HashSet<String> to_search = new HashSet<String>();
        to_search.add(city);
        if (roadNetwork.get(city) != null) {
            to_search.addAll(roadNetwork.get(city));
        }
        
        supplyLocations.add(city);
        if (allocateResources(roadNetwork, numCities-1, supplyLocations) == true) {
            return true;
        } else {
            supplyLocations.remove(city);
            return false;
        }
    }
    return false;
}

public static boolean all_covered(Map<String, HashSet<String>> roadNetwork, Set<String> supplyLocations) {
    for (String cities : roadNetwork.keySet()) {
        if (is_covered(cities, roadNetwork, supplyLocations) == false) {
            return false;
        }
    }
    return true;
}

public static boolean is_covered(String city, Map<String, HashSet<String>> roadNetwork, Set<String> supplyLocations) {
    HashSet<String> to_check = new HashSet<String>();
    to_check.add(city);
    if (roadNetwork.get(city) != null) {
        to_check.addAll(roadNetwork.get(city));
    }
    for (String allocate : to_check) {
        if (supplyLocations.contains(allocate)) {
            return true;
        }
    }
    return false;
}

问题分析 #

• numCities为0时的逻辑错误：当没有剩余分配名额时，直接返回true，但此时若仍有城市未被覆盖，应返回false，这是导致numCities=1等场景错误返回的核心原因。
• 循环提前终止：遍历城市时，只要第一个城市的递归分支失败就直接返回false，未尝试其他城市的分配可能，导致无法找到正确方案。

修复方案（修复第二种实现） #

针对第二种实现的核心问题，修改后的代码如下：

public static boolean allocateResources(Map<String, HashSet<String>> roadNetwork, int numCities, Set<String> supplyLocations) {
    // 检查是否已覆盖所有城市
    if (all_covered(roadNetwork, supplyLocations)) {
        return true;
    }
    // 无剩余名额且未覆盖全部城市，返回false
    if (numCities == 0) {
        return false;
    }
    // 遍历所有城市尝试分配
    for (String city : roadNetwork.keySet()) {
        // 跳过已分配的城市，避免重复递归
        if (supplyLocations.contains(city)) {
            continue;
        }
        // 选择当前城市分配资源
        supplyLocations.add(city);
        // 递归尝试剩余分配名额
        if (allocateResources(roadNetwork, numCities - 1, supplyLocations)) {
            return true;
        }
        // 回溯：移除当前城市的分配
        supplyLocations.remove(city);
    }
    // 所有尝试均失败
    return false;
}

// 原覆盖检查方法优化，提升可读性
public static boolean all_covered(Map<String, HashSet<String>> roadNetwork, Set<String> supplyLocations) {
    for (String city : roadNetwork.keySet()) {
        if (!is_covered(city, roadNetwork, supplyLocations)) {
            return false;
        }
    }
    return true;
}

public static boolean is_covered(String city, Map<String, HashSet<String>> roadNetwork, Set<String> supplyLocations) {
    // 自身有资源则直接覆盖
    if (supplyLocations.contains(city)) {
        return true;
    }
    // 检查邻接城市是否有资源
    HashSet<String> neighbors = roadNetwork.get(city);
    if (neighbors != null) {
        for (String neighbor : neighbors) {
            if (supplyLocations.contains(neighbor)) {
                return true;
            }
        }
    }
    return false;
}

修复说明 #

1. 修正numCities=0的逻辑：无剩余名额时，仅当已覆盖所有城市才返回true，否则返回false，解决原逻辑错误。
2. 取消循环提前终止：移除原代码中递归失败后的直接返回false，确保遍历所有可能的城市分配方案。
3. 避免重复分配：增加已分配城市的检查，跳过无效递归分支。
4. 优化覆盖检查逻辑：简化is_covered方法的判断流程，提升代码可读性。

内容的提问来源于stack exchange，提问作者user22532748