解題報告程序購房計劃

1、CTSC2002 - Day1 - Problem2購房計劃（House）問題描述Bill 和Scott 是商業(yè)對手。他們都計劃在 Javaville 城市一幢房子，但是他們希望自己的住宅盡量遠離對方的住宅。由于 Javaville 是一座新興的城市，所以暫時還沒有地圖，于是，他們只能從當(dāng)?shù)厝说目谥兴鸭畔ⅲ@些信息包括建筑物的位置和建筑物之間的距離。盡管這些信息并不完整，但是它們都是正確的。Javaville 的街道是一個矩形網(wǎng)格，包含 m 條東西的街道，依次用大寫字母 A,B,C,標(biāo)識，n 條南北的街道，依次用數(shù)字 0,1,2,標(biāo)識。把兩條街道的交點稱為交叉路口，兩個交叉路口之間的一段街道

2、稱為街區(qū)。所有的建筑物都位于交叉路口處，每個交叉路口至多只有一座建筑物。建筑物之間的距離定義為從一座建筑物到另一座建筑物所需經(jīng)過的最少的街區(qū)數(shù)。例如，Bill 和Scott 搜集了以下這些信息：城市中有 5 條東西的街道和 5 條南北的街道；住宅 1 位于交叉路口 A0；郵局位于交叉路口 A4；學(xué)校與住宅 1 距離 4 個街區(qū)；住宅 2 與郵局距離 6 個街區(qū)；學(xué)校與郵局距離 6 個街區(qū)；住宅 3 與郵局距離 6 個街區(qū)；圖 1：h1,h2,h3 = 住宅,p = 郵局s = 學(xué)校根據(jù)以上信息，可以得到Javaville 城市可能的兩種布局。發(fā)現(xiàn)：住宅 1，郵局和學(xué)校的位置都已經(jīng)確定了，而住宅

3、 2 可以位于 C0 或E2，住宅 3 可以位于 C0 或 E2。于是，城市中總是存在兩座住宅相距 6 個街區(qū)（地圖 1 中的h1 與h3，地圖 2 中的h1 與h2）。但是，對于確定的兩座住宅，可以保證的最長距離只有 4 個街區(qū) (h2 與h3 的距離總是 4 個街區(qū))。于是，要告訴 Bill和 Scott，盡管總是存在兩座相距 6 個街區(qū)的住宅，然而最安全的建議是：一人住宅 2，另一人住宅 3。下面給出所求數(shù)值的嚴(yán)格定義：一個可行的城市布局 S 的直徑 d(S)定義為該布局中距離最遠的兩座住宅之間的距離。對于確定的兩座住宅i, j，它們的安全系數(shù)ei, j定義為在所有可行的城市布局中，住宅

4、i, j 之間的距離的最小值。Bill 和Scott 希望你編寫一個程序，根據(jù)他們所搜集到的信息，計算出 D 和E。其中：D =mind(S) ；E =maxei, j。同時你還要給出最安全的購房建議，即所有滿足ei, j=E 的住宅i, j。對于上面的例子，第一種布局的 d(S1)=6，第二種布局的 d(S2)=6。每兩座住宅之間的安全系數(shù)是：e1,2=2，e1,3=2，e2,3=4。于是：D= mind(S1),d(S2)=6，E= maxe1,2,e1,3,e2,3=4，最安全的購房建議是：住宅 2 與住宅 3。輸入文件house.in 第一行包含兩個正整數(shù)m, n（1=m, n=10）

5、，分別表示東西的街道數(shù)目和南北的街道數(shù)目。第二行包含一個整數(shù)，表示所搜集到的信息條數(shù) t(1=t=50)。文件從第三行開始每行描述一條所搜集到的信息，每條信息都是以下兩種形式之一：nameLOCATIONrc或者nameDISTANCEdname2這兩種形式分別描述建筑物的位置和建筑物之間的距離。其中，name 和 name2 是僅包含數(shù)字和小寫字母的字符串，長度不超過 20，表示建筑的名稱。r 是 A 到 J 之間的大寫字母，c 是一個數(shù)字，表示建筑物所位于的交叉路口。d 是一個正整數(shù)，表示兩座建筑物之間的距離。如果建筑物名稱的前五個字符是小寫字母“house”，那么表示這是一座可以的住宅，

