天池比赛小结

天池大数据竞赛
天池, 数据结构

天池比赛小结1

巧妙利用回溯法解决路径提交所引发的血案

0 引言

前一阵子参加了天池比赛气象数据领航无人飞行器线路优化大赛，凭借着初赛一步步的稳扎稳打以及最后时刻的一波套磁 + 人品爆发，以第三名的成绩进入了决赛。但在决赛阶段，我们所遇到的最大问题并不是此次赛题中的两个重点：气象数据回归或路径规划算法，令我们差点止步前 10 的是提交路径之后，由于不同路径之间的各种组合导致的无法推知到底是哪些路径成功抵达。后来我们用了一些巧妙的解法在某种程度上解决了这个问题（并没有完全解决，下文会细讲），因此，这也是此篇博客诞生的原因，想要记录下解决这一个问题的思路。

1 问题

该比赛要求我们规划 5 天之中的 10 条飞行路线，即总共要规划 5*10 = 50 条，并要求时间最短，安全性最高。那么，这就会引发如下问题：

  • 某几条路径都是最短路径，所以其耗时是一样的。譬如：从起始点飞往城市 2 所耗费的最短时间是 200 min，那么如果我们所提交的路径之中5天的飞往城市2的时间都是最短时间，那么我们则无法推知到底是哪几条过了。
  • 不同路径之间的组合导致同一个分数有多种方案。譬如：飞往城市 1 用了 150 min， 飞往城市 2 用了250 min , 飞往城市 3 用了 100 min，飞往城市 4 用了 300 min，那么，如果最后的成绩显示是 400 min，那么我们将无法得知是路径1和2到达，还是路径3和4到达。

好，那我们其实在决赛前有想到会出现这种情况，不过我们还是too young，忽略了问题的复杂性，我们一开始的想法是只要对每条路径进行微调（在时间允许范围内+2/+4/+8啥的）从而区分耗时相同的路径即可，然而…这种解决方式会加剧问题 2 （譬如路径A+B = C+D，微调过后仍会出现 （A+2）+ （B+6）= (C+4) + (C+4) 等情况的出现），即会出现更多的不同路径组合而总消耗时间相同的情况。 所以还要花很多时间在微调数的设置上，并没有从根本上解决问题。

2 伪解决方案

为什么说其是伪解决方案呢，因为该解决方案并没有完全解决我们的问题，但是可以某种程度上解决我们的问题。话不多说，我们最终采用的方案如下：

  • Step 1 : 每次提交只提交少量的线路，比如，一次提交只涉及5天中某一天的10条路线
  • Step 2：通过基于dfs的改进k数和算法检验这些线路是否存在不同组合而消耗相同时间的问题
  • Step 3：若有，则继续微调每条线路的耗时，若没有，则可以提交

3 K数和

其实这个问题究其本质，就是K数和问题。
K数和问题定义：

Given n unique integers, number k (1<=k<=n) and target.
Find all possible k integers where their sum is target.

样例：

给出[1,2,3,4]，k=2， target=5，返回 [[1,4],[2,3]]

解题思路

利用递归与回溯来解

代码：

  • Java

    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
    public class Solution {
        /**
         * @param A: an integer array.
         * @param k: a positive integer (k <= length(A))
         * @param target: a integer
         * @return a list of lists of integer 
         */ 
        public ArrayList<ArrayList<Integer>> kSumII(int A[], int k, int target) {
            // write your code here
            ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
            ArrayList<Integer> path = new ArrayList<Integer>();
            helper(result, path, A, k, target, 0);
            return result;
        }
        public void helper(ArrayList<ArrayList<Integer>> result,ArrayList<Integer> path,int [] A,int k ,int remain,int index){
            if(path.size() == k){
                if(remain ==0)
                    result.add(new ArrayList<Integer>(path));
                else
                    return;
            }
            
            for(int i = index; i< A.length; i++){
                path.add(A[i]);
                helper(result, path, A, k, remain - A[i], i+1);
                path.remove(path.size() - 1);
            }
        }
    }

  • Python

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    class Solution:
        """
        @param A: An integer array.
        @param k: A positive integer (k <= length(A))
        @param target: Integer
        @return a list of lists of integer 
        """
        def kSumII(self, A, k, target):
            # write your code here
            path = []
            result = []
            self.helper(result,path,A,k,target,0)
            return result
        
        def helper(self,result , path ,A ,k,target,index):
            
            if len(path) == k:
                if target==0:
                    result.append(path[:])
            else: 
                for i in range(index,len(A)):
                    path.append(A[i])
                    self.helper(result,path,A,k,target - A[i] ,i + 1)
                    path.pop()

4 K数和&字典

