2024华为软件精英挑战赛记录

1. 前言
   本次主要是记录自己第一次参加华为软件挑战赛的经历。第一次参加比赛还是缺少经验，训练赛中拿到赛区的20多名，最后在正式赛中被反超了，只拿了40多名，实在是感到可惜。

• 题目：本次题目是一个智慧港口的问题。10个机器人，10个泊位，5个轮船运货，轮船到虚拟点之后就可以产生价值。
• 目标：最大化价值。

2. 处理思维
   在高层思维上，本次的思维比较简单，就是让前几任在15000帧率里面都拿到货物，轮船拼命拿货。

• 算法要求：
  • 巡路算法：本次大概有两个考虑，由于机器人只能走曼哈顿距离所以考虑就有A和BFS算法。最后尝试之后发现，A的速度比较快，但是由于其引导函数一直找不到合适的，所以求得的路径一直就不是最优的（曼哈顿距离函数做引导函数不科学），最后还是选择了最朴素的广度优先搜索算法，对其进行改进，基本上满足了帧率要求。
  • 策略：5个轮船分别分到10个一近一远的码头，这样子可以保证每个机器人的来回运输时间差不多，基本可以达到最优效果。在最后一次来码头搬货的时候，在第二个码头的时候就要压缩轮船的离开时间为最后的5帧率+自己返回码头的时间的，将时间完全利用上。机器人也是在分配码头的时候，分配一个最近，且可达的码头。
  • 碰撞挽救：由于地图的各种情况，不可避免会出现碰撞和异常问题，个人在这个方面做的最差，不然也就进决赛了。大概做了下面几个策：
    • 单通道内出现碰撞：大致就是倒车和目标交货策略。两个机器人发生碰撞，直接进行目标交换，然后pop出第一个路径即可。倒车也是种更好选择
    • 非单管道碰撞：可以选择在碰撞时候选择绕行。

