バケーション最適化

バケーション最適化

バケーションに関する最適化問題の一例として、「与えられた旅行先のリストと各場所の観光ポイント数と交通手段のコストが与えられたとき、特定の日数内で最も多くの観光ポイントを訪れるための最適な旅程を見つける」という問題を考えてみましょう。

これを解くための単純な贅沢な旅行計画をPythonで実装してみます。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
from itertools import permutations

def optimize_vacation(destinations, days):
    # 各目的地の観光ポイント数と交通手段のコストを設定
    attractions = {
        'Tokyo': {'points': 10, 'cost': 50},
        'Kyoto': {'points': 8, 'cost': 40},
        'Osaka': {'points': 6, 'cost': 30},
        'Hiroshima': {'points': 7, 'cost': 35},
        'Sapporo': {'points': 5, 'cost': 25}
        # 他の目的地も必要に応じて追加
    }

    best_itinerary = None
    max_points = 0

    # 目的地の順列を生成
    for perm in permutations(destinations):
        total_days = min(len(destinations), days)
        current_points = 0
        current_cost = 0

        # 旅程を評価
        for i in range(total_days):
            current_points += attractions[perm[i]]['points']
            current_cost += attractions[perm[i]]['cost']

        # 予算内で最大のポイントを持つ旅程を更新
        if current_cost <= 150 and current_points > max_points:
            max_points = current_points
            best_itinerary = perm

    return best_itinerary, max_points

# 旅行先のリストと旅行日数を設定
destinations = ['Tokyo', 'Kyoto', 'Osaka', 'Hiroshima', 'Sapporo']
days = 3

# 最適な旅程を計算
best_itinerary, max_points = optimize_vacation(destinations, days)

# 結果の表示
print(f"最適な旅程: {best_itinerary}")
print(f"獲得ポイント: {max_points}")

このサンプルコードでは、destinationsに旅行先のリストを、daysに旅行日数を指定しています。

各目的地の観光ポイント数と交通手段のコストが与えられ、予算内で最も多くのポイントを獲得する最適な旅程を見つけます。

[実行結果]

最適な旅程: ('Tokyo', 'Kyoto', 'Hiroshima', 'Osaka', 'Sapporo')
獲得ポイント: 25

ソースコード解説

以下にソースコードの章立てと詳細な説明を示します。

1. ライブラリのインポート

1
from itertools import permutations
  • itertoolsモジュールからpermutations関数をインポートしています。
  • permutations関数は、与えられたリストの順列を生成するために使用されます。

2. 旅行最適化関数の定義

1
2
def optimize_vacation(destinations, days):
    # ...（後続のコードが続く）
  • 与えられた旅行先と旅行日数に対して、最適な旅行プランを見つけるための関数 optimize_vacation を定義しています。

3. 目的地の情報と初期化

1
2
3
4
5
6
7
8
attractions = {
    'Tokyo': {'points': 10, 'cost': 50},
    'Kyoto': {'points': 8, 'cost': 40},
    'Osaka': {'points': 6, 'cost': 30},
    'Hiroshima': {'points': 7, 'cost': 35},
    'Sapporo': {'points': 5, 'cost': 25}
    # 他の目的地も必要に応じて追加
}
  • attractionsという辞書型の変数に、各目的地の観光ポイント数と交通手段のコストを定義しています。
  • 各目的地は都市名をキーに持ち、その値は観光ポイント数とコストの辞書です。

4. 結果を格納する変数の初期化

1
2
best_itinerary = None
max_points = 0
  • 最適な旅程と最大のポイントを格納する変数を初期化しています。

5. 目的地の順列生成と旅程評価

1
2
3
4
5
6
7
8
for perm in permutations(destinations):
    total_days = min(len(destinations), days)
    current_points = 0
    current_cost = 0

    for i in range(total_days):
        current_points += attractions[perm[i]]['points']
        current_cost += attractions[perm[i]]['cost']
  • permutations(destinations) によって、目的地のリストから順列を生成します。
  • 各順列に対して、与えられた旅行日数内での旅程を評価しています。
  • current_points は現在の旅程で獲得できる観光ポイント数を、current_cost はその旅程の総コストを表します。

6. 予算内で最大のポイントを持つ旅程の更新

1
2
3
if current_cost <= 150 and current_points > max_points:
    max_points = current_points
    best_itinerary = perm
  • 予算内で最大のポイントを持つ旅程を見つけた場合、best_itinerary と max_points を更新します。

7. 結果を返す

1
return best_itinerary, max_points
  • 最適な旅程とその際の獲得ポイントを返します。

8. 旅程の計算と結果の表示

1
2
3
4
5
6
7
destinations = ['Tokyo', 'Kyoto', 'Osaka', 'Hiroshima', 'Sapporo']
days = 3

best_itinerary, max_points = optimize_vacation(destinations, days)

print(f"最適な旅程: {best_itinerary}")
print(f"獲得ポイント: {max_points}")
  • 旅行先のリストと旅行日数を指定して、optimize_vacation 関数を呼び出し、最適な旅程と獲得ポイントを計算します。
  • 結果をコンソールに表示します。

結果解説

[実行結果]

最適な旅程: ('Tokyo', 'Kyoto', 'Hiroshima', 'Osaka', 'Sapporo')
獲得ポイント: 25

この結果は、与えられた旅行先のリストと旅行日数に対して、予算内で最も多くのポイントを獲得するための最適な旅程が次のようになることを示しています：

  • 最適な旅程: (‘Tokyo’, ‘Kyoto’, ‘Hiroshima’, ‘Osaka’, ‘Sapporo’)
  • 獲得ポイント: 25

各目的地には観光ポイント数が割り当てられており、この目的地の順列を生成していくつかの旅行プランを試しました。
予算は総コストが150以下である制約があり、それを満たしながら最も多くの観光ポイントを獲得できる旅程を見つけることが目的です。

解析結果に基づいて、最適な旅程は(‘Tokyo’, ‘Kyoto’, ‘Hiroshima’, ‘Osaka’, ‘Sapporo’)で、この旅程で訪れた各都市の観光ポイント数を合算すると25ポイントになります。

獲得ポイントが最大であるため、この旅程が与えられた条件下で最適な選択となります。