謝繼文，徐 濤，姜錫珂，李建伏

（1.中國民航大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，天津300300；2.中國民航大學(xué) 中國民航信息技術(shù)科研基地，天津300300；3.民航重慶空管分局 技術(shù)保障部，重慶400000）

0 引 言

國際航線運(yùn)價(jià)搜索［1］要解決的問題是在客戶容忍的時(shí)間內(nèi)，在時(shí)間和費(fèi)用等條件約束下，尋找出K 條 “最短路徑”，本質(zhì)上是一個(gè)擴(kuò)展的K 條多約束最短路徑 （extended K multiple constrained shortest path，EKMCSP）問 題［2］。EKMC－SP問題是在普通K 條多約束最短路徑 （K multiple constrained shortest path，KMCSP）問題的基礎(chǔ)上，將單弧圖模型擴(kuò)展為多弧圖模型后形成［3］。長(zhǎng)期以來，普通KMCSP問題 （屬NP難問題）受到了廣泛的關(guān)注和大量的研究，如互聯(lián)網(wǎng)中保證服務(wù)質(zhì)量的QoS路由問題是最基本的多約束條件下求K 條最短路徑問題［4］。求解普通KMCSP問題的算法種類繁多，例如IDA＊ ＿M(jìn)CSP 算法［5］、SAMCRA 算法［6］、隨 機(jī) 化 算 法［7］和H ＿M(jìn)CSP 算 法［8］等，這些算法僅能用來解決K＝1的情形。文獻(xiàn) ［9］提出的以A＊算法為基礎(chǔ)的A＊Prune算法，致力于尋找K 條最短路徑 （K＝1，2，3…），該算法采用Dijkstra算法做輔助計(jì)算，通過不斷搜索和剪枝，直到找出滿足約束的K 條路徑或完成所有路徑搜索為止。

針對(duì)國際航線運(yùn)價(jià)搜索中龐大的搜索規(guī)模和復(fù)雜的圖模型等問題，本文建立了國際航線運(yùn)價(jià)搜索問題的EKMCSP模型并提出了相應(yīng)的A＊Level算法。該算法結(jié)合國際航線運(yùn)價(jià)搜索問題的特點(diǎn)，采用啟發(fā)式函數(shù)思想和大量剪枝策略來大規(guī)模減小搜索空間和提高運(yùn)算效率。

1 國際航線運(yùn)價(jià)搜索模型

國際航線運(yùn)價(jià)搜索的目的是尋找最能滿足用戶需求的旅行路徑，搜索范圍為整個(gè)航線網(wǎng)絡(luò)中所有航班，主要約束條件有時(shí)間和運(yùn)價(jià)等［10］。運(yùn)價(jià)FARE 定義為兩個(gè)城市之間不論有多少航班參與情況下的單程旅行最終花費(fèi)，其中

式中：b——起飛城市到目的城市之間的航班數(shù)量，xi、fi——第i個(gè)航班的飛行時(shí)間及票價(jià)，gq、zq——第q次中轉(zhuǎn)的停留時(shí)間及金錢花費(fèi)。FARE 是所求K 條最短路徑排序的依據(jù)，當(dāng)以時(shí)間花費(fèi)為排序的主要依據(jù)時(shí)，令"＝1，#＝0，$＝1，%＝0；以金錢花費(fèi)為排序的主要依據(jù)時(shí)，令"＝0，#＝1，$＝0，%＝1。

國際航線運(yùn)價(jià)搜索的EKMCSP問題與KMCSP問題的差異主要體現(xiàn)在：

（1）圖模型不同。KMCSP問題的圖模型中節(jié)點(diǎn)之間僅有一條單向或雙向弧；而在國際航線運(yùn)價(jià)搜索的EKMCSP問題的圖模型中，節(jié)點(diǎn)之間可以有多條弧，且弧上權(quán)值復(fù)雜，包括票價(jià)，起降時(shí)間和航班號(hào)等。

（2）輔助算法不同。求解KMCSP 問題的H ＿M(jìn)CSP算法和A＊Prune算法等均采用Dijkstra算法進(jìn)行輔助運(yùn)算；而國際航線運(yùn)價(jià)搜索的EKMCSP問題因其復(fù)雜的圖模型無法使用Dijkstra算法進(jìn)行輔助運(yùn)算。

