分享本文至 E-mail 信箱
學術引用格式
MLA
APA
EndNote(.enw)

比想像中更困難-俄羅斯方塊

2011/02/08 | 未分類 |

Original publish date:Nov 10, 2002

編輯 John C. H. Chen 報導

根據幾位電腦學家的研究,他們發現了俄羅斯方塊困難的原因。

大概有玩過電動玩具的人都玩過俄羅斯方塊,這個一堆形狀不同的方塊會源源不斷的自上方落下的遊戲。這個遊戲的規則極為簡單,不過卻是讓許多人手忙腳亂,但決不影響它自1985年發明以來一直受到大家喜愛。到底困難的原因何在?MIT的Erik Demaine給出了答案。

他們表示俄羅斯方塊類似於一種稱為NP-complete的問題,相類似的範例有推銷員問題(一個推銷員要如何用最短的時間走過所有的城市)。這種問題的解決需要把所有可能做過評估,然後再尋找最佳化解。這對於電腦而言就是考驗記憶體跟運算速度的時候。當在玩俄羅斯方塊的時候,玩家必須對所有可能進行嘗試,就算是沒有任何時間壓力,還是一件麻煩事,更不用說那種來有兩人對戰功能的情形了。所以要設計一種能快速有效玩俄羅斯方塊的邏輯運算幾乎是不可能的任務。

所以下次在玩俄羅斯方塊時,或許可以套句Demaine的話:我在解決一個很困難的問題。

原始論文
Demaine, E.D., Hohenberger, S. & Liben-Nowell, D. Tetris is hard, even to approximate. Preprint, (2002).

參考來源:

本文版權聲明與轉載授權資訊:


泛知識節倒數一周!3/30、3/31隆重登場!

宇宙間有好多好多的知識,怎麼學都讓人不滿足。而學習也有好多好多方式,才不只是背誦跟考試。

讓我們在泛知識節一起探索學習的 N 種方式,找回學習的樂趣、求知的純粹,讓天下沒有難學的知識!

想知道學習還有什麼可能?就來知識節吧:http://bit.ly/2FgTb83

想了解更多可以去官網看看喔:http://bit.ly/2FhrsUF


泛科學院精選線上課程:爸媽需要搞懂的 14 堂大腦教養課(預購)

老是覺得小孩不乖?各位爸媽別煩惱,一起跟著資深心理師學習「教養心理學」,了解孩子的心理狀態和發展需求,讓親子之間溝通更順暢、關係更親密!

關於作者

科景

Sciscape成立於1999年4月,為一非營利的專業科學新聞網站。

網站更新隱私權聲明
本網站使用 cookie 及其他相關技術分析以確保使用者獲得最佳體驗,通過我們的網站,您確認並同意本網站的隱私權政策更新,了解最新隱私權政策