[發明專利]蜂巢迷宮最短路徑計算方法及蜂巢迷宮實訓系統

在審

• 申請號: 202010124030.9
• 申請日: 2020-02-21
• 公開（公告）號: CN111340296A
• 公開（公告）日: 2020-06-26
• 發明（設計）人: 余澤凡;何學智;劉小揚;劉子煒
• 申請（專利權）人: 新大陸數字技術股份有限公司
• 主分類號: G06Q10/04
• 分類號: G06Q10/04;G06Q50/20;G09B9/00
• 代理公司: 暫無信息
• 代理人: 暫無信息

本發明公開了一種蜂巢迷宮最短路徑計算方法及蜂巢迷宮實訓系統，將蜂巢形迷宮的每個節點作為一個單元結構體，將每個節點相鄰的所有節點進行編號，將相鄰節點的指針存入該節點的單元結構體中；讀取節點和邊的數據并以鄰接矩陣形式存儲，并統計出節點個數和邊的條數；在鄰接矩陣運算過程中，每個結點遍歷完鄰結點后其余連接點均設為極大值；獲取起始節點、終點節點及各中間節點的節點信息；通過迪杰斯特拉算法計算經過這些中間節點的起始點至終點的最短距離。本發明解決了在低配置單片機中無法實現蜂巢迷宮最短路徑算法的問題，在低成本的硬件環境下采用高效的算法，可用于各種教育實訓產品中，顯著降低了產品成本。

技術領域

本發明涉及教育實訓技術領域，特別涉及一種蜂巢迷宮最短路徑計算方法及蜂巢迷宮實訓系統。

背景技術

編程教育是通過編程游戲啟蒙、可視化圖形編程等課程，培養學生的計算思維和創新解難能力的課程。最短路徑計算是讓學生在已有地圖上尋找兩點間的最短路徑，是一種啟發學生邏輯思維能力的經典課程。最短路徑算法不僅在解決路徑搜索相關的應用中十分普遍，包括網絡路由算法、機器人探路、人工智能、游戲設計等，而且在交通路線導航、路徑分析領域應用更加廣泛。常用的最短路徑搜索算法有Dijkstra(迪杰斯特拉算法)，A-Star算法，但是目前主流的單片機的RAM都在64K以下，想要運行以上這些最短路徑算法均有一定難度。

發明內容

本發明要解決的技術問題是如何提供一種可應用在低硬件配置環境下的蜂巢迷宮最短路徑計算方法及蜂巢迷宮實訓系統。

為了解決上述技術問題，本發明的技術方案為：

一方面，本發明提出了一種蜂巢迷宮最短路徑計算方法，包括步驟：

將蜂巢形迷宮的每個節點作為一個單元結構體，單元結構體的屬性包括單元坐標、鄰結點的指針、單位結點權值、鄰結點的數量；將每個節點相鄰的所有節點進行編號，將相鄰節點的指針存入該節點的單元結構體中；

讀取節點和邊的數據并以鄰接矩陣形式存儲，并統計出節點個數和邊的條數；鄰接矩陣中的元素為n和max兩種，n表示直接有邊相連的權值，max表示無邊直接相連；

在鄰接矩陣的運算過程中，每個結點遍歷完鄰結點后其余連接點均設為max；

獲取起始節點、終點節點及各中間節點的節點信息，通過迪杰斯特拉算法計算經過各中間節點的起始點至終點的最短距離。

優選地，還包括步驟：從網絡圖中刪去目標路徑不經過的節點。

優選地，從網絡圖中刪去目標路徑不經過的節點的步驟為：從起點出發，深度遍歷網絡圖，將沒有遍歷到的節點從原網絡圖中刪除，生成新的網絡圖用以替換原網絡圖。

優選地，在將每個鄰節點的指針存入單元數據組中之前，還包括：

當一節點的單元坐標位置處在網絡圖的區域范圍外，則刪除該節點。

另一方面，本發明還提出一種蜂巢迷宮實訓系統，包括：

多個正六邊形的蜂巢單元，所述蜂巢單元設有一用于設置起點和終點的按鈕，以及六條分別與六條邊連通的用于感應相鄰結點是否連接的電橋，六條電橋之間相互連通；

主控設備，所述主控設備與各所述蜂巢單元通信連接，所述主控設備可執行如上所述的蜂巢迷宮最短路徑計算方法。

優選地，每個所述蜂巢單元上都設有受所述主控設備控制的信號燈。

優選地，所述主控設備包括STM32系列的控制芯片。