Demo entry 6741497

Route-planing.py

   

Submitted by r4phael on May 15, 2018 at 15:33
Language: Python 3. Code size: 8.0 kB.

import copy
import os
from lxml import etree


class Node:
    def __init__(self, name):
        self.name = name
        self.cost = 0
        self.value = 0
        self.start_time = 0
        self.end_time = 0
        self.way_cost = {}

    def __repr__(self):
        return self.name


class NodeList:
    def __init__(self):
        self.nodes = {}

    def add(self, node):
        self.nodes[node.name] = node

    def copy(self):
        new = NodeList()
        new.nodes = copy.copy(self.nodes)
        return new


class Route:
    def __init__(self, time, end):
        self.route = []
        self.value = 0
        self.time = time
        self.end_time = end

    def check_node(self, node, nodelist):
        if len(self.route) == 0:
            return True
        if node.name in self.route:
            return False
        need = nodelist.nodes[self.route[-1]].way_cost[node.name] + node.cost
        if self.time + need < self.end_time and self.time + nodelist.nodes[self.route[-1]].way_cost[node.name] > nodelist.nodes[node.name].start_time and self.time + need < node.end_time:
            return True
        return False

    def add_node(self, node, nodelist):
        if len(self.route) == 0:
            self.value += node.value
            if node.start_time > self.time:
                self.time = node.start_time + node.cost
            else:
                self.time += node.cost
            self.route.append(node.name)
            return self
        if self.check_node(node, nodelist):
            self.value += node.value
            self.time += nodelist.nodes[self.route[-1]].way_cost[node.name] + node.cost
            self.route.append(node.name)
            return self
        return None

    def del_node(self, nodelist):
        node = self.route.pop()
        self.value -= nodelist.nodes[node].value
        self.time -= nodelist.nodes[node].cost
        self.time -= nodelist.nodes[self.route[-1]].way_cost[node]

    def copy(self):
        new = Route(self.time, self.end_time)
        new.route = copy.copy(self.route)
        new.value = self.value
        return new

    def __repr__(self):
        return "%s - %s - %s" % (self.route, self.value, self.end_time-self.time)


class RouteList:
    def __init__(self):
        self.routes = []

    def add(self, route):
        self.routes.append(route)


def dfs(route, nodelist, routelist):
    ans = 0
    for i in nodelist.nodes.keys():
        if route.check_node(nodelist.nodes[i], nodelist) and i not in route.route:
            route.add_node(nodelist.nodes[i], nodelist)
            dfs(route, nodelist, routelist)
            route.del_node(nodelist)
        else:
            ans += 1
    if ans == len(nodelist.nodes.keys()):
        routelist.add(route.copy())


def init_nodelist(day1_pos=[]):
    pos = ["南京博物院", "中山陵园风景区", "汤山紫清湖旅游区", "南京总统府", "玄武湖", "牛首山文化旅游区", "明孝陵", "瞻园", "梅花山", "雨花台", "夫子庙", "南京海底世界", "红山森林动物园", "侵华日军南京大屠杀遇难同胞纪念馆", "栖霞寺", "大报恩寺遗址公园", "甘家大院", "阅江楼", "鸡鸣寺", "高淳老街", "灵谷景区", "珍珠泉风景区", "中山植物园", "老门东历史街区", "南京科技馆", "莫愁湖公园", "美龄宫", "六朝博物馆", "南京大学", "中国科举博物馆(江南贡院)", "江宁织造博物馆", "中华门瓮城", "紫金山天文台"]

    nodelist = NodeList()
    with open("value", "r") as f:
        valueList = f.readlines()
    with open("cost_time", "r") as f:
        costList = f.readlines()
    with open("start_time", "r") as f:
        startList = f.readlines()
    with open("end_time", "r") as f:
        endList = f.readlines()
    for j in range(0, len(pos)):
        i = pos[j]
        nodelist.nodes[i] = Node(i)
        nodelist.nodes[i].cost = int(costList[j]) * 60
        nodelist.nodes[i].start_time = int(startList[j]) * 60
        nodelist.nodes[i].end_time = int(endList[j]) * 60
        nodelist.nodes[i].value = int(float(valueList[j])*100)

    filenames = os.listdir("公共交通")
    for filename in filenames:
        file = open(os.path.join("公共交通", filename), "r")
        root = etree.XML(file.read().encode('utf-8'))
        duration = int(root.find("result").find("routes").find("duration").text)
        file.close()
        point = filename[:-4].split('-')
        if point[0] not in pos or point[1] not in pos:
            continue
        nodelist.nodes[point[0]].way_cost[point[1]] = duration
        nodelist.nodes[point[1]].way_cost[point[0]] = duration


    for key in day1_pos:
        try:
            nodelist.nodes.pop(key)
        except:
            pass
    return nodelist


