おにごっこ最適化 PuLP

おにごっこ最適化

おにごっこに関する最適化問題の例として、5人でおにごっこをする場合、どのように逃げた方が最適か？という問題を考えてみます。

解法

以下は、PuLPを用いた解法です。

まず、必要なライブラリをインポートします。

1
from pulp import *

次に、問題の定式化を行います。この問題では、以下のようになります。

🔹変数
　x_i (i = 1, 2, …, 5): i番目の逃げる場所に行くかどうか (1: 逃げる, 0: 逃げない)
🔹目的関数
　逃げる人数の最大化
🔹制約条件
　逃げる人数は4人以下

これをPuLPで表現すると、以下のようになります。

1
2
3
4
5
6
7
8
9
10
11
# 問題の定義
prob = LpProblem('Onigokko', LpMaximize)

# 変数の定義
x = [LpVariable('x{}'.format(i), cat='Binary') for i in range(1, 6)]

# 目的関数の定義
prob += lpSum(x)

# 制約条件の定義
prob += lpSum(x) <= 4

ここで、lpSum()はPuLPが提供する関数で、与えられたリストの要素の和を計算します。

制約条件は、<=で表現しています。

次に、PuLPを使って求解を行います。

1
2
# 求解
status = prob.solve()

このようにして、求解が終了しました。最後に、結果を表示してみます。

1
2
3
4
5
6
# 結果を表示
print('Status:', LpStatus[status])
for i in range(1, 6):
    print('x{} = {}'.format(i, int(value(x[i - 1]))))
print('Optimal value:', value(prob.objective))

これを実行すると、以下のような結果が得られます。

[実行結果]
Status: Optimal
x1 = 1
x2 = 1
x3 = 1
x4 = 1
x5 = 0
Optimal value: 4.0

結果から、最適解が得られ、1番目、2番目、3番目、4番目の場所に逃げることが最適解になることが分かりました。

また、逃げる人数は4人であることも分かります。