无环无向图燃料源半径优化问题求解咨询

问题概述 #

• 问题定义：给定无环无向树结构（节点数=边数+1），每个节点为燃料源；每条边上有若干等距灯具（间距1米），燃料源仅能为相邻边中自身半径范围内的灯具供电，燃料消耗量等于其半径值（例如半径2消耗2升燃料）。
• 优化目标：确定各燃料源的最优半径，在覆盖所有灯具的前提下，最小化总燃料消耗。
• 当前实现缺陷：采用贪心算法（每次选择剩余未覆盖灯具最多的节点，将其半径扩展1单位），但在复杂测试用例中计算结果存在偏差，无法得到最优解。

问题示例 #

输入为6个节点的树结构，边信息如下：

6     // 节点总数
0 1 3 // 节点0与节点1之间的边有3个灯具
1 2 1 // 节点1与节点2之间的边有1个灯具
2 3 2 // 节点2与节点3之间的边有2个灯具
1 4 2 // 节点1与节点4之间的边有2个灯具
1 5 2 // 节点1与节点5之间的边有2个灯具

该示例的最优解总燃料消耗为5。

当前C++实现代码 #

数据结构与边添加函数 #

struct light {
    int count;
};

struct node {
    int d;
    light* l;
};

std::vector<node*>* tree;
int numVertices;

// 根据输入添加边
void AddEdge(int src, int dest, int lights) {
    light* l = new light{ lights };
    tree[src].push_back(new node{ dest, l });
    tree[dest].push_back(new node{ src, l });
}

贪心求解函数 #

void Solve() {
    int fuel = 0;

    while (true) {
        int maxNode = 0;
        int maxNodeLights = 0;

        for (int A = 0; A < numVertices; A++)
        {
            int lightsOnNode = 0;

            for (node* B : tree[A])
            {
                lightsOnNode += B->l->count;
            }

            if (lightsOnNode > maxNodeLights) {
                maxNodeLights = lightsOnNode;
                maxNode = A;
            }
        }

        if (maxNodeLights > 0) {
            bool addedRange = false;

            for (node* B : tree[maxNode])
            {
                if (B->l->count > 0) {
                    B->l->count--;
                    addedRange = true;
                }
            }

            if (addedRange) {
                fuel++;
            }
        }
        else {
            break;
        }
    }

    std::cout << fuel << '\n';
}

失败测试用例 #

测试用例1 #

1 0 4
2 1 1
3 2 4
4 3 1
5 1 2
6 1 1
7 2 2
8 3 2
9 1 1
10 1 3
11 5 1
12 0 2
13 10 4
14 3 3
15 5 4

• 当前代码输出：16
• 正确输出：17

测试用例2 #

1 0 2
2 1 3
3 2 2
4 1 4
5 4 3
6 3 2
7 5 3
8 3 4

• 当前代码输出：10
• 正确输出：11

测试用例3 #

1 0 4
2 0 3
3 0 4
4 3 3
5 2 2
6 3 1
7 2 1
8 3 2
9 3 2
10 2 1
11 9 1
12 4 2
13 5 2
14 8 2
15 9 1
16 14 2
17 3 3
18 3 4

• 当前代码输出：15
• 正确输出：16

需求 #

寻求能够正确解决该问题的最优算法方案。

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