6、否則表示一座非民用的建筑物。如果信息是第二種形式，那么其中的name2 一定面的信息中出現(xiàn)過。這組信息中至少包含兩座可以的住宅，至多包含 25 座不同的建筑物。輸出文件 house.out 的第一行包含兩個整數(shù)，分別表示 D 和 E，之間用一個空格隔開。輸出文件從第二行開始給出所有的最安全的購房建議，每個購房建議占一行，購房建議可以以任意的順序排列，但是不能重復(fù)。輸出文件每行末尾不得有多余的空格。輸出文件輸入文件問題分析這道題目的最好方法，也只能在搜索里打轉(zhuǎn)，似乎沒有比搜索更好的算法了。所以說，問題轉(zhuǎn)換為怎樣優(yōu)化搜索過程。首先搜索的框架可以確定如下：將可以確定位置的建筑先安置好，剩下的每個建筑

7、，根據(jù)條件列出他所可能放置的位置，然后選擇一個建筑，窮舉它所有可能位置，再對其他建筑進行安置 對所有的狀態(tài)，依次每兩棟住宅的最短距離，以及最遠的兩幢住宅。也就是最后要求輸出的兩個值。這無疑是一個階乘式的復(fù)雜度，因此，不得不采取優(yōu)化措施。不難發(fā)現(xiàn)，當(dāng)確定了一個建筑以后，剩余建筑的可能位置會大大減少。因此，不難證明，每次窮舉的時候，選擇一個可能放置位置最少的建筑，再進行窮舉，效率會高許多。如果住宅已經(jīng)窮舉完畢，下幾座建筑（非住宅）沒有安放，這時候窮舉這些建筑的所有位置是耗時而無效的。因為，如果這些建筑存在一種以上的布置優(yōu)化 2優(yōu)化 1house.out6 4house2 house3house.i

8、n5 56house1 LOCATION A 0 toffice LOCATION A 4school DISTANCE 4 house1 house2 DISTANCE 6toffice school DISTANCE 6toffice house3 DISTANCE 6toffice 輸入輸出樣例方案，那么顯然所有方案中，住宅的位置都一定，那么就不影響到所需求解的數(shù)據(jù)。因此，如果找到了一個方案之后，遞歸過程就應(yīng)該回溯到最后一幢住宅的位置開始搜索，而不是前一座建筑。不難發(fā)現(xiàn)，優(yōu)化 1 中忽略了放置位置數(shù)相同時的擇優(yōu)方案。然而，有了優(yōu)化 2，這個擇優(yōu)方案就展現(xiàn)在眼前。如果住宅的放置位置數(shù)與其他

9、建筑相同，那么住宅優(yōu)先選取。程序程序中將 N*M 的地圖，從 1.N*M，方便 Hash 操作。(*$APPTYPE Console*) Program House;Uses SysUtils; ConstInf OufMaxNM MaxBuildings= House.in;= House.out;= 10;= 25;TypeTBuildings建筑信息= Array 1.MaxBuildings Of Record建筑名稱Name: String;建筑被安放位置,0表Place,示有待安放可放置位置的數(shù)NumPut :eger;目程序算法設(shè)計優(yōu)化 3CanPut : Array 1.Max

10、NM*MaxNM Ofeger;可放置位置，0 表示可放Dis存放讀入的與其它建筑距離的信息End;: Array 1.MaxBuildings Ofeger;TDistance= Array 1.MaxNM*MaxNM,1.MaxNM*MaxNM Ofeger;任意兩個位置的距離任意位置TNumber= Array 1.MaxNM,1.MaxNM Ofeger;對應(yīng)的一維TSafe= Array 1.MaxBuildings,1.MaxBuildings Ofeger;存放任意兩棟建筑之間可能的最短距離TBelongHouse= Array 1.MaxBuildings Of;BelongH

11、ousei，建筑i 是否為住宅Var平面圖大小，w表示建筑n,m,w:eger;數(shù)目Buildings Distance Number BelongHouse Time1: TBuildings;: TDistance;: TNumber;: TBelongHouse;: Extended;Procedure Init; VarFin i,j,k,l,t Str: Text; eger;: String;:返回 Str 的建筑，如Function Find(Str:String):eger;果第一次出現(xiàn)則Vari Begin:eger;For i:=1 to w DoIf Buildingsi

12、.Name=Str Then Begin Find:=i;Exit; End;Inc(w); Find:=w;Buildingsw.Name:=Str;End; BeginAssign(Fin,Inf); Reset(Fin);Fillchar(Buildings,Sizeof(Buildings),0);Readln(Fin,n,m); w:=0;Readln(F);給平面圖For i:=1 to n DoFor j:=1 to m Do Numberi,j:=(i-1)*m+j;For i:=1 to n DoFor j:=1 to m DoFor k:=1 to n DoFor l:=1

