使用两个列表如何计算一个列表中使用第二个列表作为引用的两个元素之间的最小价格?

Question

在一次Python编程面试中，有人问我这个问题，我没能正确地写出来。有两个列表:

islands=[isl_1, isl_2, isl_3, isl_4] 
tickets=[0, 100, 200, 300, 2, 0, 25, 170, 10, 20, 0, 300, 540, 80, 60, 0]

in ticket list中每4项为海岛价格:isl_1到isl_2 = 100,isl_1到isl_3 = 200，依此类推。如何写一个函数，将计算从from_isl到to_isl的最便宜的方式?

def cheapest_ticket(from_isl, to_isl) --> return min price

Answer 1

我相信你可以使用与Dijkstra算法相同的概念，但应该是一个有向图，例如isl_1->isl_2是100，但isl_2->isl_1只是2。下面是一个伪代码:

1. 构造有向加权图

   • 这将是所有岛屿之间的网络地图，其中每条路径都有关于(direction, price)的信息。
   • 需要强调的是，isl_1->isl_2将是与isl_2->isl_1
   不同的路径

2. 现在给定起点from_isl，使用通常的图算法遍历路径直到到达to_isl。

   • 注意，与width -firstrongearch不同，您不应该在第一次到达to_isl后停止。你应该继续下去，直到所有的岛屿都被访问过，因为很可能最短的路径，例如isl_1->isl_2不是最便宜的，可能较长的isl_1->isl_4->isl_2的价格更低。
     • 所以我认为depth-firstrongearch是首选。对于通向to_isl的不同可能路径，我们应该标记出访问过的和尚未访问的内容(与回溯的概念相同，在isl1->isl3->isl2之后，我们将探索isl1->isl3->isl4->isl2，以此类推)。请注意，与BFS一样，不要在第一次到达to_isl时停止，所有可能的路径仍然应该探索。
   • 对于每一个遍历的路径，确保在该点的price的总和。
   • 一旦访问了所有岛屿，停止遍历。然后，比较通向to_isl的路径的最小价格，如isl_1->isl_2 vs isl_1->isl_4->isl_2 vs isl_1->isl_3->isl_4->isl2等。

Answer 2

from itertools import permutations
cost_matrix = [[0, 100, 200, 300], [2, 0, 25, 170], [10, 20, 0, 300], [540, 80, 60, 0]]
base = [1, 2, 3, 4]
all_paths = []
for x in base:
if x > 1:
perm = permutations(base, x)
for i in list(perm):
all_paths.append(i)
# print(all_paths)

def get_paths(start, finish):
print(f"Going from island {start} to island {finish}")
return list(filter(lambda x: x[0] == start and x[-1] == finish, all_paths))

def get_costs(paths):
prices = []
for path in paths:
price = sum(
map(lambda x: cost_matrix[x[0] - 1][x[1] - 1], zip(path[:-1], path[1:]))
)
prices.append(price)
return prices

I = input("Enter start,finish > ")
[start, finish] = list(map(int, I.split(",")))
paths = get_paths(start, finish)
print("Possible paths", paths)
costs = get_costs(paths)
print("Path costs", costs)
print("Min value", min(costs))
i = costs.index(min(costs))
print("cheapest path:", paths[i])

我从a和b之间的所有路径开始，注意到a ->B != B ->一个。我对这些进行了过滤，得到了选定岛屿之间的路径，然后我问代价矩阵一个路径段的代价是多少，然后把它们加起来。然后选择最便宜的路径。这段代码可以重构成一个函数，但是我想展示一下我的工作，这样你就可以理解了。

Answer 3

给定的问题可以用以下方法解决。

1. 当给定起点和终点时，我们找出所有可能的路径。我们从给定数组(在本例中是一个岛屿列表)中过滤出开始和结束，以降低复杂性。我们将它们插入到末尾。
2. 查找从一个节点到每个其他节点的价格映射。
3. 查找路径之间的最小价格

添加以下代码，希望对您有所帮助

import json
from itertools import permutations
islands = ["isl_1", "isl_2", "isl_3", "isl_4"]
tickets = [0, 100, 200, 300, 2, 0, 25, 170, 10, 20, 0, 300, 540, 80, 60, 0]
def get_island_to_island_price_mapping():
island_to_island_price_mapping = {}
island_start = 0
island_end = len(islands)

for island in islands:
index = 0
for price in tickets[island_start:island_end]:
island_to_island_price_mapping[island+'--->'+islands[index]] = price
index += 1
island_start += len(islands)
island_end += len(islands)
print("island_to_island_price_mapping ---->", json.dumps(island_to_island_price_mapping, indent=4))
return island_to_island_price_mapping
def get_all_possible_paths(array, start, finish):
all_paths = []
array.remove(start)
array.remove(finish)
for index in range(len(array)+1):
path_object = permutations(array, index)
for path in path_object:
actual_path = list(path)
actual_path.insert(0, start)
actual_path.append(finish)
all_paths.append(actual_path)
print("ALL PATHS ---->", json.dumps(all_paths, indent=4))
return all_paths

def get_minimum_price_path():
price_mapping = get_island_to_island_price_mapping()
paths = get_all_possible_paths(islands,'isl_1','isl_4')
price_to_path_map = {}
for path_permuations in paths:
price = 0
for index in range(1, len(path_permuations)):
price += price_mapping[path_permuations[index-1]+'--->'+path_permuations[index]]
price_to_path_map[price] = '--->'.join(path_permuations)
print("price_to_path_map---->", json.dumps(price_to_path_map, indent=4))
return price_to_path_map[min(price_to_path_map.keys())]

minimum_price_path = get_minimum_price_path()