《最強大腦》收官！裡面的燈陣密碼你看懂了嗎？

最強大腦是江蘇衛視推出的一檔科學競技真人秀節目，專註於傳播腦科學知識和腦力競賽。正如其口號宣傳的那樣，這個節目從頭到尾都是在燃燒大腦。講真，小編每看完一期，都有一種感覺，和場上的選手比起來，自己的腦子好像是被注了幾十斤水一樣！而且這種感覺越來越強烈……

終於，這一狀態在2018年2月9號的一期節目中得到了緩解！在這一期節目中由於賭王的兒子何猷君意外退賽（小編確實是奔著看才子風采來的），劉星圖與張夢南進行PK，而PK的題目則是一張燈陣網路密碼圖，選手需要在規定時間內記憶這張密碼圖，推導出燈與燈之間的內在網路聯繫。隨後，兩位選手依次點亮其中一盞燈，與此燈相關聯的所有燈也會被同時點亮成相同的顏色，共十回合，最後亮燈多者獲勝。

聽完題目，艾瑪！心裡竊喜，終於有一道我能聽明白的題出現了！今天小編就和大家來具體解讀一下這個燈陣密碼究竟是何方神聖。

要看懂這個燈陣密碼，讓我們首先來了解一下什麼是社交網路數據。在我們的日常生活中，無時無刻不在接觸著這樣的數據。比如你現在正在用微信瀏覽這篇文章，諸如微信、QQ、微博等這樣的社交工具，蘊藏著大量的社交網路數據。人們在虛擬社交平台建立了聯繫（比如微博上用戶之間的互相關注），使得看似在物理世界相互獨立的個體，其實有著千絲萬縷的聯繫。再比如通訊網路，也可以看成是一種網路結構數據，如果把個體之間通過電話定義為一種聯繫，那麼根據每個人的通話詳單就可以構建一個社交網路。除此之外，網站之間的超鏈接、學術文章的互相引用、郵件往來等等都可以看成是具有某種聯繫的網路結構數據，因此只要我們能夠合理的定義一種聯繫，那麼就可以構建出相應的網路結構。如果非要給社交網路數據下一個定義的話，那麼社交網路數據就是由網路拓撲結構和附著在該結構上的數據構成的。

1網路拓撲結構

首先我們來看一下什麼是網路拓撲結構，網路拓撲結構是由節點和邊構成的一個具有複雜關係的圖結構。為了讓大家能更直觀的了解網路拓撲結構，我們隨機生成了一個具有20個節點的網路（如圖1），圖中的圓圈代表節點，而節點之間的連線就是邊。

圖1 20個節點的網路圖

網路拓撲結構中，根據邊的方向可以分為有向圖和無向圖（如圖2）。其中左側圖中邊有具體指向，是一個有向圖，右側圖中邊無具體指向，是一個無向圖。有向圖類似於單行道，只能從1到2，而不能從2返回到1，而無向圖是可以互相連通的。

圖2 有向圖（左）、無向圖（右）

回到節目中的燈陣，這就是一個擁有更多節點（由20個到100個）和更多複雜關係的升級版網路圖，我們看到當大屏幕上顯示出100盞燈的關係圖時，底下觀眾目瞪口呆發出一陣驚呼，大家肯定在想這麼複雜的連接關係要怎麼找啊？！

誠然，即便你視力再好，拿著放大鏡去尋找燈與燈之間的關係，也是無濟於事的。不過不用擔心，聰明的人們早就想出了一個巧妙的辦法來記錄這看似複雜的關係。這便是鄰接矩陣，鄰接矩陣是用來表示節點之間相鄰關係的矩陣。對於無向網路圖，鄰接矩陣一定是對稱的，且主對角線全為零，而有向圖的鄰接矩陣不一定對稱。以圖2中的兩個簡單網路圖為例，用鄰接矩陣表示為下表1。以左表為例，如果1號節點到2號節點有一條邊，那麼相應的在第1行第2列的格子里記為1，否則為0。