13、 to m Do計算任意兩點距離DistanceNumberi,j,Numberk,l:=abs(i-k)+abs(j-l);For i:=1 to t Do BeginReadln(Fin,Str); j:=Find(Copy(Str,1,( ,Str)-1);Delete(Str,1,( ,Str); 安 放 建 If Copy(Str,1,8)=LOCATION Then Begin筑Delete(Str,1,9); k:=ord(Str1)-ord(A)+1; Delete(Str,1,2); l:=ord(Str1)-ord(0)+1;Buildingsj.Place:=Number

14、k,l; End設(shè)置兩個建筑的距離Else BeginDelete(Str,1,9);Val(Copy(Str,1, Delete(Str,1, l:=Find(Str);( ,Str)-1),k,k); ( ,Str);Buildingsj.Disl:=k;Buildingsl.Disj:=k;End;End;For i:=1 to w Do Buildingsi.NumPut:=n*m;Close(Fin);End;Procedure Put(i:將建筑 i 放置在 Buildingsi.Placeeger);位置上將其它建筑因此無法放置的位置置為Varij,k Begin:eger;Fo

15、r j:=1 to w Do BeginIf Buildingsi.Disj0 Then For k:=1 to N*M DoIf (Buildingsj.CanPutk=0) And距離不滿足條件(DistanceBuildingsi.Place,kBuildingsi.Disj)ThenBeginBuildingsj.CanPutk:=i; Dec(Buildingsj.NumPut);End;If Buildingsj.CanPutBuildingsi.Place=0 Then Begin 該位置被第 i個建筑占用Buildingsj.CanPutBuildingsi.Place:=i;

16、 Dec(Buildingsj.NumPut);End;End;End;Procedure UnPut(i: 取 消 建 筑i放 置 在eger);Buildingsi.Place 位置將其它建筑在 Put 中置為 i 的全部恢Var復(fù)j,k Begin:eger;For j:=1 to w Do BeginIf Buildingsi.Disj0 Then For k:=1 to N*M Do距離不滿足的If Buildingsj.CanPutk=i Then Begin Buildingsj.CanPutk:=0; Inc(Buildingsj.NumPut);End;If Building

17、sj.CanPutBuildingsi.Place=i Then Begin 該位置被第i個建筑占用Buildingsj.CanPutBuildingsi.Place:=0; Inc(Buildingsj.NumPut);End;End;End;Procedure FindHouse;Vari Begin生成BelongHouse 數(shù)組:eger;For i:=1 to w DoIf Copy(Buildingsi.Name,1,5)=house Then BelongHousei:=TrueElse BelongHousei:=False;End; Procedure VarFou i,j,

18、Longest, MaxSafet;: Text;存放每種可能布局直徑的最小值:eger;存放任意兩棟建筑之間可: TSafe;能的最短距離優(yōu)化 2，到退回最近一座Back:;住宅時用嘗試安置第o 個建筑Procedure Tryit(o:Vari,j,Max Begineger);:eger;產(chǎn)生了一種布局If o=w+1 Then Begin地圖直徑f BelongHousei Thenf BelongHousej Then任意兩座房子Max:=0;For i:=1 to w-1For j:=i+1 to wBeginIf DistanceBuildingsi.Place,Building

19、sj.PlaceMaxThenMax:=DistanceBuildingsi.Place,Buildingsj.Place;If DistanceBuildingsi.Place,Buildingsj.PlaceSafei,j ThenSafei,j:=DistanceBuildingsi.Place,Buildingsj.Place; 更新它們的 Safe 屬性以及End;Max更新直徑的最小If MaxLongest Then Longest:=Max;值Back:=True; Exit;End;找到一個可放置位置數(shù)最小的建i:=0;筑iFor j:=1 to w DoIf (Buildi

20、ngsj.Place=0) And (i=0) Or(Buildingsj.NumPutBuildingsi.NumPut) Or(Buildingsj.NumPut=Buildingsi.NumPut) And BelongHousej)Then Begini:=j;If Buildingsi.NumPut=1 Then Break;End;窮舉所放置的位置For j:=1 to n*m DoIf Buildingsi.CanPutj=0 Then Begin Buildingsi.Place:=j;Put(i);放入j下一層遞歸Tryit(o+1);取消放入UnPut(i);Buildin

21、gsi.Place:=0;如果已經(jīng)到If BelongHousei Then Back:=False;一幢住宅如果還沒到住宅，接If Back Then Exit;著End;End; BeginAssign(Fou,Ouf); Rewrite(Fou);Longest:=high(Longest); Fillchar(Safe,Sizeof(Safe),$7F);j:=0;For i:=1 to w Do給定位置的建筑預(yù)先放置If Buildingsi.Place0 Then Begin Put(i);Inc(j); End;Back:=False; Tryit(j+1);Max:=0;For i:=1 to w-1 DoIf BelongHousei Then For j:=i+1 to w DoIf BelongHousej Then求出問題所求的EIf Safei,jMax Then Max:=S