【最新版】ポケモンしりとりの最長を、線形計画法で導き出す！

f:id:imslotter:20170702115124p:plain

こんにちは、ほけきよです。

数年前に、こんな素敵な論文が流行りましたね。

ポケモンつなげるもん♪

グラフ問題としてしりとりを定式化し、線形計画法で解く。といった一見普通の問題ですが、題材がポケモンであったことから、とある界隈では大きな反響を呼びました。

この時(2011年)はポケモンブラック&ホワイトだったので全646匹, しりとりの最長は305という結果でした。

時は流れて2017年。色々と状況が変わってきました。

線形計画法を解く、簡単なライブラリが増えてきた((pulp, scipy.linprogなど))
ポケモンが増えた(646⇨802)
私の情報処理レベルがアップした

というわけで、 最新版！ポケモン繋げるもん♪やりましょう。

※結果を知りたい方は 3.ポケモンしりとりからどうぞ！

線形計画問題とは
線形計画法ライブラリ「pulp」
- インストール
- さっきの問題をとく
ポケモンしりとり
- ポケモンデータを打ち込む用意
結果しりとり。
- 151匹
- 最新版、ポケモンつなげるもん♪
終わりに

※今回は、結果を知りたいのがメインなので、巨人の肩に乗っかりまくりです。

線形計画問題とは

線形計画問題とは、目的関数と制約条件が１次式で表される最適化問題。工場の生産管理なんかでよく使われたりします。例として、Wikipediaに載っている問題を実際に値を入れながら解いてみましょうか。

農業を営む人が、小麦と大麦のための $A$ 平方キロメートルの農地を持っている。農家は限度 $F$ で肥料、限度 $P$ で殺虫剤を使用することができる。これらはそれぞれ単位面積あたり小麦が $(F_1, P_1)$ 、大麦が $(F_2,P_2)$ を必要とする。小麦の販売価格を $S_1$ 、大麦の販売価格を $S_2$ 、小麦を育てる領域を $x_1$ 、大麦を育てる領域を $x_2$ とすると、利益を最大化するためには、大麦と小麦をどれだけ育てればいいか。(育てる領域×販売価格をここでの利益と定義する)

なお、今回は
$A = 10, F_1 = 2, F_2 = 3, F =40, P_1 = 4, P_2 =1, P =20, S_1 = 100, S_2 = 200$
としてみます。

項目	大麦	小麦	条件	今回
育てる領域	$x_1$	$x_2$	$x_1+x_2 \le A$	$x_1+x_2 \le 6$
肥料の使用量	$F_1x_1$	$F_2x_2$	$F_1x_1+F_2x_2\le F$	$2_1x_1+3_2x_2\le 15$
殺虫剤の使用量	$P_1x_1$	$P_2x_2$	$P_1x_1+P_2x_2 \le F$	$4x_1+1x_2\le 20$
利益	$S_1x_1$	$S_2x_2$	最大化したい	$100x_1+200x_2$

なにやら複雑ですね。こうやって様々な要素が絡み合った問題を解くのが線形計画問題です。

可視化するとこんな感じ。ここの赤で囲まれたところを

線形計画法ライブラリ「pulp」

解くのには、それなりの知識や、早く解くためには専門的な知識が必要なのですが、軽く作った問題を解きたい！！という時には、ライブラリを使うのが今の時代なら良いでしょう。

ここでは、pythonのpulpというライブラリを使います。 pulp、公式ドキュメントが割と貧弱なので、先人のQiita記事がとても参考になり助かります。

PuLP による線型計画問題の解き方ことはじめ - Qiita

インストール

pip install pulp

でOKです。

さっきの問題をとく

記事を見ながら、さっきの問題を解きましょう。ポンポンっと条件を入れていけば、答えを出してくれます。

#coding:  utf-8
import pulp

problem = pulp.LpProblem('sample', pulp.LpMaximize)
# 変数の設定
x1 = pulp.LpVariable('x1', 0)
x2 = pulp.LpVariable('x2', 0)
# 最適化したいものの設定
problem += 100*x1 + 100*x2
# 制約条件の設定
problem += x1 + x2 <= 6
problem += 2*x1 + 3*x2 <= 15
problem += 4*x1 + x2 <= 20

# 結果
print ("Result : (x1, x2) = ({},{})".format(x1.value(), x2.value()))
>>> Result : (x1, x2) = (3.0,3.0)

これは便利ですねぇ。

ポケモンしりとり

では、これを使ってポケモンしりとりを解いていきましょう。

こちらも先人様のサイトを参考に。

最長しりとりを組合せ最適で解く - Qiita

