在Python中查找在给定两个位置中拾取黄金的最低成本的程序

在这篇文章中，我们将学习如何在Python中编写程序来查找在给定两个位置中拾取黄金的最低成本。首先，我们需要了解何为最低成本。

在这里，最低成本是指走过所有路径的总成本。假设有三个地点：A、B、C，每个地点的成本分别为2、3、5。如果我们要从地点A到达地点C，可以通过地点B，那么总成本为5（从A->B的成本为2，从B->C的成本为3）。

现在我们就可以开始编写代码了。首先，我们需要创建一个函数来计算成本。

def calculate_cost(costs, path):
    total_cost = 0
    for i in range(len(path)-1):
        total_cost += costs[path[i]][path[i+1]]
    return total_cost

该函数接收两个参数：costs表示每个地点之间的成本，path表示路线（即从哪个位置到哪个位置）。通过循环遍历path列表，我们计算从一个位置到下一个位置所需的成本，并将其相加得到总成本。

接下来，我们需要编写另一个函数来获取从起点到终点的所有可能的路径。

def get_all_routes(start, end, routes, path=[]):
    path = path + [start]
    if start == end:
        routes.append(path)
    for i in graph[start]:
        if i not in path:
            get_all_routes(i, end, routes, path)
    return routes

该函数接收四个参数：起点、终点、路径列表和一个可选的路径参数。我们首先将当前位置添加到路径中，并检查当前位置是否是终点。如果是，我们就将路径添加到路径列表中，然后返回该列表。

如果当前位置不是终点，我们就遍历所有可能到达的位置，递归地调用该函数，并通过将当前位置添加到路径中来不断构造路径。在这里，我们使用了图来表示每个地点之间的连接关系，graph变量存储该图。

graph = {'A': ['B', 'C'],
         'B': ['C', 'D'],
         'C': ['D'],
         'D': ['C'],
         'E': ['F'],
         'F': ['C']}

让我们来看看如何使用这两个函数来查找最低成本。首先，我们需要定义成本和位置。

# define costs
costs = {'A': {'B': 2, 'C': 5},
         'B': {'C': 3, 'D': 7},
         'C': {'D': 1},
         'D': {'C': 2},
         'E': {'F': 3},
         'F': {'C': 1}}

# define start and end positions
start = 'A'
end = 'D'

在这里，我们通过字典来定义每个地点之间的成本。接下来，我们定义起点和终点。

现在，我们可以使用这些变量来查找从起点到终点的最低成本。我们首先获取所有可能的路径。

# get all possible routes
routes = get_all_routes(start, end, [])

然后，我们循环遍历所有路径，计算每个路径的成本，并找到最低成本。

# calculate cost for each route and find the cheapest
lowest_cost = float('inf')
for route in routes:
    cost = calculate_cost(costs, route)
    if cost < lowest_cost:
        lowest_cost = cost
        cheapest_route = route

在这里，我们将最低成本设置为无限大。然后，我们循环遍历所有路径，计算每个路径的成本，并将最低成本更新为该路径的成本，如果该成本小于当前的最低成本则将该路径设置为最低成本路径。

最后，我们可以输出最低成本路径和成本。

# print cheapest route and cost
print(f"Cheapest route is {' -> '.join(cheapest_route)} with a cost of {lowest_cost}")

现在，我们可以将整个程序组合在一起。

# define costs
costs = {'A': {'B': 2, 'C': 5},
         'B': {'C': 3, 'D': 7},
         'C': {'D': 1},
         'D': {'C': 2},
         'E': {'F': 3},
         'F': {'C': 1}}

# define start and end positions
start = 'A'
end = 'D'

# define functions
def calculate_cost(costs, path):
    total_cost = 0
    for i in range(len(path)-1):
        total_cost += costs[path[i]][path[i+1]]
    return total_cost

def get_all_routes(start, end, routes, path=[]):
    path = path + [start]
    if start == end:
        routes.append(path)
    for i in graph[start]:
        if i not in path:
            get_all_routes(i, end, routes, path)
    return routes

# get all possible routes
routes = get_all_routes(start, end, [])

# calculate cost for each route and find the cheapest
lowest_cost = float('inf')
for route in routes:
    cost = calculate_cost(costs, route)
    if cost < lowest_cost:
        lowest_cost = cost
        cheapest_route = route

# print cheapest route and cost
print(f"Cheapest route is {' -> '.join(cheapest_route)} with a cost of {lowest_cost}")

运行该代码，我们可以得到以下输出结果：

Cheapest route is A -> C -> D with a cost of 3

结论

在Python中查找在给定两个位置中拾取黄金的最低成本可以通过定义成本、位置以及两个函数来实现。get_all_routes函数可以获取从起点到终点的所有可能的路线，calculate_cost函数可以计算每个路线的成本。最后，我们可以通过循环遍历所有路径，找到最低成本路径，并输出结果。