# 2023华为软件精英挑战赛

**Repository Path**: xjl12/huawei_program_2023

## Basic Information

- **Project Name**: 2023华为软件精英挑战赛
- **Description**: 2023华为软件精英挑战赛初赛代码仓库，最终成绩：江苏山东赛区三等奖，排名41（前32进入复赛）
- **Primary Language**: C++
- **License**: Not specified
- **Default Branch**: traditional
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 0
- **Forks**: 0
- **Created**: 2023-03-14
- **Last Updated**: 2023-06-05

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

# 基本定义

### 原子动作

【原子动作（SingleAction）】为一个机器人将原料（中间产物）从产出工作台搬运至需要该原料的工作台，同时贩卖的过程。注意只考虑从原料工作台至消耗工作台的过程，机器人行至原料工作台的过程在此结构体中不予考虑。

```C++
struct SingleAction
{
    int workbench_start, workbench_end, // 起止工作台编号（可通过工作台编号取得工作台位置）
        load_type, // 运载的货物类型
        bar,       // 购买所需金额
        sell,      // 卖出价格
        time,      // 执行时间
        gain;      // 预期获得收益
};
```

可以证明，【原子动作】的数量是有限的，每个时刻有不同的原子动作可供进行，每个原子动作可以带来一定收益，最终成绩取决于调度策略。

### 机器人

【机器人（Robot）】数量固定为4个，是【原子动作】的执行体，有面积，会碰撞，同一时刻一个机器人只能执行一个原子动作。定义如下：

```C++
struct Robot
{
    int cur_workbench_id, // 当前所处工作台
        load_type;        // 当前所负载物品类型
    action_iterator cur_action; // 当前所执行的任务（指向actions中某个SingleAction对象的指针）
    Location loc,         // 当前机器人所处的位置
    		 expect_loc;
    double w,       // 角速度
        face_angle; //  朝向的角度
} robot_list[ROBOT_CNT];
```

### 工作台

【工作台（Workbench）】是生产物品或收购物品（或既生产又收购）的点，其面积不予考虑，不会与机器人发生碰撞，数量不固定（$\leq50$）。定义如下：

```C++
struct Workbench
{
    Location loc;            // 工作台位置
    int type,                //  工作台类型
        remain_time,         // 剩余生产时间
        raw_material_status, // 原理格状态
        output_status;       // 产出格状态
} workbench_list[MAX_WORKBENCH_CNT];
```

# 算法基本过程

首先找出所有的【原子动作】，保存在`vector<SingleAction> actions`中，然后一旦某机器人空闲，就按照**一定的调度算法**，为该机器人分配最优的【原子动作】。分配过程首先会过滤出当前时刻所有可供执行的【原子动作】，保存在`vector<vector<SingleAction>::iterator> available_action`中，面临的任务是如何从available_action中挑选最优动作，交由该机器人执行。

# 算法实例

### 随机分配

纯粹随机选择，成绩【168W】

```C++
bool assainTaskForRobot(Robot &cur_robot)
{
    filterAvailableAction(cur_robot.loc); // 过滤可用action，得到available_action
    if(available_action.empty())
        return false;
    cur_robot.cur_action = available_action[rand() % available_action.size()]; // 利用rand()随机从available_action中挑选一个执行
    return true;
}
```

### 总时间最短优先

该分配方案对总时间进行贪心，每次选出花费最小时间的动作执行。成绩【211W】

```C++
bool assainTaskForRobot(Robot &cur_robot)
{
    filterAvailableAction(cur_robot.loc); // 过滤可用action，得到available_action
    if(available_action.empty())
        return false;
    vector<pair<int, int>> v;
    int s = available_action.size();
    for (int i = 0; i < s; i++)
    {
        int total_time = calculateTimeBetweenLoc(workbench_list[available_action[i]->workbench_start].loc,cur_robot.loc)
            		+ available_action[i]->time // 总时间 = 机器人行至起始工作台的时间 + 动作的执行时间（机器人从起始工作台行至终止工作台）
        v.push_back({total_time, i});
    }
    sort(v.begin(), v.end());
    cur_robot.cur_action = available_action[v[0].second];
    return true;
}
```

### 时间与收益比值

通过最小化$\frac{总时间}{收益}$分配动作，成绩【216W】

```C++
bool assainTaskForRobot(Robot &cur_robot)
{
    filterAvailableAction(cur_robot.loc);
    if(available_action.empty())
        return false;
    vector<pair<double, int>> v;
    int s = available_action.size();
    for (int i = 0; i < s; i++)
    {   // 计算总时间
        double t = available_action[i]->time 
                 + calculateTimeBetweenLoc(workbench_list[available_action[i]->workbench_start].loc, cur_robot.loc);
        v.push_back({t/available_action[i]->gain, i});  // available_action[i]->gain就是某个动作的预期收益
    }
    sort(v.begin(), v.end());
    cur_robot.cur_action = available_action[v[0].second];
    return true;
}
```

# 尾声

比赛结束，初赛排名【41】，总分：2646331