狀態(tài)空間搜索策略

三、搜索策略3.1圖搜索策略3.2盲目搜索3.3啟發(fā)式搜索

從問(wèn)題表示到問(wèn)題的解決，有一個(gè)求解的過(guò)程。常見(jiàn)的AI問(wèn)題求解技術(shù)有兩種，即“搜索”（Search）和“推理”（Reasoning）方法。

邏輯推理，是通過(guò)構(gòu)造一個(gè)邏輯系統(tǒng)，由它可以從已有的斷言（公理）推導(dǎo)出新的斷言。并用邏輯形式語(yǔ)言描述的一組公理來(lái)表達(dá)問(wèn)題域。用這種方法來(lái)解決問(wèn)題就是通過(guò)推理來(lái)積聚越來(lái)越多的斷言，直到獲得問(wèn)題的解答。雖然問(wèn)題求解可通過(guò)搜索方法，也可用邏輯推理，但二者的側(cè)重點(diǎn)是不一樣的。前者著重于尋求問(wèn)題解答的過(guò)程，而后者強(qiáng)調(diào)前提（初始）問(wèn)題空間（公理集合）與問(wèn)題解答間連接的邏輯正確性。或者簡(jiǎn)單地講，搜索著重于發(fā)現(xiàn)（Discovery），而推理強(qiáng)調(diào)證明（Proof）。搜索在狀態(tài)圖中尋找目標(biāo)或路徑的基本方法從初始節(jié)點(diǎn)，沿著與之相連的邊，尋找目標(biāo)節(jié)點(diǎn)的過(guò)程搜索樹(shù)搜索過(guò)程中經(jīng)過(guò)的節(jié)點(diǎn)和邊，按照原圖的連接關(guān)系，便形成一個(gè)樹(shù)形的有向圖盲目搜索無(wú)向?qū)阉?窮舉式搜索從初始節(jié)點(diǎn)，沿連接邊逐一考察各個(gè)節(jié)點(diǎn)，或反向進(jìn)行啟發(fā)式(heuristic)搜索利用“啟發(fā)性信息”引導(dǎo)的搜索啟發(fā)式信息是與問(wèn)題有關(guān)的有利于盡快找到問(wèn)題解的信息或知識(shí)3.1

圖搜索策略圖（狀態(tài)圖）搜索控制策略

一種在圖中尋找路徑的方法。

圖中每個(gè)節(jié)點(diǎn)對(duì)應(yīng)一個(gè)狀態(tài)，每條連線(xiàn)對(duì)應(yīng)一個(gè)操作符。這些節(jié)點(diǎn)和連線(xiàn)(即狀態(tài)與操作符)又分別由產(chǎn)生式系統(tǒng)的數(shù)據(jù)庫(kù)和規(guī)則來(lái)標(biāo)記。求得把一個(gè)數(shù)據(jù)庫(kù)變換為另一數(shù)據(jù)庫(kù)的規(guī)則序列問(wèn)題就等價(jià)于求得圖中的一條路徑問(wèn)題。圖組成節(jié)點(diǎn)有向邊圖分類(lèi)或圖（直接圖、狀態(tài)圖）與或圖圖搜索過(guò)程圖圖（狀態(tài)圖）搜索策略CLOSED表：用來(lái)記錄考察過(guò)的節(jié)點(diǎn)對(duì)樹(shù)形搜索，存儲(chǔ)的是搜索樹(shù)對(duì)線(xiàn)式搜索，存儲(chǔ)的是折線(xiàn)OPEN表：記錄待考察的節(jié)點(diǎn)排序方式不同，對(duì)應(yīng)的搜索算法不同節(jié)點(diǎn)父節(jié)點(diǎn)編號(hào)編號(hào)節(jié)點(diǎn)父節(jié)點(diǎn)編號(hào)CLOSED表OPEN表開(kāi)始把S放入OPEN表OPEN表為空表？把第一個(gè)節(jié)點(diǎn)(n)從OPEN表移至CLOSED表n為目標(biāo)節(jié)點(diǎn)嗎？把n的后繼節(jié)點(diǎn)放入OPEN表的末端，提供返回節(jié)點(diǎn)n的指針修改指針?lè)较蛑嘏臤PEN表失敗成功圖3.1

圖搜索過(guò)程框圖是是否否3.2

