動(dòng)畫里有一段女主每天看電視的場(chǎng)景，也不管電視放的啥，反正就是看。就跟刷抖音快手的人一個(gè)心態(tài)。我自己也被這種蜘蛛網(wǎng)抓住了，盡管不覺得這樣很舒服，甚至垃圾信息過多搞得頭疼，也不愿意停下來。寫這些東西也是，頭疼，其實(shí)也沒那么疼。

以前看到一個(gè)視頻，一個(gè)日本小哥天天送完外賣就呆旅館看油管，三和大神一樣。

根本原因是沒人愿意朝200米高的籃筐投籃了吧。我在潛意識(shí)深處還是認(rèn)為自己做的事并不能帶來什么改變，對(duì)于變化我永遠(yuǎn)都只能當(dāng)被動(dòng)接受的一方，連主觀能動(dòng)性都被剝奪，跟死了沒有區(qū)別。

啊對(duì)，我就爛，我就擺，我就是不如它們，這又怎么樣呢？這也是演的啊，就像要跟Typec接口的手機(jī)交換數(shù)據(jù)，你就也得是個(gè)Typec接口，實(shí)際上你們JB誰啊，真的沒興趣，別再控制我的大腦了行嗎？真是麻煩啊，真是麻煩死了，搞這些亂七八糟的。

我還真就是典型INTP，我覺得自己以前很外向，覺得我肯定是哪里病了，但仔細(xì)想想我的外向是怎么來的。是被強(qiáng)迫的，而且也沒有多外向，只是跟誰都能聊兩句所以朋友多而已。

那如果我真的是INTP，為什么我還需要社交？我不是可以從跟自己的對(duì)話中汲取能量嗎？我沒有這樣的功能？我以前有，但是被剝奪了。

再怎么社交依舊感到孤獨(dú)，交流也極度無聊，就用MBTI來解釋，是因?yàn)槲腋緵]辦法從這些東西上汲取能量，這些東西沒法內(nèi)化為我的內(nèi)驅(qū)力，又回到了那個(gè)問題——內(nèi)驅(qū)力。

PTSD可能是一個(gè)原因，但其實(shí)沒那么嚴(yán)重，不存在的東西有什么好怕的呢，只是我總覺得那玩意兒消失了我會(huì)......沒有，自己嚇自己真的無聊，一點(diǎn)都不帥，撈的淌口水真的。

我說說我真正在思考，真正覺得有意思的事吧：

我一直不明白為什么用隊(duì)列在圖上做BFS求最短路是對(duì)的，雖然無論用多少個(gè)例子去測(cè)試，都是正確的，動(dòng)態(tài)調(diào)試也確實(shí)正確，但是到底為什么他喵的，他是正確的，我一直把這個(gè)問題壓在心底。

但是昨天我問了Newbing以后，我明白了：

先假設(shè)點(diǎn)A到點(diǎn)B存在一條最短路C，這很重要，不要糾結(jié)點(diǎn)A到點(diǎn)B怎么就是最短路了，我們假設(shè)它是，那它就是，最初的數(shù)學(xué)也是這樣的，就好像Bootloader一樣，啟動(dòng)(構(gòu)建)一個(gè)系統(tǒng)總要先有最基礎(chǔ)的部分，但是已有知識(shí)為0的話，那個(gè)基礎(chǔ)的部分就只能靠想象了，這就是想象力的重要性，因此不要再花時(shí)間質(zhì)疑這一點(diǎn)了，只要它可以正常工作，那就是對(duì)的，最底層的東西背后沒有本質(zhì)，“造物主”肯定不懂?dāng)?shù)學(xué)，但不妨礙我們用數(shù)學(xué)解釋世界，只要它可以工作就行了，別再TMD糾結(jié)這種最根本的東西了，求求了。有用=正確，僅限最底層的東西，因?yàn)橛械臅r(shí)候你不把房子蓋起來，是不知道房子可以蓋多高的，而現(xiàn)在的房子已經(jīng)捅破天了，即使有更好的底座，也已經(jīng)不可能重建了，所以糾結(jié)這個(gè)真的沒有意義，真沒有.....

好，在認(rèn)同這一點(diǎn)的基礎(chǔ)上，往下想：

假如點(diǎn)A到點(diǎn)B沒有中間點(diǎn)，那么C就是最短路；假如有，設(shè)這個(gè)點(diǎn)為X，那么就有AX，和XB兩條路徑。因?yàn)镃已經(jīng)確定是最短路了，別糾結(jié)，我說是就是，因此AX的長(zhǎng)度+XB的長(zhǎng)度一定是等于C的長(zhǎng)度的，這也沒有異議。那么如果C不是最短路，則AX或XB這兩條路徑里面，一定有一條更短的路徑，即AX的長(zhǎng)度+XB的長(zhǎng)度<C的長(zhǎng)度。

但是C我們已經(jīng)假設(shè)過它是最短路了，而且它的長(zhǎng)度也已經(jīng)確定了，是等于AX+XB的。

然后精彩的地方來了，這里矛盾產(chǎn)生了，C不是最短路這個(gè)結(jié)論被我們?cè)贑是最短路下的前提下的某個(gè)推理推翻了......說實(shí)話，我從來沒有這么想過。

