解空間樹在算法設計中的不同形式研究

方宇彤

河北大學計算機科學與技術學院

解空間樹在算法設計中的不同形式研究

方宇彤

河北大學計算機科學與技術學院

本文介紹了解空間樹的概念，解空間樹分為子集樹和排列樹，子集樹又分為二叉樹和多支樹。通過幾個問題介紹了解空間樹在不同算法中的應用，在旅行售貨員等多元問題中，本文提出了解空間樹的另一種可行的結構并對此展開討論。

子集樹；排列樹；回溯法；解空間

1 樹與解空間樹

1.1 樹的概念

樹（Tree）的定義[1]是：n（n≥0）個結點構成的有限集合。最上層節點稱為根節點，除去根節點之外的其余節點可以分為許多互不相交的子集，每一個子集又是一棵樹，稱為根的子集樹。

1.2 解空間樹的概念

1.2.1 解向量：一個問題的解，能夠表示成一個n元式（X1,X2... Xn）的形式，叫做解向量。

1.2.2 解空間：要了解什么是解空間樹，首先要明確什么是解空間。解空間就是一個算法執行后，由解向量組成的集合。即解空間是一個集合。

1.2.3 解空間樹：在確定了可行的、易于搜索的解空間后，將解空間用二叉樹或樹的形式表示，即為問題的解空間樹。

1.2.4 分類

解空間樹[2]可以分為子集樹和排列樹兩種。其中子集樹是如下圖左側，當所給的問題是從n個元素的集合S中找出滿足某種性質的子集時，相應的解空間樹成為子集樹，子集樹通常有2^n個葉結點。如0-1背包問題。

排列樹如下圖右側所示，當所給的問題是確定n個元素滿足某種性質的排列時，相應的解空間樹稱為排列樹。排列樹通常有n!個葉節點。如旅行售貨員問題。

圖1 子集樹和排列樹

2 解空間樹在算法中的應用

2.1 子集樹的應用

2.1.1 二叉樹—01背包問題

問題描述：

物品重量w[]={16，14，25}；物品價值p[]={45，23，37}；背包重量上界為42；求不超過背包可裝重量的最大價值物品組合。

解：其解空間樹如圖1左圖所示，對于每一個節點，它只有兩種狀態：屬于/不屬于物品組合，每一處分叉代表一個物品是否加入組合。A到BC結點表示物品1是否加入書包,B到DE結點表示在物品1裝入的情況下物品2的裝入情況。因此，求解過程可以看作對三個物品進行取舍的過程。共有八種解，分別計算，滿足總重小于c的解，并計算價值和，求出最優解。

2.1.2 多叉樹換錢問題

問題描述：一元錢，可換1角、2角、5角的硬幣，可以有哪些方案？

解：與背包問題類似，本題的w[]={1,2,5}；c=10；最后求解得有10種方案。區別在于每種硬幣可取多次，所以對應的解空間樹是多枝樹，每一個結點分出1、2、5三枝。屬于多元問題。

2.2 排列樹的應用

n后問題：

為了簡便，這里討論4皇后問題，在4*4的棋盤上放置4個皇后，每兩個皇后不能在同一行或同一列或同一斜線。0和1層之間的區域表示第一行的皇后放置在第幾列，后邊同理。

第i行第j列的皇后，安排的下一個位于k行，x[k]列。則要滿足要求有i≠k,j≠x[k],│i-k│≠│j-x[k]│。若下標從0開始，可得出（1，3，0，2）第一行第二列，第二行第四列，第三行第一列，第四行第三列各放一個皇后和（2，0，3，1）兩組解。

3 對新形式解空間樹的思考

3.1 一個節點代表一個元素的解空間樹

通過對許多例題的思考，本文提出了一種解空間樹結構的改變，下面以大家熟知的旅行售貨員問題為例作出解釋。

在傳統的旅行售貨員問題中，有這樣一個邊的帶權圖（圖2），為使走的總路程最短，得出圖3解空間樹。

圖3 解空間樹

圖2 帶權圖

用隊列式（FIFO）分支限界法解此題，以廣度優先的方式搜索解空間樹。每一個活結點一旦成為擴展結點，就一次性產生其所有兒子結點。導致不可行解或非最優解的兒子結點被舍棄，其余兒子結點被加入活結點表中。此后從活結點表中取下一結點成為當前擴展結點，并重復上述擴展過程。得出兩個最優解（1，3，2，4，1）和（1，4，2，3，1）路程都是25。

提出一個大膽的設想，若把這四個地點放在解空間樹的節點處是否可行呢？下面進行驗證。其改進后的解空間樹如圖4。