盲目搜索特點(diǎn)：不需重排OPEN表種類(lèi)：寬度優(yōu)先、深度優(yōu)先、等代價(jià)搜索等。3.2.1

寬度優(yōu)先搜索

定義

以接近起始節(jié)點(diǎn)的程度逐層擴(kuò)展節(jié)點(diǎn)的搜索方法。特點(diǎn)：一種高代價(jià)搜索，但若有解存在，則必能找到它。

算法廣度（寬度）優(yōu)先搜索

(Breadth-firstsearch,BFS)優(yōu)先在同一級(jí)節(jié)點(diǎn)中考察，只有當(dāng)同一級(jí)節(jié)點(diǎn)考察完畢之后，才考察下一級(jí)節(jié)點(diǎn)自頂向下一層一層逐漸生成的寬度優(yōu)先搜搜索算法步1：把初始節(jié)節(jié)點(diǎn)So放入OPEN表中。步2：若OPEN表為空,則搜索失敗敗,退出。步3：取OPEN表中前面第第一個(gè)節(jié)點(diǎn)點(diǎn)N放在CLOSED表中,并冠以順序序編號(hào)n。步4：若目標(biāo)節(jié)節(jié)點(diǎn)Sg=N,則搜索成功功,結(jié)束。步5：若N不可擴(kuò)展,則轉(zhuǎn)步2。步6：擴(kuò)展N,將mj子節(jié)點(diǎn)配上上指向N的指針依次次放入OPEN表尾尾部部,轉(zhuǎn)步步2。注解解：OPEN表是是一一個(gè)個(gè)隊(duì)隊(duì)列列CLOSED表是是一一個(gè)個(gè)順順序序表表，，表表中中各各節(jié)節(jié)點(diǎn)點(diǎn)按按順順序序標(biāo)標(biāo)號(hào)號(hào)，，正正在在被被考考察察的的節(jié)節(jié)點(diǎn)點(diǎn)在在表表中中編編號(hào)號(hào)最最大大如果果問(wèn)問(wèn)題題有有解解，，目目標(biāo)標(biāo)點(diǎn)點(diǎn)Sg必出出現(xiàn)現(xiàn)在在OPEN表中中，，算算法法結(jié)結(jié)束束根據(jù)據(jù)返返回回指指針針，，在在CLOSED表中中回回溯溯，，得得到到求求解解路路徑徑開(kāi)始始把S放入入OPEN表OPEN表為為空空表表？？把第第一一個(gè)個(gè)節(jié)節(jié)點(diǎn)點(diǎn)(n)從OPEN表移移至至CLOSED表是否否有有后后繼繼節(jié)節(jié)點(diǎn)點(diǎn)為目目標(biāo)標(biāo)節(jié)節(jié)點(diǎn)點(diǎn)？？擴(kuò)展展n，把把n的后后繼繼節(jié)節(jié)點(diǎn)點(diǎn)放放入入OPEN表的的末末端端，，提提供供返返回回節(jié)節(jié)點(diǎn)點(diǎn)n的指指針針失敗敗成功功圖3.2寬度度優(yōu)優(yōu)先先算算法法框框圖圖是否是否例子子八數(shù)數(shù)碼碼難難題題（（8-puzzleproblem）1238456712384567（目標(biāo)狀態(tài)）規(guī)定定：：將牌牌移移入入空空格格的的順順序序?yàn)闉椋海簭膹目湛崭窀褡笞筮呥呴_(kāi)開(kāi)始始順順時(shí)時(shí)針針旋旋轉(zhuǎn)轉(zhuǎn)。。不不許許斜斜向向移移動(dòng)動(dòng)，，也也不不返返回回先先輩輩節(jié)節(jié)點(diǎn)點(diǎn)。。從圖圖可可見(jiàn)見(jiàn)，，要要擴(kuò)擴(kuò)展展26個(gè)節(jié)節(jié)點(diǎn)點(diǎn)，，共共生生成成46個(gè)節(jié)節(jié)點(diǎn)點(diǎn)之之后后才才求求得得解解（（目目標(biāo)標(biāo)節(jié)節(jié)點(diǎn)點(diǎn)））。。123845671238412384567412385671238412384567123845671238456767891011121312384567567567112384567123845671238456712384567234513456123845671238456712384567123845671238456723242526271236782212384567123845671238456712384567123845671238456712384567141516171819202112384567圖3.4八數(shù)數(shù)碼碼難難題題的的寬寬度度優(yōu)優(yōu)先先搜搜索索樹(shù)樹(shù)寬度度優(yōu)優(yōu)先先搜搜索索算算法法寬度度優(yōu)優(yōu)先先/橫向向搜搜索索優(yōu)點(diǎn)點(diǎn)策略略是是完完備備的的如果果有有解解，，肯肯定定找找到到解解，，且且找找到到的的解解是是最最優(yōu)優(yōu)解解(最短短路路徑徑)缺點(diǎn)點(diǎn)效率率低低節(jié)點(diǎn)點(diǎn)深深度度：：根節(jié)節(jié)點(diǎn)點(diǎn)深深度度=0其它它節(jié)節(jié)點(diǎn)點(diǎn)深深度度=父節(jié)節(jié)點(diǎn)點(diǎn)深深度度+13.2.2深度度優(yōu)優(yōu)先先搜搜索索3.2.2深度度優(yōu)優(yōu)先先搜搜索索定義義首先先擴(kuò)擴(kuò)展展最最新新產(chǎn)產(chǎn)生生的的(即最最深深的的)節(jié)點(diǎn)點(diǎn)。。算法法防止止搜搜索索過(guò)過(guò)程程沿沿著著無(wú)無(wú)益益的的路路徑徑擴(kuò)擴(kuò)展展下下去去，，往往往往給給出出一一個(gè)個(gè)節(jié)節(jié)點(diǎn)點(diǎn)擴(kuò)擴(kuò)展展的的最最大大深深度度———深度度界界限限。。與寬寬度度優(yōu)優(yōu)先先搜搜索索算算法法最最根根本本的的不不同同在在于于：：將將擴(kuò)擴(kuò)展展的的后后繼繼節(jié)節(jié)點(diǎn)點(diǎn)放放在在OPEN表的的前前端端。。（算算法法框框圖圖見(jiàn)見(jiàn)教教材材））深度度優(yōu)優(yōu)先先搜搜索索（Depth-firstsearch，DFS）在搜搜索索樹(shù)樹(shù)的的每每一一層層始始終終只只擴(kuò)擴(kuò)展展一一個(gè)個(gè)子子結(jié)結(jié)點(diǎn)點(diǎn)，，不不斷斷地地向向縱縱深深前前進(jìn)進(jìn)直到到不不能能再再前前進(jìn)進(jìn)（（到到達(dá)達(dá)葉葉子子結(jié)結(jié)點(diǎn)點(diǎn)或或深深度度限限制制）），，才才從從當(dāng)當(dāng)前前節(jié)節(jié)點(diǎn)點(diǎn)返返回回上上一一級(jí)級(jí)節(jié)節(jié)點(diǎn)點(diǎn)，，沿沿另另一一方方向向又又繼繼續(xù)續(xù)前前進(jìn)進(jìn)從樹(shù)樹(shù)根根開(kāi)開(kāi)始始一一枝枝一一枝枝逐逐漸漸生生成成的的路徑徑節(jié)點(diǎn)點(diǎn)序序列列為為(n0,n1,……,nk)對(duì)于于i=1,……,k，若若節(jié)節(jié)點(diǎn)點(diǎn)ni-1具有有一一個(gè)個(gè)后后繼繼節(jié)節(jié)點(diǎn)點(diǎn)ni，該序序列列稱(chēng)稱(chēng)為為從從n0到nk的路徑徑n0nkn1nk-1n3n2深度度優(yōu)優(yōu)先先搜搜索索算算法法縱向向搜搜索索缺點(diǎn)點(diǎn)如果果一一個(gè)個(gè)有有解解的的問(wèn)問(wèn)題題樹(shù)樹(shù)可可能能有有無(wú)無(wú)窮窮分分支支，，如如果果誤誤入入無(wú)無(wú)窮窮分分支支（（即即深深度度無(wú)無(wú)限限）），，則則不不可可能能找找到到目目標(biāo)標(biāo)節(jié)節(jié)點(diǎn)點(diǎn)策略略不不是是完完備備的的找到到的的解解是是不不一一定定最最優(yōu)優(yōu)解解最最短短路路徑徑)3.2.3等代代價(jià)價(jià)搜搜索索定義義是寬寬度度優(yōu)優(yōu)先先搜搜索索的的一一種種推推廣廣，，不不是是沿沿著著等等長(zhǎng)長(zhǎng)度度路路徑徑斷斷層層進(jìn)進(jìn)行行擴(kuò)擴(kuò)展展，，而而是是沿沿著著等等代代價(jià)價(jià)路路徑徑斷斷層層進(jìn)進(jìn)行行擴(kuò)擴(kuò)展展。。搜索索樹(shù)樹(shù)中中每每條條連連接接弧弧線(xiàn)線(xiàn)上上的的有有關(guān)關(guān)代代價(jià)價(jià),表示示時(shí)時(shí)間間、、距距離離等等花花費(fèi)費(fèi)。。算法法若所所有有連連接接弧弧線(xiàn)線(xiàn)具具有有相相等等代代價(jià)價(jià)，，則則簡(jiǎn)簡(jiǎn)化化為為寬寬度度優(yōu)優(yōu)先先搜搜索索算算法法。。開(kāi)始始把S放入入OPEN表OPEN表為為空空表表？？把具具有有最最小小g(i)值的的節(jié)節(jié)點(diǎn)點(diǎn)i從OPEN表移移至至CLOSED表是否否有有后后繼繼節(jié)節(jié)點(diǎn)點(diǎn)為目目標(biāo)標(biāo)節(jié)節(jié)點(diǎn)點(diǎn)？？失敗敗成功功圖3.2等代代價(jià)價(jià)搜搜索索算算法法框框圖圖是否是否S是否否目目標(biāo)標(biāo)節(jié)節(jié)點(diǎn)點(diǎn)？是成功功擴(kuò)展展i，計(jì)計(jì)算算其其后后繼繼節(jié)節(jié)點(diǎn)點(diǎn)j的g(j)，并并把把后后繼繼節(jié)節(jié)點(diǎn)點(diǎn)放放入入OPEN表否令g(s)=0國(guó)際際象象棋棋對(duì)對(duì)弈弈程程序序:深藍(lán)藍(lán)開(kāi)發(fā)發(fā)者者:IBM的MurryCampbell,Feng-HsiungHsu和JosephHoane采用用30個(gè)IBMRS/6000處理理器器來(lái)來(lái)運(yùn)運(yùn)行行軟軟件件搜搜索索使用用480個(gè)定定制制VLSI國(guó)際際象象棋棋處處理理器器執(zhí)執(zhí)行行生生成成行行棋棋的的功功能能﹑樹(shù)的的最最后后幾幾層層的的”硬件件搜搜索索”以及及對(duì)對(duì)葉葉節(jié)節(jié)點(diǎn)點(diǎn)的的評(píng)評(píng)價(jià)價(jià).每秒秒平平均均搜搜索索12.6億種種走走法法，，峰峰值值時(shí)時(shí)每每秒秒鐘鐘搜搜索索33億個(gè)個(gè)節(jié)節(jié)點(diǎn)點(diǎn).每走走一一步步至至多多能能夠夠預(yù)預(yù)先先計(jì)計(jì)算算300億種種個(gè)個(gè)棋棋局局,常規(guī)規(guī)搜搜索索深深度度是是14步.機(jī)器器的的核核心心算算法法是是使使用用調(diào)調(diào)換換表表的的標(biāo)標(biāo)準(zhǔn)準(zhǔn)迭迭代代深深入入α-β搜索,而且對(duì)關(guān)鍵的的點(diǎn)具備產(chǎn)生生超越搜索深深度的擴(kuò)展能能力,在某些情況下下可以達(dá)到40層的深度.評(píng)價(jià)函數(shù)采用用了超過(guò)8000個(gè)特征;使用一本有4000個(gè)棋局的”開(kāi)局手冊(cè)”以及一個(gè)存有有70萬(wàn)個(gè)大師級(jí)比比賽棋譜的數(shù)數(shù)據(jù)庫(kù);使用一個(gè)大型型殘局?jǐn)?shù)據(jù)庫(kù)庫(kù)保存已解決決的棋局.Video/v_show/id_XMzk1MzQ0ODYw.htmlDeepBlue15years/v_show/id_XMTEyOTU5MjQ0.html卡斯帕羅夫/v_show/id_XMzU4NzY0NzE2.htmlWindows8/v_show/id_XMzE4MzM5OTA0.htmlKinect問(wèn)題的提出窮舉算法可以解決狀態(tài)態(tài)空間很小的的簡(jiǎn)單問(wèn)題大空間無(wú)法勝勝任：組合爆爆炸組合爆炸64階梵塔：節(jié)點(diǎn)：364=0.94*1030理論最短路徑徑：264-1=2*1019博弈一字棋：9！=3.6*105西洋棋：1078國(guó)際象棋：10120（極限并行速度度10-104秒/步，需1016年）圍棋：107613.3啟發(fā)式搜索啟發(fā)性信息按其用途劃分分,啟發(fā)性信息可可分為以下三三類(lèi)：用于擴(kuò)展節(jié)點(diǎn)點(diǎn)的選擇,即用于決定應(yīng)應(yīng)先擴(kuò)展哪一一個(gè)節(jié)點(diǎn),以免盲目擴(kuò)展展。用于生成節(jié)點(diǎn)點(diǎn)的選擇,即用于決定應(yīng)應(yīng)生成哪些后后續(xù)節(jié)點(diǎn),以免盲目地生生成過(guò)多無(wú)用用節(jié)點(diǎn)。用于刪除節(jié)點(diǎn)點(diǎn)的選擇,即用于決定應(yīng)應(yīng)刪除哪些無(wú)無(wú)用節(jié)點(diǎn),以免造成進(jìn)一一步的時(shí)空浪浪費(fèi)。3.3啟發(fā)式搜索特點(diǎn)：重排OPEN表，選擇最有有希望的節(jié)點(diǎn)點(diǎn)加以擴(kuò)展種類(lèi)：有序搜搜索、A*算法等3.3.1啟發(fā)式搜索策策略和估價(jià)函函數(shù)盲目搜索可能能帶來(lái)組合爆爆炸啟發(fā)式信息用用來(lái)來(lái)加速搜索過(guò)過(guò)程的有關(guān)問(wèn)問(wèn)題領(lǐng)域的特特征信息。啟發(fā)函數(shù)啟發(fā)函數(shù)是用用來(lái)估計(jì)搜索索樹(shù)上節(jié)點(diǎn)x與目標(biāo)節(jié)點(diǎn)Sg接近程度的一一種函數(shù),通常記為h(x)定義一個(gè)節(jié)點(diǎn)到目目標(biāo)節(jié)點(diǎn)的某某種距離或差差異的度量一個(gè)節(jié)點(diǎn)處于于最佳路徑上上的概率根據(jù)經(jīng)驗(yàn)的主主觀打分估價(jià)函數(shù)為為獲得某些些節(jié)點(diǎn)“希望”的啟發(fā)信息，，提供一個(gè)評(píng)評(píng)定侯選擴(kuò)展展節(jié)點(diǎn)的方法法，以便確定定哪個(gè)節(jié)點(diǎn)最最有可能在通通向目標(biāo)的最最佳路徑上。。f(n)——表示節(jié)點(diǎn)n的估價(jià)函數(shù)值值應(yīng)用節(jié)點(diǎn)“希望”程度（估價(jià)函函數(shù)值）重排排OPEN表3.3.2有序搜索實(shí)質(zhì)選擇OPEN表上具有最小小f值的節(jié)點(diǎn)作為為下一個(gè)要擴(kuò)擴(kuò)展的節(jié)點(diǎn)。開(kāi)始把S放入OPEN表，計(jì)算估價(jià)價(jià)函數(shù)f(s)OPEN表為空表？選取OPEN表中f值最小的節(jié)點(diǎn)點(diǎn)i放入CLOSED表i為目標(biāo)節(jié)點(diǎn)嗎嗎？擴(kuò)展i，得后繼節(jié)點(diǎn)點(diǎn)j，計(jì)算f(j)，提供返回節(jié)節(jié)點(diǎn)i的指針，利用用f(j)對(duì)OPEN表重新排序，，調(diào)整親子關(guān)關(guān)系及指針失敗成功圖3.9有序搜索算法法框圖是否是否算法例子八數(shù)碼難題（（8-puzzleproblem）12384567（目標(biāo)狀態(tài)）12384567（初始狀態(tài)）八數(shù)碼難題的的有序搜索樹(shù)樹(shù)見(jiàn)下圖：123845671238456712384567（4）（6）（6）123845671238456712384567（6）（5）（5）1238456712384567（5）（7）1238456712384567（6）（7）12384567（5）8132456712384567（5）（7）圖3.10八數(shù)碼難題的的有序搜索樹(shù)樹(shù)123846（4）7啟發(fā)式搜索利用問(wèn)題擁有有的啟發(fā)信息來(lái)引導(dǎo)搜索，，達(dá)到減少搜搜索范圍，降降低問(wèn)題復(fù)雜雜度的目的在保證找到最最佳解的情況況下，盡可能能減少搜索范范圍，提高搜搜索效率啟發(fā)信息強(qiáng)降低搜索工作作量，但可能能導(dǎo)致找不到到最優(yōu)解弱產(chǎn)生式系統(tǒng)在在找到一條路路徑之前將擴(kuò)擴(kuò)展過(guò)多的節(jié)節(jié)點(diǎn)，一般導(dǎo)導(dǎo)致工作量加加大極限情況下盲盲目搜索，但但可能可以找找到最優(yōu)解3.3.3A*算法A*算法評(píng)價(jià)函數(shù)f(n)=g(n)+h(n)n是被評(píng)價(jià)的結(jié)結(jié)點(diǎn)f(n)評(píng)價(jià)函數(shù)從s經(jīng)過(guò)n到g的路徑的耗散散值g(n)代價(jià)函數(shù)從s到n的路徑的耗散散值h(n)啟發(fā)函數(shù)從n到g的路徑的耗散散值3.3.3A*算法估價(jià)函數(shù)的定定義：對(duì)節(jié)點(diǎn)n定義f*(n)=g*(n)+h*(n),表示從S開(kāi)始約束通過(guò)過(guò)節(jié)點(diǎn)n的一條最佳路路徑的代價(jià)。。