（3）搜索方式不同。KMCSP問題中，可以進(jìn)行無序或有序搜索；而在國際航線運(yùn)價(jià)搜索中，無論是以最低票價(jià)還是以最短旅行時(shí)間為目標(biāo)，旅客轉(zhuǎn)機(jī)次數(shù)均是有限的，因此國際航線運(yùn)價(jià)搜索的EKMCSP問題更適合于有限的層次搜索。

1.1 EKMCSP問題的一般描述

令GRA ＝（VR，EG，LI）為一網(wǎng)絡(luò)圖，其中VR 為節(jié)點(diǎn)集，VR ＝｛vi｜1≤i≤n｝，n為節(jié)點(diǎn)數(shù)目；EG 為邊集，記eh（vi，vj）為節(jié)點(diǎn)vi與vj之間的第h條邊，EG ＝｛eijh｜eijh＝eh（vi，vj），vi，vj∈VR｝；LI 為 所 有 邊 的 權(quán) 值 集 合，記l（eijh）為邊eijh的權(quán)值，LI＝｛lijh｜lijh＝l（eijh），eijh∈EG｝。假設(shè)有起始節(jié)點(diǎn)s，目標(biāo)節(jié)點(diǎn)t和約束集CON ＝｛CONi｜i＝1，2，…，R｝，記p（s，t）為s到t的某條可達(dá)路徑所經(jīng)邊的集合，Y（p（s，t））為p（s，t）在約束CON 下的花費(fèi)，其中

EKMCSP問題即從起始節(jié)點(diǎn)s到目標(biāo)節(jié)點(diǎn)t的所有可達(dá)路徑中找出K 條最短路徑p（s，t）。

1.2 國際航線運(yùn)價(jià)搜索的EKMCSP模型

國際航線運(yùn)價(jià)搜索問題的EKMCSP模型可以直觀地反映航線網(wǎng)絡(luò)的特點(diǎn)。圖1是一個(gè)簡(jiǎn)單航線網(wǎng)絡(luò)的EKMCSP模型圖示例，其中A、B、C、D、E、F 代表6個(gè)城市，節(jié)點(diǎn)間的每條弧代表執(zhí)行該航段的一個(gè)航班。記MCT ＿TIME為中轉(zhuǎn)過程中降落航班和起飛航班之間的最小連接時(shí)間，BCT＿TIME 表示中轉(zhuǎn)過程中降落航班和起飛航班之間所允許的最大連接時(shí)間，TR 表示可容忍的最大花費(fèi)，約束條件通常包括：①抵達(dá)航班的降落時(shí)間與換乘航班的起飛時(shí)間之差要大于MCT＿TIME，且小于BCT＿TIME；②已搜索路徑的花費(fèi)和小于TR；③轉(zhuǎn)機(jī)次數(shù)。

針對(duì)起始節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的可達(dá)路徑搜索以樹形層次順序進(jìn)行。在圖1 中，設(shè)起始節(jié)點(diǎn)為C，目標(biāo)節(jié)點(diǎn)為B，MCT＿TIME為30分鐘，BCT＿TIME 為120分鐘，轉(zhuǎn)機(jī)次數(shù)不超過3次，以C到B的直達(dá)航班最高票價(jià)作為TR。若任意節(jié)點(diǎn)u和d之間存在多弧的情況，則將邊eh（u，d）依次記為udh（h＝1，2，…）。于是，從C 到B 的可達(dá)路徑有｛CB1｝，｛CA1，AB1｝，｛CA2，AB1｝，｛CF1，F(xiàn)D1，DB1｝，｛CF2，F(xiàn)D2，DE1，EB2｝等。其中｛CA2，AB1｝不滿足約束條件①，｛CF1，F(xiàn)D1，DB1｝不 滿 足 約 束 條 件②，｛CF2，F(xiàn)D2，DE1，EB2｝不滿足約束條件③。因此在該模型下，運(yùn)價(jià)搜索的結(jié)果按照金錢花費(fèi)多少排序?yàn)椋鸆A1，AB1｝，｛CB1｝。

2 基于EKMCSP模型的搜索算法

