剛參加完人生中第一個程序設(shè)計比賽，雖然沒有進(jìn)入復(fù)賽，但是還是感覺有所收獲的辩昆。在這里把成果分享一下，也算給自己一個圓滿的收尾旨袒。
初賽訓(xùn)練地圖的調(diào)度時間是2000以內(nèi)汁针；比賽地圖代碼提交慢了，不過調(diào)度時間也比較長砚尽，將近10000施无，沒有充足的時間來調(diào)試，所以輸?shù)眯姆诜毓隆２贿^怎么我們隊也是江大獨苗嘛猾骡，也進(jìn)過前20?(? ???ω??? ?)?，爭了口氣敷搪！
代碼貼在Git 2019HuaWei--JZE
這是一個車輛調(diào)度問題兴想，文件資料我也貼在Git上了，大家可以自行鉆研赡勘，這里就不解讀了嫂便。
首先實現(xiàn)將道路（Road）通過路口（Cross）信息連接起來，獲得地圖完整的道路狀況闸与，如某條道路起點在那個路口毙替，終點在哪個路口曼振，前后各能通向哪里等。
這里實現(xiàn)的邏輯如果從程序看上去蔚龙，是比較復(fù)雜的冰评，首先我們給出Road、Cross和Car的三個類定義：
class CROSS(object):
def __init__(self,ID,road1,road2,road3,road4):
self.ID = ID
self.road1 = road1
self.road2 = road2
self.road3 = road3
self.road4 = road4
class ROAD(object):
left_road = None
right_road = None
stright_road = None
back_left = None
back_right = None
back_stright = None
all_right = 1
def __init__(self,ID,length,speed_lim,channels,cross_begin,cross_end,isDuplex):
self.ID = ID
self.length = length
self.speed_lim = speed_lim
self.channels = channels
self.cross_begin = cross_begin
self.cross_end = cross_end
self.isDuplex = isDuplex
class CAR(object):
now_post = None
def __init__(self,ID,start_loc,dest_loc,speed,start_time):
self.ID = ID
self.start_loc = start_loc
self.dest_loc = dest_loc
self.speed = speed
self.start_time = start_time
然后讀取訓(xùn)練地圖的信息：
cars = pd.read_csv(r"C:\Users\Administrator\Desktop\JZE\1-map-training-1\car.txt",skipinitialspace = True)
roads = pd.read_csv(r"C:\Users\Administrator\Desktop\JZE\1-map-training-1\road.txt",skipinitialspace = True)
crosses = pd.read_csv(r"C:\Users\Administrator\Desktop\JZE\1-map-training-1\cross.txt",skipinitialspace = True)
然后創(chuàng)建三類對象鏈表木羹，其中甲雅，在初始化Cross對象時進(jìn)行Road道路信息寫入
car_dict = {}
for car_info in cars.iterrows():
car_dict[car_info[1][0].replace("(","")] = CAR(car_info[1][0].replace("(",""),car_info[1][1],car_info[1][2],car_info[1][3],car_info[1][4].replace(")",""))
road_dict = {}
for road_info in roads.iterrows():
road_dict[road_info[1][0].replace("(","")] = ROAD(road_info[1][0].replace("(",""),road_info[1][1],road_info[1][2],road_info[1][3],road_info[1][4],road_info[1][5],road_info[1][6].replace(")",""))
cross_dict = {}
for cross_info in crosses.iterrows():
the_cross = cross_info[1][0].replace("(","")
fir = str(int(cross_info[1][1]))
sec = str(int(cross_info[1][2]))
thi = str(int(cross_info[1][3]))
fot = str(int(cross_info[1][4].replace(")","")))
if fir != "-1":
if cross_info[1][0].replace("(","") == str(road_dict[fir].cross_begin):
if (road_dict[fir].isDuplex == "1"):
road_dict[fir].back_left = road_dict[sec] if sec != "-1" and ((road_dict[sec].isDuplex == "1") or str(road_dict[sec].cross_begin) == the_cross) else None
road_dict[fir].back_stright = road_dict[thi] if thi != "-1" and ((road_dict[thi].isDuplex == "1") or str(road_dict[thi].cross_begin) == the_cross) else None
road_dict[fir].back_right = road_dict[fot] if fot != "-1" and ((road_dict[fot].isDuplex == "1") or str(road_dict[fot].cross_begin) == the_cross) else None
else:
road_dict[fir].back_left = None
road_dict[fir].back_stright = None
road_dict[fir].back_right = None
else:
road_dict[fir].left_road = road_dict[sec] if sec != "-1" and ((road_dict[sec].isDuplex == "1") or str(road_dict[sec].cross_begin) == the_cross) else None
road_dict[fir].stright_road = road_dict[thi] if thi != "-1" and ((road_dict[thi].isDuplex == "1") or str(road_dict[thi].cross_begin) == the_cross) else None
road_dict[fir].right_road = road_dict[fot] if fot != "-1" and ((road_dict[fot].isDuplex == "1") or str(road_dict[fot].cross_begin) == the_cross) else None
...
...
...
cross_dict[cross_info[1][0].replace("(","")] = CROSS(cross_info[1][0].replace("(",""),road_dict[fir] if fir in road_dict else None,road_dict[sec] if sec in road_dict else None,\
road_dict[thi] if thi in road_dict else None,road_dict[fot] if fot in road_dict else None)
for index,item in road_dict.items(): #以列表返回可遍歷的(鍵, 值) 元組數(shù)組
print("當(dāng)前道路:",item.ID,"\t直行:",item.stright_road.ID if item.stright_road != None else None,"\t左轉(zhuǎn):",item.left_road.ID if item.left_road != None else None,"\t右轉(zhuǎn):",item.right_road.ID if item.right_road != None else None,\
"\t反直:",item.back_stright.ID if item.back_stright != None else None,"\t反左:",item.back_left.ID if item.back_left != None else None,"\t反右:",item.back_right.ID if item.back_right != None else None)
這里為了方便理解，上面程序只貼出對于路口一的判斷來說明：
首先判斷cross中的road1的起點是否為該cross坑填。如果是抛人，那么判斷road1是否為雙向：如果為雙向，那么將該路口其他三條road分別作為road1的反向道路寫入脐瑰；如果是單向線妖枚，那么road1只能從起點通往終點，那么該路口的其他road就不能通過road1到達(dá)苍在，即road1的反向三個路口為None绝页。如果road1起點不是該cross（則該cross是road1終點），那么該cross的其他三條road邊肯定是road1的前向三路口寂恬，且能到達(dá)续誉。（大家好好琢磨一下賽制和規(guī)則，這里就好理解了）
實現(xiàn)道路后初肉，下面就是按照一個規(guī)則（算法）來實現(xiàn)道路分配酷鸦，這里提一下，聽說大佬們都用的退火做的牙咏，保持各賽區(qū)最低系統(tǒng)調(diào)度時間臼隔。我們這里就簡單了一下，所以時間比較高妄壶。摔握。。也不能說懶盯拱，就沒花時間去鉆研吧盒发，所以唉例嘱。狡逢。。追悔莫及有點過拼卵，多多少少還是有遺憾的奢浑。
這里我是按照當(dāng)前car所在cross和car終點兩個位置來作比較得到car的行駛路線的，這樣容易出現(xiàn)找不到終點一直徘徊的情況（因為不是越靠近終點的road就一定有條路通向終點腋腮，之后正式比賽更是如此）雀彼。所以如果出現(xiàn)這樣的情況壤蚜，我就讓徘徊不前的路暫時關(guān)閉，然后倒退重新搜索徊哑；如果本輪搜索不到終點袜刷，即road全部被關(guān)閉，那么重新選擇初始道路重新進(jìn)行一輪道路規(guī)劃（car的起點是cross莺丑，一個cross有多個road著蟹，所以car的起點也有多個）。
至于小車的出發(fā)時間梢莽，哈哈哈~我們就更偷懶了萧豆，抱著僥幸的心理我們是給了一個“像樣”的隨機策略來給小車安排出發(fā)時間的。
所以這兩部分的代碼昏名，我就不貼出來獻(xiàn)丑了涮雷，需要的畫直接去2019HuaWei--JZEclone吧（如果覺得還行的話，可否給個給個星星呢(*>.<)）
說明一下轻局，Git上的代碼是根據(jù)比賽要求的SDK進(jìn)行編寫的洪鸭，如果你要本地跑的話，把讀取文件的地方改一下就好仑扑。
上面的是初賽訓(xùn)練地圖的程序卿嘲，比賽地圖的規(guī)模大了很多，而且cross信息也不像訓(xùn)練地圖那么簡單夫壁，所以程序也做了很大的修改拾枣，主要有如下兩點：
