python 中类似于旅行商的动态规划问题

Question

所以我刚刚开始更深入地探索动态规划，我遇到了一个我已经有一段时间无法解决的问题。我将不胜感激任何帮助。

假设一个推销员知道他每天在每个城市将获得多少收入，假设他有空 len(days_travel) 天，求他的最大收入；

输入列表收入显示他将在特定日期在特定城市获得的收入（例如revenue[0][1] = 2: day 0 and at city 'b'），旅行天数是他从一个城市旅行到另一个城市所需的天数（例如 days_travel[2][1] = 2 days is required to move from city c to city b 和 start 是他开始的城市（第 0 天）

Answer 1

这个问题看似简单，但代码复杂，至少对于我这样的菜鸟来说是这样。我会从蛮力方法来解决这个问题。在这个例子中，我们只有 3 天可用，旅行天数为零，这样就大大减少了暴力破解。假设 T 代表旅行天数，A、B、C 代表城市。那么我们有：

Day0 Day1 Day2  Expected 3-day Revenue
A     A    A       $  5
A     T    B          2 
A     T    C        101
B     B    B          6
B     T    A          3
B     T    C        102 
C     C    C        102
C     T    A          2
C     T    B          2

所以，我们只需要为每一天编写代码，将日期、城市（或旅行）和美元联系起来，然后比较总计。旅行仅创造 $0 天。我敢肯定，对你们中的一些人来说是小菜一碟。如果我能达到50分，那将是一个奇迹。

Answer 2

编辑：

经过测试我发现代码并没有完美运行我得出的结论是所需的效率是 O(n^3 * d^2) 这是超级低效的。

我的代码是一个充分的折衷方案，效率为 O(n * d^2)

最终代码：

        def floyd_warshall_days(days_travel):

    nV = len(days_travel)
    G = days_travel
    # Adding vertices individually
    for k in range(nV):
        for i in range(nV):
            for j in range(nV):
                G[i][j] = min(G[i][j], G[i][k] + G[k][j])
    return G

# The algorithm is similar to Floyd-Warshall
def floyd_warshall_rev(revenue, best_days_travel, city_to_start):

    nV = len(revenue)

    # Set G to array of zeroes by size of nV, When G[0] equals to the starting city revenue
    G = [revenue[0][city_to_start]] + [0]*(nV-1)

    # Set the start city as the best city we can go to in day zero
    StartCityArr = [city_to_start]
    best = city_to_start

    for day in range(1, nV): # For each day
        for city in range(len(revenue[0])): # For each city
            for Previous_Days in range(len(StartCityArr)): # For all previous days

                # The best way from the city we were in a few days ago to the current city
                travel_helper = best_days_travel[city][StartCityArr[Previous_Days]]

                # Normalize zero days travel time to one
                if travel_helper == 0: travel_helper = 1

                # Checks 2 things:
                # 1. Enough days have passed to get to this city
                # 2. The revenue of the current path is greater than the revenue of the best path so far

                if (day - travel_helper) >= Previous_Days and G[day] <= revenue[day][city] + G[Previous_Days]:

                    # The current path is the best one
                    G[day] = revenue[day][city] + G[Previous_Days]
                    # Update the last city visited on the best path
                    best = city

        # Append each day the last city visited on the best path to this day
        StartCityArr.append(best)

    return G


def main():
    #      city: a  b  c  # day:
    revenue = [[1, 2, 1],  # 0
               [3, 3, 1],  # 1
               [1, 1, 100]]  # 2

    #         city:  a   b   c    # city:
    days_travel = [[0, 1, 1],  # a
                   [1, 0, 1],  # b
                   [1, 2, 0]]  # c

    # Finds the best time to travel from each city to another
    best_days_travel = floyd_warshall_days(days_travel)

    # Finds the best travel by revenue from some "start city" for each number of day
    best_revenue_by_day = floyd_warshall_rev(revenue, best_days_travel,1)

    print(best_revenue_by_day)

main()

代码使用了动态规划，在外环的每个运行中，算法会在给定的天数内找到任何城市的最佳路线，外环的每个运行都会上升。

所以在第一个运行算法中找到了在我们只有一天的条件下从B出发的最佳路线

在第二个运行中，算法找到从 B 出发的最佳路线，条件是我们使用前一个运行

只有两天的时间

等等...

因此对于当前数据，输出将如下所示：

[2, 5, 102]

2 如果从 B

开始，是 1 天工作的答案

5 如果从 B

开始，是 2 天工作的答案

102 如果从 B

开始，是 3 天工作的答案

python 中类似于旅行商的动态规划问题

dynamic programming question similar to traveling salesman in python

python

dynamic-programming