要将K数和与本问题结合，还需要做一点小小的处理。即我们希望最后是直接输出路径的组合，而非路径耗时的组合，因此，最终我们的代码如下：

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
class GetSuccessPath():
    def helper(self, results_len, path, len_list, target, index):
        """
        DFS+回溯法
        :param results_len: 成功到达的每条路径所耗时长组成的list
        :param path: 成功到达的路径组合
        :param len_list: 提交结果中每条路径所耗时长组成的list
        :param target: 总共耗时
        :param index: 当前路径的index
        :return:
        """
        if target == 0:
            results_len.append(path[:])
        else:
            for i in range(index, len(len_list)):
                path.append(len_list[i])
                self.helper(results_len, path, len_list, target - len_list[i], i + 1)
                path.pop()
    def get_path(self, dict_path_len, target):
        """
        用于快速求得提交路径中成功到达的路径
        :param dict_path_len: 将提交结果用字典形式表示出来，{key: path 形如"day6path5", value: len 路径所耗时长}
        :param target: 提交之后得到的总时间
        :return: 成功到达的路径，每个list代表一种可能，如[['day6path5', 'day6path6'], ['day6path7']]
        """
        len_list = [value for key, value in dict_path_len.items()]  # 求提交结果中每条路径所耗时长组成的list
        # key value对调，为后续依靠路径长度得到成功到达的路径做准备
        dict_len_path = {value: key for key, value in dict_path_len.items()}
        path = []
        results_len = []
        self.helper(results_len, path, len_list, target, 0)
        # 根据成功到达路径长度的组合得到成功到达的各个路径名
        results_path = []
        for result in results_len:
            result_path = [dict_len_path.get(length) for length in result]
            results_path.append(result_path)
        return results_path
if __name__ == "__main__":
    dict_path_len = {"day6path5": 1, "day6path6": 15, "day6path7": 3, "day6path8": 4, "day6path9": 5}
    g = GetSuccessPath()
    print(g.get_path(dict_path_len, 16))

以上代码未考虑到线上评分机制：
目标函数值 = 2460飞行器坠毁数 + 顺利到达的飞行器总飞行时长（分钟）

考虑以上机制后，我们的代码改进为：

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
#!/usr/bin/env python
# -*- coding: utf-8 -*-
# @Time    : 2018/2/2 16:50
# @Author  : WangliLin
# @Site    : 
# @File    : get_success_path.py
# @Software: PyCharm
class GetSuccessPath():
    def helper(self, results_len, path, len_list, target, index):
        """
        DFS+回溯法
        :param results_len: 成功到达的每条路径所耗时长组成的list
        :param path: 成功到达的路径组合
        :param len_list: 提交结果中每条路径所耗时长组成的list
        :param target: 总共耗时
        :param index: 当前路径的index
        :return:
        """
        if target == 0:
            results_len.append(path[:])
        else:
            for i in range(index, len(len_list)):
                path.append(len_list[i])
                self.helper(results_len, path, len_list, target - len_list[i], i + 1)
                path.pop()
    def get_path(self, dict_path_len, online_score):
        """
        用于快速求得提交路径中成功到达的路径
        :param dict_path_len: 将提交结果用字典形式表示出来，{key: path 形如"day6path5", value: len 路径所耗时长}
        :param online_score: 线上成绩
        :return: 成功到达的路径，每个list代表一种可能，如[['day6path5', 'day6path6'], ['day6path7']]
        """
        target = 24*60*50 - online_score
        len_list = [24*60-value for key, value in dict_path_len.items()]
        # key value对调，为后续依靠路径长度得到成功到达的路径做准备
        dict_len_path = {24*60-value: key for key, value in dict_path_len.items()}
        path = []
        results_len = []
        self.helper(results_len, path, len_list, target, 0)
        # 根据成功到达路径长度的组合得到成功到达的各个路径名
        results_path = []
        for result in results_len:
            result_path = [dict_len_path.get(length) for length in result]
            results_path.append(result_path)
        return results_path
if __name__ == "__main__":
    """
    24*60*总条数 - 线上总成绩 = 24*60*成功到达的路径 - Sum(成功到达的路径耗时)
    """
    dict_path_len = {
            "day10path2": 202,
            "day10path9": 130,
            "day6path10": 222,
            "day6path2" : 200,
            "day6path5" : 904,
            "day6path9" : 128,
            "day7path2" : 204,
            "day7path9" : 132,
            "day8path2" : 206,
            "day8path5" : 460,
            "day8path7" : 660,
            "day8path8" : 706,
            "day9path2" : 208,
            "day9path9" : 136,
            "day8path6" : 550
        }
    online_score = 56338
    g = GetSuccessPath()
    print(g.get_path(dict_path_len, online_score))

全部思路大致如上。接下来即可实现两个功能：

  1. 线下模拟评测不同耗时下的路线组合数，从而对路线进行微调
  2. 根据线上成绩，快速得到成功到达的路径组合
Compartir Comentarios