しりとりを線形計画問題として定式化します。

	条件式	意味
最適化対象	$\sum_i \sum_j x_{ij}$	なるべく多くポケモンをつなげる
変数	$x_{ij} \in \left\{0,1\right\} \forall i,j$	しりとりでのキーワードのつながりを示す(i,jはポケモン図鑑の番号みたいなもの)
	$y_{i} \in \left\{0,1\right\} \forall i$	i番目がしりとりの先頭かどうか
	$z_{i} \in \left\{0,1\right\} \forall i$	i番目はしりとりでは何番目か
条件	$\sum_i x_{ij} = 1 \forall i$	同じ単語は使わない(入力制約)
	$\sum_j x_{ji} =1 \forall i$	同じ単語は使わない(出力制約)
	$\sum_j x_{ij} \le \sum_j x_{ij} + y_i \forall i$	yに関する制約
	$z_i \le z_j -(n+1)\times (1-x_{ij}) \forall i,j$	zに関する制約
	$\sum_i y_i = 1$	先頭は1つだけ

ポケモンデータを打ち込む用意

いちいち入力するのは面倒なので、wikipediaからぶっこぬいて使いましょう。ポケモンデータも、以下の前処理をしておきます

記号のカタカナ化ポリゴン2, ポリゴンZ, ニドラン♀, ニドラン♂
拗音, 濁音, 半濁音を修正ょ⇨よ, が⇨かなど
最後の"ー"は排除

こうすると"ポリゴン2"⇨"ホリコンツ"となります。ぶっこ抜くコードはこちら(python3系)

# スクレイピング
from bs4 import BeautifulSoup
from urllib import request

pokemons = []
poke_num = 802
# スクレイピング
html = request.urlopen("https://ja.wikipedia.org/wiki/%E5%85%A8%E5%9B%BD%E3%83%9D%E3%82%B1%E3%83%A2%E3%83%B3%E5%9B%B3%E9%91%91%E9%A0%86%E3%81%AE%E3%83%9D%E3%82%B1%E3%83%A2%E3%83%B3%E4%B8%80%E8%A6%A7")
soup = BeautifulSoup(html, "html5lib")
tables = soup.find_all("td")
for table in tables:
    pokes = table.find_all("td")
    for i,poke in enumerate(pokes):
        if i%2 == 1:
            if poke.string != '\xa0':
                pokemons.append(poke.string)
pokemons = pokemons[:poke_num]
kw = [pokemon for pokemon in pokemons]
# 処理1 記号を日本語に
kw[28] = "ニドランメス"
kw[31] = "ニドランオス"
kw[232] = "ポリゴンツー"
kw[473] = "ポリゴンゼット"
# 処理2　濁音、拗音を処理、"ー"を除去
d = {i:j for i, j in zip('ガギグゲゴザジズゼゾダヂヅデドバビブベボパピプペポィャュョ',
                         'カキクケコサシスセソタチツテトハヒフヘホハヒフヘホイヤユヨ')}
kw = [''.join(d.get(c, c) for c in s.rstrip('ー')) for s in kw]

結果しりとり。

これkwとして、を先ほどのQiita記事の線形計画法に入れてやりましょう。(最後の出力部分のところだけkwをpokemonsに変えれば、元のポケモン名になります。)

151匹

ポケモン初期なら何個繋がるのか。答えは61でした！ベロリンガから始まり、タッツーから終わる。

[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]ハクリュー -> [45]ユンゲラー -> [46]ラプラス -> [47]スリープ -> [48]フリーザー -> [49]サンダース -> [50]スピアー -> [51]アーボ -> [52]ポッポ -> [53]ポニータ -> [54]タマタマ -> [55]マタドガス -> [56]スターミー -> [57]ミュウ -> [58]ウインディ -> [59]イシツブテ -> [60]ディグダ -> [61]タッツー

最新版、ポケモンつなげるもん♪

さあ、いよいよ最新版の802匹でしりとり検索です！！結果は…

387

でした！

そして、これが最長のしりとり結果です。

