程式語言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迷宮有利呢!

作者簡介


熱門新聞

Advertisement