如何用 JavaScript、Python 和 Google Flights 计划一场说走就走的旅行

我计划去南美洲旅行已经有一段时间了。我的时间比较灵活，对于南美洲我也有几个特别想去的地方，但是很难找到合适的航班。因此，我决定使用最程序员的方式去尝试做一些便捷且实用的攻略。

其实，早在三年前，我已经利用 Clojure 和 Chrome 做过类似的挑战（https://nvbn.github.io/2015/07/17/flight-prices/），但那只是单次飞行，并不适用这次。

解析航班信息

很显然，网上没有获取航班信息的开放 API。但是由于 Google Flights（Google 旗下的航班搜索服务） 可以显示两个月内航班的价格和日期，所以我决定就用它：

如此一来，我生成了所有南美目的地与往返阿姆斯特丹航班的所有可能的组合。我通过改变目的地输入和开关日历模拟了用户的交互。最后，我在新的页面上输出了结果 JSON。

整体来看，代码如下所示：

const getFlightsData = async ([from, to]) => {
  await setDestination(FROM, from);
  await setDestination(TO, to);

  const prices = await getPrices();

  return prices.map(([date, price]) => ({
    date, price, from, to,
  }));
};

const collectData = async () => {
  let result = [];
  for (let flight of getAllPossibleFlights()) {
    const flightsData = await getFlightsData(flight);
    result = result.concat(flightsData);
  }
  return result;
};

const win = window.open('');

collectData().then(
  (data) => win.document.write(JSON.stringify(data)),
  (error) => console.error("Can't get flights", error),
);

运行试试看：

我为中途转机和直飞分别运行了一次，然后将结果保存到了 JSON 文件中，内容如下：

[{"date":"2018-07-05","price":476,"from":"Rio de Janeiro","to":"Montevideo"},
{"date":"2018-07-06","price":470,"from":"Rio de Janeiro","to":"Montevideo"},
{"date":"2018-07-07","price":476,"from":"Rio de Janeiro","to":"Montevideo"},
...]

虽然可以正常工作，但是在极少数情况下，GoogleFlights 似乎有某种反解析的情况，且会显示“随机”价格。

选择最佳旅行

在上述过程中，我解析了 10110 个带中途转机的航班，和 6422 个直飞的航班，靠穷举算法的蛮力在这里行不通（我试过了）。鉴于从 JSON 读取数据没什么可说的，所以我跳过这部分。

首先，我建立了一个索引：从目的地→日期→到目的地：

from_id2day_number2to_id2flight = defaultdict(
    lambda: defaultdict(
        lambda: {}))
for flight in flights:
    from_id2day_number2to_id2flight[flight.from_id] \
        [flight.day_number][flight.to_id] = flight

接下来，创建一个递归生成器来创建所有可能的旅程：

def _generate_trips(can_visit, can_travel, can_spent, current_id,
                    current_day, trip_flights):
    # The last flight is to home city, the end of the trip
    if trip_flights[-1].to_id == home_city_id:
        yield Trip(
            price=sum(flight.price for flight in trip_flights),
            flights=trip_flights)
        return

    # Everything visited or no vacation days left or no money left
    if not can_visit or can_travel < MIN_STAY or can_spent == 0:
        return

    # The minimal amount of cities visited, can start "thinking" about going home
    if len(trip_flights) >= MIN_VISITED and home_city_id not in can_visit:
        can_visit.add(home_city_id)

    for to_id in can_visit:
        can_visit_next = can_visit.difference({to_id})
        for stay in range(MIN_STAY, min(MAX_STAY, can_travel) + 1):
            current_day_next = current_day + stay
            flight_next = from_id2day_number2to_id2flight \
                .get(current_id, {}).get(current_day_next, {}).get(to_id)
            if not flight_next:
                continue

            can_spent_next = can_spent - flight_next.price
            if can_spent_next < 0:
                continue

            yield from _generate_trips(
                can_visit_next, can_travel - stay, can_spent_next, to_id,
                                current_day + stay, trip_flights + [flight_next])