# 机器人控制函数
void control_robots() {
    std::vector<std::pair<int, int>> robot_next; // 最新机器人坐标
    for (int i = 0; i < 10; ++i) {
        robot_next.push_back({robot[i].x, robot[i].y});
    }

    
    for (int robot_id : robot_list) {
         //改成，先判断机器人是否存在异常
            if(robot[robot_id].status == 0)
            {
                if (robot[robot_id].goods == 1)//机器人携带货物异常
                {
                    robot[robot_id].target[0] = -1;
                    robot[robot_id].target[1] = -1; 
                    robot[robot_id].berth = -1;
                    robot[robot_id].ops.clear();
                    search_berth(robot_id, best_robot_map[robot_id].second);
                }
                else //机器人没有携带货物发生异常，则可以搜索货物
                {  
                    robot[robot_id].target[0] = -1;
                    robot[robot_id].target[1] = -1; 
                    robot[robot_id].ops.clear();
                    search_goods( robot_id, 100, 1);
                }
            }



        //如果机器人有目标的话，就执行下面的操作。有目标但是不一定有货物。可能是泊位目标，也可能是货物目标
        if (robot[robot_id].target[0] != -1) { 
             //有货物但是没有泊位，就搜匹配的泊位路径
            if (robot[robot_id].goods == 1 && robot[robot_id].berth == -1) {     
                search_berth(robot_id, best_robot_map[robot_id].second);          //search_berth()函数前面是机器人id，后面是泊位id
            }
            //前面不执行的话说明就是机器人是有目标，身上没货，其实就是有货物目标但是没有拿到，那么传的就是机器人目标
            auto target_i = robot[robot_id].target;  //不管如何，都要将机器人的目标传出去，前面如果执行目标位置就是泊位，如果不执行，目标位置就是原来的货物
            if (!robot[robot_id].ops.empty()) {
                auto DOA = robot[robot_id].ops.front();
                auto temp_next = direction(robot[robot_id].x, robot[robot_id].y, DOA);
                if (std::find(robot_next.begin(), robot_next.end(), temp_next) == robot_next.end()) {//如果当前机器人的下一个位置，在10个机器人机器人坐标里面都没有找到，则说明没有发生碰撞
                    if (robot[robot_id].status == 1) //如果机器人status正常，处于正常状态，那么就移动机器人
                    {
                        robot_next.push_back(temp_next);
                        robot[robot_id].ops.erase(robot[robot_id].ops.begin()); // 移除已执行的操作
                        printf("move %d %d\n", robot_id, DOA);
                    }

                }
            }

            //机器人到达指定位置
            if (robot[robot_id].x==target_i[0] && robot[robot_id].y == target_i[1] && robot[robot_id].goods == 0) { 
                printf("get %d\n", robot_id);
                gds[target_i[0]][target_i[1]].reset();
            }

            //机器人到达了指定码头
            if (robot[robot_id].goods == 1 && robot[robot_id].x==berth[best_robot_map[robot_id].second].x && robot[robot_id].y == berth[best_robot_map[robot_id].second].y) {
                printf("pull %d\n", robot_id);
                berth[best_robot_map[robot_id].second].goods += 1;
                robot[robot_id].target[0] = -1;
                robot[robot_id].target[1] = -1; // 重置目标
                robot[robot_id].berth = -1;
                search_goods( robot_id, 100, 1); //一放下货物就开始搜
            }
        }

        else 
        //如果机器人没有目标的话，就搜索货物，因为没有目标的情况只有一种，就是在码头放完货的时候
            search_goods( robot_id, 100, 1);
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76

#轮船控制函数
void control_robots() {
    std::vector<std::pair<int, int>> robot_next; // 最新机器人坐标
    for (int i = 0; i < 10; ++i) {
        robot_next.push_back({robot[i].x, robot[i].y});
    }

    
    for (int robot_id : robot_list) {
         //改成，先判断机器人是否存在异常
            if(robot[robot_id].status == 0)
            {
                if (robot[robot_id].goods == 1)//机器人携带货物异常
                {
                    robot[robot_id].target[0] = -1;
                    robot[robot_id].target[1] = -1; 
                    robot[robot_id].berth = -1;
                    robot[robot_id].ops.clear();
                    search_berth(robot_id, best_robot_map[robot_id].second);
                }
                else //机器人没有携带货物发生异常，则可以搜索货物
                {  
                    robot[robot_id].target[0] = -1;
                    robot[robot_id].target[1] = -1; 
                    robot[robot_id].ops.clear();
                    search_goods( robot_id, 100, 1);
                }
            }



        //如果机器人有目标的话，就执行下面的操作。有目标但是不一定有货物。可能是泊位目标，也可能是货物目标
        if (robot[robot_id].target[0] != -1) { 
             //有货物但是没有泊位，就搜匹配的泊位路径
            if (robot[robot_id].goods == 1 && robot[robot_id].berth == -1) {     
                search_berth(robot_id, best_robot_map[robot_id].second);          //search_berth()函数前面是机器人id，后面是泊位id
            }
            //前面不执行的话说明就是机器人是有目标，身上没货，其实就是有货物目标但是没有拿到，那么传的就是机器人目标
            auto target_i = robot[robot_id].target;  //不管如何，都要将机器人的目标传出去，前面如果执行目标位置就是泊位，如果不执行，目标位置就是原来的货物
            if (!robot[robot_id].ops.empty()) {
                auto DOA = robot[robot_id].ops.front();
                auto temp_next = direction(robot[robot_id].x, robot[robot_id].y, DOA);
                if (std::find(robot_next.begin(), robot_next.end(), temp_next) == robot_next.end()) {//如果当前机器人的下一个位置，在10个机器人机器人坐标里面都没有找到，则说明没有发生碰撞
                    if (robot[robot_id].status == 1) //如果机器人status正常，处于正常状态，那么就移动机器人
                    {
                        robot_next.push_back(temp_next);
                        robot[robot_id].ops.erase(robot[robot_id].ops.begin()); // 移除已执行的操作
                        printf("move %d %d\n", robot_id, DOA);
                    }

                }
            }

            //机器人到达指定位置
            if (robot[robot_id].x==target_i[0] && robot[robot_id].y == target_i[1] && robot[robot_id].goods == 0) { 
                printf("get %d\n", robot_id);
                gds[target_i[0]][target_i[1]].reset();
            }

            //机器人到达了指定码头
            if (robot[robot_id].goods == 1 && robot[robot_id].x==berth[best_robot_map[robot_id].second].x && robot[robot_id].y == berth[best_robot_map[robot_id].second].y) {
                printf("pull %d\n", robot_id);
                berth[best_robot_map[robot_id].second].goods += 1;
                robot[robot_id].target[0] = -1;
                robot[robot_id].target[1] = -1; // 重置目标
                robot[robot_id].berth = -1;
                search_goods( robot_id, 100, 1); //一放下货物就开始搜
            }
        }

        else 
        //如果机器人没有目标的话，就搜索货物，因为没有目标的情况只有一种，就是在码头放完货的时候
            search_goods( robot_id, 100, 1);
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76

写在最后：由于代码较长，版幅有限所以就把资源放到个人哪里，明年再战。
2024年3月25日于深圳大学