def output_duration_matrix(nodelist):
    f = open("matrix.txt", "w")
    f.write("%10.8s" % " ")
    for i in nodelist.nodes.keys():
        f.write("%10.8s" % i[:4])
    f.write("\n")
    for i in nodelist.nodes.keys():
        f.write("%10.8s" % i[:4])
        for j in nodelist.nodes.keys():
            if i == j:
                f.write("%10.8s" % 0)
            else:
                f.write("%10.8s" % nodelist.nodes[i].way_cost[j])
        f.write("\n")
    f.close()


def calc(nodelist_in, filename):
    nodelist = [nodelist_in.copy(), nodelist_in.copy()]
    routelist = [{}, {}]
    node = ["", ""]
    route = [Route(480*60, 720*60-300), Route(810*60, 1050*60-300)]
    max_route = [(0, Route(480*60, 720*60-300), Route(810*60, 1050*60-300))]
    ans = 0
    for node[0] in nodelist[0].nodes.keys():
        ans += 1
        routelist[0][node[0]] = RouteList()
        route[0] = Route(480*60, (720)*60)
        route[0].add_node(nodelist[0].nodes[node[0]], nodelist[0])
        dfs(route[0], nodelist[0], routelist[0][node[0]])
        routelist[0][node[0]].routes = sorted(routelist[0][node[0]].routes, key=lambda item: item.value, reverse=True)

        for item1 in routelist[0][node[0]].routes:
            print("%s/%s | %s/%s" % (ans, len(nodelist[0].nodes.keys()), routelist[0][node[0]].routes.index(item1), len(routelist[0][node[0]].routes)))
            if routelist[0][node[0]].routes.index(item1)*10 > len(routelist[0][node[0]].routes) and routelist[0][node[0]].routes.index(item1) > 50:
                break
            nodelist[1] = nodelist[0].copy()
            for node[1] in item1.route:
                if node[1] != item1.route[-1]:
                    nodelist[1].nodes.pop(node[1])
            routelist[1][item1.route[-1]] = RouteList()
            route[1] = Route(810*60, (1050)*60)
            route[1].add_node(nodelist[1].nodes[item1.route[-1]], nodelist[1])
            route[1].time = 810*60
            route[1].value = 0
            dfs(route[1], nodelist[1], routelist[1][item1.route[-1]])
            routelist[1][item1.route[-1]].routes = sorted(routelist[1][item1.route[-1]].routes, key=lambda item: item.value, reverse=True)
            if item1.value + routelist[1][item1.route[-1]].routes[0].value > max_route[-1][0]:
                max_route.append((item1.value + routelist[1][item1.route[-1]].routes[0].value, item1.copy(), routelist[1][item1.route[-1]].routes[0].copy()))
                max_route = sorted(max_route, key=lambda x: x[0], reverse=True)
                if len(max_route) > 100:
                    max_route.pop()
                print(max_route[0])
    wfile = open("路线规划/%s-%s" % (filename, max_route[0][0]), "w")
    for item in max_route:
        wfile.write("%s - %s - %s" % (item[0], item[1], item[2]) + "\n")
    wfile.close()
    return max_route


if __name__ == '__main__':
    max = 0
    max_route = []
    day1 = calc(init_nodelist(), "route-day1")
    ans = 1
    for record in day1:
        day2 = calc(init_nodelist(record[1].route+record[2].route), "route-day2-%s" % ans)
        max_route.append((record[0]+day2[0][0], record, day2[0]))
        ans += 1
    max_route = sorted(max_route, key=lambda x: x[0], reverse=True)
    wfile = open("路线规划/route-total", "w")
    for item in max_route:
        wfile.write("%s - %s - %s" % (item[0], item[1], item[2]) + "\n")
    wfile.close()

This snippet took 0.02 seconds to highlight.

Back to the Entry List or Home.

Delete this entry (admin only).