因为这个算法很容易实现并行，所以我通过 Pool.pool.imap_unordered 来运行，并使用合并排序进行了预排序：

def _generator_stage(params):
    return sorted(_generate_trips(*params), key=itemgetter(0))

然后并行生成第一个航班与其他旅行航班：

def generate_trips():
    generators_params = [(
        city_ids.difference({start_id, home_city_id}),
        MAX_TRIP,
        MAX_TRIP_PRICE - from_id2day_number2to_id2flight[home_city_id][start_day][start_id].price,
        start_id,
        start_day,
        [from_id2day_number2to_id2flight[home_city_id][start_day][start_id]])
        for start_day in range((MAX_START - MIN_START).days)
        for start_id in from_id2day_number2to_id2flight[home_city_id][start_day].keys()]

    with Pool(cpu_count() * 2) as pool:
        for n, stage_result in enumerate(pool.imap_unordered(_generator_stage, generators_pa
rams)):
            yield stage_result

并利用 heapq.merge 进行排序：

trips = [*merge(*generate_trips(), key=itemgetter(0))]

这看起来像是一道面试题的解决方案。

由于没有进行优化，所以代码运行需要一个多小时，并照用了几乎所有的RAM（很显然利用 multiprocessing 处理 typing.NamedTuple 非常耗内存），但是现在的这个实现在我电脑上需要花费 1 分 22 秒。

最后一步，我将结果保存到 csv 文件中，如下所示：

price,days,cities,start city,start date,end city,end date,details
1373,15,4,La Paz,2018-09-15,Buenos Aires,2018-09-30,Amsterdam -> La Paz 2018-09-15 498 & La Paz -> Santiago 2018-09-18 196 & Santiago -> Montevideo 2018-09-23 99 & Montevideo -> Buenos Aires 2018-09-26 120 & Buenos Aires -> Amsterdam 2018-09-30 460
1373,15,4,La Paz,2018-09-15,Buenos Aires,2018-09-30,Amsterdam -> La Paz 2018-09-15 498 & La Paz -> Santiago 2018-09-18 196 & Santiago -> Montevideo 2018-09-23 99 & Montevideo -> Buenos Aires 2018-09-27 120 & Buenos Aires -> Amsterdam 2018-09-30 460
1373,15,4,La Paz,2018-09-15,Buenos Aires,2018-09-30,Amsterdam -> La Paz 2018-09-15 498 & La Paz -> Santiago 2018-09-20 196 & Santiago -> Montevideo 2018-09-23 99 & Montevideo -> Buenos Aires 2018-09-26 120 & Buenos Aires -> Amsterdam 2018-09-30 460
1373,15,4,La Paz,2018-09-15,Buenos Aires,2018-09-30,Amsterdam -> La Paz 2018-09-15 498 & La Paz -> Santiago 2018-09-20 196 & Santiago -> Montevideo 2018-09-23 99 & Montevideo -> Buenos Aires 2018-09-27 120 & Buenos Aires -> Amsterdam 2018-09-30 460
...

源代码地址：

• https://gist.github.com/nvbn/05225aa1f55e5d57b71824010c3ba892

原文：https://nvbn.github.io/2018/07/10/trip-planner/

作者：VladimirIakovlev，软件开发工程师，主要从事Python、Clojure和JavaScript开发。

译者：弯月，责编：屠敏

_“

征稿啦_”

CSDN 公众号秉持着「与千万技术人共成长」理念，不仅以「极客头条」、「畅言」栏目在第一时间以技术人的独特视角描述技术人关心的行业焦点事件，更有「技术头条」专栏，深度解读行业内的热门技术与场景应用，让所有的开发者紧跟技术潮流，保持警醒的技术嗅觉，对行业趋势、技术有更为全面的认知。

如果你有优质的文章，或是行业热点事件、技术趋势的真知灼见，或是深度的应用实践、场景方案等的新见解，欢迎联系 CSDN 投稿，联系方式：微信（guorui_1118，请备注投稿+姓名+公司职位），邮箱（guorui@csdn.net）。