A* 解鎖校園之旅：路徑規劃與智能決策

項目簡介

學生初到校園，不熟悉環境，常常找不到合適的路徑快速到達想去的專業教室?；谶@一真實情境，本項目嘗試解決的核心問題為：如何利用人工智能技術解決校園找路困難的問題？

項目規劃

本項目中，學生將綜合運用信息技術、數學和地理學科的知識與技能，學習如何將復雜的校園平面地圖進行抽象表示，巧妙運用搜索算法進行精準的路徑規劃，并通過回歸分析技術，實現智能化的決策過程，最終優化路徑選擇，培養跨學科學習思維和問題解決能力。

項目目標

本項目旨在讓學生通過校園路徑規劃的項目學習，能夠知道地圖的抽象表示、搜索、回歸等基本概念，對智能決策和搜索算法有所了解，進而理解將路徑規劃技術應用于解決生活中問題的基本思想和方法。

項目實施

項目依據問題解決的基本過程設計了4課時，單一課時重點解決1個小問題。每個課時的設計思路都遵循從現實世界形成問題，提煉對應的計算機問題，利用學科知識學習、理解計算機對這類問題的解決方案，再將其應用于實際問題的解決，甚至推廣到生活中更多問題的解決。

建立數據基礎：抽象地圖

用5×5的柵格地圖對學校地圖進行柵格化表示機器人眼中的地圖表示形式有很多，比如點云地圖、柵格地圖、拓撲地圖、語義地圖等。其中，柵格地圖是用一個個方格組成的網格代表地圖，柵格里可以存儲不同的數值，代表不同的含義。本階段，學生需要將真實的平面地圖進行柵格表示，并用0或1標記柵格的可通行狀態，為在程序中表示校園地圖作準備。

利用二維數組表示柵格地圖每個點的位置

無論是Python、C++還是MATLAB，矩陣更適合數組的表達，更便于編程。在這一活動中，學生能夠利用二維數組表示地圖中的點位，比如設定起點為[1，3]，終點為[7，7]，并嘗試找到可通行的路徑，為路徑規劃作鋪墊，也為后續問題的解決奠定基礎。

A*算法助力：啟發式搜索

熱身活動

提出現實問題，比如從教室到食堂的路線有哪些？哪條最短？讓學生想一想、畫一畫，激活學生的思維。然后，引出路徑規劃的概念及其在生活中的應用，比如手機地圖導航中的路徑規劃、掃地機器人的清掃路線規劃、商場中快速查找商鋪的路線規劃等，進而引出本課的重點內容——搜索算法。

讓計算機找到最短通行路徑

學生合作學習模擬計算機尋找最短路徑的方法，并歸納提煉出盲目式搜索的典型方法，即深度優先搜索和廣度優先搜索。學生在討論過程中指出：盲目式搜索效率比較低，如何才能更智能一些呢？

更加智能地找到最短路徑

通過更多的提示信息，可以“啟發”計算機更加智能地搜索，學生依托多樣學習資源的幫助，逐步理解A*算法的關鍵：如何尋找最優節點？啟發函數如何估算距離？A*算法為了尋找到最優的下一步（最優節點），需要估計經過候選節點的從起點到終點的路徑總長度（F），即從起點到該節點的實際路徑（G）加上從該節點到終點的最短路徑（H）。而最短路徑（H）需要通過啟發函數進行估算，這里的啟發函數使用的是歐式距離（兩點之間線段最短）。

應用A*算法解決實際問題

學生明確了A*算法的原理后，就可以模擬計算機的運算過程，最后通過運行程序代碼驗證問題解決。此外，通過對比和評價本課涉及的3種算法效率，加深對于搜索算法思想的理解。

解決方案優化：回歸分析與智能決策

隨著對知識原理的深入學習，學生發現了更多細節問題。比如，他們意識到由于學校內不同區域在不同時間段的人流量存在差異，因此僅僅依賴啟發式搜索得出的最短路徑，在實際應用中可能并非總是最優選擇。面對這一問題，他們繼續進行深入思考，探究課間休息時長與人流量的關系是否會對路徑規劃的結果產生影響。

課前數據準備

首先，要進行數據收集與處理，學生結合數學統計的知識和方法，建立起不同課間人流量的數據基礎。學生記錄了不同課間時段學森樓前一段路徑的通行人數，包括普通課間、課間操課間、午休時間、眼保健操課間等。

線性回歸模型建立

課上，學生通過“探究小車的運動速度隨時間變化的規律”這一物理實驗的引例，體驗了線性回歸預測方法及過程。然后，學生需要學習利用Python中的sklearn及matplotlib模塊，實現線性回歸算法并解決實際問題。根據學生統計的課間休息時長與人流量的數據，編程求得人流量與課間時長之間的定量關系。借助Python編程語言中的sklearn模塊探索兩個變量之間的線性關系，并以時長為x軸，人流量為y軸，通過matplotlib模塊繪制出擬合圖像。

最小二乘法優化

對照機器學習的一般過程解析程序代碼，學生可以明確和理解運用fit、predict及score訓練數據，得出模型、使用模型預測結果的方法。LinearRegression最小二乘線性回歸的優化技術是將殘差平方值和最小化作為目標，從而使預測數據與實際數據的誤差平方和最小。

綜合考量：智能決策

經過程序運行，得到的人流量與課間時長之間的關系式為：y=12.54x-89.2；R2為0.94。算法訓練完成后，得到的R2比較接近1，說明訓練得出的模型效果較好。由此可見，給定一組數據，在假設數據間存在一元線性關系的前提下，就可通過機器學習中的線性回歸算法擬合數據。

項目評價

項目學習效果評價包含多個內容和多種評價方式。進行過程性評價時，綜合考量了學生的課堂參與程度、每課時項目學習單的完成質量，以及學生的自主評價，全面評估學生對于核心知識的掌握情況及項目實踐的進展。進行總結性評價時，依托項目報告的完成情況，包括利用北斗系統測繪校園平面地圖、實現學校地圖的抽象建模、借助搜索算法和智能決策得出的路徑規劃結論等，考查學生對于項目主要知識的整體掌握程度，以及在問題解決過程中核心素養的體現與提升。