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

有效

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

技術領域

本發明涉及計算機技術領域，特別是涉及一種公交線路搜索方法。

背景技術

獲取用戶輸入的起點和終點、提供從起點至終點的公交乘坐方案的公交查詢服務是互聯網上人們經常使用的一項服務。

一個城市的公交線路往往是錯綜復雜的，而用戶輸入的起點和終點附近可能都有多個公交站點(分別記為起點公交站點和終點公交站點)，而且每一個起點公交站點內可能停靠多條公交線路(記為起點公交線路)，每一個終點公交站點內也可能停靠多條公交線路(記為終點公交線路)；比較復雜的是，起點公交線路和終點公交線路可能不包括相同的公交線路，從而需要查詢搭乘哪一趟起點公交線路并換乘哪一趟終點公交線路從而從起點抵達終點；更為復雜的是，起點公交線路與終點公交線路之間不能直接換乘，而是在起點公交線路與終點公交線路之間還需要搭乘其它公交線路，而搭乘其它公交線路的方案又包括多種。

因此，查詢起點至終點的公交乘坐方案需要耗費大量的時間以及計算資源。

發明內容

基于此，有必要提供一種可減小時間及計算資源耗費的公交線路查詢方法和裝置。

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

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

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

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

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

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

一種公交線路搜索裝置，包括：

輸入獲取模塊，用于獲取輸入的起點和終點的位置信息；

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

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

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

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

上述公交線路搜索方法和裝置，獲取起點對應的起點公交線路和終點對應的終點公交線路，并以廣度優先原則搜索與起點公交線路連通的公交線路的過程、以及以廣度優先原則搜索與終點公交線路連通的公交線路的過程輪番進行，每當與起點公交線路連通的公交線路以及與終點公交線路連通的公交線路之間有公共線路，則獲取起點公交線路至公共線路的最短連通路徑以及終點公交線路至公共線路的最短連通路徑，根據該兩最短連通路徑合成從起點至終點的乘坐路徑；由于上述方法和裝置從兩個方向上按照廣度優先原則搜索與起點公交線路和終點公交線路連通的公交線路，實時判斷兩個方向上搜索到的公交線路是否有公共線路，并獲取包含公共線路的從起點公交線路至終點公交線路的最短連通路徑為從起點至終點的乘坐路徑，因此可大大減少搜索到從起點至終點的乘坐路徑所耗費的計算資源以及搜索所需的時間。

附圖說明

圖1為一個實施例中運行本發明的公交線路搜索方法的電子設備100的部分結構框圖；

圖2為一個實施例中的公交線路搜索方法的流程示意圖；

圖3A為一個實施例中根據預先存儲的公交數據生成并存儲線路連通圖以及線路連通站點信息的步驟的流程示意圖；

圖3B為一個實施例中的線路連通圖的圖形化表示；