智慧港口调度系统 - 代码记录

1. 初始版本：基础框架与寻路

目标: 搭建 C++ 程序框架，实现地图读取、基础 BFS 寻路以及最简单的“找最近”贪心策略。

核心代码结构

// 核心结构体
struct Goods { int x, y, val; };
struct Robot { int has_goods, x, y, status; };

// BFS 寻路算法
// 输入起点和终点，返回下一步的最佳移动方向（0-3）
int bfs(int start_x, int start_y, int target_x, int target_y) {
    // 使用 std::queue 实现标准广度优先搜索
    // 记录 parent 数组用于回溯路径
}

// 主逻辑
int main() {
    load_map(); // 读取 maps/map1.txt
    while (read_frame_data()) {
        for (int i = 0; i < ROBOT_NUM; i++) {
            if (robots[i].has_goods) {
                // 策略：遍历所有泊位，找曼哈顿距离最近的
            } else {
                // 策略：遍历所有货物，找曼哈顿距离最近的
            }
            // 调用 BFS 计算移动方向并输出 move 指令
        }
        // 轮船逻辑：每帧尝试发送 go 指令
    }
}

---

2. 优化一：碰撞避免与防卡死

目标: 解决机器人互相穿模（移动到同一格子）的问题，以及在狭窄地形或冲突时卡死不动的情况。

改动详情

1. 引入占用标记: 增加 bool occupied[N][N] 数组，每帧开始时标记所有机器人当前位置。
2. 状态追踪: 在 Robot 结构体中增加 stuck_count（卡死计数）和 last_x, last_y（上一帧位置）。
3. 随机逃逸: 当机器人连续 5 帧位置未变时，强制执行随机移动以打破死锁。

struct Robot {
    // ... 原有字段
    int last_x = -1, last_y = -1;
    int stuck_count = 0; // 新增：卡死计数器
};

// 在 BFS 和移动判断中增加 occupied 检查
if (grid[nx][ny] != '*' && grid[nx][ny] != '#' && !occupied[nx][ny]) {
    // ...
}

// 防卡死逻辑
if (robots[i].x == robots[i].last_x && robots[i].y == robots[i].last_y) {
    robots[i].stuck_count++;
}
if (robots[i].stuck_count > 5) {
    // 随机选择一个可行的方向移动
}

---

3. 优化二：性价比优先策略 (Value Heuristic)

目标: 解决“捡芝麻丢西瓜”的问题。之前的策略只看距离，导致机器人可能会为了一个很近的 10 元货物，忽略稍远一点的 100 元货物。

改动详情

修改货物选择的评价函数，引入价值因素。

旧逻辑:

int d = abs(robots[i].x - goods_list[j].x) + abs(robots[i].y - goods_list[j].y);
if (d < best_dist) { ... } // 只看距离

新逻辑:

// 评价公式：价值 / (距离 + 1)
double score = (double)goods_list[j].val / (d + 1.0);
if (score > best_score) { ... } // 综合看性价比

---

4. 优化三：全局贪心任务分配 (Global Assignment)

目标: 解决多机器人抢夺同一货物，或分配不均（近水楼台先得月）的问题。之前的策略是机器人按 ID 顺序依次选择，ID 小的机器人可能会抢走离 ID 大的机器人更近的货物。

改动详情

不再让每个机器人独立选择，而是生成所有 (Robot, Good) 的候选对，按得分排序，优先满足高分匹配。

// 定义候选匹配对象
struct Candidate {
    int robot_id;
    int good_idx;
    double score;
    // 重载 < 运算符用于排序
    bool operator<(const Candidate& other) const {
        return score > other.score;
    }
};

// 主循环中的新逻辑
vector<Candidate> candidates;
// 1. 生成所有可能的 (机器人, 货物) 组合
for (int i = 0; i < ROBOT_NUM; i++) {
    if (robot_is_free) {
        for (int j = 0; j < goods_list.size(); j++) {
            double score = calculate_score(i, j);
            candidates.push_back({i, j, score});
        }
    }
}

// 2. 按分数从高到低排序
sort(candidates.begin(), candidates.end());

// 3. 贪心分配
vector<int> robot_target_good(ROBOT_NUM, -1);
vector<bool> good_assigned(goods_list.size(), false);

