[發明專利]公交線路搜索方法和裝置

有效

• 申請號: 201410476675.3
• 申請日: 2014-09-17
• 公開（公告）號: CN104268190B
• 公開（公告）日: 2017-03-22
• 發明（設計）人: 李曉濤;左志鵬
• 申請（專利權）人: 騰訊科技（深圳）有限公司
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 廣州華進聯合專利商標代理有限公司44224
• 代理人: 何平,鄧云鵬

1.一種公交線路搜索方法，包括以下步驟：

獲取輸入的起點和終點的位置信息；

搜索所述起點附近預設范圍內停靠的起點公交線路和所述終點預設范圍內停靠的終點公交線路；

判斷所述起點公交線路和所述終點公交線路之間是否有公共線路，若否，以廣度優先原則輪番搜索與所述起點公交線路連通的公交線路以及與所述終點公交線路連通的公交線路，判斷與所述起點公交線路連通的公交線路以及與所述終點公交線路連通的公交線路之間是否有公共線路；

每當與所述起點公交線路連通的公交線路以及與所述終點公交線路連通的公交線路之間有公共線路，則獲取起點公交線路至各條公共線路的最短連通路徑，并獲取終點公交線路至各條公共線路的最短連通路徑；

根據起點公交線路至各條公共線路的最短連通路徑以及終點公交線路至各條公共線路的最短連通路徑，合成從所述起點至所述終點的各條乘坐路徑，每一條乘坐路徑中各條公交線路按照需要的乘坐順序依次排列。

2.根據權利要求1所述的公交線路搜索方法，其特征在于，所述以廣度優先原則輪番搜索與起點公交線路連通的公交線路以及與終點公交線路連通的公交線路，判斷與起點公交線路連通的公交線路以及與終點公交線路連通的公交線路之間是否有公共線路的步驟包括：

以所有所述起點公交線路構成所述起點的首層公交線路，并以所有所述終點公交線路構成所述終點的首層公交線路，以起點的首層公交線路和所述終點的首層公交線路為基礎，輪番逐層擴展與所述起點公交線路連通的公交線路層以及與所述終點公交線路連通的公交線路層，其中，擴展任意一個公交線路層的步驟包括：搜索與上一層公交線路中各公交線路直接連通且不包含在上級公交線路層中的公交線路，以該搜索到的公交線路構成本層公交線路層；

每擴展一個公交線路層，都將與所述起點公交線路連通的最外層公交線路層以及與所述終點公交線路連通的最外層公交線路層進行比較，判斷其中是否有公共線路。

3.根據權利要求2所述的公交線路搜索方法，其特征在于，在搜索與上一層公交線路中各公交線路直接連通且不包含在上級公交線路層中的公交線路時，不搜索與上一層公交線路中的公共線路直接連通的公交線路。

4.根據權利要求2所述的公交線路搜索方法，其特征在于，所述方法還包括：

判斷搜索得到的與所述起點公交線路連通的公交線路層數加上與所述終點公交線路連通的公交線路層數之和是否超過閾值，若是，則停止擴展公交線路層。

5.根據權利要求1所述的公交線路搜索方法，其特征在于，所述方法還包括：

獲取各條乘坐路徑包含的公交線路的公交線路信息，公交線路的公交線路信息包括公交線路所停靠的公交站點的信息；

根據各條乘坐路徑包含的公交線路的排列順序以及公交線路所停靠的公交站點，獲取通過各條乘坐路徑從所述起點至所述終點需要依次換乘的公交站點；

判斷各條乘坐路徑需要依次換乘的公交站點中前一公交站點至后一公交站點的方向是否與對應的公交線路的行駛方向相逆，若是，則過濾相應的乘坐路徑。

6.根據權利要求5所述的公交線路搜索方法，其特征在于，所述方法還包括步驟：

生成地址映射數組，該地址映射數組的元素數量與已存儲的公交線路的數量相等，該地址映射數組中的各個元素用于依次存放按照序列號排序的所述已存儲的公交線路在內存中對應的存儲位置；

所述獲取各條乘坐路徑包含的公交線路的公交線路信息的步驟中，獲取一條公交線路的公交線路信息的步驟包括：

讀取該公交線路的序列號在所述地址映射數組中對應的元素的值，判斷讀取的值是否對應內存中的存儲位置，若否，則從本地存儲中將該公交線路的公交線路信息加載到內存，將該公交線路的公交線路信息在內存中的存儲位置寫入所述地址映射數組中該公交線路的序列號對應的元素中，并從內存中讀取該公交線路的公交線路信息，若是，則從內存中所述元素的值對應的存儲位置讀取該公交線路的公交線路信息。