國際航線運(yùn)價(jià)搜索的EKMCSP模型中，節(jié)點(diǎn)之間存在一條或多條弧，而KMCSP 算法只能解決節(jié)點(diǎn)間單弧連接的模型，如A＊Prune算法和約束剪枝算法［11］等。為此針對(duì)國際航線運(yùn)價(jià)搜索問題的EKMCSP模型，以A＊算法為基礎(chǔ)，借鑒A＊Prune算法的路徑搜索方式，從初始節(jié)點(diǎn)開始搜索，在擴(kuò)展下一個(gè)節(jié)點(diǎn)時(shí)，不再使用Dijkstra算法進(jìn)行輔助運(yùn)算，而是采用路徑價(jià)值評(píng)估函數(shù)的運(yùn)算結(jié)果作為啟發(fā)信息。根據(jù)這些信息對(duì)存儲(chǔ)的路徑集按價(jià)值高低進(jìn)行排序，優(yōu)先擴(kuò)展價(jià)值較高的路徑。并且在搜索過程中加入有限層搜索的思想，通過不斷的擴(kuò)展，將生成的新的路徑存儲(chǔ)在價(jià)值優(yōu)先隊(duì)列中，利用時(shí)間和費(fèi)用等方面的約束條件對(duì)搜索空間進(jìn)行剪枝，從而形成多約束條件下有限層搜索的A＊算法，簡(jiǎn)稱A＊Level算法。

圖1 某航線網(wǎng)絡(luò)的EKMCSP模型

2.1 關(guān)鍵步驟

2.1.1 數(shù)據(jù)預(yù)處理

對(duì)航班屬性等相關(guān)數(shù)據(jù)進(jìn)行整理并建立相應(yīng)的數(shù)據(jù)結(jié)構(gòu)。該數(shù)據(jù)結(jié)構(gòu)以offairport（起飛機(jī)場(chǎng)）為主要標(biāo)識(shí)建立數(shù)據(jù)塊，數(shù)據(jù)塊中包含offairport（起飛機(jī)場(chǎng)），offcity （起飛城市），inairport（降落機(jī)場(chǎng)），incity （降落城市），offtime（起飛時(shí)間），intime （降落時(shí)間），cost（運(yùn)價(jià)），dep＿longi（起飛機(jī)場(chǎng)經(jīng)度），dep＿lati（起飛機(jī)場(chǎng)緯度），arr＿longi（降落機(jī)場(chǎng)經(jīng)度），arr＿lati（降落機(jī)場(chǎng)緯度），ct（航班 所 屬 國 家），fltno （航 班 號(hào)），onlynumber （唯 一 標(biāo)識(shí)）等信息。所有數(shù)據(jù)塊以鄰接鏈表形式存儲(chǔ)，并輔助以onlynumber進(jìn)行定位。

以圖1中的某航線網(wǎng)絡(luò)為例，所形成的數(shù)據(jù)結(jié)構(gòu)如圖2所示。

圖2 數(shù)據(jù)結(jié)構(gòu)

2.1.2 路徑價(jià)值評(píng)估函數(shù)

記任意節(jié)點(diǎn)u的地理坐標(biāo)為（ulongi，ulati），其中ulongi和ulati分別代表節(jié)點(diǎn)u的經(jīng)度和緯度。

設(shè)任意節(jié)點(diǎn)u和d之間的距離為DISud，則

設(shè)起始節(jié)點(diǎn)s到目標(biāo)節(jié)點(diǎn)t經(jīng)過節(jié)點(diǎn)w，SW（p（s，w））為p（s，w）的路徑和，則

設(shè)路徑p（s，w）的價(jià)值為VAL（p（s，w）），則

路徑價(jià)值評(píng)估函數(shù)中，綜合考慮了機(jī)場(chǎng)地理坐標(biāo)信息和運(yùn)價(jià)花費(fèi)等因素，VAL（p（s，w））的值越小，則表示路徑p（s，w）的價(jià)值越高。

2.2 算法描述

A＊Level算法的輸入有起飛機(jī)場(chǎng)、目的機(jī)場(chǎng)、起飛時(shí)間和搜索層次等。輸出為起飛機(jī)場(chǎng)到目的機(jī)場(chǎng)的K 條可達(dá)路徑。A＊Level算法的完整描述如下：

步驟1 數(shù)據(jù)預(yù)處理。對(duì)航班數(shù)據(jù)進(jìn)行整理，并存入特定的數(shù)據(jù)結(jié)構(gòu)中。