for (const auto& cand : candidates) {
    // 如果该机器人还没任务 且 该货物还没被分走
    if (robot_target_good[cand.robot_id] == -1 && !good_assigned[cand.good_idx]) {
        robot_target_good[cand.robot_id] = cand.good_idx;
        good_assigned[cand.good_idx] = true;
    }
}

---

5. 优化四：泊位距离场与综合评分公式

目标: 进一步优化货物选择策略。之前的评分只考虑了“去捡货”的成本，忽略了“运货去泊位”的成本。如果货物离泊位很远，即使离机器人很近，整体效率也不高。

改动详情

1. 预计算泊位距离场:

   • 新增 berth_dist[N][N] 数组。
   • 实现 init_berth_dist() 函数，使用多源 BFS 从所有泊位出发，计算全图每个点到最近泊位的真实行走距离（避开障碍物）。
   • 在 main 函数初始化时调用一次。

2. 改进评分公式:

   • 将“货到泊位距离”纳入考量。
   • 新公式：Score = Value / (dist(Robot, Good) + berth_dist[Good] + 1)。

// 预计算逻辑
void init_berth_dist() {
    // 多源 BFS 初始化 berth_dist
}

// 新的评分计算
int dist_to_berth = berth_dist[goods_list[j].x][goods_list[j].y];
if (dist_to_berth != -1) {
    double score = (double)goods_list[j].val / (d + dist_to_berth + 1.0);
    // ...
}

---

6. 文档完善

目标: 提高代码可读性。

改动详情

• 将 main.cpp 中的所有英文注释翻译为中文，详细解释了数据结构、算法逻辑和坐标系定义。

---

7. 优化五：智能防卡死与动态避让

目标: 解决随机逃逸策略带来的不稳定性。原有的“随机移动”策略虽然能解开死锁，但效率低且不可控。新策略旨在实现确定性的、智能的避让。

改动详情

1. 智能避让逻辑: 当机器人检测到卡死（连续 2 帧未移动）时，不再盲目随机移动。
2. 启发式选择:
   • 搜索所有可行的相邻格子（不越界、无障碍、未被占用）。
   • 优先选择离当前目标（货物或泊位）曼哈顿距离最近的格子作为避让方向。
   • 这种“退一步海阔天空”的策略，既解决了死锁，又保证了机器人不会偏离目标太远。
3. 降低触发阈值: 将卡死判定阈值从 5 帧降低到 2 帧，反应更迅速。

// 防卡死机制：如果最优路径被阻挡，且已卡住一段时间
if (final_move_dir == -1 && robots[i].stuck_count > 2) {
    // 寻找所有可行的替代方向
    // ...
    // 按曼哈顿距离排序，优先选择离目标近的
    sort(alt_dirs.begin(), alt_dirs.end(), [&](int a, int b){
        // ...
    });
    final_move_dir = alt_dirs[0];
}

---

8. 优化六：基于优先级的协调机制

目标: 解决多机器人路径冲突问题。当两个机器人想去同一个位置时，应该让“更重要”的机器人先走，而不是随机决定。

改动详情

1. 优先级定义:
   • 携带货物的机器人优先级最高（10000），因为它们需要尽快卸货变现。
   • 未携带货物的机器人，优先级等于其目标货物的价值。
   • 无任务机器人优先级最低（0）。
2. 执行顺序调整:
   • 不再按 ID 顺序（0-9）处理机器人。
   • 每帧开始前，计算所有机器人的优先级，并按优先级降序排序。
   • 高优先级的机器人先规划路径并移动，它们移动后会标记 occupied。
   • 低优先级的机器人规划时，会看到高优先级机器人已经占据的位置，从而自动避让。

// 优先级计算
vector<int> robot_priority(ROBOT_NUM, 0);
// ... 计算逻辑 ...

// 按优先级排序执行顺序
sort(p_order.begin(), p_order.end(), [&](int a, int b){
    return robot_priority[a] > robot_priority[b];
});

// 按排序后的顺序处理
for (int k = 0; k < ROBOT_NUM; k++) {
    int i = p_order[k];
    // ... 机器人 i 的逻辑 ...
}

---

总结

通过这六次迭代，程序从一个简单的“能动就行”的版本，进化为一个具备价值评估、全局统筹、全链路成本估算、智能避障以及多机优先级协调能力的智能调度系统。最终得分从最初的 1700+ 提升至 5000+，且运行表现更加稳定。