表1 有向圖鄰接矩陣（左）、無向圖鄰接矩陣（右）

了解了鄰接矩陣，再來看節目的燈陣密碼，就不難理解，選手們就是通過這樣的一個密碼圖（鄰接矩陣）來記憶燈與燈之間的關係。例如圖中的「小黑點」就是鄰接矩陣里的「1」，點亮10號燈，和他有關聯的44、49、54、74和99會被同時點亮。這張密碼圖是一個典型的無向圖，因為燈之間是互相聯繫的，並不存在方向。我們仔細觀察一下，就會發現這張圖是完全對稱的。

2節點出（入）度

選手們接下來要做的是依次報燈號，看誰點亮的燈最多。如何做呢？對於每一個行坐標的燈號，選手需要數一數這一行中「小黑點」的個數，個數越多，點亮的燈數越多，於是選手應該先報連接「小黑點」個數最多的燈號。

在這個過程中，我們不知不覺的在統計節點的度。節點的度定義為與該節點相連的邊的條數。特別的對於有向圖，又分為出度和入度，根據字面上的含義不難理解，出度就是由該節點指向其他節點的有向邊條數，入度就是由其他節點指向該節點的有向邊條數。根據鄰接矩陣的行和和列和能夠直接表示出節點的出度和入度。如表1中有向圖鄰接矩陣，對鄰接矩陣的行求和，1號到4號節點的出度分別是2,、0、1、2。列求和後，1號到4號的入度分別為0、3、2、0。對於無向圖，某一節點的出度與入度是相等的，如表1中無向圖鄰接矩陣，矩陣行和與所對應的列和是相等的，1號到4號節點的出（入）度分別為2、3、4、2。

選手需要在20分鐘內逐行記憶這個燈陣密碼圖，包括每盞燈的出（入）度，一盞燈與哪幾盞燈相連。以A燈為例，選擇A燈後，與A燈相連的9盞燈被同時點亮。可以想像，如果此時選手手裡有一台筆記本電腦，只需要對這100盞燈的鄰接矩陣做一個行加總的運算，得出每一盞燈的出度多少，並且將他們按照降序排列，排在最前面的燈號應該先報。

3共同「好友數」

顯然要想贏得比賽不可能只選擇度數最多的燈點亮，因為根據比賽規則，每個回合選手所報燈號，除了會把與其相關聯的燈點亮成該選手的顏色，若所報燈號相關聯的燈與先手方重合，則顯示為後手方的顏色，即該燈為後手方所有。難度瞬間增加了有木有！

進一步分析遊戲規則可以發現，這個遊戲策略主要從兩個方面入手，第一，所選燈號關聯的燈儘可能的多，因此可以在每個回合中點亮更多的燈；第二，所選燈號關聯的燈儘可能多地與對手已經點亮的燈重合，這樣可以滅掉對手更多的燈。看到這，可能有人會發出「站著說話不腰疼」的感慨！確實，只知道這兩個策略是遠遠不夠的，關鍵是如何實現這兩個戰略目標。光說不練假把式！下面，我們就以最開始構建的20個節點的簡單網路圖為例，通過實際演練來理解並且運用這兩個策略。

對於第一個策略，我們在上文中已經給出了答案，即尋找節點度最多的燈。那麼對於第二個策略：滅對手的燈，對應到網路數據，實際上是在找兩個節點的「共同好友」，找到「共同好友」越多的兩個節點，滅掉對手的燈就越多。例如，如果10號燈和44、49、54、74、99號相連，同時我們發現11號燈和23、49、51、54、88相連，那麼10號燈和11號燈的「共同好友」就是49和54號兩盞燈。我們用上文模擬的20個節點的網路結構為例進行說明。首先將該網路結構的鄰接矩陣定義為A，如下圖3所示。

圖3 模擬的20個節點的鄰接矩陣

