精华内容
下载资源
问答
  • 中兴捧月
    千次阅读
    2021-07-11 15:36:37

    一、2021中兴捧月杯算法赛

    本次比赛我参加的是迪杰斯特拉门派,题目是人口流量预测。最终成绩:西北区域优胜奖,38/500,初赛全国前50可进入复赛,获得区域优胜,然后组织面试,根据面试结果,大概15人左右可进入全国总决赛。总体来说,中兴算法赛的难度不是很大(但想做得好冲击国奖还是很有难度),且可获得很多招聘机会,非常推荐大家参加。

    初赛一阶段

    给定训练数据集(传感器ID,日期,流量),测试数据集(传感器ID,日期(后91天)),完成流量预测任务。
    其实这个赛题的难度就在于数据处理方面,有的传感器可能损坏或者出现测量噪声,数据可能缺失或者异常,而且提供的特征只有ID号和日期,这都增加了比赛的难度。
    初赛我利用决策树和随机森林作了很多尝试,有效果提升,但不够好,LGB和XGB出现了很差的效果,而且一直不知道什么原因(可能特征太少?)。最后还是5天的滑动平均效果最好。。。

    初赛二阶段

    初赛二阶段其实和初赛一阶段差不多,就是增加了传感器和数据量,总数据量好像在千万级别。
    这一阶段我做了更多特征工程的工作,直接将当时的笔记搬过来:
    一、 数据处理
    1.1预处理

    初赛第二阶段的数据较第一阶段增加了ID数目和数据量。经检查,没有发现重复值、缺失值,只发现三行数据的“value”值大于100,视为异常值,直接删除。
    1.2构造特征
    初始特征:id(1)
    年月日特征(4)
    累积天数特征(6)
    周几特征(7)
    季节特征(8)
    年月周one-hot(29)
    周末特征(30)
    上中下旬特征及one-hot(34)
    月份,星期组合特征(37)

    将滑动平均值也作为特征:
    4天滑动平均:roll4_last
    特征归一化

    除此之外,尝试过7、14、28天的滑动均值,平均流量,均值分箱等特征,但效果均不好;

    1.3划分数据集
    按时间序列划分训练集、测试集,训练集最大是第715天(以2017-1-1为起始),以91天作为验证集,则[625:]为验证集,不足的划分到训练集里面!

    二、 模型训练
    2.1 滑动均值baseline

    以4天为窗口对每个ID作滑动均值,并将每个ID的最后一天的滑动均值roll4_last作为赛题测试集的预测值:
    在自己的验证集得分为68.914分,在赛题测试集上得分为62.865分。

    2.2 基于树模型
    (1)基于所有构造的特征,不进行任何处理效果很差
    (2)利用决策树,挑选特征,在赛题测试集上可以取得61分
    (3)利用PCA+LGBM,在自己验证集上得分58,在赛题测试集上效果不好

    2.3 其他尝试
    (1)注意到value值的严重偏态分布,使用对数变换、boxcox变换,效果有微弱提升,但不明显;
    (2)注意到赛题评分的20%误差,尝试修改损失函数权重,使大于20%误差的梯度加大,但结果也无明显提升;
    (3)根据每个ID的平均流量来划分区域,分区域预测:
    ave_value > 80 : 看最后一天是否是100,是则输出100,不是则输出nan
    43 < ave_value <= 80
    17 < ave_value <= 43
    10 < ave_value <= 17
    5 < ave_value <= 10
    1 < ave_value <= 5
    0 < ave_value <= 1
    ave_value == 0 : 输出nan
    ave_value == -1 :
    效果也无提升。

    复赛

    复赛采取线上面试的形式,两个面试官,一个负责询问比赛建模过程,另一个负责问其他方面。

    总结

    这个题的数据有点变态,以后在数据处理、特征工程上还要下很大功夫。

    二、2021模面大赛

    本次模拟面试赛旨在通过提前模拟面试,提高同学们的面试技巧与能力,获奖者还可提前获得校招直通终面的资格。我本来报名了,但后来由于时间安排和其它原因没有参赛,全程只听了第一场宣讲讲座,有一个交大的大学长作了关于面试技巧的分享,个人觉得有所收获,现把它总结如下,希望对明年的自己和校招的朋友们有所帮助。

    标题:面试“十问”

    1.简历和面试的关系是什么?
    简历是为了获得面试资格,针对不同的求职岗位,简历需要具有针对性,每份简历为不同公司独家定制
    2.面试的核心逻辑是什么?
    仔细了解岗位描述,思考公司需要什么样的人?我就是你想要的人,我做好了哪些准备,所以我来面试。
    3.面试的第一个问题是什么?
    自我介绍,有一个重点:我这次来应聘什么岗位,我很愿意加入!
    4.面试的最后一个问题?
    反问环节,注意你的面试官是负责专业面的,不要问薪资这类HR的问题,通常比较喜欢回答的是入职之后的培训问题和晋升机制相关问题。
    5.应该如何介绍自己的项目?
    逻辑:什么项目?在其中扮演什么角色?使用什么软件、工具、技巧、语言?取得了什么收获?注意最好有量化数据!
    6.以何种心态、姿态面对考官?
    不卑不亢、破釜沉舟,注意压力面试问题。
    7.群体面试如何应对?
    技术类面试,一般没有“群面”(无领导面试)。
    8.如何回答压根就不会的问题?
    (1)勇敢承认自己不会;(2)我认为…,我猜想…,尝试解决问题,尝试给出思路…;(3)反客为主,虽然我不会…,但我在另一个方面…比较强。
    9.面试中我注意过自己的礼仪吗?
    老师问了问题,思考几秒再作回答,以表稳重。
    10.我准备好了吗?

    更多相关内容
  • 2020中兴捧月算法大赛迪杰斯特拉赛道初赛题解源码,50个字的限制真的好傻啊
  • 文件是本人参加2017年的中兴捧月算法大赛(Dijstra派)的代码和可执行文件,得分86,获得中南赛区区域优胜奖
  • 2020年中兴捧月Dijkstra派程序,获得西南赛区区域优胜奖。
  • 2020中兴捧月傅里叶派题目和参考答案。 二分图的DFS,剪枝优化等。
  • 根据2017年中兴捧月算法大赛地接斯特拉派比赛,给出蚂蚁行走的花费和路径信息,寻找出满足条件的最优路径
  • 参加2021年中兴捧月图灵派初赛,自己跑通的一个代码思路梳理
  • 中兴捧月杯程序(套娃),用的算法比较特别,自己看吧,在我的机子上跑255*255只要10多秒。
  • 这是本人参加中兴比赛的提交报告,因为有同学看了我的提交代码之后私信跟我要报告,所以发出来,我的提交结果是中南赛区的区域优胜奖
  • ZTE.rar_中兴捧月

    2022-09-20 20:19:45
    2012年中兴捧月编程大赛第4题“负荷分担的可靠性系统仿真”复赛程序,属于网络编程内容,内含程序和文档,有详细注释
  • 2013年中兴捧月第一题之复赛,大家一起学学
  • zhongxing.rar_中兴捧月

    2022-09-24 19:37:50
    2013中兴捧月大赛C++程序实现,各个模块及相关功能
  • 吐槽一下中兴这个网页编辑器怎么就没法输出看结果呢?我人麻了,编辑器只能给我反馈一个“未通过”,我想输出一下中间结果看一下也不行!?看了半个多小时才发现除法可能会除以0(某两个相等的数相减,然后作为被除...

    吐槽

    读完题眼前一亮,这不就是24点游戏嘛,小时候和我弟玩过。吐槽一下中兴这个网页编辑器怎么就没法输出看结果呢?我人麻了,编辑器只能给我反馈一个“未通过”,我想输出一下中间结果看一下也不行!?看了半个多小时才发现除法可能会除以0(某两个相等的数相减,然后作为被除数这种情况)。。。。 还是太菜了,除以0都能写得出来。。。

    题意

    给定4个数,是否能用算术运算(±*/和括号)得到24?

    分析

    首先想到的是搜索,前半个小时一直在尝试深度优先搜索去尝试所有情况,但是代码越写越臭,直奔上百行去了,而且也A不掉。然后就仔细想了想以前玩24点游戏,我是怎么快速判断当前4张牌能够凑出24的?应该是先试探2张牌能凑出什么,然后往多了考虑3张牌、4张牌能凑出什么。

    于是得出了最终的解决方案,有点动态规划的思想:

    定义一个二维数组 m a r k [ i ] [ j ] mark[i][j] mark[i][j]表示 i i i这个状态能否凑出 j j j这个数字。由于数组很大,不妨把第二维换成 m a p map map,反正只是用来标记。其中 i i i是二进制位压缩的牌集合,例如 i = ( 10 ) 10 = ( 1010 ) 2 i=(10)_{10}=(1010)_2 i=(10)10=(1010)2表示取第1和第3张牌。然后就是1张牌、2张牌、3张牌、4张牌依次考虑能凑出来多少。

    例如考虑3张牌能凑出来啥的时候,一定是由2张牌和1张牌计算而来的,而4张牌可能是3+1张牌或2+2张牌。

    代码

    #include <bits/stdc++.h>
    using namespace std;
    
    unordered_map<int, bool> mark[16];
    
    void merge(int status1, int status2){
        int status = (status1 | status2);
        for (auto &x : mark[status1]){
            for (auto &y : mark[status2]){
                mark[status][x.first + y.first] = true;
                mark[status][abs(x.first - y.first)] = true;
                mark[status][x.first * y.first] = true;
                if (y.first > 0 && x.first % y.first == 0)
                    mark[status][x.first / y.first] = true;
                if (x.first > 0 && y.first % x.first == 0)
                    mark[status][y.first / x.first] = true;
            }
        }
    }
    
    bool damage(vector<int> &power){
        for (int i = 0; i < 16; i++)
            mark[i].clear();
        // 1 nums
        for (int i = 0; i < 4; i++)
            mark[1 << i][power[i]] = true;
        // 2 nums
        for (int i = 0; i < 4; i++)
            for (int j = i + 1; j < 4; j++)
                merge(1 << i, 1 << j);
        // 3 nums
        for (int i = 0; i < 4; i++)
            for (int j = 0; j < 4; j++)
                for (int k = 0; k < 4; k++)
                    if (i != j && j != k && k != i)
                        merge((1 << i) | (1 << j), 1 << k);
        // 4 nums
        for (int i = 0; i < 4; i++)
            for (int j = 0; j < 4; j++)
                for (int k = 0; k < 4; k++)
                    for (int t = 0; t < 4; t++)
                        if (i != j && i != k && i != t && j != k && j != t && k != t)
                        {
                            merge((1 << i) | (1 << j), (1 << k) | (1 << t));
                            merge((1 << i) | (1 << j) | (1 << k), 1 << t);
                        }
        return mark[15].count(24) > 0;
    }
    
    // 本地测试:
    int main()
    {
        vector<int> power({1, 1, 2, 7});
        cout << damage(power) << endl;
    }
    
    展开全文
  • 中兴捧月杯程序设计大赛往届题目,这是往届的题目,希望对大家有参考作用
  • 中兴捧月比赛信风系统设计的源代码实现和设计文档、使用文档
  • 谈谈中兴捧月大赛决赛以及总结

    千次阅读 2021-06-30 10:28:09
    四月份,在师兄的推荐下,报名参加了中兴捧月大赛。一开始只是为了混一个面笔试的资格(因为提交有效成绩即可免笔试),然后为了找一个简单的赛道,注册了几个号看了两三个赛道的题目。发现自己每个都不熟悉,然后就...

    前言

    四月份,在师兄的推荐下,报名参加了中兴捧月大赛。一开始只是为了混一个面笔试的资格(因为提交有效成绩即可免笔试),然后为了找一个简单的赛道,注册了几个号看了两三个赛道的题目。发现自己每个都不熟悉,然后就选了一个看起来比较小众的赛道(图灵派,音视频编解码),可能竞争压力会小一点(报一点侥幸)。

    初赛

    初赛因为就是为了混免笔试,因此就调库(不调库也没办法,我也不会,也没时间天天搞这个,毕竟还有科研任务)。
    具体的初赛内容可以看前几篇文章。
    https://blog.csdn.net/qq_37207042/article/details/116209375

    复赛

    这个赛道的复赛好像特别简单(其他赛道好像还有题),复赛就是面试,郭老师远程面试我们,然后基本没有问技术层面的,就问了一下思路。然后做了一些自我介绍,其实我就是念了一下简历,另外问了一些项目经验之类的以及就业意向。因为毕竟不是本专业学这个的,技术深度还是不够,只能问一些浅层的思路。本以为复赛混个奖品就可以了,意外的是,公布决赛名单时候竟然找到了我的牛客ID。

    决赛

    听说决赛还有参与奖品,而且还包差旅食宿(还有这种好事,当然要去)。然后领我意外的是,中兴对待比赛还挺认真的,赛务组安排的都很好,吃住等生活事务都安排的明明白白。
    在这里插入图片描述
    第一天去先是入住,然后等晚上发布赛题,发布完赛题会住处就开始开发了。
    第二天,第三天都是开发,第三天下午5点提交,提交完开始做PPT,第四天答辩,第四天下午终极答辩(前六名),晚上颁奖典礼。
    开发开始比较累的,我每天差不多都搞到晚上1点,搞了两天。吃住都在中兴自己的酒店,酒店还行吧,吃饭就酒店自助。

    赛题

    扯了那么多,毕竟这是个技术博客,还是谈一谈技术。

    决赛(图灵派)赛题

    图灵派主要涉及的就是音视频编解码,涉及一些深度学习方法。
    决赛题目是VR视频编码算法的问题

    背景

    在VR领域中,对于传输带宽要求极高,需要对于视频进行进一步的压缩,
    以降低传输带宽的需求,给用户更好的使用体验,业内常用 tile 编码方案进行传输。

    问题1:tile权重预测

    根据相关研究表明,对于 360°视频,大约有超过 30%的内容未被参与测试的人观看。因此,通过 tile 编码,可以对于不重要内容进行低权重编码,对于观看频率较高的采用高权重编码。
    在这里插入图片描述
    上图展示了一个全景图像中,用户关注的重点位置和图像。
    在 tile 编码时,根据 saliency 的预测权重结果进行西能优化,有线高质量编码更容易被观看的 tile,对不容易被观看的区域视权重情况进行低质量快速编码。 从而完成对编码服务器的性能优化,降低服务成本。 根据附件中所提供的 40 个参与用户对于 40 个视频的头动数据集,对于 tile 编码算法进行设计和训练。

    评分标准

    在测试的 8 个视频中(赛程过程不提供),对于视频数据进行 tile 编码,对于所预测的权重结果和实际的头动数据集进行相关性计算。最后输出一个 txt 文 本文件,输出分为两列,分别为各个 tile 的观看命中次数和该 tile 对应的权重, 示例如所给压缩包中的 txt 文件。运行压缩包中 pcc.py 计算相关性,获取最终的 相关性评分。同时,对于本问题的解题思路,输出相关文档进行阐述。
    在这里插入图片描述

    问题2:tile编码方案优化

    对于单个 tile 的编码方案进行优化。 在第一题全景 tile 编码的基础上,相同的视频内容,不同的编码方案(q、s、t)对主观感知质量的影响较大。不同的视频内容呈现出的规律有一定的差异。 可参考:
    https://github.com/NJUVISION/QSTAR
    https://vision.nju.edu.cn/20/86/c29466a467078/page.htm
    请给出在给定码率下的最佳编码策略。

    评分标准

    针对测试的 8 个视频,以及第一题解出的 tile 数据,输出最佳编码方案。与理论最佳编码方案匹配的给分。同时,对于本问题的解题思路,输出相关文档进行阐述。

    赛题思路

    由于赛方给配备了一台服务器,虽然算力不高,但还是比我的小笔记本强的,所以首先就是配置服务器,服务器配置为ubuntu18.04 + cuda 11.0.2/Driver 450.80.02/CUDNN 8.0.4

    由于之前没有用过linux系统和服务器,所以用的都是比较简单的操作:
    主要操作在window PowerShell上完成,使用ssh指令完成连接,例如:ssh root@47.98.183.224
    输入密码,由于linux键入后是不显示的,所以不要担心没输进去。
    进入服务器后,左侧的提示符会变为root@xxxx:
    另外比较简单的几个操作是必要的:
    ls :显示文件夹内容
    cd xxx:到xxx文件
    cd .. :回退到上一级文件夹
    vim xxx:编辑xxx,进入编辑模式后需要按i进入insert编辑模式,按ESC退出模式,输入:wq保存退出
    python xxx.py :执行python文件
    unzip xxx.zip :解压xxx文件
    至于工具的安装和python的安装就不啰嗦了,大多都是pip install xxx以及apt install xxx这些操作。
    在这里插入图片描述
    另外重要的就是主机与服务器的文件交互,这个交互需要在cmd命令提示薄。
    下面是从服务器下载weg.txt文件
    在这里插入图片描述
    下面是从主机上传test.txt文件
    在这里插入图片描述
    主要是用了scp指令。

    这些只是下酒菜,下面到正题,赛题应该如何解决。
    为了尽可能容易理解并且少看文字,着重用图解释问题。
    在这里插入图片描述
    在球体中相同的角度对应的弧长相同,因此在坐标转换时根据经纬度等比例转换
    在这里插入图片描述
    在这里插入图片描述
    由于用户关注的tile通常是关注图像中的人物或者物体、抑或是图像信息较多的部分(图像细节较多),因此考虑使用擅长图像感知的卷积神经网络进行训练建立

    使用卷积神经网络实现对图像每块tile的权值预测,模型的输入为图像、输出为tile权重。
    由于资源与时间限制,该卷积神经网络模型使用使用4层卷积层,两层映射层。
    利用头动数据集与划分好的tile可以建立每一帧图像的tile权重(命中为1,未命中为0)
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    还有不明白的可以看下面文字补充解释:

    问题1:tile权重预测

    已知40个VR视频与40个参与用户观看40个视频的头动数据(头动数据给出的是用户观看的VR视频的经纬度)。目的是要根据已知的数据建立算法模型,以达到预测参与用户对视频的不同位置块的关注程度,也就是tile权重。

    根据已知数据可以抽象一个简单的数学模型,输入设计为视频中的每一帧图像,输出为tile权重。由于用户关注的tile通常是关注图像中的人物或者物体、抑或是图像信息较多的部分(图像细节较多),因此考虑使用擅长图像感知的卷积神经网络进行训练建立(进一步可以考虑前后帧图像之间的关系,加入循环神经网络的元素,结合实现序列上的轨迹与视频内容以达到更好的预测)。

    明确数学模型后,需要得到模型的输入与输出数据用于神经网络的训练。首先,对头动数据集进行坐标转换,将头动数据集的经纬度转换为图像中的坐标位置。由于头动数据的经纬度所表示的为球面的位置,球面高纬度的纬线周长小,低纬度的纬线周长大,因此根据经纬度对其进行等比例变换到平面坐标。其次,需要明确图像中的tile划分,由于VR视频本质是一个球形的图像形式,因此将其转化为平面图像后,其高纬度部分的图像也就是平面图像的上下两侧存在拉伸,拉伸会导致用户在VR图像中所关注的部分在平面图像下会变大。因此,将平面图像上下两侧的tile划分为较大的块,中部划分为较小的块。其中,上下部分与中部划分的线为60°纬度线,因为当纬度为60°时,纬线周长等于赤道线周长的一半,也就是 c o s ( 6 0 ∘ ) cos(60^{\circ}) cos(60)

    确定tile区块划分后,根据头动数据可以计算每一帧图像中用户所关注的tile位置,由此建立深度学习的Label集(用户关注的tile位置标签为1,其余区域为0)。

    确定模型的输入输出后,建立卷积神经网络,(由于训练时间与资源限制,使用较为简便的卷积模型)。

    由于图像数据较大,服务器的存储容量不足,将图像的分辨率调整为480*240,每次读取一个视频的图像数据进行训练,头动数据与图像帧的长短不一致的以起始数据为基准对齐进行截取训练。训练完成后的神经网络可以针对视频中的每一帧图像输出tile权重,若输出权重总和不为1,按比例调整到总和为1。

    采用神经网络对每个视频中图像的tile权重预测求均值,得到每个tile块的权重;将坐标转换后的头动数据与划分的tile比对,得出每个tile的统计命中次数,写入最后输出的txt。

    使用pcc.py求取根据头动数据得到的tile命中次数与深度学习算法给出的tile权重预测两个统计变量之间的皮尔逊相关系数,得出机器预测与用户观看之间的相关度作为评价指标。

    问题2:tile编码方案优化

    目前针对基于视点的全景视频的视频质量评价机制主要是基于SP、QP、TR等代表空间、时间、量化幅度、分辨率等的参数。建立这些参数与主观观看平均评分(MOS)之间的关系,形成客观视频评分模型。

    为了达到在给定码率下尽可能的提供视频质量,可以依据tile的权重调整上述几中影响视频评分的参数。
    在这里插入图片描述
    上述评分模型中,设计三个参数,时间(t,帧速率)、空间(s,分辨率)、量化(q,量化质量)。若上述三个参数增加则视频的码率相应的增加,若其减小,则视频评分质量将下降。

    依据评价模型对编码方案进行优化需要在上述参数与cost funtion也就是评价模型的值Q之间做trade-off。

    假设量化值为q、帧速率为t、分辨率为s,码率为b,假定以下数学模型:
    在这里插入图片描述
    其中, f f f为已知常数。
    根据Q质量模型转化为寻优问题。

    根据南京大学视觉实验室文章的描述,求取多个tile的视频质量时,直接对其进行加权求和即可得到最终的视频质量 。由此可以有以下式子:
    在这里插入图片描述
    根据第一问得到的权值的预测 ,结合上式,可以建立视频全局的质量评价模型与参数之间的关系,进而在码率约束条件下,可以利用拉格朗日乘数法求取多元函数极值,得到参数值。

    另外,当tile划分的块较小时,可以更精确的定位到用户所关注的区域,但是当tile过小时,一个tile将无法覆盖用户的关注的视觉区域。
    一般而言人眼的观察范围为180°,当观看视频时,关注的区域往往小于60°的范围,当视频分辨率为4k时,用户关注的区域大小大致为680x680。考虑到若tile的大小划分为680x680时,若用户关注的范围在tile边缘时,提高邻近的tile画面质量将造成码率资源浪费。应将680x680的块划分为4等分,甚至16等分,并且在进行基于视点的视频编码时,提高视点关注的tile以及邻近tile的画面质量。

    代码

    还是贴几行代码吧,只贴小部分仅供参考。
    写的比较乱,将就着看吧。

    # -*- coding: utf-8 -*-
    """
    Created on Fri Jun 25 23:56:01 2021
    
    @author: MYM
    """
    '''将头动数据的经纬度转换为平面图像的坐标系,平面图像的大小通过读取图片得到。'''
    import numpy as np 
    import os
    import matplotlib.pyplot as plt
    import matplotlib.image as mpimg
    
    
    
    for person in range(1,41):
        folder_name = r"H:\tuning\head-tracking\Subject_" + str(person)
        for file_name in os.listdir(folder_name):
            # print(file_name)
            img_path = r"H:\tuning\48Sequences" + "\\" + file_name[0:-4] + r"\0.jpg"
            img = mpimg.imread(img_path)
            
            length = img.shape[1]
            highth = img.shape[0]
            data = np.loadtxt(folder_name + '\\' + file_name)
            data_num = len(data)  # 数据数目
            
            high = [0 for x in range(data_num)] # 初始化列表
            leng = [0 for x in range(data_num)]
            
            for i in range(data_num):
                high[i] = ((90 - data[i][0]) / 90) * highth / 2 
                leng[i] = ((180 + data[i][1]) / 180) * length /2
            
            
            new_folder_name = "new_Subject_" + str(person)
            new_file_name = "new_" + file_name
            
            isExists=os.path.exists(new_folder_name)
            if not isExists:
                os.mkdir(new_folder_name)
            else:
                print("文件夹已存在")
            
            with open(new_folder_name + '\\' + new_file_name,"w") as f:
                for j in range(data_num):
                    f.write(str(high[j]))
                    f.write(' ')
                    f.write(str(leng[j]))
                    f.write('\n')
    
    import tensorflow as tf
    from tensorflow.keras.layers import Conv2D,MaxPooling2D,Dense,Flatten,Activation
    from tensorflow.keras import Input 
    from tensorflow.keras import Model
    import os
    import cv2
    import numpy as np
     '''建立并训练卷积神经网络(改自vgg16)'''
    def conv2d_1(input_tensor,filters,kernel_size=3):
        x=Conv2D(filters,kernel_size,padding='same',activation='relu')(input_tensor)
        x=Conv2D(filters,kernel_size,padding='same',activation='relu')(x)
        x=MaxPooling2D(strides=2)(x)
        return x
    def conv2d_2(input_tensor,filters,kernel_size=3):
        x=Conv2D(filters,kernel_size,padding='same',activation='relu')(input_tensor)
        x=Conv2D(filters,kernel_size,padding='same',activation='relu')(x)
        x=MaxPooling2D(strides=2)(x)
        return x
    def vgg16(filters,input_tensor):
        filter1,filter2,filter3,filter4=filters
        x=conv2d_1(input_tensor,filter1)
        x=conv2d_2(x,filter4)
        return x
    inputs=Input([240,480,3])
    x=vgg16([64,64,64,8],inputs)
    x=Flatten()(x)
    x=Dense(32,activation='relu')(x)
    x=Dense(32)(x)
    outputs=Activation('softmax')(x)
    model=Model(inputs,outputs)
    model.summary()
    model.compile(
        optimizer="rmsprop",
        loss='CategoricalCrossentropy',
        metrics='mse',
    )
    # 读取数据
    '''训练网络'''
    folder_name = os.listdir("./48Sequences")
    for name_f in folder_name : 
        file_name = os.listdir("./48Sequences/" + name_f)
        img_num = len(file_name)
        img_list = []
        for x in range(img_num): # 读取图片
            img = cv2.imread("./48Sequences/" + name_f + "/" + str(x) + ".jpg")
            img_list.append(img)
        img_data = np.stack(img_list, axis=0)
        del img_list
        for i in range(1,41):
            label_path = "./label/"
            label = np.loadtxt(label_path + str(i) + "_" + name_f + ".txt")
            cut_num = min(img_num,len(label))
            model.fit(img_data[0:cut_num,:,:,:],label[:cut_num,:],epochs =1)
    model.save('my_model.h5')
    
    '''预测步骤,并写入tile预测权重,对每张图片预测的权重取均值,每张图片32的权重,因为32个tile'''
    ans_list = []       
    for name_f in folder_name : 
        file_name = os.listdir("./48Sequences/" + name_f)
        img_num = len(file_name)
        img_list = []
        for x in range(img_num): # 读取图片
            img = cv2.imread("./48Sequences/" + name_f + "/" + str(x) + ".jpg")
            img_list.append(img)
        img_data = np.stack(img_list, axis=0)      
        del img_list        
        ans = model.predict(img_data[:,:,:,:])
        ans_list.append(ans)
    ans_data = np.concatenate(ans_list,axis = 0)
    del ans_list
    total_num = ans_data.shape[0]
    weg_sum = np.sum(ans_data,axis = 0)
    weg = weg_sum/total_num
    with open("weg.txt",'w') as f:
        for x in weg:
            f.write(str(x))
            f.write('\n')
        
    

    参考文献

    [1]基于深度学习的视频编解码技术研究_邓宣
    [2]全景视频处理与呈现架构和关键技术研究_罗莹
    [3]3D_HEVC帧内编码优化算法研究_任海
    [4]基于用户观看行为预测的全景视频高效编码与传输_戴震宇
    [5]全景视频的质量评估研究_闵楠
    [6]基于超高分辨率全景视频的VR系统研究_陈志杰

    结语

    大概思路就是这样,结束当天身体不舒服,没认真听得奖大佬的思路,不过后来听同学说好像也差不多,没有什么更特别的东西。

    最后,本人由于不是视频编解码方向,只是突击了几天,如有描述不当或者错误,请大家指正,谢谢。

    以上内容纯属原创,如有转载,请注明。

    展开全文
  • 最近我在总结研究生阶段参与的一些项目和比赛,翻到了2020年参加的中兴捧月算法大赛,题目很有意思,解法上也有一些有趣的创新,所以拿出来特别记录一下。 中兴捧月算法大赛是中兴通讯公司主办的算法赛事,每年都会...

    大家好,我是轶扬。
    最近我在总结研究生阶段参与的一些项目和比赛,翻到了2020年参加的中兴捧月算法大赛,题目很有意思,解法上也有一些有趣的创新,所以拿出来特别记录一下。
    中兴捧月算法大赛是中兴通讯公司主办的算法赛事,每年都会根据当下热点设置多个赛道,包括图像、音频、通信和数据库等。由于我是通信背景出身,所以我在2020年参加了中兴捧月的“傅里叶”赛道,这个赛道的题目有一种大家很容易想到的解法,因此有很多非通信专业的同学参与进来,人数达到了一千多名,是当年5个赛道之最。我最终凭借算法效率的巨大优势(程度运行时间最短),在傅里叶赛道的两个阶段中均获得第一名,并大幅领先于第二名。下面是对于赛题和解决方案的详细介绍。

    这个赛道的题目很有意思,出题方用一个有趣的小故事描述了一个数学问题。

    赛题描述

    丰收祭前的游戏

    情景描述:
    在某片遥远的大陆上,居住着两个世代友好的部落,分别是部落A和部落B。他们一起耕耘劳作,互相帮助,亲如一家。久而久之,部落里的每个人都在对方部落里找到了志趣相投,互相欣赏的好朋友。有的人性格热情开朗,好朋友很多;有的人性格沉稳内敛,好朋友相对少一些。
    每到秋天丰收的季节,这两个部落的人民都会聚集在一起举行盛大的“丰收祭”,来祈祷下一年的风调雨顺。今年的丰收祭马上又要举行了。为了进一步增进两个部落的友谊,也为了明年能有一个好收成,这两个部落的祭司们商量后决定:在今年的丰收祭前举办一场特别的“击鼓传花”游戏。只不过游戏中并非有人真的击鼓,并且所传递的“花”也不是真的花,而是等待在丰收祭上献上的祭品。
    游戏规则如下:

    1. 两个部落的所有人都可以事先准备自己的祭品,且每个人的祭品样式都不同,每一个祭品都分别盛放在一个相对应的木托盘里;准备此祭品的人熟悉自己的祭品;
    2. 每个人可以准备的祭品数量不限;祭品的最小不可分割单位是1份;
    3. 游戏开始后,在整个游戏过程中,每个人都能且只能将祭品(包括木托盘)传递给自己在对方部落里的好朋友们,每个好友可以接收的祭品数量不限;
    4. 收到祭品的人必须在盛放此祭品的木托盘上刻上自己的名字(代表留下自己美好的祝愿),随后按按照上一条规则,继续传递;
    5. 如果祭品回到最初准备此祭品的人手中,此人也在木托盘上刻上自己的名字之后,终止传递;
    6. 木托盘上不允许出现重复的人名,如果无法满足此条件,则不再继续传递该祭品;
    7. 当所有的祭品都不再传递后,游戏结束;

    游戏开展得非常顺利。游戏结束后,祭司们将收集同时满足如下三个条件的祭品用于接下来的丰收祭活动:

    1. 此祭品回到了最初准备它的人手中;
    2. 盛放此祭品的木托盘上至少有4个名字,至多有14个名字;
    3. 如果有多个木托盘上的名字完全一样(不区分名字的排列顺序),则从其中随机选择一个木托盘所对应的祭品。

    问题:
    已知这两个部落里的所有人都不重名,并且部落A的人和部落B的人之间的好朋友关系以附件的csv数据表格文件给出,其中行索引代表部落A中的人,列索引代表部落B中的人,表格中的数字“1”代表他们两人是好朋友,“0”代表他们两人不是好朋友。请问:
    如果以木托盘上的名字的数量对用于丰收祭的祭品分类,每一类分别最多有多少个祭品?

    请参赛者答题:
    木托盘上有4个名字的祭品最多有()个;木托盘上有6个名字的祭品最多有()个;木托盘上有8个名字的祭品最多有()个;木托盘上有10个名字的祭品最多有()个;木托盘上有12个名字的祭品最多有()个;木托盘上有14个名字的祭品最多有()个;
    请在每个()中填写一个正整数答案;
    网上初赛将分为两个阶段,其中第一阶段将于赛题发布的同时启动。参赛者需参加全部两阶段的比赛。两阶段的结果准确性得分及排名互相独立。即第二阶段启动后,第一阶段的的得分及排名将不再更新。赛事方将根据参赛者在两阶段比赛中提交的结果的准确性得分和参赛者所设计的算法的效率给出参赛者的综合成绩。

    参赛者需注意以下事项:

    • 参赛者以个人为单位参赛,最后结果只关联到一个参赛自然人。
    • 每天第一次登陆时参赛者会随机得到一个代表两个部落的人民之间好朋友关系的csv数据表格文件。参赛者需要在得到此表格文件后的1小时内提交答案,在此时间内参赛者最多可提交答案2次。超过该指定时间,则需等待至第二天再重新答题,重新答题后,参赛者将获得一份新的csv数据表格文件,并基于新得到的csv数据表格文件给出答案。
    • 参赛者可使用C/C++/Python/Matlab 计算机编程语言,在自己的计算机上计算出结果,再把计算结果输入到系统中。
    • 参赛者分别给出不同种类的祭品数量。系统将根据参赛者所提交的祭品数量的准确性给出参赛者的当次得分和历史最高得分。系统理论上能给出的最高得分为100分;系统将对参赛者的历史最高得分排名,该排名数据公开;得分相同的,以先提交结果者排名靠前。
    • 参赛者还需提供可在PC个人电脑上使用CPU单线程执行的算法程序源代码文件、编译后的程序文件(如有)和算法原理及测试环境搭建说明文档。参赛者需将源代码文件、编译后的程序文件(如有)和算法原理及测试环境搭建说明文档打包压缩为zip文件后上传系统,压缩包文件的命名规则为“拼音姓名_学校英文缩写.zip”。例如ZhangSan_NJU.zip。
    • 参赛者提交的源代码应当可直接读取符合赛题形式的本地csv数据表格文件,并将计算结果保存在以“result.txt”命名的文本文件中。源代码应符合常见的代码书写规范,源代码文件中应有必要的注释信息,具备良好的可读性。输出结果的内容应清晰可读。算法原理说明文档应使用中文文字清晰地说明所设计算法的思想。参赛者提交的说明文档不要和历史提交的文档关联,即提交的说明文档应是对算法原理和测试环境搭建的完整描述,而不是增量描述。算法原理的说明应不少于300字,说明文档请使用PDF或MS Word文件格式。
    • 在一般家用计算机配置条件下,使用CPU单线程,计算结果应当能在十分钟之内得到。如果参赛者的计算耗时明显高于此时间,则应考虑为所设计算法程序的效率问题,请对算法程序进行优化。留意观察数据的特征,参赛者也许可以找到提升效率的思路。

    题目理解

    对于这样一个以故事的形式描述的赛题,首先我们需要抽象出数学问题,其实就是Tanner图中不同长度的无向环的查找和计数问题,对应到我们通信领域中,就是要解决一个LDPC校验矩阵的短环问题,因为短环的存在会影响LDPC迭代译码时外信息传播的独立性,降低迭代译码收敛速度,甚至会使得算法最终无法收敛,因此评估LDPC校验矩阵的短环分布十分重要。说回到赛题,Tanner图中校验节点和变量节点的关系由一个256*640大小的邻接矩阵给出,我们把第一维看作校验节点,把第二维看作是变量节点,那么邻接矩阵中的每一个元素就表示两个节点之间是否有连接。根据题目描述,可知我们需要找出Tanner图中长度为4、6、8、10、12、14的无向环。因为数据维度较高,并且其中包含的无向环数量很大(长度为14的环的个数有两亿多个),所以需要我们在保证找出所有环的前提下(正确率必须达到100%),算法的计算复杂度越低越好(程序运行速度越快越好),这也符合5G 数据信道大带宽低延时的要求。

    传统算法

    对于LDPC校验矩阵中的短环查找问题,有研究者提出一种算法将短环计数问题转换为路径计数问题,最多可以对长度为g+4(tanner图的最短环长称为围长,用g表示)的短环进行计数,但本赛题的围长是4,同时要找出最大环长为14的环数量,所以这种算法不适用;还有一种算法通过枚举校验矩阵中不同环的形状,然后进行类似模式匹配的方法查找校验矩阵中不同长度的环,文献列举了环长最大到8的pattern,这种方法的缺点也很明显,随着环长增大,需要考虑的情况呈指数级增加。当然还可以直接从深度优先搜索DFS的方法出发,查找Tanner图中的无向环,这也是本赛题大部分选手使用的方法,这类算法相当于需要对图中的所有节点进行遍历,然后用回溯+去重的思路查找不同的无向环,算法的整体复杂度极高。

    基于树结构展开的无向环查找算法

    我所使用的是一种基于树结构展开的算法,具体来说,将tanner图中某一个变量节点作为根节点,构建一个树结构,树的偶数层由与变量节点连接的校验节点构成,树的奇数层则由与校验节点连接的变量节点构成,当树的第k层中某一变量节点或校验节点出现两次或两次以上时,就会构成长度为2k的环。我们来画一个图进行更具象的解释:
    在这里插入图片描述
    矩阵H表示了一个由4个变量节点和6个校验节点构成的Tanner图,其中变量节点和校验节点的编号为1到10。现在以1号节点为根节点,与其相连的有5、6、8号节点,因此这三个节点构成了树的第一层(包括根节点则为第二层),然后同理,在矩阵中找到和这三个节点相连的节点,构成树的第二层,分别为3、2、4,至此,还没有同层中含有相同节点的情况,再继续构造第三层,此时发现7、9、10均有两个,因此可以形成长度为2k=6的三个不同的环,即(1,5,3,9,2,6),(1,5,3,10,4,8),(1,6,2,7,4,8),注意(1,6,2,9,3,5)与第一个环相比只是路径顺序不同,在此塞题中,路径不同但所经过节点相同的环被认为是同一种环。图中右边的表格记录了每一层的每个结点到根节点的路径,在第三层中,两个颜色相同的行表示相同编号节点到根节点的两条路径,将这两条路径相连,即形成一个环。因此,通过上图介绍的树展开思想,一直构建到k=7,即可找出所有环长为4、6、8、10、12、14的环。

    排除无效环

    但是,由于本赛题的特殊性,我们还需要排除三种“无效环”情况,并设计相应的算法进行处理:
    1)提前成环:第k层出现相同的结点,若其父节点也存在相同,则此时长度为2k环即为无效环。我的处理方法是,将两条分支所经过的点进行桶计数,如果某个结点出现大于一次(不包括根),则应对其进行去重;
    2)顺序不同但结点相同:根据题意,当环所经过的节点相同但路径顺序不同时(例如1A2B与1B2A),上述方法会进行多次计数,但在本题要求中只能记一次。我的处理方法是,保留环的路径后对其进行排序,然后放入无序集合中(其底层是hashmap,将路径进行hash散列,放在对应的桶中,同一个桶中的hash值相同),如果出现上述情况,则不同路径但经过节点相同的环的hash值相同,可实现只记一次的目的;
    3)由环上的不同根节点展开得到相同的环:由于对所有变量结点展开至k层时,一种环会共计出现k次,因此将最后的计数除以k即为长度为2k环的数目。

    利用数据特征提升算法效率

    出题方在题目中指出 “留意观察数据的特征,参赛者也许可以找到提升效率的思路” 因此,分析一下数据特征,矩阵的维度为256 * 640, 可以明显看出是一个稀疏矩阵,对应到LDPC校验矩阵中,是一个QC-LDPC矩阵,其基矩阵大小为64*64,这一特征说明以64行为一组,将其中每个变量节点作为根节点,利用树结构展开之后所形成的环的数量是相同的,所以对于这64个变量节点来说,只需要以任意一个为根节点,然后计算环的数量,最后乘64即可,这个思路也大大降低了算法整体的计算时间。

    其他实现细节与代码优化思路

    • 因为LDPC是稀疏矩阵,所以将结点之间的关系由邻接矩阵转换为邻接表存储可以节省内存空间的同时加快查找速度。邻接表主要由两种指针构建,第一种指针是vertex结点指针(其中值为结点的值,指针为第一条边的指针),第二种指针是edge边指针(其中值为结点的值,指针为下一条边的指针),所以对所有变量节点和校验节点创建结点指针,然后根据节点之间的关系构建edge边指针即可。
    • 为解决“顺序不同但结点相同”的情况,需要把排序后的环放入unordered_set中保证元素的唯一性,因为它能够快速查找和添加,首先需要对环进行散列,散列的对象是类型为array<short int,14>的数组,其中array中保存的是14环的排序后的路径(不足14则补零),因此散列函数需要自定义:arrayhash相当于对所有元素进行hash变换之后进行异或,最终得到该array的hash值。
    //unordered_set需要自定义hash函数
    struct ArrayHash {
    	size_t operator()(const std::array<short int, 14>& v) const {
    		std::hash<short int> hasher;
    		size_t seed = 0;
    		for (short int i : v) {
    			seed ^= hasher(i) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
    		}
    		return seed;
    	}
    };
    
    • 使用visual studio的性能探查器,可以针对每一行代码或者每一个函数的调用次数以及运行时间占比进行统计:大量的时间都耗费在了unordered_set.insert()这个函数中,分析其原因,就是是扩容造成的。然后还有去重算法、vector初始化大小上的优化。

    • 扩容优化:在vector中,每当我们插入一个新元素时,如果当前的容量(capacity)已不足,需要向系统申请一个更大的空间,然后将原始数据拷贝到新空间中。这种现象在unordered_set中也存在,在本题中也极大的影响了计算时间。每个桶放太多的元素就会影响到unordered_set的存取效率,而标准库通过采用某种策略来对当前空间进行扩容,来提高存取效率。但是这里面有一点我们需要注意的是,每当unordered_set内部进行一次扩容或者缩容,都需要对表中的数据重新计算,也就是说,扩容或者缩容的时间复杂度至少为O(N)。标准库的默认初始桶的数量是16,而在我们的任务中,环的数量以亿为单位,环长14的环为两亿左右,最终近三百多万个桶,如果按照标准库的策略进行扩容,需要非常多次的扩容操作,将导致时间的大量耗费,这一问题是使用性能探查器的时候发现的,因此我查看unordered_set的底层实现,发现我们可以通过rehash函数进行桶的人为初始化,如果不初始化则默认为16,所以将桶的初始数量设置为三百万,这样就避免了多次扩容,节省了大量的时间。

    • 使用5*5的全1矩阵进行算法校验,然后把找到的环打印出来,可以看到自己到底是没有针对哪种情况进行剪枝。

    • 对数据结构的优化,例如
      (1)Vector的排序要比array的排序快20%;
      (2)将存储的结点类型从4字节int改为short int 也就是2字节的,由于需要进行大量的hash变换,这样可以大大节省计算量,时间从0.8秒左右,降低为了0.5秒。

    比赛结果

    比赛分为两个阶段,第二个阶段的矩阵维度更大,环的数量更多,因此对算法的计算复杂度要求更严格,一部分选手的算法由于过于复杂,没有在要求的30分钟内找到所有环。本文所使用的基于树展开的算法在两个阶段均为第一名,并在算法效率上大幅领先于第二名。
    比赛第一阶段
    在256 * 640大小的LDPC矩阵中,找到所有长度为4、6、8、10、12、14的环时间为0.5秒左右
    在这里插入图片描述
    比赛第二阶段
    在1344 * 1344大小的LDPC矩阵中,找到所有长度为4、6、8、10、12、14的环时间为5秒左右
    在这里插入图片描述

    展开全文
  • 中兴捧月 婚恋匹配 java源码 复赛优秀奖
  • 2013年 中兴捧月杯 程序设计(第二题)初赛 此代码成功进入复赛
  • 中兴捧月初赛试题答案,已成功进入复赛,快来下载 一个是用C写的,一个是C++写的,希望对大家有用~~
  • 2020中兴捧月傅里叶派记录

    千次阅读 多人点赞 2020-05-14 15:15:19
      前段时间看到了同学转发的中兴通讯的比赛链接,之前也没有参加过算法类的比赛,这次打算报着试一试的态度参加下,增加下经验。在初步看了几个门派的题目简介后,发现只有傅里叶派比较适合自己,所以最终选择了...
  • 本程序是2011年中兴捧月杯程序设计比赛中进入决赛的作品。 名称:IPTV的实现 功能:共三个子程序,分别为服务器,交换机,机顶盒 具体:服务器可以实时显示三个频道的信息,并把三个频道的视频帧以UDP单播形式发送到...
  • 大家有了解的吗,本人大三党,想参与一下?但是不知道参与了有啥好处啊
  • 中兴捧月复赛程序

    2013-07-29 21:47:00
    中兴捧月 复赛程序 可运行 在初赛程序的基础上改的
  • 中兴捧月比赛讲解

    2014-10-22 18:21:23
    谈谈“中兴捧月”比赛首先自我介绍一下,我的专业是通信与信息系统,研究方向为移动通信,我所在的团队是重邮信科 3G 研究院,因此研究生期间我主要从事与 TD/ TD-LTE 芯片相关的开发工作。在 11 年 6 月到 10 月...
  • 说明: 并非最终获奖版本,该版本最快时长为1100ms左右,中间有一些我当时分析各个操作时间占比的代码并没有注释掉 代码思路: 首先进行文件读取 然后是连接算法,这里采用了sort merge
  • 赛道选择上还是出了些问题,对于编解码不够熟悉导致决赛在理解题意上就费了不少时间,不过也是第一次参加这种竞赛,也算是有所收获了,而且zte的工作人员都挺热情的,接下来会更多刷题和刷题思路的更新了。...
  • 此为2013年中兴捧月杯编程大赛晋级作品,欢迎提出意见
  • 中兴捧月比赛2020

    千次阅读 2020-04-11 11:33:40
    今年的比赛主要分为以下5个门派 傅里叶派:信号 迪杰斯特拉派:智能网络调度 图灵派 :音视频 阿尔法·勒克斯特派:目标检测与跟踪 埃德加·考特派:数据库 先码住,之后进行技术分享 中兴捧月2020年比赛CV方向思路
  • 中兴捧月历年题目

    2012-05-09 17:35:08
    中兴捧月历年题目 要比赛的同学们注意啦,整理不容易呀

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 678
精华内容 271
关键字:

中兴捧月