步驟2 初始化。設(shè)已找到的路徑數(shù)k＝0，并確定TR的值。如果起始節(jié)點(diǎn)s和目標(biāo)節(jié)點(diǎn)t之間有直達(dá)航班，則以該航班的最高運(yùn)價(jià)為TR；否則從起始節(jié)點(diǎn)s開始做兩層搜索，在形成的所有路徑中以花費(fèi)最多的路徑的運(yùn)價(jià)為TR。從起始節(jié)點(diǎn)s開始做一次擴(kuò)展，形成的所有滿足約束的路徑放入隊(duì)列AL＿QUEUE中。

步驟3 隊(duì)列排序。對(duì)AL＿QUEUE 中所有路徑按其價(jià)值從大到小排序。

步驟4 路徑擴(kuò)展。AL＿QUEUE 隊(duì)首的路徑出隊(duì)，設(shè)該路徑的尾節(jié)點(diǎn)為lnode，擴(kuò)展節(jié)點(diǎn)lnode的后繼節(jié)點(diǎn)生成若干條新的路徑。

步驟5 剪枝。遍歷擴(kuò)展生成的所有新的路徑，對(duì)產(chǎn)生回路或者不滿足約束條件①、②的路徑進(jìn)行剪枝。

步驟6 有限層搜索。只在有限層進(jìn)行路徑擴(kuò)展，超過限定的層次則進(jìn)行剪枝。

步驟7 判斷。如果路徑的尾節(jié)點(diǎn)即為目標(biāo)節(jié)點(diǎn)，則k＝k＋1。

步驟8 擴(kuò)充路徑隊(duì)列。將擴(kuò)展后沒有產(chǎn)生回路，且滿足約束條件①、②、③的路徑加入隊(duì)列AL＿QUEUE。

步驟9 重復(fù)步驟3～步驟8，直到k＝K （目標(biāo)最短路徑數(shù)）或隊(duì)列AL＿QUEUE為空。

3 實(shí)驗(yàn)結(jié)果及分析

實(shí)驗(yàn)所采用數(shù)據(jù)集包含網(wǎng)上采集及其它途徑獲得的航班數(shù)據(jù)，共有12716個(gè)國際航班的相關(guān)數(shù)據(jù)。每條航班數(shù)據(jù)包含offairport，offcity，inairport，incity，offtime，intime，cost，dep＿longi，dep＿lati，arr＿longi，arr＿lati，ct，fltno，onlynumber等字段。設(shè)MCT＿TIME 為30 分鐘，BCT＿TIME 為180 分鐘。實(shí)驗(yàn)機(jī)器配置：Intel

CoreTM2Duo CPU E4600 2.40GHz，內(nèi)存2.00GB，操作系統(tǒng)：Microsoft Windows XP Professional 2002Service Pack 3，數(shù)據(jù)庫：Oracle 9i，編程：Java＋Myelipse＋struts。為驗(yàn)證基于EKMCSP 模型的A＊Level算法的性能，共設(shè)計(jì)了3個(gè)實(shí)驗(yàn)來進(jìn)行驗(yàn)證。

實(shí)驗(yàn)一：設(shè)查詢得到的路徑數(shù)為K 且為K 條最短路徑，或得到的路徑數(shù)小于K 且均為最短路徑，則查詢成功；否則查詢失敗。多組實(shí)驗(yàn)的綜合正確率ACC 為

式中：a——進(jìn)行實(shí)驗(yàn)的組數(shù)，mi（1≤i≤a）表示第i組實(shí)驗(yàn)進(jìn)行的實(shí)驗(yàn)次數(shù)，ci——第i組實(shí)驗(yàn)中搜索結(jié)果正確的次數(shù)。對(duì)12716條航班數(shù)據(jù)進(jìn)行處理，如果城市間存在多個(gè)航班，則只保留一個(gè)航班，即將節(jié)點(diǎn)間多弧連接的國際航線運(yùn)價(jià)搜索的EKMCSP 模型簡(jiǎn)化為節(jié)點(diǎn)間單弧連接的KMCSP模型。分別對(duì)A＊Level算法和約束剪枝算法進(jìn)行5組實(shí)驗(yàn)，其中每組實(shí)驗(yàn)5次，每次輸入不同的起飛機(jī)場(chǎng)，目的機(jī)場(chǎng)，起飛時(shí)間和票價(jià)類型等。通過實(shí)驗(yàn)后發(fā)現(xiàn)，整體上A＊Level算法搜索的正確率和時(shí)間效率均高于約束剪枝算法。圖3和表1給出了進(jìn)行5組實(shí)驗(yàn)的搜索結(jié)果。