[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]ブラッキー -> [45]キバニア -> [46]アーボック -> [47]グソクムシャ -> [48]ヤミラミ -> [49]ミカルゲ -> [50]ケルディオ -> [51]オーロット -> [52]トリデプス -> [53]スワンナ -> [54]ナマケロ -> [55]ロゼリア -> [56]アーマルド -> [57]ドククラゲ -> [58]ケララッパ -> [59]ハネッコ -> [60]ゴニョニョ -> [61]ヨワシ -> [62]シママ -> [63]マメパト -> [64]トドゼルガ -> [65]ガラガラ -> [66]ライチュウ -> [67]ウリムー -> [68]ムクバード -> [69]トゲチック -> [70]クヌギダマ -> [71]マナフィ -> [72]イトマル -> [73]ルージュラ -> [74]ランクルス -> [75]ストライク -> [76]グライガー -> [77]カプ・レヒレ -> [78]レックウザ -> [79]サメハダー -> [80]タッツー -> [81]ツボツボ -> [82]ポポッコ -> [83]コジョフー -> [84]フシギダネ -> [85]ネマシュ -> [86]ユキワラシ -> [87]シードラ -> [88]ライボルト -> [89]ドンメル -> [90]ルナアーラ -> [91]ラランテス -> [92]ズバット -> [93]ドレディア -> [94]アシマリ -> [95]リオル -> [96]ルリリ -> [97]リザード -> [98]ドクロッグ -> [99]クサイハナ -> [100]ナッシー -> [101]ジラーチ -> [102]チルット -> [103]ドヒドイデ -> [104]テッカグヤ -> [105]ヤンヤンマ -> [106]マッギョ -> [107]ヨルノズク -> [108]グレイシア -> [109]アママイコ -> [110]コロトック -> [111]クルミル -> [112]ルンパッパ -> [113]バケッチャ -> [114]ヤナップ -> [115]ブーバー -> [116]バニリッチ -> [117]チュリネ -> [118]ネクロズマ -> [119]マネネ -> [120]ネイティ -> [121]イルミーゼ -> [122]ゼニガメ -> [123]メノクラゲ -> [124]ゲンガー -> [125]カラナクシ -> [126]シェルダー -> [127]ダゲキ -> [128]キリンリキ -> [129]キテルグマ -> [130]マダツボミ -> [131]ミミッキュ -> [132]ユンゲラー -> [133]ランドロス -> [134]スピアー -> [135]アリゲイツ -> [136]ツンベアー -> [137]アマージョ -> [138]ヨーテリー -> [139]リグレー -> [140]レジロック -> [141]グラエナ -> [142]ナゾノクサ -> [143]サニーゴ -> [144]ゴルバット -> [145]トルネロス -> [146]スボミー -> [147]ミツハニー -> [148]ニンフィア -> [149]アズマオウ -> [150]ウソッキー -> [151]キュレム -> [152]ムウマ -> [153]マクノシタ -> [154]ダグトリオ -> [155]オノンド -> [156]ドゴーム -> [157]ムチュール -> [158]ルチャブル -> [159]ルカリオ -> [160]オムスター -> [161]ダーテング -> [162]クレベース -> [163]スターミー -> [164]ミネズミ -> [165]ミミロップ -> [166]フリージオ -> [167]オタチ -> [168]チェリム -> [169]ムーランド -> [170]ドテッコツ -> [171]ツツケラ -> [172]ラブカス -> [173]スカタンク -> [174]クルマユ -> [175]ユキノオー -> [176]オンバット -> [177]トゲピー -> [178]ヒドイデ -> [179]ディグダ -> [180]タブンネ -> [181]ネオラント -> [182]ドダイトス -> [183]ズルッグ -> [184]クレッフィ -> [185]イベルタル -> [186]ルクシオ -> [187]オニゴーリ -> [188]リングマ -> [189]マグマッグ -> [190]クズモー -> [191]モンジャラ -> [192]ラフレシア -> [193]アメタマ -> [194]ママンボウ -> [195]ウツロイド -> [196]ドラミドロ -> [197]ロトム -> [198]ムシャーナ -> [199]ナットレイ -> [200]イーブイ -> [201]イノムー -> [202]ムンナ -> [203]ナゲキ -> [204]キバゴ -> [205]コアルヒー -> [206]ビッパ -> [207]バルキー -> [208]キノココ -> [209]ゴローニャ -> [210]ヤナッキー -> [211]ギラティナ -> [212]ナックラー -> [213]ラッタ -> [214]ダイケンキ -> [215]キャモメ -> [216]メリープ -> [217]フワンテ -> [218]デデンネ -> [219]ネッコアラ -> [220]ランプラー -> [221]ライコウ -> [222]ウソハチ -> [223]チャーレム -> [224]ムックル -> [225]ルギア -> [226]アギルダー -> [227]タマンタ -> [228]ダークライ -> [229]イワパレス -> [230]スリープ -> [231]プロトーガ -> [232]カミツルギ -> [233]キャタピー -> [234]ビクティニ -> [235]ニャスパー -> [236]ハーデリア -> [237]アマカジ -> [238]シュバルゴ -> [239]コソクムシ -> [240]シシコ -> [241]ゴーリキー -> [242]キュワワー -> [243]ワタッコ -> [244]コロボーシ -> [245]ジュナイパー -> [246]バオップ -> [247]フラベベ -> [248]ペリッパー -> [249]バネブー -> [250]フーパ -> [251]バニプッチ -> [252]チコリータ -> [253]ダルマッカ -> [254]カエンジシ -> [255]ジグザグマ -> [256]マンキー -> [257]ギャロップ -> [258]フィオネ -> [259]ネイティオ -> [260]オニスズメ -> [261]メガヤンマ -> [262]マケンカニ -> [263]ニョロゾ -> [264]ゾロア -> [265]アブリー -> [266]リリーラ -> [267]ラクライ -> [268]イシズマイ -> [269]イシツブテ -> [270]ディアルガ -> [271]ガマゲロゲ -> [272]ケムッソ -> [273]ソルガレオ -> [274]オオタチ -> [275]チャオブー -> [276]フシギソウ -> [277]ウパー -> [278]ハトーボー -> [279]ボクレー -> [280]レディバ -> [281]ハリテヤマ -> [282]マグカルゴ -> [283]コジョンド -> [284]トゲキッス -> [285]スバメ -> [286]メブキジカ -> [287]カイオーガ -> [288]カメテテ -> [289]デンリュウ -> [290]ウデッポウ -> [291]ウインディ -> [292]イワンコ -> [293]ゴンベ -> [294]ヘイガニ -> [295]ニャルマー -> [296]マニューラ -> [297]ラッキー -> [298]キモリ -> [299]リーフィア -> [300]アチャモ -> [301]モグリュー -> [302]ユキメノコ -> [303]ゴロンダ -> [304]タマザラシ -> [305]ジヘッド -> [306]ドロバンコ -> [307]コスモッグ -> [308]クレセリア -> [309]アゴジムシ -> [310]シズクモ -> [311]モココ -> [312]ゴビット -> [313]ドードー -> [314]トサキント -> [315]ドジョッチ -> [316]チョロネコ -> [317]コスモウム -> [318]ムウマージ -> [319]ジガルデ -> [320]デンヂムシ -> [321]ジャラランガ -> [322]カプ・コケコ -> [323]コラッタ -> [324]ダンゴロ -> [325]ロズレイド -> [326]トドグラー -> [327]ラティオス -> [328]ズガイドス -> [329]スリーパー -> [330]ハスボー -> [331]ホルビー -> [332]ヒヤップ -> [333]フォッコ -> [334]ゴチム -> [335]ムクホーク -> [336]クロバット -> [337]ドデカバシ -> [338]シロデスナ -> [339]ナマコブシ -> [340]シュシュプ -> [341]フリーザー -> [342]サボネア -> [343]アシレーヌ -> [344]ヌイコグマ -> [345]マグマラシ -> [346]シザリガー -> [347]カラカラ -> [348]ラムパルド -> [349]ドーミラー -> [350]ラルトス -> [351]スコルピ -> [352]ビブラーバ -> [353]バスラオ -> [354]オドシシ -> [355]ジュペッタ -> [356]タツベイ -> [357]イワーク -> [358]クチート -> [359]ドードリオ -> [360]オオスバメ -> [361]メラルバ -> [362]ハヤシガメ -> [363]メレシー -> [364]シキジカ -> [365]カモネギ -> [366]キノガッサ -> [367]サンダー -> [368]タマゲタケ -> [369]ケケンカニ -> [370]ニャビー -> [371]ピッピ -> [372]ヒノヤコマ -> [373]マフォクシー -> [374]ジャローダ -> [375]タマタマ -> [376]マッスグマ -> [377]マスキッパ -> [378]パルキア -> [379]アマルルガ -> [380]カイリキー -> [381]キルリア -> [382]アーボ -> [383]ホーホー -> [384]ホイーガ -> [385]カブト -> [386]トランセル -> [387]ルナトーン

最後が「ン」で終わり、まとまりがよろしいようで。

終わりに

いかがでしたでしょうか。みなさんの疑問も解決できたのではないのでしょうか。組合せ最適化問題なので、数が増えると時間が爆発的に増えていきます。ポケモンがこの先増えていくと、より早いアルゴリズムが必要になって来るかもしれません。

また、2017年11月17日にポケモン新作が発売されるらしいです。新キャラ出るのかな？新キャラ出たらまた最新版ポケモンを更新しなければいけないですね。乞うご期待！

しかし、802匹も覚えられるんだろうか...

プロクラシスト

今日の寄り道明日の近道

PROCRASIST

Profile

ほけきよ

Search

Categories

【最新版】ポケモンしりとりの最長を、線形計画法で導き出す！

線形計画問題とは