三段航线多数组低价航班组合查找算法技术问询

Alright, let's tackle this problem of finding the cheapest flight combinations for the Paris → London → Hamburg → Moscow route. Here's a straightforward, actionable algorithm that covers all valid scenarios and accounts for those tricky price differences between combined and split flights:

1. First, Define All Valid Full Itinerary Combinations #

Since we can use flight units that are either single-segment or two-segment combinations, and we need to cover the full 3-segment route, the only valid full itinerary types are:

• Type 1: Three single-segment flights: Paris→London + London→Hamburg + Hamburg→Moscow
• Type 2: One two-segment combo + one single-segment:
  • Subtype 2a: Paris→London→Hamburg (two-segment) + Hamburg→Moscow (single)
  • Subtype 2b: Paris→London (single) + London→Hamburg→Moscow (two-segment)
    We can skip any combinations that overlap segments (like two two-segment combos that double up on London→Hamburg) since they don't make logical sense for a single itinerary.

2. Calculate Total Price for Every Possible Combination #

For each valid itinerary type, iterate through all possible flight combinations and compute their total cost:

• For Type 1: Loop through every Paris→London flight, pair it with every London→Hamburg flight, pair that with every Hamburg→Moscow flight, sum their individual prices.
• For Subtype 2a: Loop through every Paris→London→Hamburg two-segment flight, pair it with every Hamburg→Moscow single flight, sum their prices.
• For Subtype 2b: Loop through every Paris→London single flight, pair it with every London→Hamburg→Moscow two-segment flight, sum their prices.

Make sure you store not just the total price, but also the full flight details (like flight numbers) for each combination—this is key to returning all cheapest options later.

3. Find the Minimum Price Across All Combinations #

Once you have a list of all valid combinations with their total prices, scan through the list to find the lowest price value.

4. Extract All Combinations That Match the Minimum Price #

Finally, filter your full list to keep only those combinations where the total price equals the minimum price you found. These are all your cheapest flight options.

Example Pseudocode #

Here's a simplified pseudocode implementation to make this concrete:

# Assume we have these input data structures
single_pl = [{"flight_num": "100", "price": 50}, {"flight_num": "200", "price": 45}]
single_lh = [{"flight_num": "101", "price": 30}, {"flight_num": "201", "price": 25}]
single_hm = [{"flight_num": "103", "price": 60}, {"flight_num": "203", "price": 55}]
combo_plh = [{"flights": ["100", "101"], "price": 70}, {"flights": ["100", "201"], "price": 65}]
combo_lhm = [{"flights": ["101", "103"], "price": 80}, {"flights": ["201", "203"], "price": 75}]

all_combinations = []

# Type 1: 3 singles
for pl in single_pl:
    for lh in single_lh:
        for hm in single_hm:
            total = pl["price"] + lh["price"] + hm["price"]
            all_combinations.append({
                "flights": [pl["flight_num"], lh["flight_num"], hm["flight_num"]],
                "total_price": total
            })

# Subtype 2a: PLH combo + HM single
for plh in combo_plh:
    for hm in single_hm:
        total = plh["price"] + hm["price"]
        all_combinations.append({
            "flights": plh["flights"] + [hm["flight_num"]],
            "total_price": total
        })

# Subtype 2b: PL single + LHM combo
for pl in single_pl:
    for lhm in combo_lhm:
        total = pl["price"] + lhm["price"]
        all_combinations.append({
            "flights": [pl["flight_num"]] + lhm["flights"],
            "total_price": total
        })

# Find minimum price
min_price = min(combo["total_price"] for combo in all_combinations)

# Get all cheapest combinations
cheapest_combinations = [c for c in all_combinations if c["total_price"] == min_price]

# Output the result
print("Cheapest flight combinations:")
for combo in cheapest_combinations:
    print(f"Flights: {' → '.join(combo['flights'])}, Total Price: {combo['total_price']}")

Key Notes #

• Edge Cases: Don't forget to handle cases where multiple combinations have the same lowest price—you need to return all of them, not just one.
• Data Validation: Before calculating, ensure that flight combinations actually connect logically (though in this problem, the input arrays are already pre-filtered to valid routes, but it's a good habit to add checks if your input might be messy).
• Performance: If your flight lists are very large, you can optimize by precomputing the cheapest single flights for each segment, but only if you're sure combining them will give the minimum—wait, no, because sometimes a combo flight plus a single might be cheaper than the sum of individual cheapest singles, so you still need to check all combinations.

内容的提问来源于stack exchange，提问作者Vladimir