圖3 約束剪枝算法和A＊Level算法的耗時(shí)對(duì)比

表1 約束剪枝算法和A＊Level算法的效果對(duì)比

實(shí)驗(yàn)二：實(shí)驗(yàn)處理的數(shù)據(jù)對(duì)象為12716 個(gè)國際航班的相關(guān)數(shù)據(jù)，如果城市間存在多個(gè)航班，則保留多個(gè)航班，即保持節(jié)點(diǎn)間多弧連接的國際航線運(yùn)價(jià)搜索的EKMCSP模型。實(shí)驗(yàn)輸入為：PEK （北京，出發(fā)城市），CDG （巴黎，目的城市），2011－01－08 （出發(fā)日期），成人 （購票類型）。分別設(shè)置4，5和6這3種搜索層次，進(jìn)行3次實(shí)驗(yàn)。通過實(shí)驗(yàn)后發(fā)現(xiàn)，對(duì)傳統(tǒng)KMCSP 算法無能為力的國際航線運(yùn)價(jià)搜索的EKMCSP 問題，A＊Level算法可以得到比較滿意的結(jié)果。在600ms以內(nèi)，輸出與搜索層次相對(duì)應(yīng)的最短路徑集，以及每條最短路徑相應(yīng)的總時(shí)間花費(fèi)和總金錢花費(fèi) （見表2）。

表2 A＊Level算法的輸出結(jié)果

實(shí)驗(yàn)三：實(shí)驗(yàn)處理的數(shù)據(jù)對(duì)象為12716 個(gè)國際航班的相關(guān)數(shù)據(jù)，如果城市間存在多個(gè)航班，則保留多個(gè)航班，即保持節(jié)點(diǎn)間多弧連接的國際航線運(yùn)價(jià)搜索的EKMCSP模型。表3給出了進(jìn)行3組實(shí)驗(yàn)的搜索結(jié)果，其中每組實(shí)驗(yàn)10次，每次輸入不同的起飛機(jī)場(chǎng)，目的機(jī)場(chǎng)，起飛時(shí)間和票價(jià)類型等。

表3 A＊Level算法的正確率驗(yàn)證

根據(jù)式 （4），可得本次實(shí)驗(yàn)的綜合正確率為93.3%。由此可得，A＊Level算法具有較高的正確率。通過3組實(shí)驗(yàn)，證明了A＊Level算法既可以處理節(jié)點(diǎn)間存在單弧的模型，也可以處理節(jié)點(diǎn)間存在多弧的模型，并具有較優(yōu)的正確率和時(shí)間效率。

4 結(jié)束語

目前，國內(nèi)外對(duì)于普通KMCSP問題的應(yīng)用研究很多，但是針對(duì)國際航線運(yùn)價(jià)搜索的EKMCSP問題研究尚少?；贓KMCSP模型的A＊Level算法首先在搜索前進(jìn)行數(shù)據(jù)預(yù)處理，利用時(shí)間、費(fèi)用等約束條件對(duì)搜索空間進(jìn)行剪枝，并根據(jù)民航運(yùn)輸?shù)奶攸c(diǎn)，采用了有限層搜索的思想。另外，結(jié)合機(jī)場(chǎng)地理坐標(biāo)信息和運(yùn)價(jià)花費(fèi)等因素設(shè)計(jì)了路徑價(jià)值評(píng)估函數(shù)，以此提高搜索效率。經(jīng)過驗(yàn)證，A＊Level算法可以實(shí)現(xiàn)國際航線運(yùn)價(jià)搜索的EKMCSP 問題的快速求解，搜索正確率也較高?，F(xiàn)實(shí)中的全球航線網(wǎng)絡(luò)異常復(fù)雜，航班數(shù)量增加迅速，隨之產(chǎn)生的搜索規(guī)模也異常龐大。如何設(shè)計(jì)更加科學(xué)合理的約束條件和更高效率的路徑價(jià)值評(píng)估函數(shù)是下一步研究的重點(diǎn)。

