ツイストバルーンを
グラフ問題に帰着させる
p4sobaya (蕎麦屋)
● 自己紹介
蕎麦屋 (p4sobaya)
・AtCoder 水 1447 (程々に頑張ります・・・)
・CGエンジニア【社会人1年目】
使う言語
・C#（と言ってもUnity内が多い）
・GLSL（シェーダー言語）
・Python（競プロで一番使ってうる）
・Processing（数十分程度でプロトタイピングする時はこれ）
学生時代は 数理最適化・メタヒューリスティクス・極値統計学 など
● 基本的なひねり方 ３種（実演）
・ループツイスト
・ロックツイスト
・ピンチツイスト
● 設計図が存在する
※数値は長さ(cm)
実演！
● 設計図は、無向グラフとして記述可！！！！
無向グラフによる設計図
一筆書きするように 風船を区切っていく！
しかし、作品のサイズが大きい時
ある問題が生じる
● ツイストバルーンとは
←
大学時代に
頑張ってた頃
つくってたやつ！！
● つまり・・・
一筆書き問題 ならぬ
【長さ制約付き Ｎ筆書き問題】
【長さ制約】１本の風船は, 長さ20以下
3
3
3
2
4
3
6
3
5
6
5
5
3
3
2
2
3
3
3
3
2
5
4
2
風船を５本使った！
20
19
19
19
6
設計図（重み付き無向グラフ）が与えられる
この本数を最小化したい！
枝 i の 始点の頂点番号
枝 i の 終点の頂点番号
枝 i の 長さ（重み）
枝 i の 色（整数で指定）
● 問題設定
制約
グラフの頂点数 N ( 2≦N≦1000 )
枝の数 E ( 2≦E≦3000 )
風船の色の数 C (1≦C≦20)
風船の最長の長さ L (1≦L≦200)
入力
入力は以下の形式で標準入力から与えられる。
問題文
高橋君は風船が大好きです。
高橋君は、設計図をもとにバルーンアート作品を作りたいと思っています。しかし、風船はとても高価なので、使う風船の本数をなるべく少なくしたいと考えています…(以下略)
● 欲しい出力
出力
必要な最小の風船の本数 M と、
それを構成する風船の巡回路を出力せよ
但し は i 番目の風船が j 番目に通過する頂点番号
は i 番目の風船が通過する頂点数 を表す。
特に は i 番目の風船の始点
は i 番目の風船の終点を表す。
● テストケース１
立方体の各面に
正方形錐を
くっつけたやつ
頂点数：１４
線分数：３６
長さは全て同じ
● 求まった！！
辺の長さは全て １
辺の数は ３６
に対して
長さ制限 ６
雑に貪欲法を繰り返すだけでも
厳密解が求まった！！
※条件がきれいなので、
３６÷６＝６本…が
答の下界とすぐ分かる
AtCoder300～400点くらい？
（実装がやや面倒臭い！！）
● 折角なので
作ってみた
[[9, 4, 1, 10, 2, 3, 4], [9, 1, 13, 4, 8, 13, 5], [14, 5, 1, 2, 9, 3, 7],
[14, 6, 7, 11, 6, 10, 5], [11, 2, 6, 5, 8, 14, 7], [11, 3, 12, 8, 7, 12, 4]]
● 過程
こうなって
● 過程
こうなって
● 過程
こうなった(実物登場)
※ちゃんと出力通りの順序で風船を組み合わせると
所望の形状が組みあがり、割と感動しました
● テストケース２
斜方切頂
二十・十二面体
(一部三角形分割)
頂点数：１２０
線分数：３００
長さは全て同じ
● メタヒューリスティクス
[[116, 117, 95, 138, 116, 115, 85, 86, 138, 117, 118, 96, 139, 105, 119, 139], [135, 108, 107, 140, 120, 111, 140, 106, 107, 64, 65, 111, 112, 136, 113, 114], [53, 52, 125, 11, 12, 13, 121, 12, 2, 121, 21, 3, 2, 1, 125, 53], [121, 30, 29, 126, 14, 13, 30, 21, 22, 4, 3, 121], [139, 97, 96, 95, 94, 138, 87, 94, 93, 88, 133, 89, 88, 87, 86, 116], [123, 33, 34, 35, 36, 37, 132, 82, 36, 132, 83, 78, 132, 79, 37, 38], [41, 123, 50, 49, 34, 128, 48, 49, 128, 35, 81, 82, 83, 84, 85, 137], [134, 102, 103, 104, 105, 106, 120, 119, 118, 139, 104, 97, 98, 103, 134, 98], [123, 6, 5, 31, 40, 39, 38, 80, 71, 25, 24, 127, 80, 79, 78, 77], [38, 127, 39, 24, 23, 22, 122, 5, 4, 122, 23, 40, 122, 31, 32, 33], [133, 47, 89, 90, 81, 128, 90, 48, 47, 46, 133, 93, 92, 91, 129, 58], [140, 64, 63, 62, 135, 109, 17, 135, 16, 15, 14, 29, 28, 70, 126, 61], [140, 65, 66, 136, 74, 75, 136, 67, 66, 112, 113, 75, 76, 137, 115, 114], [127, 71, 72, 73, 74, 67, 68, 73, 131, 68, 69, 27, 131, 69, 70, 61], [20, 19, 130, 18, 17, 16, 62, 61, 15, 126, 28, 27, 26, 131, 72, 26], [98, 99, 57, 58, 59, 44, 43, 124, 60, 59, 129, 45, 44, 129, 100, 58], [20, 11, 1, 10, 52, 51, 60, 43, 42, 8, 9, 124, 51, 9, 10, 125], [133, 92, 46, 45, 91, 100, 99, 134, 56, 55, 101, 130, 54, 53, 20, 125], [41, 7, 6, 32, 123, 7, 8, 124, 42, 41, 50, 33], [134, 57, 56, 102, 101, 110, 130, 55, 54, 19, 18, 110, 109, 108, 63, 135], [137, 84, 77, 137, 114, 76, 77], [127, 25, 26]]
めでたい
● メタヒューリスティクス
【問題設定】
長さ１ 線分数300 に対して
長さ制限15 で分割を考える
完全ランダム多スタート：25本
遺伝的アルゴリズム：32本 （普通に相性が悪い）
焼きなまし法：24本
近傍を徐々に狭める、ランダム多スタート：22本
果たしてこれ厳密解を求める方法はあるのでしょうか
（長さ15 × 20本…となる解は存在するでしょうか？？？）
● メタヒューリスティクス
メタヒューリスティクスの数理
久保 幹雄 著
第2章 代表的なメタヒューリスティクス
2.1 局所探索法
2.2 多出発局所探索法
2.3 反復局所探索法
2.4 模擬焼なまし法
2.5 禁断探索法
2.6 誘導局所探索法
2.7 大近傍探索法
2.8 探索空間平滑化法と交互平滑化法
2.9 部品最適化法
2.10 多レベル法
2.11 貪欲ランダム適応型探索法
2.12 蟻群生法
2.13 遺伝的アルゴリズム
2.14 散布探索法
「焼きなまし」法
結構色々あった！
● 近似解なら色々やりようがありそう
解x に対する目的関数 f(x)
f(x) = (使う風船の本数)
これでも良いのだが、あまりに目的関数が離散的すぎて良い解に近づきにくい
最小化対象が同じ値でも、「良い解に近い状態」ほど目的関数は小さくなるよう、加工するとよい
f(x) = (使う風船の本数) + (各風船の長さ最小値) / (長さ最大値)
・・・と目的関数を加工する！！
今回は、これを最小化した
● 避けられない難点
・自己ループや多重辺を許してしまう
→ ので、有名アルゴリズムは使えないことも多い
● より現実の問題に近い制約として…
・時々、一方通行もある（有向グラフを考える必要がある）
・「長さ」と同時に「耐久性」を加味する必要
１本の風船につき、ピンチツイストは10回までしかできない等
風船の耐久性には限界がある！！！
・風船を「くぐらせる」「途中で割る」などの作り方も…
→ 始点・終点にしてはいけない節点が出てくる
風船、一応たくさん持ってきたので、
やってみたい人は懇親会の時にでも話しかけて下さい！！
● その他 社会人エンジニアになってみた１感想
・「競プロがエンジニアに必要か？」と言われると恐らく No で、灰色でも多くの分野では余裕
…だが、あったらあったで使える場面はそれなりに多く、
どっちかっていうとその能力自体より、過程で得られた色んな習慣、が実務に役に立つ印象
・フロントエンドやスマホアプリの人たちに数学プログラミングを説明した際に…
「absは絶対値の意味なんだけど… あれ、絶対値を知らない！？」
その場で絶対値の意味が分かったのは11人中6人であった
けれど彼らは実際、いいWebアプリを作っている。エンジニアリングってそんな物なのかも
プログラミング ≠ エンジニアリング
● OWARI
ご清聴ありがとうございました
問題を解いてみたい方は
Twitter @p4sobaya_sci へ！！