接下來計算矩陣B=AA』，這裡需要複習一下線性代數的知識，A』表示A的轉置，即將A矩陣的行和列調換之後的矩陣，此時矩陣B中的每一個元素代表的就是相應兩節點的「共同好友」數。矩陣B如下圖4所示。例如，第1行第6列格子里的數為1，說明1號節點和6號節點僅有1個共同好友，同理第3行第6列的數為2，說明3號節點和6號節點有2個共同好友（從網路圖也可以看出，它們的「共同好友」為5號節點和20號節點）。此外，細心的讀者可能已經發現B中對角線元素即為相應節點的出（入）度，因此兩個策略可以同時在矩陣B中進行決策。

圖4 節點間「共同好友」數矩陣

明白了上述原理後，讓我們開展實戰演習來加深對以上策略的理解。假設甲為先手方，其燈標記為藍色；乙為後手方，其燈標記為紅色。在第一回合，作為先手方的甲，不需要考慮滅對手的燈，因此，選擇出（入）度最大的6號燈，同時點亮了關聯的6盞燈，總共點亮7盞燈，如圖3左圖所示。此時，作為後手方的乙，從策略一來說，應該傾向於選擇剩餘燈中出（入）度最大的13號或4號燈；從策略二來說，他可以選擇滅掉對手更多的燈，即選擇和6號有更多共同好友數的3號燈。我們在節目中看到，在最開始的幾個回合，選手們都傾向於先佔領地盤，即點亮最多的燈（策略一）。因此這裡我們假設乙選擇點亮13號燈。此時點亮6盞燈，同時滅了甲1盞燈，結果如圖5右圖所示，第一回合結束，場上比分6:6。

圖5 第1回合結束時結果

進入第二回合，目前只有8盞燈可以選擇。如果甲繼續選擇具有最大出（入）度的燈，有3號燈和9號燈可供選擇，但因為3號燈關聯的燈有兩盞已經被自己點亮，因此甲在此輪中選擇9號燈，而此時乙已經沒有機會滅掉甲的燈，即使乙選擇了12號燈，將全部燈點亮，仍然還是藍色燈居多，第二回合結束比分11：9。

圖6 比賽結束比分

這是我們列舉的其中一個策略，讀者們可以自行模擬出不同策略下的比賽結果。比賽雙方的不同策略選擇組合，會導致不同的結果。一般來說，在比賽開始階段，比賽雙方都會儘可能地點亮更多的燈（選擇出（入）度較大的燈號），先佔領一定的地盤；在比賽角逐過程中，處於劣勢的一方應將重點放在儘可能多地熄滅對手的燈，這樣更容易實現比賽形勢的逆轉，而處於領先的一方往往更注重繼續攻佔更多的燈，保持領先優勢，同時儘可能熄滅一些對手的燈。在瞬息萬變的賽場上，每一個決策都關注著最終的勝負。

這裡我們僅僅模擬了20個燈的情況，實際比賽中，比這複雜的多，有100個燈，並且，選手不能看到燈與燈之間的真實聯繫，而是在有限的時間內通過記憶燈陣密碼圖來獲得。小編表示，即使比賽的時候把密碼圖擺在面前，或者甚至把這些連接關係用線連接在一起展示出來，小編也沒法在30秒之內做出像選手那般快、准、好的抉擇！

實際比賽中，不到最後一刻，很難判斷最終誰勝誰負，雙方在做選擇時稍有差池，都有可能造成局面的大逆轉，尤其在小編全神貫注、屏住呼吸看了2018-3-23期中美對戰點燈新世界（點燈小世界震撼升級版）中郭小舟與Henry Prior的激烈角逐之後，對此深有感觸！不信你去看一看就知道了（但要注意保護好自己的小心臟）！

更多精彩敬請關注「狗熊會」公眾號！

狗熊會簡介：

致力於數據產業的高端智庫。狗熊會以數據治理為核心，以數據資源資產化為目的，幫助合作夥伴制定數據戰略，培養數據人才，研究數據業務，發現數據價值，推動產業進步！

狗熊會使命：

聚數據英才，助產業振興！

狗熊會關注數據科學基礎教育，希望通過生產優質的數據科學教育內容，提供卓越的研究、實踐、就業機會，幫助相關專業