希望估價(jià)價(jià)函數(shù)f定義為：f(n)=g(n)+h(n)——g是g*的估計(jì)，h是h*的估計(jì)A*算法的定義：：定義1在GRAPHSEARCH過(guò)程中，如果果第8步的重排OPEN表是依據(jù)f(x)=g(x)+h(x)進(jìn)行的，則稱(chēng)稱(chēng)該過(guò)程為A算法。定義2在A算法中，如果果對(duì)所有的x存在h(x)≤h*(x),則稱(chēng)h(x)為h*(x)的下界，它表表示某種偏于于保守的估計(jì)計(jì)。定義3采用h*(x)的下界h(x)為啟發(fā)函數(shù)的的A算法，稱(chēng)為A*算法。當(dāng)h=0時(shí)，A*算法就變?yōu)橛杏行蛩阉魉惴ǚ?。評(píng)價(jià)函數(shù)的計(jì)計(jì)算g（n）根據(jù)已搜索的的結(jié)果，按照照從初始結(jié)點(diǎn)點(diǎn)s到結(jié)點(diǎn)n的路徑，計(jì)算算其耗散值即即可g(n)對(duì)g*(n)作出估計(jì)，有有g(shù)(n)≥g*(n)h(n)依賴(lài)于啟發(fā)信信息，稱(chēng)為啟發(fā)函數(shù)對(duì)未來(lái)擴(kuò)展的的方向作出估估計(jì)f(n)按f(n)遞增的順序來(lái)來(lái)排列OPEN表的節(jié)點(diǎn)，優(yōu)優(yōu)先擴(kuò)展f(n)值小的節(jié)點(diǎn)，，體現(xiàn)了好的的優(yōu)先搜索思思想3.3.3A*算法八數(shù)碼2831647512384765初始狀態(tài)八數(shù)碼評(píng)價(jià)函數(shù)f(n)=g(n)+h(n)g(n)：從初始節(jié)點(diǎn)點(diǎn)到當(dāng)前節(jié)點(diǎn)點(diǎn)的耗散值h(n)：當(dāng)前節(jié)點(diǎn)““不在位”的的將牌數(shù)2831647512345768h(n)=42831647528314765283164752831647523184765283147652831476528371465832147652318476523184765123847651238476512378465S(4)A(6)B(4)C(6)D(5)E(5)F(6)G(6)H(7)I(5)J(7)K(5)L(5)M(7)124356g=0h=4f=4g=1h=5f=6g=1h=3f=4g=1h=5f=6g=2h=3f=5g=2h=3f=5g=2h=4f=6g=3h=2f=5g=3h=4f=7g=3h=