NTT、「1つのケーキを2人で公平に分割する」アルゴリズムを開発

　あるAnonymous Coward 曰く、

　NTTが「一つのクリスマスケーキを２人で公平に分けるには、どこにナイフを入れたらいいか」という「ケーキ分割問題」を正しく解くアルゴリズムを開発したそうだ（日刊工業新聞）。

「ケーキ分割問題」とは、2人で1つのケーキを分割する際に、両者が満足するように分割するにはどうすれば良いか、という問題。2人が異なる価値観を持っているというのがポイント。今回発表された新アルゴリズムは「両者が同時に切りたい場所を申告し、その中間でカット、申告した場所を含むケーキを分配する」というものだそうだ。

今日・明日とケーキを食べる機会は多いかと思うが、さっそく応用してみてはいかがだろうか。しかし、3人以上で分割する場合はどうすれば良いのだろうか？

　スラッシュドットのコメントを読む | サイエンス

　関連ストーリー：
「歴史的出来事が最も少なかった日」は1954年4月11日 2010年11月29日
ミツバチはコンピュータよりも速く巡回セールスマン問題を解ける 2010年10月26日
Google は非リア充にムチ打つようだ 2009年12月01日
粘菌が組み合せ最適化問題を解く 2008年04月14日