9.1 從問(wèn)題到狀態(tài)

????解決這個(gè)問(wèn)題的關(guān)鍵是要搞清楚老鼠所有可能的位置可以等價(jià)為幾種可能的狀態(tài)，答案是兩種，如圖所示：

????解法：假設(shè)老鼠第一天在 (2,4) 狀態(tài)，

????第1天：可以在2、4之間隨便打開(kāi)一個(gè)，比如2，如果老鼠碰巧在2中，直接結(jié)束。如果在4中，那么老鼠第二天必在3或5；

????第2天：打開(kāi)3，如果老鼠在3，直接結(jié)束，如果不在，那么老鼠肯定在5，第三天必在4

????第3天：打開(kāi)4，直接抓住結(jié)束

????第4天：如果3天后未果，說(shuō)明一開(kāi)始的假設(shè)錯(cuò)誤，說(shuō)明老鼠第一天在 (1,3,5) 狀態(tài)，但如今已經(jīng)第4天了，由轉(zhuǎn)換圖可知第4天老鼠必在 (2,4) 狀態(tài)，直接按照第1-2-3天的流程再走一遍即可，因此最多6天老鼠必落入法網(wǎng)。

9.2 等價(jià)性：抽象出狀態(tài)的工具

????

????1）矢量量化（Vector Quantization, i.e.?VQ）：將物理性質(zhì)投射到幾個(gè)主要維度中，比如投射到形狀、顏色、大小和旋轉(zhuǎn)角度等維度中，記為<w,x,y,z>。這樣能夠?qū)β淙胪环菔噶恐械臇|西進(jìn)行合并，并產(chǎn)生富有價(jià)值的信息。

????信息矢量化的應(yīng)用場(chǎng)景主要在信息壓縮方面，比如計(jì)算機(jī)上顯示的矢量字庫(kù)、矢量圖等。另外在語(yǔ)音的壓縮編碼和識(shí)別、圖像壓縮、信號(hào)檢測(cè)以及通信標(biāo)準(zhǔn)的制定上也都要用到。

????2）傅立葉變換（Fourier Transform）：人發(fā)音的讀音波形記錄的是在任何一個(gè)時(shí)刻的聲波強(qiáng)度，這種方式記錄的語(yǔ)音信號(hào)被稱為【時(shí)域信號(hào)】：

????如果里面有噪聲則無(wú)法濾除，但傅立葉變換提供了另一種記錄聲波信息的方式，即記錄每一個(gè)頻率下信號(hào)的強(qiáng)度和相位，被稱為【頻域信號(hào)】。對(duì)于該類信號(hào)，則可以過(guò)濾掉不屬于語(yǔ)言頻率范圍的全部信號(hào)（即噪聲，如交流電信號(hào)、宇宙輻射信號(hào)、電路接觸不良的脈沖信號(hào)）。

????不僅語(yǔ)音可以這樣處理，存儲(chǔ)照片也可以用到等價(jià)信息，常用的圖片JPEG格式，就是把空間信號(hào)變成等價(jià)的頻率信號(hào)，以壓縮圖像大小。

9.3 因果關(guān)系：建立狀態(tài)間的聯(lián)系

????利用【圖論】這個(gè)工具將狀態(tài)之間的因果關(guān)系清晰的描述出來(lái)，可以幫助解決一些復(fù)雜問(wèn)題：

????圖(a)中初始狀態(tài)出發(fā)的三種狀態(tài)中，因?yàn)榭紤]到B和D、b和c的性質(zhì)相同（即對(duì)稱），可以將B/b、C/c的各種情況合并到一起：

????如何將具體問(wèn)題變成計(jì)算問(wèn)題，才是計(jì)算機(jī)從業(yè)者需要解決的問(wèn)題。需要做好控制，就需要有清晰的邏輯和系統(tǒng)的方法。將問(wèn)題中的各種情況抽象成狀態(tài)，將大量看似無(wú)關(guān)的情況用少數(shù)狀態(tài)覆蓋，在理清狀態(tài)之間的邏輯關(guān)系，是計(jì)算機(jī)從業(yè)者所應(yīng)具備的能力。