feature image

2024年3月21日 | ブログ記事

メタヒューリスティクスで美しくいたずらしたい!

この記事は新歓ブログリレー2024の14日目です。


はじめまして、あるいは、こんにちは。アルゴリズム班のComaviusです。

さて、皆さんは唐突にいたずらをしたくなることはありませんか?ありますよね?少なくとも私にはあります。今回は私がtraPの部内SNSであるtraQ(「トラック」と読みます)でちょっとしたいたずらをした時の話をしようと思います。

本題

実はtraQにはtraQgazerというエゴサ支援ツールがあり、これはユーザーが事前に登録した文字列を含む投稿を通知してくれます。そして、やはり自分のユーザー名を登録している人が多いようなので、全ユーザーのユーザー名を部分文字列として持つ文字列を投稿してエゴサをしている陰険な人間(たとえば私など!)を呼び出してやろうと思います。しかし、ただ呼び出すだけでは美しくありません。

アルゴリズム

ここで、美しさために、可能な限り短い文字列でこれを実現することを考えます。これはShortest Superstring Problemという名前の問題で、現実的な時間で厳密解を得ることはできません[1]。今回は焼きなまし法[2][3]という近似アルゴリズムを使ってこれを解きたいと思います。

結果と評価

結果として、10分程度の実行で ユーザー名の総文字数=3242文字 から 2674文字 まで改善することができました。これがどれだけ優秀なのかは正直よくわかりませんが、PythonのライブラリであるSageMathのソルバーを十分な時間動かした時の解と同じスコアらしいため、優秀だということにしておきます。


呼び出されてしまった被害者の皆様
Many Stamps on traQ

宣伝

この記事に興味を抱いた新入生の皆さん、朗報です。来る3/22から競技プログラミングサイトのAtCoderで新しくヒューリスティックコンテスト(AHC031)が開かれ、焼きなまし法をはじめとした近似解法を使って全世界1000人以上の参加者とスコアを競うことができます。ぜひ参加しましょう!


明日は@ikura-hamuさんと@beferiaさんの素晴らしい記事が投稿されます。お楽しみに!


  1. NP困難と検索するとこの辺りの情報が出てくるはずです。 ↩︎

  2. 最初は広い範囲を探索し、次第に探索する範囲を狭めていくことを意図した手法です。 ↩︎

  3. 実装にあたってyunixさんの記事を参考にしました。 ↩︎

comavius icon
この記事を書いた人
comavius

algoとheurと諸々と

この記事をシェア

このエントリーをはてなブックマークに追加
共有

関連する記事

2024年3月22日
traPグラフィック班の活動紹介2024
haru10 icon haru10
2024年3月17日
⑨でもわかる8bitアレンジ講習会
vPhos icon vPhos
2024年3月11日
思想の強いゲーム制作をしよう!
Kirby0717 icon Kirby0717
2023年9月26日
traP コンペ 2023 夏 sponsored by ピクシブ株式会社 運営後記
abap34 icon abap34
2023年7月13日
アルゴリズム班はやとき王選手権「競(けい)プロ」を開催しました!
abap34 icon abap34
2022年10月11日
アルゴリズム班にKaggle部を設立し、初心者向けデータ分析体験会を開催しました!
abap34 icon abap34
記事一覧 タグ一覧 Google アナリティクスについて 特定商取引法に基づく表記