解空間樹在算法設(shè)計(jì)中的不同形式研究

方宇彤

河北大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院

解空間樹在算法設(shè)計(jì)中的不同形式研究

方宇彤

河北大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院

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

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

1 樹與解空間樹

1.1 樹的概念

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

1.2 解空間樹的概念

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

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

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

1.2.4 分類

解空間樹[2]可以分為子集樹和排列樹兩種。其中子集樹是如下圖左側(cè)，當(dāng)所給的問題是從n個(gè)元素的集合S中找出滿足某種性質(zhì)的子集時(shí)，相應(yīng)的解空間樹成為子集樹，子集樹通常有2^n個(gè)葉結(jié)點(diǎn)。如0-1背包問題。

排列樹如下圖右側(cè)所示，當(dāng)所給的問題是確定n個(gè)元素滿足某種性質(zhì)的排列時(shí)，相應(yīng)的解空間樹稱為排列樹。排列樹通常有n!個(gè)葉節(jié)點(diǎn)。如旅行售貨員問題。

圖1 子集樹和排列樹

2 解空間樹在算法中的應(yīng)用

2.1 子集樹的應(yīng)用

2.1.1 二叉樹—01背包問題

問題描述：

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

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

2.1.2 多叉樹換錢問題

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

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

2.2 排列樹的應(yīng)用

n后問題：

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

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

3 對(duì)新形式解空間樹的思考

3.1 一個(gè)節(jié)點(diǎn)代表一個(gè)元素的解空間樹

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

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

圖3 解空間樹

圖2 帶權(quán)圖

用隊(duì)列式（FIFO）分支限界法解此題，以廣度優(yōu)先的方式搜索解空間樹。每一個(gè)活結(jié)點(diǎn)一旦成為擴(kuò)展結(jié)點(diǎn)，就一次性產(chǎn)生其所有兒子結(jié)點(diǎn)。導(dǎo)致不可行解或非最優(yōu)解的兒子結(jié)點(diǎn)被舍棄，其余兒子結(jié)點(diǎn)被加入活結(jié)點(diǎn)表中。此后從活結(jié)點(diǎn)表中取下一結(jié)點(diǎn)成為當(dāng)前擴(kuò)展結(jié)點(diǎn)，并重復(fù)上述擴(kuò)展過程。得出兩個(gè)最優(yōu)解（1，3，2，4，1）和（1，4，2，3，1）路程都是25。

提出一個(gè)大膽的設(shè)想，若把這四個(gè)地點(diǎn)放在解空間樹的節(jié)點(diǎn)處是否可行呢？下面進(jìn)行驗(yàn)證。其改進(jìn)后的解空間樹如圖4。