［1］HU Xin，XU Tao，DING Xiaolu，et al.Improvement and simulation of K－shortest－paths algorithm in international flight route network ［J］.Journal of Computer Applications，2014，34 （4）：1192－1195 （in Chinese）. ［胡 欣，徐 濤，丁 曉 璐，等.國際航線網(wǎng)絡(luò)中K 條最短路徑算法改進(jìn)與仿真 ［J］.計(jì)算機(jī)應(yīng)用，2014，34 （4）：1192－1195.］

［2］WANG Zhijian，HAN Weiyi，LI Yijun.Shortest path problem with multiple shortest paths［J］.Journal of Harbin Institute of Technology，2010，42 （9）：1428－1431 （in Chinese）.［王志堅(jiān)，韓偉一，李一軍.具有多條最短路徑的最短路問題［J］.哈爾濱工業(yè)大學(xué)學(xué)報(bào)，2010，42 （9）：1428－1431.］

［3］WANG Haimei，ZHOU Xianzhong.Improved shortest path algorithm for restricted searching area［J］.Journal of Nanjing University of Science and Technology （Natural Science），2009，33 （5）：638－642 （in Chinese）.［王海梅，周獻(xiàn)中.一種限制搜索區(qū)域的最短路徑改進(jìn)算法 ［J］.南京理工大學(xué)學(xué)報(bào)（自然科學(xué)版），2009，33 （5）：638－642.］

［4］WAN Zhiping，LV Zhimin.A kind of adaptive species optimization of wireless Mesh network Qos routing algorithm ［J］.Journal of Shandong University（Natural Science），2013，48（9）：10－16 （in Chinese）. ［萬智萍，呂志民.一種自適應(yīng)物種尋優(yōu)的無線Mesh網(wǎng)絡(luò)Qos路由算法 ［J］.山東大學(xué)學(xué)報(bào)（理學(xué)版），2013，48 （9）：10－16.］

［5］MA Yueyong，WANG Haimei，LIAO Jianjun.Comparative study of multi－constrained optimal path algorithms ［J］.Journal of Nanjing University of Science and Technology，2011，35（6）：749－754 （in Chinese）. ［馬躍勇，王海梅，廖建軍.多約束最優(yōu)路徑算法比較研究 ［J］.南京理工大學(xué)學(xué)報(bào)，2011，35 （6）：749－754.］

［6］Zhang Z，Zhao J.Multi－constraint－pru－ning：An algorithm for finding K shortest paths subject to multiple constraints［C］／／Proceedings of APCC，2008：1－5.

［7］ZOU Yonggui，WEI Lai.Optimal path algorithm with multconstrained condition ［J］.Computer Applications，2008，28（5）：1101－1104 （in Chinese）.［鄒永貴，魏來.帶多約束條件的最優(yōu)路徑選擇算法研究 ［J］.計(jì)算機(jī)應(yīng)用，2008，28 （5）：1101－1104.］

［8］NING S.K constrained shortest path problem ［J］.IEEE Transactions on Automation Science and Engineering，2010，7（1）：15－23.

［9］IIT S V，PANDIT A K.A＊prune modified algorithm in video compression ［J］.Ubiquitous Computing and Communication Journal，2008，3 （5）：49－52.

［10］XU Tao，DING Xiaolu，LI Jianfu.Review on K shortest paths algorithms ［J］.Computer Engineering and Design，2013，34 （11）：3900－3906 （in Chinese）. ［徐濤，丁曉璐，李建伏.K 最短路徑算法綜述 ［J］.計(jì)算機(jī)工程與設(shè)計(jì)，2013，34 （11）：3900－3906.］

［11］XU Tao，DING Xiaolu，LI Jianfu.K－multiple constrained shortest paths problem for connecting path search in international flight path network ［J］.Journal of Southwest Jiaotong University，2014，49 （1）：153－159（in Chinese）. ［徐濤，丁曉璐，李建伏.國際航線網(wǎng)絡(luò)聯(lián)程路徑搜索的KMCSP問題研究 ［J］.西南交通大學(xué)學(xué)報(bào)，2014，49 （1）：153－159.］