我從來沒有想過可以先假設(shè)一個(gè)結(jié)論是正確的，然后基于它去做各種推理，來反證它是對(duì)的。

這很......奇怪我說實(shí)話。先假設(shè)一件事正確，真的可以這樣嗎？你都假設(shè)它正確了，它能是不正確的嗎？我的這個(gè)問題有點(diǎn)奇怪，但我確實(shí)一直被這種想法遮蔽著。

好吧，繼續(xù)往下：

A到B之間C是最短路，這一點(diǎn)確定了。但是這跟BFS正確有什么關(guān)系呢？

剛剛的矛盾還能得出另一個(gè)結(jié)論：AB是最短路，則AX或XB也一定是最短路，因?yàn)榘袮X或XB換成一條更短的路徑，會(huì)跟AX的長(zhǎng)度+XB的長(zhǎng)度=AB的長(zhǎng)度這一點(diǎn)矛盾，因此AX或XB也是最短路。

換句話說，這個(gè)問題擁有最優(yōu)子結(jié)構(gòu)，子問題的解可以當(dāng)作原問題的輸入用。

你可以把AX跟XB再分成兩半，直到最后變成最簡(jiǎn)單的情況，沒有中間點(diǎn)。

然后因?yàn)殛?duì)列總是會(huì)先訪問離當(dāng)前節(jié)點(diǎn)最近的節(jié)點(diǎn)，也就是沒有中間點(diǎn)的情況，這種情況是最短路，這是確定的。然后繼續(xù)往后訪問，也都是這種沒有中間點(diǎn)的最短路，因?yàn)檫@個(gè)問題有最優(yōu)子結(jié)構(gòu)，所以就像剛剛說的，AX最短，XB也最短，那么AB也將最短，因此從根節(jié)點(diǎn)開始隊(duì)列往后延申的所有路徑，都將是最短路。

更形象一點(diǎn)，有一個(gè)這樣的無向圖：

A-B-C

A首先加入隊(duì)列，然后出隊(duì)列，然后訪問B。AB最短路確定，然后從B入列，出列，訪問C，BC最短確定，因此AC最短也確定，如果AC不是最短，那么AB,BC中一定有一條更短的路，但是前面證明了這條路不存在。從C出發(fā)繼續(xù)往后遍歷，也都可以用這一套理論證明路徑是最短的。

神了。我真的從來沒有這么思考過，但是這樣想以后瞬間理解了好多東西：就單單這一個(gè)問題，首先就有動(dòng)態(tài)規(guī)劃的思想，有數(shù)學(xué)歸納法，然后有BFS，能看出隊(duì)列的性質(zhì)。

原來這一切不是分散的，而是全部串聯(lián)在一起的。之所以突然發(fā)現(xiàn)某道題會(huì)做了，是因?yàn)槟硥K缺少的拼圖后來找到了，因?yàn)橐磺卸际蔷o密結(jié)合在一起的，這種結(jié)合就是創(chuàng)造的本質(zhì)。

補(bǔ)充一點(diǎn)：按照上面的想法，其實(shí)你做DFS也能得出一樣的結(jié)論，假如圖變成這樣：

A-B-C

? ?\/

就是AC之間直接連起來，那么DFS也是ABC的順序，然后上面那一套證明ABC最短。

我要怎么證明DFS是錯(cuò)的呢？

不需要證明，因?yàn)榈诙泳鸵呀?jīng)得到AC的最短路徑了，BFS下從B到C的路徑是被封死的。

還是需要證明，這只能說明BFS為什么是對(duì)的，不能說明DFS為什么是錯(cuò)的。

那么還是先假設(shè)ABC是一條最短路，這樣AB,BC也一定最短，這已經(jīng)確定了。

不對(duì)，這個(gè)問題不在同一個(gè)層面：AB-BC最短，那么ABC肯定最短，這是對(duì)的。

但是這并不能說明這條路徑就是A到C的最短路。

這真的需要證明嗎？如果ABC是最短路，設(shè)它的長(zhǎng)度為L(zhǎng)，那么任何一條A通往C的路徑長(zhǎng)度都必須大于等于L，但是肉眼可見的，有一條路徑的長(zhǎng)度小于L，因此ABC不是最短路。

這樣吧：假設(shè)DFS找到的路徑是A到C之間存在的一條最短路P；再假設(shè)存在一個(gè)點(diǎn)D，也是C的鄰接節(jié)點(diǎn)，并且跟A相連。這里別糾結(jié)為什么P不是ADC，就假設(shè)DFS找到的第一條路徑是P，并且它是最短路。

此時(shí)得出結(jié)論：

1.ADC的長(zhǎng)度>=P的長(zhǎng)度

好，在這樣前提下：設(shè)P的長(zhǎng)度為10，但是ADC的長(zhǎng)度為2，矛盾了，所以DFS找到的不是最短路。

不全對(duì)。其實(shí)DFS記錄一下，還是可以用來找最短路的，只能證明DFS無法在第一次到達(dá)某個(gè)節(jié)點(diǎn)時(shí)，就經(jīng)過了最短路徑......

以前都是靠直覺理解的這些，完全沒有一種可靠的感覺，就有一種隨時(shí)有可能崩塌的感覺，所以做題做不出來，但是公式是絕對(duì)的，比直覺可靠，這條路才是對(duì)的。