精华内容
下载资源
问答
  • 京东2017算法大赛数据集
  • ZTE2017中兴捧月算法大赛无线通信算法相关题目及作品。资源内包含ZTE2017中兴捧月算法大赛题目和ZTE2017中兴捧月算法大赛作品。
  • 2020腾讯广告算法大赛——算法小白的复盘

    在这里插入图片描述

    写在前面

    全文共计11958字,请合理使用目录(阅读助手)辅助阅读
    在这里插入图片描述
    《2020腾讯广告算法大赛》复赛已经接近尾声,作为一瓶初赛酱油,打算做个复盘,留个笔记,本来初赛结束就打算写的,被各种事情耽搁了,直到今天才动手开写

    先说下个人情况:某电商公司任职,数据分析方向,做的大部分是DBA和爬虫的活(从过往博客也看的出来),了解过sklearn库的一些传统机器学习(eg:决策树、随机森林、Kmeans、逻辑回归等基础传统机器学习算法),(卷积)神经网络,lgb,lstm,W2V,RNN等都是在比赛过程中听大佬们分享后现学的(虽然还是不太会用,原理也推不出来,至少比一开始听见这些词都一脸懵逼要好太多太多 了),

    可以说是算法纯小白,最终成绩:score — 1.269806;排名 — 367

    在这里插入图片描述

    赛题介绍

    题目:广告受众基础属性预估
    在这里插入图片描述

    赛题描述
    本届算法大赛的题目来源于一个重要且有趣的问题。众所周知,像用户年龄和性别这样的人口统计学特征是各类推荐系统的重要输入特征,其中自然也包括了广告平台。这背后的假设是,用户对广告的偏好会随着其年龄和性别的不同而有所区别。许多行业的实践者已经多次验证了这一假设。然而,大多数验证所采用的方式都是以人口统计学属性作为输入来产生推荐结果,然后离线或者在线地对比用与不用这些输入的情况下的推荐性能。本届大赛的题目尝试从另一个方向来验证这个假设,即以用户在广告系统中的交互行为作为输入来预测用户的人口统计学属性。

    我们认为这一赛题的“逆向思考”本身具有其研究价值和趣味性,此外也有实用价值和挑战
    性。例如,对于缺乏用户信息的实践者来说,基于其自有系统的数据来推断用户属性,可以帮助其在更广的人群上实现智能定向或者受众保护。与此同时,参赛者需要综合运用机器学习领域的各种技术来实现更准确的预估。

    具体而言,在比赛期间,我们将为参赛者提供一组用户在长度为91天(3 个月)的时间窗
    口内的广告点击历史记录作为训练数据集。每条记录中包含了日期(从1到91)、用户信息(年龄,性别),被点击的广告的信息(素材 id、广告 id、产品 id、产品类目 id、广告主id、广告主行业id等),以及该用户当天点击该广告的次数。测试数据集将会是另一组用户的广告点击历史记录。提供给参赛者的测试数据集中不会包含这些用户的年龄和性别信息。

    本赛题要求参赛者预测测试数据集中出现的用户的年龄和性别,并以约定的格式提交预测结果。大赛官网后台将会自动计算得分并排名。详情参见【评估方式】和【提交方式】。
    初赛和复赛除了所提供的训练数据集的量级有所不同之外,其他设置均相同。

    提交方式
    参赛者提交的结果为一个带标题行的 submission.csv 文件,编码采用无 BOM 的 UTF-8,
    具体格式如下(字段顺序以下面的描述为准,各字段用逗号分隔,中间无空格):
    ⚫ user_id
    ⚫ predicted_age: 预测的用户年龄分段,取值范围[1,10]。
    ⚫ predicted_gender: 预测的用户性别,取值范围[1,2]。
    测试数据集中每个用户均应在submission.csv文件中对应有且仅有一行预测结果。各用户
    的预测结果在该文件中的出现顺序与评估结果无关。

    评估方式
    大赛会根据参赛者提交的结果计算预测的准确率(accuracy)。年龄预测和性别预测将分别评估准确率,两者之和将被用作参赛者的打分。

    测试数据集会和训练数据集一起提供给参赛者。大赛会将测试数据集中出现的用户划分为两组,具体的划分方式对参赛者不可见。其中一组用户将被用于初赛和复赛阶段除最后一天之外的排行榜打分计算,另一组则用于初赛和复赛阶段最后一天的排行榜打分计算,以及最后的胜出队伍选择。

    2020腾讯算法大赛初赛数据集下载【提取码:46lw】

    个人赛况

    阶段一:score 0.89+
    ①3+1
    descirbe() 对train训练数据描述可得 年龄age3的概率最大,性别gender1的概率最大
    直接提交 预测结果age3+gender1 score就可达到0.893+

    ②word2vec训练参数错误
    在参考了各路大佬的w2v方案后依然没有突破 0.89,一度弃赛,在某个月黑风高的夜晚,突然来了一手神来之笔,查看W2V训练后的词向量,结果发现训练出来的词向量是0-9,

    阶段二:score 1.2+
    word2vec+Lgb
    纠正了word2vec训练的词向量之后就达到了1.2+
    由于深度学习啥也不懂,还是没有达到大佬们的baseline

    解题思路(代码思路)——copy的各路大佬的基本思路:
    把每个点击的广告id当作一个词,把一个人90天内点击的广告id列表当作一个句子,使用word2vec来制作一个“word embedding”,把问题转化成一个NLP题目;把广告id的embedding喂入lgb——一度试图把所有的的特征组合训练wordembedding,keras内存爆炸 ,后来试了挑选三个进行组合,score反而下降了,可能组合姿势有问题

    代码开源-score 1.2+

    【00】数据导入TI-ONE

    #安装&导入库
    !pip install wget
    import wget,tarfile,zipfile
    
    #压缩数据包下载
    filename = wget.download("https://tesla-ap-shanghai-1256322946.cos.ap-shanghai.myqcloud.com/cephfs/tesla_common/deeplearning/dataset/algo_contest/train_preliminary.zip")
    print(filename)
    
    #解压缩
    zFile = zipfile.ZipFile(filename, "r")
    for fileM in zFile.namelist():
        zFile.extract(fileM, "./")
        print(fileM)
    zFile.close();
    

    【01】按userid聚合(groupby)特征

    #导入库
    import tensorflow as tf
    import pandas as pd
    import numpy as np
    import gc
    
    #聚合去重并计数
    def get_groupby_data(data,group_zd='user_id',pj_zd='ad_id'):
        data_dict=dict(list(data.groupby(group_zd)))
        result=[]
        for key in data_dict.keys():
            result.append([key,str(data_dict[key][pj_zd].to_list())[1:-1].replace(',','')])
        pd_result=pd.DataFrame(result)
        pd_result.columns=[group_zd,pj_zd]
        return pd_result
        
    #设置聚合特征
    # zd_list=['ad_id','product_category','advertiser_id', 'time', 'click_times']
    zd_list=['creative_id']
    
    #train_data读取
    train_ad=pd.read_csv("../train_preliminary/ad.csv",na_values="\\N")
    train_click_log=pd.read_csv("../train_preliminary/click_log.csv",na_values="\\N")
    train_user=pd.read_csv("../train_preliminary/user.csv",na_values="\\N")
    data=pd.merge(pd.merge(train_ad,train_click_log),train_user)
    
    #内存清理
    del train_ad,train_click_log
    gc.collect()
    
    #train_data聚合
    for zd in zd_list:
        new_data=data[[zd,'user_id']]
        new_data=get_groupby_data(new_data,pj_zd=zd)
        new_data=pd.merge(new_data,train_user)
        new_data.to_csv(zd+"/groupby_data/train_%s.csv"%zd,index=False)
        print("-"*10+zd+'汇总完成'+'-'*10)
    
    
    #test_data读取
    test_ad=pd.read_csv("../test/ad.csv")
    test_click_log=pd.read_csv("../test/click_log.csv")
    test_data=pd.merge(test_ad,test_click_log)
    
    #test_data聚合
    for zd in zd_list:
        test_data_new=test_data[[zd,'user_id']]
        test_data_new=get_groupby_data(test_data_new,pj_zd=zd)    
        test_data_new.to_csv(zd+"/groupby_data/test_%s.csv"%zd,index=False)
        print("-"*10+zd+'汇总完成'+'-'*10)
    

    【02】word2vec训练

    #导入库
    import tensorflow as tf
    import pandas as pd
    import numpy as np
    import os
    !pip install gensim
    import gc
    from gensim.models.word2vec import Word2Vec
    
    # 设定词向量训练的参数
    num_features = 128   # Word vector dimensionality
    min_word_count = 0   # Minimum word count
    num_workers = 4       # Number of threads to run in parallel
    context = 10         # Context window size
    model_name = '{}features_{}minwords_{}context.model'.format(num_features, min_word_count, context)
    
    #设置训练特征
    # zd_list=['creative_id','ad_id','product_category','advertiser_id', 'time', 'click_times']
    zd_list=['creative_id']
    
    #词向量训练
    for zd in zd_list:
        new_data=pd.read_csv(zd+"/groupby_data/train_%s.csv"%zd,na_values="\\N")
        new_data2=pd.read_csv(zd+"/groupby_data/test_%s.csv"%zd,na_values="\\N")
        new_data3=pd.concat([new_data,new_data2])
        del new_data,new_data2
        gc.collect()#清理内存
        sentences_list = []
        #注意:需要split传入list,第一次没有split训练的词模型是0-9
        for line in new_data3[zd]:
            sentences_list.append(line.split())
        model = Word2Vec(sentences_list, workers=num_workers, \
                    size=num_features, min_count = min_word_count, \
                    window = context)
        model.save(os.path.join(zd, 'models', model_name))
        print("-"*10+zd+'训练完成'+'-'*10)
    

    【03】数据特征化

    #导入库
    import tensorflow as tf
    import pandas as pd
    import numpy as np
    import os
    !pip install gensim
    from gensim.models.word2vec import Word2Vec
    
    def to_review_vector(review):
        global word_vec
        word_vec = np.zeros((1,300))
        for word in review.split():
            #word_vec = np.zeros((1,300))
            if word in fastmodel:
                word_vec += np.array([fastmodel[word]])
        #print (word_vec.mean(axis = 0))
        return pd.Series(word_vec.mean(axis = 0))
    
    #由于机器限制,数据分段特征化&存储
    #zd_list=['creative_id','ad_id','product_category','advertiser_id', 'time', 'click_times']
    model_name='300features_0minwords_10context.model'
    # zd_list=['product_category','advertiser_id', 'time', 'click_times']
    zd_list=['creative_id']
    for zd in zd_list:
        data=pd.read_csv(zd+"/groupby_data/train_%s.csv"%zd)
        try:
            os.mkdir(zd+"/train_feature")
        except:
            pass
        fastmodel=Word2Vec.load(zd+'/models/'+model_name)
        count=0
        mm=0
        for i in range(100000,len(data)+1,100000):
            train_data_features = data[count:i][zd].apply(to_review_vector)
            w2c_data=pd.concat([data[count:i][['user_id','age','gender']],train_data_features],axis=1)
            w2c_data.to_csv(zd+"/train_feature/w2c_data_%s%s.csv"%(zd,mm),index=False)
            print("---%s第 %s 段数据特征向量化完成---"%(zd,mm))
            mm+=1
            count=i
            
    

    【04】lgb模型训练

    #导入库
    !pip install lightgbm
    import lightgbm as lgb
    from sklearn.metrics import mean_squared_error
    from sklearn.datasets import load_iris
    from sklearn.model_selection import train_test_split
    import tensorflow as tf
    import pandas as pd
    import numpy as np
    import os
    import gc
    
    # zd_list=['creative_id','ad_id','product_category','advertiser_id','time','click_times']
    zd_list=['creative_id']
    
    #分段特征数据合并
    for zd in zd_list:
        path=zd+"/train_feature/"
        wjs=os.listdir(path)
        data=pd.DataFrame()
        for wj in wjs:
            data_path=path+wj
            data0=pd.read_csv(data_path)#.drop(zd,axis=1)
            data=data.append(data0)
            print(len(data))
        data.columns=[zd+'_'+cc if cc not in ['user_id', 'age', 'gender'] else cc for cc in data.columns]
        if zd==zd_list[0]:
            data1=data
        else:
            data1=pd.merge(data1,data)
        gc.collect()#清理内存
        print('!'*10+zd+'拼接完成')
        
    #内存清理
    del data,data0
    gc.collect()
    
    #age模型训练
    train_x=data1[data1.columns.difference(['user_id','age','gender'])]
    target=data1.age.astype(int)
    # 划分训练集和测试集
    X_train, X_test, y_train, y_test = train_test_split(train_x, target, test_size=0.2)
    del train_x,data1
    gc.collect()#清理内存
    print("Train data length:", len(X_train))
    print("Test data length:", len(X_test))
    # 转换为Dataset数据格式
    lgb_train = lgb.Dataset(X_train, y_train)
    lgb_eval = lgb.Dataset(X_test, y_test, reference=lgb_train)
    
    # 参数
    params = {
        'task': 'train',
        'boosting_type': 'gbdt',  # 设置提升类型
        'objective': 'multiclass',  # 目标函数
        'num_class': 11,  
    #     'metric': {'l2', 'auc'},  # 评估函数
        'num_leaves': 31,  # 叶子节点数
        'learning_rate': 0.05,  # 学习速率
        'feature_fraction': 0.9,  # 建树的特征选择比例
        'bagging_fraction': 0.8,  # 建树的样本采样比例
        'bagging_freq': 5,  # k 意味着每 k 次迭代执行bagging
        'verbose': 1  # <0 显示致命的, =0 显示错误 (警告), >0 显示信息
    }
    
    # 模型训练
    gbm = lgb.train(params, lgb_train, num_boost_round=1000, valid_sets=lgb_eval, early_stopping_rounds=5)
    # 模型保存
    gbm.save_model('model_age.txt'
    # 模型加载
    gbm = lgb.Booster(model_file='model_age.txt')
    # 模型预测
    y_prob = gbm.predict(X_test, num_iteration=gbm.best_iteration)
    
    arr=pd.DataFrame(y_prob)
    arr['max_value']=arr.max(axis=1)
    arr['max_index']=np.argmax(y_prob,axis=1)
    y_pred1=arr['max_index']
    
    # 模型评估
    print('The rmse of prediction is:', mean_squared_error(y_test,y_pred1) ** 0.5)
    
    
    #gender模型训练
    train_x=data1[data1.columns.difference(['user_id','age','gender'])]
    target=data1.gender.astype(int)
    # 划分训练集和测试集
    X_train, X_test, y_train, y_test = train_test_split(train_x, target, test_size=0.2)
    del train_x,data1
    gc.collect()#清理内存
    print("Train data length:", len(X_train))
    print("Test data length:", len(X_test))
    # 转换为Dataset数据格式
    lgb_train = lgb.Dataset(X_train, y_train)
    lgb_eval = lgb.Dataset(X_test, y_test, reference=lgb_train)
    
    # 参数
    params = {
        'task': 'train',
        'boosting_type': 'gbdt',  # 设置提升类型
        'objective': 'multiclass',  # 目标函数
        'num_class': 11,  
    #     'metric': {'l2', 'auc'},  # 评估函数
        'num_leaves': 31,  # 叶子节点数
        'learning_rate': 0.05,  # 学习速率
        'feature_fraction': 0.9,  # 建树的特征选择比例
        'bagging_fraction': 0.8,  # 建树的样本采样比例
        'bagging_freq': 5,  # k 意味着每 k 次迭代执行bagging
        'verbose': 1  # <0 显示致命的, =0 显示错误 (警告), >0 显示信息
    }
    
    # 模型训练
    gbm = lgb.train(params, lgb_train, num_boost_round=1000, valid_sets=lgb_eval, early_stopping_rounds=5)
    # 模型保存
    gbm.save_model('model_gender.txt')
    # 模型加载
    gbm = lgb.Booster(model_file='model_gender.txt')
    # 模型预测
    y_prob = gbm.predict(X_test, num_iteration=gbm.best_iteration)
    
    arr=pd.DataFrame(y_prob)
    arr['max_value']=arr.max(axis=1)
    arr['max_index']=np.argmax(y_prob,axis=1)
    y_pred1=arr['max_index']
    
    # 模型评估
    print('The rmse of prediction is:', mean_squared_error(y_test,y_pred1) ** 0.5)
    

    【05】test分批次预测

    #导入库
    !pip install lightgbm
    import lightgbm as lgb
    from sklearn.metrics import mean_squared_error
    from sklearn.datasets import load_iris
    from sklearn.model_selection import train_test_split
    import tensorflow as tf
    import pandas as pd
    import numpy as np
    import gc
    import os
    
    # zd_list=['creative_id','ad_id','product_category','advertiser_id', 'time', 'click_times']
    zd_list=['creative_id']
    for zd in zd_list:
        path=zd+"/test_feature/"
        wjs=os.listdir(path)
    #     wjs=os.listdir(path)[5:]
        data=pd.DataFrame()
        for wj in wjs:
            data_path=path+wj
            data0=pd.read_csv(data_path).drop(zd,axis=1)
            data=data.append(data0)
            del data0
            gc.collect()#清理内存
            print(len(data))
        data.columns=[zd+'_'+cc if cc not in ['user_id'] else cc for cc in data.columns]
    #     data.columns=[zd+'_'+cc if cc not in ['user_id', 'age', 'gender'] else cc for cc in data.columns]
        if zd==zd_list[0]:
            data1=data
        else:
            data1=pd.merge(data1,data)
        del data
        gc.collect()#清理内存
        print('!'*10+zd+'拼接完成')
    
    # data1=data1[:500000]
    data1=data1[500000:]
    
    result=data1[['user_id']].reset_index(drop=True)
    test_X=data1[data1.columns.difference(['user_id'])]
    del data1
    gc.collect()#清理内存
    # 模型加载
    gbm = lgb.Booster(model_file='model_age.txt')
    # 模型预测
    y_test = gbm.predict(test_X, num_iteration=gbm.best_iteration)
    arr=pd.DataFrame(y_test)
    arr['max_value']=arr.max(axis=1)
    arr['max_index']=np.argmax(y_test,axis=1)
    result['age']=arr['max_index']
    
    
    # 模型加载
    gbm = lgb.Booster(model_file='model_gender.txt')
    # 模型预测
    y_test = gbm.predict(test_X, num_iteration=gbm.best_iteration)
    arr=pd.DataFrame(y_test)
    arr['max_value']=arr.max(axis=1)
    arr['max_index']=np.argmax(y_test,axis=1)
    result['gender']=arr['max_index']
    
    
    result.columns=['user_id','predicted_age','predicted_gender']
    # result.to_csv('submission1.csv',index=False)
    result.to_csv('submission2.csv',index=False)
    print(len(result))
    

    【06】合并和提交到COS存储桶

    import pandas as pd
    import numpy as np
    
    #文件合并
    data1=pd.read_csv("submission1.csv")
    data2=pd.read_csv("submission2.csv")
    data=pd.concat([data1,data2])
    print(len(data))
    data.to_csv("submission.csv",index=False)
    
    from ti import session
    ti_session = session.Session()
    # path:结果文件的路径
    # bucket:指定存储桶。
    # key_prefix:存储桶下的 cos 路径
    inputs = ti_session.upload_data(path="submission.csv", bucket="game-gt-1252065438", key_prefix="test")
    

    参考资料

    【00】如何使用 TI-ONE Notebook 玩转算法大赛

    【01】易观性别年龄预测chizhu大佬的冠军开源

    【02】2020腾讯广告算法大赛:赛题理解与解题思路

    【03】2020腾讯广告算法大赛基本思路(线上1.3+)

    【04】2020腾讯广告算法大赛:如何突破分数瓶颈?

    【05】2020腾讯广告算法大赛:高分进阶

    【06】大神干货:冠军选手分享解题思路,助你轻松突围初赛

    【07】高分选手讲解:如何突破思维圈限,从NLP角度挖掘新的解题思路

    【08】超值赛题分享大礼包,你的“六一”礼物来咯!

    【09】【王牌选手分享】一发问鼎!鹅厂大神上分思路,助你玩转初赛!

    【10】【前排选手分享】初赛尾声将至,大神带你最后一搏!

    【11】【特色团队采访】1+1+1>3?看新人团队如何高效合作

    特别感谢各位大佬的分享,虽然最终没进复赛,也算感受了一波算法的魅力,尤其感谢鱼佬的耐心解惑;最后还得特别感谢下腾讯智能钛机器学习 TI-ML,要不然我那渣渣机器连 数据都读不完就内存溢出了,确实挺好用的,我只用了notebook,已经集成好了tensflow环境,贼方便,还有其他机器学习操作,没玩转,对notebook比较熟!全程都是notebook,而且对于社畜而言还有个好处就是云上同步,不论在哪我都不用把代码倒腾过来倒腾过去,只要连网就可以看到你原先操作的代码,甚至于在公司点了运行,坐个地铁到家直接登陆看结果!从一开始感觉特别麻烦不习惯,到最后的”真香"!!!没人逃得掉王镜泽定律(没收鹅厂广告费 ,麻烦腾讯云看到了给打笔广告费)

    展开全文
  • 中兴算法大赛

    2017-05-20 15:01:00
    由华为软件大赛得出的结论,比赛真的很重要,要不然一些机会就会失之交臂,所以抓紧参加了中兴举报的算法大赛,大赛的成绩终于定下来了,出乎意料的低,35分连评语都没有,虽然大家都在群里讽刺中兴算法大赛是程序员...

    由华为软件大赛得出的结论,比赛真的很重要,要不然一些机会就会失之交臂,所以抓紧参加了中兴举报的算法大赛,大赛的成绩终于定下来了,出乎意料的低,35分连评语都没有,虽然大家都在群里讽刺中兴算法大赛是程序员营销大赛,评分只看PPT,不过还是有很多可以总结的地方。

    赛题为:

    最强大脑中的收官蜂巢迷宫变态级挑战,相信大家都叹为观止!最强大脑收官战打响后,收视率节节攀升,就连蚁后也不时出题难为一下她的子民们。在动物世界中,称得上活地图的,除了蜜蜂,蚂蚁当仁不让。在复杂多变的蚁巢中, 蚂蚁总是能以最快、最高效的方式游历在各个储藏间(存储食物)。今天,她看完最新一期节目,又发布了一项新任务:小蚁同学,我需要玉米库的玉米,再要配点水果,去帮我找来吧。小蚁正准备出发,蚁后又说:哎呀,回来,我还没说完呢,还有若干要求如下:

    1.小蚁同学,你需要尽可能以最少的花费拿到食物(附件图中路线上的数值表示每两个储物间的花费);

    2.小蚁同学,你最多只能经过9个储藏间拿到食物(包含起止两个节点,多次通过同一节点按重复次数计算);

    3.小蚁同学,你必须经过玉米间,水果间(附件图中标绿色节点);

    4.别忘了,食蚁兽也在路上活动呢,一旦与食蚁兽相遇,性命危矣!不过小蚁微信群公告已经公布了敌人信息(附件图中标红色路段);

    5.最后,千万别忘了,还有两段路是必须经过的,那里有我准备的神秘礼物等着你呢(附件图中标绿色路段)。

    这下小蚁犯难了,这和它们平时找食物的集体活动规则不一样嘛,看来这次需要单独行动了。要怎么选路呢?小蚁经过一番苦思冥想,稿纸堆了一摞,啊,终于找到了!亲爱的同学们,你们能否也设计一种通用的路径搜索算法,来应对各种搜索限制条件,找到一条最优路径,顺利完成蚁后布置的任务呢?

    注:

    1、蚁巢,有若干个储藏间(附件图中圆圈表示),储藏间之间有诸多路可以到达(各储藏间拓扑图见附件);

    2、节点本身通行无花费;

    3、该图为无向图,可以正反两方向通行,两方向都会计费,并且花费相同;

    4、起止节点分别为附件图中S点和E点。

    5、最优路径:即满足限制条件的路径。

    由于成绩未出,稍后还有决赛还不便公布自己的算法,先写到这里吧

     

    一、算法思路:

    我们把题目看成旅行商问题,然后用遗传算法求出最优解或者次优解。

    二、模型建立

    本题属于单源单点间附加必经点、必经边的问题,为将本题转化为旅行商问题,加上还需一条从源点S到终点T的附加边,该边的花费为源点到终点的花费,然后将边当做一条必经边来处理。对于必经边,采用将必经边也处理成一个特殊的必经点的方法,该特殊必经点包含起点和终点。在染色体中只出现必经边u-v上的一点,如果是u则代表从必经边的u点进入,从v点出去;如果是v则代表从必经边的v点进入,从u点出去,然后本题就可以转化为存在一定数量必经点的旅行商问题。

         初始化:生成SUM个初始解,初始解1为贪心解,其余SUM-1个解均为随机生成。贪心解的思想是,离源点S越近的必经点或必经边,越先放进解中,如例图,离远点最近的是属于必经边2-4的点2,所以将必经点2放进初始解(隐含了2-4这条边),接下来是点7,将其放进解中,然后是属于必经边(13-14)的点14,将点14放进初始解中(隐含了14-13这条边),然后是点12,最后把终点T到源点S的边放进去,生成第一个贪心的初始解,为2(4)-7-14(13)-12-17(0);其余SUM-1个初始解均为随机生成必经点必在解中,必经边中的一个点u在解中,隐含了u-v这条边,例如:上节随机初始化的另一组解4 13 12 7 17,其中点4代表路径4-2,13代表路径13-1417代表路径17-0

    个体评价:以贪心生成的解2(4)-7-14(13)-12-17(0)为例:染色体中第一个基因是点2,属于必经边,现加上边2-4的权值,然后加上4到下一个结点7的权值;结点7不是必经边,直接加上结点7到下一个点14的权值;结点14属于必经边,先加上14-13的权值,再加上结点13-12的权值;结点12不是必经边,直接加上结点12到下一结点17(即终点)的权值;结点17属于必经边,先加上结点17到结点0(即源点)的权值,然后加上结点02的权值;然后最后减去源点到起点的权值,即为此路径的花费,上述贪心解的花费为13

    对于该染色体经历的结点数量使用的方法是提前通过弗洛伊德算法得到的最短路径信息得到所有必经点之间两两的最小花费经历结点数,然后对某一必经点组合,只需要遍历一遍所有节点然后加起来,就可以得到改染色体所经历的结点数;

    选择运算:因为通过交叉得到的子代总是小于等于父代,所以这里直接选择交叉变异产生的子代。

    记录最优:有两个记录最优的方面,一方面是记录满足结点数满足最少结点要求的最优解,一个室结点数不满足最少节点数的次优解;

    交叉运算:选择两个参加交叉的染色体作为父代,例如:

    A=2(4)-7-14(13)-12-17(0)

    B=12-7-13(14)-4(2)-17(0)

    染色体Acost13,染色体Bcost19;首先比较结点47的权值为3127之间的权值也为3;就以2(4)为头结点,将初始解右转动为(染色体B中没有特殊节点2(4),但是因为24均属于必经边2-4,在此将染色体B中的4(2)替换成2(4)代表从2点进入,然后从4点出)

    A=2(4)-7-14(13)-12-17(0)

    B=2(4)-17(0)-12-7-13(14)

    然后比较47的权值为3417的权值为4,所以就有:

    A=*-7-14(13)-12-17(0)

    B=*-7-13(14)-17(0)-12

    由此规则计算可得:

    O=2(4)-7-14(13)-12-17(0)

    我们本来是2个不同的解,现在得到了一个比两个解都优的解,总不能让原来的两个解都等于现在的这个局部最优解吧,这样不利于下次交叉,我们可以用随机旋转的方法改变另外一个解的路径:Rotate(q.info, NUMmustp, rand() % NUMmustp);

    变异运算只需要在一个解中随机的选择两个基因,然后交换它们即可。

     

    三、算法实现结果分析

     

        读图(邻接表),将食蚁兽所在的路径花费设为0x3f3f3f,既不经过此路径(剪枝)

     

    1.弗洛伊德算法求取加权图中多源点之间最短路径

     

        因为后期需要大量计算最短路径,选择迪杰斯特拉只能求取单源单汇之间的最短路径,多次调用的话时间消耗太大。所以这里使用弗洛伊德算法一次求取,后面直接调用。迪杰斯特拉算法复杂度为主要依赖于最小优先队列的实现,使用简单数组算法复杂度为OV^2),使用二叉堆可以优化到O(ElgV),使用斐波那契堆可以优化到O(VlgV+E);而弗洛伊德时间复杂度为O(N^3),空间复杂度为O(N^2)。当图的规模比较大,并且必经点、必经边比较多的话,使用弗洛伊德算法可以大规模减少时间

     

    2.初始化初始种群

     

        第一个解为贪心求得,其余SUM个解为随机生成;因为例图里面的点比较少,所以使用贪心求取的路径已经是局部最优了

     

    3.遗传全局优化

     

         因为图比较小,通过贪心就直接获得最优了,所以这里我统计了每一代所有染色体的权值和的平均,种群规模SUM10000,制成图。从上图可以看出来通过遗传可以很快收敛到最优附近,然后利用遗传的全局寻优能力寻找最优解

     

    4.输出

     

        针对题中所给用例,通过我们的解题算法,在满足所有要求的情况下并未搜索一条最优的路径,经统计每一代最终的平均花费是逐渐变小并最终稳定在13,最终输出一组次优路径,路径为:0->2->4->5->6->7->8->14->13->12->16->17,经过12个点,花费为13

     

    #include<stdio.h>
    #include <stdlib.h>  
    #include <memory.h>
    
    #define MAXN 10000
    #define INF 0x3f3f3f
    #define SUM 10            //总共的染色体数量  
    #define MAXloop 10000       //最大循环次数  
    #define error 0.01        //若两次最优值之差小于此数则认为结果没有改变  
    #define crossp 0.7        //交叉概率  
    #define mp 0.1           //变异概率 
    
    int numnode = 0;
    int dis[MAXN][MAXN];
    int pathmatirx[MAXN][MAXN];
    int numofnodepath[MAXN][MAXN];
    int S ;   //起点
    int T ;   //终点
    int mustp[MAXN];
    int nummustp = 0;   //必经点的个数,必经边算两个必经点
    int NUMmustp = 0;   //个体中的染色体个数
    
    int ret[1000];
    int ptri = 0;
    
    struct gen                        //定义染色体结构  
    {  
        int info[MAXN];               //染色体结构,表示从0开始经过这个染色体结构之后,到达T
        int cost;            //次染色体所对应的适应度函数值,在本题中为表达式的值  
    	int numofnode;
    }; 
    struct gen gen_group[SUM];//定义一个含有20个染色体的组    
      
    struct gen gen_result;     //记录次优的染色体 
    struct gen gen_result2;    //记录最优的染色体 
    int result_unchange_time; //记录在error前提下最优值为改变的循环次数  
    
    struct mustedge{
    	bool flag;
    	int u;
    	int v;
    }ismustedge[MAXN];
    
    
    //**************************************普通函数声明*****************************//
    void reading();                            //读图
    void floyd();                              //弗洛伊德求最短路径
    void init();                               //初始化
    int   randsign(float p);    //按照概率p产生随机数0、1,其值为1的概率为p   
    int   randbit(int i,int j); //产生一个在i,j两个数之间的随机整数   
    void findway( int a , int b );
    int numofnode( int i , int j );
    
    //**************************************遗传函数声明*****************************//
    void gen_swap(gen *a,gen *b);                         //结构体交换
    void gen_quicksort(gen *number,int left,int right);   //种群排序
    void initiate();            //初始化函数,主要负责产生初始化种群   
    void evaluation(int flag);  //评估种群中各染色体的适应度,并据此进行排序   
    void Cross_group( gen &p, gen &q);               //交叉函数   
    void selection();           //选择函数   
    int  record();              //记录每次循环产生的最优解并判断是否终止循环   
    void Varation_group(gen group[]);            //变异函数   
    int Search_son( int path[], int len, int city);
    int Search_son1( int path[], int len, int city);
    void Rotate(int path[],int len, int m);
    
    void evaluation(int flag)  
    {  
        int i , j , node1 , node2 ;  
        struct gen *genp;   
    	genp = gen_group; 
        for(i = 0 ; i < SUM ; i++)//计算各染色体对应的表达式值  
        {  
    		genp[i].cost = 0;
    		int cost = 0;
    		int num = 0;
    		for( j = 0 ; j < NUMmustp - 1 ; ++j ){
    			if( !ismustedge[genp[i].info[j]].flag ){
    				node1 = genp[i].info[j];
    				node2 = genp[i].info[j + 1];
    				cost += dis[node1][node2];
    				num += numofnodepath[node1][node2];
    			}
    			else{
    				node1 = genp[i].info[j];
    				node2 = ismustedge[genp[i].info[j]].v;
    				cost += dis[node1][node2];
    				node1 = genp[i].info[j + 1];
    				cost += dis[node2][node1];
    				num += 1;
    				num += numofnodepath[node2][node1];
    			}
    		}
    		if( !ismustedge[genp[i].info[NUMmustp - 1]].flag ){
    			node1 = genp[i].info[NUMmustp - 1];
    			node2 = genp[i].info[0];
    			cost += dis[node1][node2];
    			num += numofnodepath[node1][node2];
    		}
    		else{
    			node1 = genp[i].info[NUMmustp - 1];
    			node2 = ismustedge[genp[i].info[NUMmustp - 1]].v;
    			cost += dis[node1][node2];
    			node1 = genp[i].info[0];
    			cost += dis[node2][node1];
    			num += 1;
    			num += numofnodepath[node2][node1];
    		}
    		cost -= dis[T][S];
            genp[i].cost = cost;
    		genp[i].numofnode = num;
        }  
    	gen_quicksort(genp ,0 ,SUM-1 );              //对种群进行重新排序
    }  
    
    void calnodenum(){
    	int i , j;
    	for(i = 0 ; i < nummustp ; i++) {
    		for(j = 0 ; j < nummustp; j++ ) {
    			if(mustp[i] == mustp[j]){
    				numofnodepath[mustp[i]][mustp[j]] = 0;
    			}
    			else{
    				numofnodepath[mustp[i]][mustp[j]] = numofnode(mustp[i] , mustp[j]);
    			}
    			/*if(i == j){
    				numofnodepath[i][j] = 0;
    			}
    			else{
    				numofnodepath[i][j] = numofnode(i , j);
    			}*/
    		}
    	}
    }
    
    int main(){
    	
    	int i , j;
    	reading();
    
    	
    
    	floyd();
    
    	calnodenum();
    
    	result_unchange_time = 0;
    	gen_result.cost = INF;
    	gen_result2.cost = INF;
    	initiate();
    	evaluation( 0 );        //对初始化种群进行评估、排序   
    	for( i = 0 ; i < MAXloop && result_unchange_time < 10 ; i++ )  
    	{  
    		printf("第%d次迭代:",i);
    		for(int  ii = 0 ; ii < SUM ; ++ii ){
    			printf("染色体%d:    ",ii);
    			for(j = 0 ; j < NUMmustp; ++j ){
    				printf("%d ",gen_group[ii].info[j]);
    			}
    			printf("    花费为:%d,结点数为:%d\n",gen_group[ii].cost,gen_group[ii].numofnode);
    		}printf("\n");
    		float temp = 0;
    		for (j = 0; j < SUM; j+= 1)   
    		{  
    			temp += gen_group[j].cost;  
    		}  
    
    		printf("本代平均花费为:%f\n",temp/SUM);
    
    		printf("\n\n\n\n");
    		if (gen_group[0].cost < gen_result.cost)   
            {  
    			result_unchange_time = 0;
                memcpy(&gen_result, &gen_group[0], sizeof(gen));  
            }
    		else{
    			result_unchange_time++;
    		}
    
    		for( j = 0; j < SUM ; ++j){
    			if(gen_group[j].numofnode <= 9 && gen_group[j].cost < gen_result2.cost){
    				result_unchange_time = 0;
    				memcpy(&gen_result2, &gen_group[0], sizeof(gen));
    			}
    		}
    
    		for (j = 0; j < SUM / 2; j+= 1)   
    		{  
    			Cross_group(gen_group[j], gen_group[ SUM - j -1]);  
    		}  
    		evaluation( 0 );
    		Varation_group(gen_group);
    		evaluation( 0 );
    
    	}
    
    	if(gen_result2.cost != INF){
    		printf("有最优解:\n");
    		memcpy(&gen_result, &gen_result2, sizeof(gen));
    	}
    	else{
    		printf("无最优解,输出次优解:\n");
    	}
    
    	for(int ii=0;ii<NUMmustp - 1;ii++)  
    	{  
    		i = gen_result.info[ii];
    		j = gen_result.info[ii+1];
    		if(ismustedge[i].flag){
    			//printf(",V%d,",i);
    			ret[ptri++] = i;
    			findway(ismustedge[i].v , j);
    		}
    		else
    			findway(i , j);
    	} 
    	i = gen_result.info[NUMmustp-1];
    	j = gen_result.info[0];
    	if(ismustedge[i].flag){
    		//printf(",V%d,",i);
    		ret[ptri++] = i;
    		findway(ismustedge[i].v , j);
    	}
    	else
    		findway(i , j);
    	//printf("\n");printf("\n");
    
    
    	int pos1 = Search_son1( ret, ptri, S);
    	Rotate(ret, ptri, pos1);
    	for( i = 0 ; i < ptri ; ++i){
    		printf("%d->",ret[i]);
    	}
    	printf("\n");
    	system("pause");
    	return 0;
    }
    int numofnode( int i , int j ){
    	int k , retnum = 0;
    	k=pathmatirx[i][j];                               //取路径上Vi的后续Vk  
    	if(k==-1)  
    	{  
    		printf("顶点%d 和 顶点%d 之间没有路径\n",i,j);//路径不存在   
    	}  
    	else  
    	{  
    		retnum++;
    		while(k!=j)  
    		{                          
    			retnum++;
    			k=pathmatirx[k][j];                   //求路径上下一顶点序号   
    		}  
    	} 
    	return retnum;
    }
    
    void findway( int i , int j ){
    	int k ;
    	k=pathmatirx[i][j];                               //取路径上Vi的后续Vk  
    	if(k==-1)  
    	{  
    		printf("顶点%d 和 顶点%d 之间没有路径\n",i,j);//路径不存在   
    	}  
    	else  
    	{  
    		ret[ptri++] = i;
    		while(k!=j)  
    		{                          
    			ret[ptri++] = k;
    			k=pathmatirx[k][j];                   //求路径上下一顶点序号   
    		}  
    	}  
    }
    
    void Varation_group(gen group[])  
    {  
        int i, j, k;  
        double temp;  
        //变异的数量,即,群体中的个体以PM的概率变异,变异概率不宜太大  
        int num = SUM * mp;  
      
        while (num--)   
        {  
            //确定发生变异的个体  
            k = rand() % SUM;  
      
            //确定发生变异的位  
            i = rand() % NUMmustp;  
            j = rand() % NUMmustp;  
      
            //exchange  
    		temp  = group[k].info[i];  
            group[k].info[i] = group[k].info[j];   
            group[k].info[j] = temp;  
        }  
    }  
    
    int Search_son1( int path[], int len, int city)  
    {  
        int i = 0;  
        for (i = 0; i < len; i++)   
        {  
            if (path[i] == city)   
            {  
                return i;  
            }
        }  
        return -1;  
    }  
    
    int Search_son( int path[], int len, int city)  
    {  
        int i = 0;  
        for (i = 0; i < len; i++)   
        {  
            if (path[i] == city)   
            {  
                return i;  
            }
    		else if( ismustedge[ city ].flag && ismustedge[ city ].v == path[i] ){
    			path[i] = ismustedge[ path[i] ].v;
    			return i;
    		}
        }  
        return -1;  
    }  
    
    //reverse a array  
    //it's a auxiliary function for Rotate()   
    void Reverse(int path[], int b, int e)  
    {  
        int temp;  
      
        while (b < e)   
        {  
            temp = path[b];   
            path[b] = path[e];  
            path[e] = temp;  
      
            b++;  
            e--;  
        }  
    }  
      
      
    //旋转 m 位  
    void Rotate(int path[],int len, int m)  
    {  
        if( m < 0 )  
        {  
            return;  
        }  
        if (m > len)   
        {  
            m %= len;  
        }  
      
        Reverse(path, 0, m -1);  
        Reverse(path, m, len -1);  
        Reverse(path, 0, len -1);  
    }  
    
    void Cross_group( gen &p, gen &q)  
    {  
    	//for(int ii = 0 ; ii < NUMmustp ; ++ ii){
    	//	printf("%d ",p.info[ii]);
    	//}printf("\n");
    	//for(int ii = 0 ; ii < NUMmustp ; ++ ii){
    	//	printf("%d ",q.info[ii]);
    	//}printf("\n");printf("\n");printf("\n");
    
        int i = 0;  
        int pos1, pos2;  
        int len = NUMmustp;  
        int first;  
    
    	double len1 ,len2 ;
    	if( ismustedge[ p.info[0] ].flag )
    		len1 = dis[ismustedge[ p.info[0]].v][ p.info[1] ];  
    	else
    		len1 = dis[p.info[0] ][ p.info[1] ];  
    	if( ismustedge[ q.info[0] ].flag )
    		len2 = dis[ismustedge[ q.info[0]].v][ q.info[1] ];
    	else
    		len2 = dis[q.info[0] ][ q.info[1] ];  
    
        if (len1 <= len2)   
        {  
            first = p.info[0];  
        }  
        else  
        {  
            first = q.info[0];  
        }  
        pos1 = Search_son( p.info + i, len, first);  
        pos2 = Search_son( q.info + i, len, first);  
      
        Rotate(p.info + i, len, pos1);  
        Rotate(q.info + i, len, pos2);  
    
        while ( --len > 1)   
        { 
    		i++;  
    		int span1 , span2 ;
    
    		int temp;
    		if(ismustedge[ p.info[i - 1] ].flag){
    			temp = ismustedge[ p.info[i - 1] ].v;
    		}
    		else{
    			temp = p.info[i - 1];
    		}
    		span1 = dis[temp][ p.info[i] ];  
    
    		if(ismustedge[ q.info[i - 1] ].flag){
    			temp = ismustedge[ q.info[i - 1] ].v;
    		}
    		else{
    			temp = q.info[i - 1];
    		}
    		span2 = dis[temp][ q.info[i] ];  
    
    		if ( span1 <= span2 )  
    		{  
    			pos2 = Search_son( q.info + i, len, p.info[i]);  
    			Rotate(q.info + i, len, pos2);  
    		}  
    		else  
    		{  
    			pos1 = Search_son( p.info + i, len, q.info[i]);  
    			Rotate(p.info + i, len, pos1);  
    		} 
    	}  
    	
        Rotate(q.info, NUMmustp, rand() % NUMmustp); 
    }  
    
    
    
    
    
    void initiate(){
    	/*********第一个初始解定义为按离起点的距离的顺序*********************/
    	bool *flag = NULL;                                 //用于标记必经点中的某点是否被选进染色体中
    	flag = (bool*)malloc(sizeof(bool) * nummustp);
    	if(flag == NULL){
    		printf("error initiate\n");  
            exit(1);  
    	}
    	for(int i = 0 ; i < nummustp; ++i )flag[i] = false;
    	int i , j , z ;
    	gen_group[0].info[NUMmustp - 1] = T ; flag[nummustp - 1] = true; flag[0] = true;
    	for( i = 0 ; i < NUMmustp - 1 ; ++i ){
    		int min = INF;int k = INF;
    		for( j = 0 ; j < nummustp ; ++j ){
    			if(!flag[j] && dis[S][mustp[j]] < min ){
    				min = dis[S][mustp[j]];
    				k = j;
    			}
    		}
    		
    		if(k != INF){
    			if( !ismustedge[mustp[k]].flag ){     //如果是必经点
    				gen_group[0].info[i] = mustp[k];
    				flag[k] = true;
    			}
    			else{                                 //如果是必经边
    				gen_group[0].info[i] = mustp[k];
    				flag[k] = true;
    				for(z = 0 ; z < nummustp ; ++z ){
    					if( mustp[z] == ismustedge[mustp[k]].v ){
    						flag[z] = true;break;
    					}
    				}
    			}
    		}
    		else{
    			break;
    		}
    	}
    
    	/*********随机生成剩余初始解*********************/
    	int k;
    	for( i = 1 ; i < SUM ; ++i ){
    		for(j = 0 ; j < nummustp; ++j )flag[j] = false;
    		gen_group[i].info[NUMmustp - 1] = T; flag[0] = true; flag[nummustp - 1] = true;
    		for(j = 0 ; j < NUMmustp - 1 ; ++j ){
    			k = randbit(0 , nummustp-1);
    			while( flag[k] ){
    				k = randbit(0 , nummustp-1);
    			}
    
    			if( !ismustedge[mustp[k]].flag ){     //如果是必经点
    				gen_group[i].info[j] = mustp[k];
    				flag[k] = true;
    			}
    			else{                                 //如果是必经边
    				gen_group[i].info[j] = mustp[k];
    				flag[k] = true;
    				for(z = 0 ; z < nummustp ; ++z ){
    					if( mustp[z] == ismustedge[mustp[k]].v ){
    						flag[z] = true;break;
    					}
    				}
    			}
    		}
    	}
    
    	free(flag);
    	flag = NULL;
    }
    
    void reading(){
    	FILE *fp;  
        if(NULL == (fp = fopen("case0.txt", "r")))  
        {  
            printf("error reading\n");  
            exit(1);  
        }  
    
    	S = 0; numnode = 0;
    	char ch;  
        while( '\n' != (ch=fgetc(fp)) )  //总的点的个数
        {  
    		numnode = numnode*10 + ch - '0';  
    		//printf("%c", ch);  
        }  
    	T = numnode - 1;
    	//printf("起点为%d,终点为%d,结点数目为%d\n" , S, T, numnode);
      
    	ch=fgetc(fp);
    
    	nummustp = 0;
    	memset(mustp,0,sizeof(mustp));
    	mustp[++nummustp] = S;++NUMmustp;
    	while( '\n' != (ch=fgetc(fp)) )    //读取必经点
        {  
    		if(ch == ' '){
    			++nummustp;++NUMmustp;
    		}
    		else{
    			mustp[nummustp] = mustp[nummustp]*10 + ch - '0';  
    			//printf("%c", ch);  
    		}
        } 
    
    	ch=fgetc(fp);
    
    	init();
    	int temp[3] = {0,0,0} , j = 0;
    	while( '\n' != (ch=fgetc(fp)) )    //读取图
        {  
    		temp[0] = 0 ,temp[1] = 0 ,temp[2] = 0 , j = 0;
    		while(ch != '\n'){
    			if( ch == ' ' ){
    				++j;
    			}
    			else{
    				temp[j] = temp[j]*10 + ch - '0';
    			}
    			ch = fgetc(fp);
    		}
    		dis[temp[0]][temp[1]] = temp[2];
    		dis[temp[1]][temp[0]] = temp[2];
    		pathmatirx[temp[0]][temp[1]] = temp[0];
    		pathmatirx[temp[1]][temp[0]] = temp[1];
        }  
    
    	while( '\n' != (ch=fgetc(fp)) )   //必经边的权值设为0
        {  
    		temp[0] = 0 ,temp[1] = 0 ,temp[2] = 0 , j = 0;
    		while(ch != '\n'){
    			if( ch == ' ' ){
    				++j;
    			}
    			else{
    				temp[j] = temp[j]*10 + ch - '0';
    			}
    			ch = fgetc(fp);
    		}
    		mustp[++nummustp] = temp[0];
    		mustp[++nummustp] = temp[1];
    		++NUMmustp;
    		ismustedge[temp[0]].flag = true;
    		ismustedge[temp[0]].u = temp[0];
    		ismustedge[temp[0]].v = temp[1];
    		ismustedge[temp[1]].flag = true;
    		ismustedge[temp[1]].u = temp[1];
    		ismustedge[temp[1]].v = temp[0];
        }  
    
    	while( '\n' != (ch=fgetc(fp)) )   //惩罚边的权值设为INF
        {  
    		temp[0] = 0 ,temp[1] = 0 ,temp[2] = 0 , j = 0;
    		while(ch != '\n'){
    			if( ch == ' ' ){
    				++j;
    			}
    			else{
    				temp[j] = temp[j]*10 + ch - '0';
    			}
    			ch = fgetc(fp);
    		}
    		dis[temp[0]][temp[1]] = INF;
    		dis[temp[1]][temp[0]] = INF;
    	} 
    	++NUMmustp;
    	mustp[++nummustp] = T;
    	ismustedge[S].flag = true;
    	ismustedge[S].u = S;
    	ismustedge[S].v = T;
    	ismustedge[T].flag = true;
    	ismustedge[T].u = T;
    	ismustedge[T].v = S;
    	++nummustp;            //必经点的数量+1
    	//printf("\n");
        fclose(fp); 
    }
    
    void floyd(){                                  //计算所有顶点到所有顶点的最短路径
        int k , i , j;  
    
    	for( i = 0 ; i <= numnode ; ++i ){
    		for( j = 0 ; j <= numnode ; ++j ){
    			if(dis[i][j] < INF)
    				pathmatirx[i][j] = j;               //初始化路径数组
    			else
    				pathmatirx[i][j] = -1;
    		}
    	}
    
        for(k = 0 ; k < numnode ; ++k )  
        {  
            for( i = 0 ; i < numnode ; ++i )  
            {  
                for( j = 0 ; j < numnode ; ++j )  
                {  
                    if( dis[i][j] > dis[i][k] + dis[k][j] ) {  
    					//如果经过下标为k顶点路径比原两点间路径更短
                        dis[i][j] = dis[i][k] + dis[k][j];   //更新当前两点间权值
    					pathmatirx[i][j] = pathmatirx[i][k]; //路径设置为经过下标为K的顶点
    				}
                }  
            }  
        }  
    }  
    
    void gen_swap(gen *a,gen *b)
    {
    	gen temp;
    	temp = *a;
    	*a = *b;
    	*b = temp;
    }
    
    void gen_quicksort(gen *number,int left,int right)//快速排序,用于结构体排序
    {
    	int i ,j ,s ;
    	if(left < right)
    	{
    		s = number[(left + right) / 2].cost ,j = right+1 ,i = left-1;
    		while(1)
    		{
    			while(number[++i].cost < s )  ;
    			while(number[--j].cost > s )  ;
    			if(i>=j)
    				break;
    			gen_swap(&number[i] ,&number[j] );
    		}
    		gen_quicksort(number ,left ,i-1 );
    		gen_quicksort(number ,j+1 ,right );
    	}
    }
    
    void init(){
    	int i , j ;
    	for( i = 0 ; i <= numnode ; ++i ){
    		for( j = 0 ; j <= numnode ; ++j ){
    			//pathmatirx[i][j] = j;               //初始化路径数组
    			if(i == j ) dis[i][j] = 0;
    			else dis[i][j] = INF;
    		}
    	}
    	for(i = 0 ; i < MAXN ; ++i ){
    		ismustedge[i].flag = false;
    	}
    }
    
    int randsign(float p)//按概率p返回1  
    {  
        if(rand() > (p * 32768))  
            return 0;  
        else return 1;  
    }  
    int randbit(int i, int j)//产生在i与j之间的一个随机数  
    {  
        int a , l;  
        l = j - i + 1;  
        a = i + rand() * l / 32768;  
        return a;  
    }  
    

     

      

     

    转载于:https://www.cnblogs.com/dfguo/p/6882172.html

    展开全文
  • JData京东算法大赛入门程序
  • 关于腾讯算法大赛

    2018-01-30 00:40:00
    腾讯算法大赛本文参考于我协会前会长吴师兄的文档腾讯社交广告高校算法大赛是面向高校大学生的算法大赛,作为腾讯核心的广告业务单元,腾讯社交广告通过对海量社交数据进行深入分析,构建多样广告场景,与8亿用户...
        

    腾讯算法大赛

    本文参考于我协会前会长吴师兄的文档

    腾讯社交广告高校算法大赛是面向高校大学生的算法大赛,作为腾讯核心的广告业务单元,腾讯社交广告通过对海量社交数据进行深入分析,构建多样广告场景,与8亿用户连接对话。在大数据、机器学习领域的持续创新投入,驱动社交广告生态发展。本次大赛旨在开放腾讯在社交和数字广告领域的真实数据,面向高校学生征集最智慧的算法解决方案。

    详细的赛题见腾讯算法大赛, 记得也把 FAQ 看完, 里面也包含了许多重要信息

    赛题比较难理解, 因为赛题属于广告学范畴, 如果实在难以理解赛题的可以先看看这篇文章, 看完再重新看一遍赛题就会通透许多转化率预估

    官方已经不再关闭数据的下载通道了, 不过之前已经备份到了百度云, 在这里提供给大家官方数据下载


    赛题要求

    官方提供17-30天移动 APP 的广告、用户的转化情况,及相关上下文, 根据这些数据预测第31天指定用户和对应广告的转化率.

    评估方式 (赛题中提供的计算公式)

    通过Logarithmic Loss评估(越小越好),公式如下:


    9125154-a92d8eafb91b2b43.png

    其中,

    N是测试样本总数,

    yi是二值变量,取值0或1,表示第i个样本的label,

    pi为模型预测第i个样本 label为1的概率。

    示例代码(Python语言实现):


    9125154-4001fb36e7430b3e.png

    项目目的

    主要在于剖析和学习大赛中取得 第64 名大牛的分享, 对其代码进行理解和分析, 主要着重点在于特征工程。

    机器学习的主要流程

    6228549-6b31771e91c77ed6.png
    机器学习流程


    数据分析和清洗方法

    9125154-d2436a747591af22.png

    关于数据分析,阅读FAQ可知:

    App 的激活定义为用户下载后启动了该App,即发生激活行为。从用户点击广告到广告系统得知用户激活了App(如果有),通常会有较长的时间间隔,主要由以下两方面原因导致:

    1) 用户可能在下载之后过了很久才启动App;

    2) 用户启动App的行为需要广告主上报回传给广告系统,通常会有一定的延时。

    这里回流时间表示了广告主把App激活数据上报给广告系统的时间,回流时间超过5天的数据会被系统忽略。

    值得注意的是,本次竞赛的训练数据提供的截止第31天0点的广告日志,因此,对于最后几天的训练数据,某些label=0并不够准确,可能广告系统会在第31天之后得知label实际上为1。

    某些app和用户的记录比较少

    最后几天有部分数据不准确

    对于这个问题, 这里采用了比较暴力的方法, 将最后几天这些可能会出现问题的数据删除


    特征工程

    特征工程即根据基本的数据提取出更多有用的数据, 然后结合基本特征来选取最终决定需要采用训练的特征数据, 往往特征工程决定了最终预测的效果

    基本数据在官方已经提供了数据描述的表格, 这个一定要好好理解每一个字段的作用, 这里就不重复描述数据的字段了

    在这里先强调一下,在做完特征工程之后, 我们得到了更多的特征, 但并不是每一个特征都对模型的训练有用, 故此我们需要对特征进行筛选 (不仅仅是单方面的取舍, 还需要根据重要的程度进行权重的分配)

    通过数据分析,计划以下的特征作为最终的训练数据标签

    1.基础特征:计数特征、转化率、比例特征等各种基本的特征(各种ID)

    2.用户当天行为特征:基于当天数据统计的用户行为、app行为的特征

    3.用户历史行为特征:word2vec 计算用户行为与历史行为的关联


    1. 基础特征

    基础特征即腾讯官方提供的数据,各种的ID标签,将一些没用的标签去掉即可,不需

    要作过多的处理


    2、3 用户行为特征的处理

    用户行为特征的处理逻辑较为繁琐, 也是整个项目中最繁琐的操作, 逻辑比较难理

    清,建议通过源码来理解

    展开全文
  • 关于腾讯算法大赛

    2018-01-30 00:40:00
    腾讯算法大赛 本文参考于我协会前会长吴师兄的文档 腾讯社交广告高校算法大赛是面向高校大学生的算法大赛,作为腾讯核心的广告业务单元,腾讯社交广告通过对海量社交数据进行深入分析,构建多样广告场景,与8亿用户...

    腾讯算法大赛

    本文参考于我协会前会长吴师兄的文档

    腾讯社交广告高校算法大赛是面向高校大学生的算法大赛,作为腾讯核心的广告业务单元,腾讯社交广告通过对海量社交数据进行深入分析,构建多样广告场景,与8亿用户连接对话。在大数据、机器学习领域的持续创新投入,驱动社交广告生态发展。本次大赛旨在开放腾讯在社交和数字广告领域的真实数据,面向高校学生征集最智慧的算法解决方案。

    详细的赛题见腾讯算法大赛, 记得也把 FAQ 看完, 里面也包含了许多重要信息

    赛题比较难理解, 因为赛题属于广告学范畴, 如果实在难以理解赛题的可以先看看这篇文章, 看完再重新看一遍赛题就会通透许多转化率预估

    官方已经不再关闭数据的下载通道了, 不过之前已经备份到了百度云, 在这里提供给大家官方数据下载


    赛题要求

    官方提供17-30天移动 APP 的广告、用户的转化情况,及相关上下文, 根据这些数据预测第31天指定用户和对应广告的转化率.

    评估方式 (赛题中提供的计算公式)

    通过Logarithmic Loss评估(越小越好),公式如下:


    img_1145a19821d280defc5f5996ec7f7bfc.png

    其中,

    N是测试样本总数,

    yi是二值变量,取值0或1,表示第i个样本的label,

    pi为模型预测第i个样本 label为1的概率。

    示例代码(Python语言实现):


    img_0dc00fe262043fb23e8ef83fb0855152.png

    项目目的

    主要在于剖析和学习大赛中取得 第64 名大牛的分享, 对其代码进行理解和分析, 主要着重点在于特征工程。

    机器学习的主要流程

    img_b555dfeaf8734c140afc681748bb7d54.png
    机器学习流程


    数据分析和清洗方法

    img_06dfe69f900845b79a5c49047ef4cbf8.png

    关于数据分析,阅读FAQ可知:

    App 的激活定义为用户下载后启动了该App,即发生激活行为。从用户点击广告到广告系统得知用户激活了App(如果有),通常会有较长的时间间隔,主要由以下两方面原因导致:

    1) 用户可能在下载之后过了很久才启动App;

    2) 用户启动App的行为需要广告主上报回传给广告系统,通常会有一定的延时。

    这里回流时间表示了广告主把App激活数据上报给广告系统的时间,回流时间超过5天的数据会被系统忽略。

    值得注意的是,本次竞赛的训练数据提供的截止第31天0点的广告日志,因此,对于最后几天的训练数据,某些label=0并不够准确,可能广告系统会在第31天之后得知label实际上为1。

    某些app和用户的记录比较少

    最后几天有部分数据不准确

    对于这个问题, 这里采用了比较暴力的方法, 将最后几天这些可能会出现问题的数据删除


    特征工程

    特征工程即根据基本的数据提取出更多有用的数据, 然后结合基本特征来选取最终决定需要采用训练的特征数据, 往往特征工程决定了最终预测的效果

    基本数据在官方已经提供了数据描述的表格, 这个一定要好好理解每一个字段的作用, 这里就不重复描述数据的字段了

    在这里先强调一下,在做完特征工程之后, 我们得到了更多的特征, 但并不是每一个特征都对模型的训练有用, 故此我们需要对特征进行筛选 (不仅仅是单方面的取舍, 还需要根据重要的程度进行权重的分配)

    通过数据分析,计划以下的特征作为最终的训练数据标签

    1.基础特征:计数特征、转化率、比例特征等各种基本的特征(各种ID)

    2.用户当天行为特征:基于当天数据统计的用户行为、app行为的特征

    3.用户历史行为特征:word2vec 计算用户行为与历史行为的关联


    1. 基础特征

    基础特征即腾讯官方提供的数据,各种的ID标签,将一些没用的标签去掉即可,不需

    要作过多的处理


    2、3 用户行为特征的处理

    用户行为特征的处理逻辑较为繁琐, 也是整个项目中最繁琐的操作, 逻辑比较难理

    清,建议通过源码来理解

    展开全文
  • 搜狐算法大赛:主要实体词情绪识别 baseline
  • 2019腾讯广告算法大赛完整代码(冠军)
  • 该文件是2019年中兴算法大赛试题,属于无线信道估计题型。
  • 滴滴算法大赛算法解决过程 - 拟合算法 拟合 概论 Gap的预测,是建立在一个拟合函数上的。也有一些机器学习的味道。 总的Gap函数 = 函数(时间,地区) TimeID : 时间片编号DistricID:地区编号...
  • 易观第二届OLAP漏斗算法大赛
  • 2020腾讯广告算法大赛

    2020-04-20 10:42:28
    2020腾讯广告算法大赛开赛了! 点击专属链接即可报名 点击报名
  • 数据分析: http://codesnippet.info/Article/Index?ArticleId=00000038拟合算法: http://codesnippet.info/Article/Index?ArticleId=00000041滴滴算法大赛到底需要什么样子的答案?我一开始的想法是建立一个模型...
  • 19年中兴算法大赛迪杰斯特拉门派答案。第二种方法。用的D算法加模拟退火优化过的。代码是java语言。最终结果达到了430多的优化结果。排名起初是几十名,后来掉到了100名左右。
  • 19年中兴算法大赛迪杰斯特拉门派题目答案。提供两种算法答案。第一种,纯遗传算法寻找合适已知路径组合。最终结果不理想,结果貌似在530,因为只是寻找路径组合,且是启发式算法,只能跑通,完成大赛题目要求,排名...
  • 腾讯广告算法大赛2020赛题初探坑

    千次阅读 热门讨论 2020-05-12 17:44:45
    腾讯算法大赛2020初赛
  • 第二届腾讯广告算法大赛(Rank 9)
  • 2017易观OLAP算法大赛

    千次阅读 2017-08-09 15:26:53
    2017易观OLAP算法大赛 大赛简介 目前互联网领域有很多公司都在做APP领域的“用户行为分析”产品,与Web时代的行为分析相类似,其目的都是帮助公司的运营、产品等部门更好地优化自家产品,比如查看日活和月活,查看...
  • 拍拍贷数据资源,风控算法大赛的数据。可配合github上的demo
  • 2020中兴捧月算法大赛迪杰斯特拉赛道初赛题解源码,50个字的限制真的好傻啊
  • 点击立即报名 2021腾讯广告算法大赛 全球算法达人注意啦,2021腾讯广告算法大赛...腾讯广告算法大赛已成功举办四届,随着比赛规模的逐渐升级,赛事影响力的不断扩大,腾讯广告算法大赛已然成为全球最受瞩目的算法竞技
  • 阿里移动推荐算法大赛冠军答辩PPT

    热门讨论 2015-09-09 17:05:09
    阿里移动推荐算法大赛冠军答辩PPT, 阿里云 天池 移动推荐算法 冠军答辩PPT 视频在:http://tianchi.aliyun.com/mini/reply.htm?spm=0.0.0.0.DUevYN
  • 本文原作者:腾讯广告算法大赛,经授权后发布。 2020年 腾讯广告算法大赛广撒“英雄帖” 面向全社会召集技术人前来一“战”! 腾讯广告算法大赛步入第四年 已经为来自海内外的企业和研究人员 提供了富有...
  • 2019搜狐内容识别算法大赛季军
  • 2018年腾讯广告算法大赛Rank10代码:深度部分
  • 文件是本人参加2017年的中兴捧月算法大赛(Dijstra派)的代码和可执行文件,得分86,获得中南赛区区域优胜奖
  • 加减乘除算法大赛,原理很简单。修改了一下,成了英文的单页。 加了一个谷歌的小广告。看看显示英文广告的效果了。 有需要的朋友可以下载了。 使用说明: 1、选择参与游戏时间,系统会计算您在一分钟内的结果相符。...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 2,885
精华内容 1,154
关键字:

算法大赛