演算法＋資料結構＝程式

程式語言Pascal的創建者曾經說過：「演算法+資料結構=程式」，事實上，演算法往往決定了該如何解決問題的大方向，至於我們對於資料結構的選擇，則決定了實作程式的難易度。

演算法與資料結構

基本上，資料結構描述的是（電腦中）儲存、組織資料的方式，而演算法規範的是一系列運算步驟，並不涉及特定程式語言（甚至是不涉及電腦的運用），因而我們可以使用虛擬碼、流程圖，或甚至自然語言來描述。

演算法當中雖然討論空間複雜度，不過，嚴格來說，演算法並不涉及特定資料結構，只不過在存取特定資料結構時，確實也需要一系列的運算步驟，而這類步驟，就是為了解決特定資料結構組織、存取資料時的演算法。

雖然演算法與資料結構是兩個不同的研究領域，然而，實際上，選擇不同的資料結構，會影響存取該資料結構的演算方式，而存取資料結構的演算方式，其實是會影響程式主要演算法實作上的難易度、效率等問題。

正確的資料結構也可以提高程式主要演算法的效率，而有些資料結構更是為了解決特定問題而設計，兩者其實是相輔相成。

舉例來說，想要創建迷宮，我們可以使用遞迴回溯演算，若要運用這演算並不需要電腦，只使用紙筆，也可以實現遞迴回溯演算來手繪迷宮，簡單來說，四個方向隨機選一個鄰居細胞，若下個細胞未造訪過，打通該面牆、走到下個細胞，若沒有可造訪的細胞就原路返回，重複以上流程、直到全部細胞都造訪過為止。

若是方形迷宮，程式實作上很自然地，會選擇二維陣列之類的資料結構，因為上下左右的選擇，在演算法上只是行（column）、列（row）索引加或減一的關係，無論是索引存取或行、列索引計算，二維陣列都是適合方形迷宮的資料結構，也適於實現遞迴回溯演算。

如果想實現其他形狀的迷宮，我在先前專欄〈從節點編碼看迷宮〉中，所談過的遮罩迷宮、蜂巢狀迷宮、圓柱迷宮，甚至是基於迷宮的哈密頓路徑等，其實，也都可以基於二維陣列來實現。不過，如果是圓形迷宮呢？

從方形到圓形

如果想做個圓形迷宮，方式之一是透過遮罩，圓範圍外的全部細胞設為已走訪，我們只走訪圓範圍內的細胞，只不過這有點投機取巧。

實際上，圓範圍內的細胞，還是以行列的方式繪製，而我們在這邊想要製作的圓形迷宮，細胞必須是同心圓式的排列，至於這類迷宮又常俗稱為Theta迷宮。

我在〈從節點編碼看迷宮〉中談過，可以基於二維陣列、遞迴回溯演算來走訪細胞，只要在繪圖上做些變化，就能實現蜂巢狀迷宮，那麼，如果我們單純將細胞繪製為同心圓排列，是否就能實現Theta迷宮？

基本上，這是可行的，我們只要將列索引當成環索引，行索引當成逆時針方向索引，以極座標方式繪製。而關於這樣的概念，我們可以在〈Theta 迷宮（一）〉看到具體實現方式。

只不過，若運用這種方式來處理，越外環的迷宮道路會有開口越大的問題，畢竟只是純粹將方形拉成圓形罷了，雖然這也可以是迷宮的一種風格，不過若想避免這個問題，就必須決定在某個環數之後切分細胞，而在這樣的情況下，依舊可以使用遞迴回溯演算，只不過往外環選擇鄰居細胞時，某些環上會是二選一罷了，然而，這意謂著，各環的細胞數可能不同，也就是不再能從m列n行的迷宮來變換，單純採用二維陣列作為細胞的資料結構，顯然行不通了。

這問題長年以來困擾著我，後來想到的方式是改變資料結構，改採一維陣列，此時，陣列中僅加入走訪過的細胞，而細胞的逆時針座標可由最外環的細胞數來決定，座標的步進值則看是位於哪一環，而在計算時，最簡單的作法是每兩環切分一次細胞，若環索引是從0開始，就是在每個偶數環時進行切分。

然而，每兩環切分一次細胞，雖然解決了越外開口越大的問題，卻也造成了越外環細胞越小的問題，而且這可是二的n次方在增長，只要八環左右，細胞就會密到不像話了。

如果想要改善上述的狀況，我們可以試著改為兩環一切、三環一切、四環一切……不過，這在計算上就變得更為複雜了，而且，也只是減緩細胞過快變小的問題罷了，關於實作細節部份，我們可以參考〈Theta 迷宮（二）〉的內容。

鏈結各個細胞

想要更進一步解決這個問題，依圓周長決定將細胞一切為二的時機，顯然會是一個比較好的作法，然而，這就直接面臨了逆時針座標計算上的難度。這不禁讓我重新思考，到底是資料結構選擇的問題？還是遞迴回溯演算的問題？

我在紙上計算著細胞的逆時針座標時，不經意地在細胞間畫了線連起來，突然想到：「如果細胞彼此間採鏈結（link）結構組織呢？」

每個細胞記得自身的（內環）父細胞、順時針、逆時針與（外環）子細胞的話，就不用計算逆時針座標了，直接查詢細胞鏈結的細胞就可以了，而且改變資料結構，依舊可以使用遞迴回溯演算，實作細節部份可以參考〈Theta 迷宮（三）〉的內容。

實際上，依圓周長決定選擇將細胞一切為二的時機，外環細胞還是會變小，只是收斂地很慢，然而，實現時可以留個權重參數，讓使用者能根據需要的迷宮大小，來調整對分的時機，而這就足以應付百環以上的Theta迷宮問題了（只要硬體或執行環境上能支援）。

這時的我才驚覺，長年以來解決不了的問題，是因為採用了不適合的資料結構，又試著強行從中尋找解決方式造成的。

實際上，採用鏈結作為資料結構，也適用於方形迷宮，不過這是需求與設計間平衡的問題，若只是要方形迷宮，二維陣列還是最好的選擇，畢竟只要處理列、行索引加減一的問題，採用鏈結的話，可能還會覺得多此一舉。

然而，如果一開始就是想使用遞迴回溯演算，並用同一個程式作為通用實作，可同時處理方形迷宮與Theta迷宮的問題，那麼，一開始就採用鏈結作為資料結構的實作方式，就會有價值。

演算法+資料結構=程式

其實，在試著從二維陣列改為一維陣列，實作出Theta迷宮時，我第一個想到的，就是Pascal創建者Niklaus E. Writh講過的這句話：「演算法+資料結構=程式（Algorithms+Data Structures=Programs）」。

而在試著更改資料結構為鏈結，實現了依圓周長而切分細胞的程式時，我更是進一步體會到：資料結構選擇的適當與否，真的是一件重要的工作。

原來，我自己一直被資料結構框住了想法，而不自覺。或許我也應該從另一個角度來探索看看，思考一下其他的迷宮演算法，是否對實作Theta迷宮有利呢！