一、什么是 lapsolver？

lapsolver 是一個用于求解線性分配問題（Linear Assignment Problem, LAP） 的 Python 庫。線性分配問題是運籌學中的經典問題，核心是在兩個集合（如“工人”與“任務”）之間找到一組最優匹配，使得總代價最小（或總收益最大）。

lapsolver 的核心功能：

• 高效求解稠密矩陣（Dense Matrix）和稀疏矩陣（Sparse Matrix）形式的分配問題
• 基于 C++ 底層實現，結合 Python 接口，兼顧性能與易用性
• 支持多種數據類型（如整數、浮點數），適配不同場景的代價矩陣輸入

適用場景：

• 目標跟蹤（如多目標跟蹤中，將檢測到的目標與歷史軌跡匹配）
• 資源分配（如任務調度、人員-崗位匹配）
• 圖像匹配（如特征點匹配、像素級對齊）
• 組合優化問題中的最優配對場景

二、安裝 lapsolver 時的常見問題：編譯失敗

在 macOS 上使用 pip install lapsolver 安裝時，常遇到如下錯誤：

CMake Error at CMakeLists.txt:1 (cmake_minimum_required):Compatibility with CMake < 3.5 has been removed from CMake.
...
subprocess.CalledProcessError: Command '['cmake', ...]' returned non-zero exit status 1.
ERROR: Failed building wheel for lapsolver

這是 lapsolver 安裝的典型問題，根源在于CMake 版本兼容性，而非庫本身的功能缺陷。

三、問題根源分析

1. lapsolver 依賴 C++ 編譯
   lapsolver 的核心算法由 C++ 實現，通過 pybind11 模塊與 Python 綁定，安裝時需要本地編譯，因此依賴 CMake 工具。

2. 低版本 CMake 聲明與高版本工具沖突
   lapsolver 源碼及依賴的 pybind11 模塊中，CMakeLists.txt 文件使用了舊版本聲明（如 cmake_minimum_required(VERSION 2.8.12) 或 3.1），而現代 macOS 系統中安裝的 CMake 版本通常為 3.5+（甚至 4.x），高版本 CMake 會嚴格檢查兼容性，直接拒絕執行低版本聲明的配置文件。

3. 嵌套依賴的連鎖問題
   除了 lapsolver 主目錄的配置文件，其依賴的 pybind11 子模塊及工具腳本（pybind11/tools/pybind11Tools.cmake）也存在低版本聲明，需逐一修復。

四、分步解決：在 macOS 上成功安裝 lapsolver

步驟 1：確認系統環境

1. 檢查 CMake 版本
   終端執行以下命令，確認當前 CMake 版本（需 ≥ 3.5）：

   cmake --version
   

   若版本過低，可通過 conda 或 Homebrew 升級：

   # 推薦：使用 conda 安裝（適合 Python 虛擬環境）
   conda install -c conda-forge cmake# 或使用 Homebrew
   brew install cmake
   

2. 確認編譯工具鏈
   確保已安裝 Xcode 命令行工具（macOS 編譯基礎環境）：

   xcode-select --install  # 已安裝會提示“command line tools are already installed”
   

步驟 2：下載源碼并定位問題文件

1. 下載 lapsolver 源碼
   終端執行以下命令，單獨下載源碼包（不自動安裝）：

   pip download lapsolver --no-deps -i https://pypi.tuna.tsinghua.edu.cn/simple
   

2. 解壓并進入源碼目錄
   找到下載的 .tar.gz 文件（如 lapsolver-1.1.0.tar.gz），解壓后進入目錄：

   tar -zxvf lapsolver-1.1.0.tar.gz
   cd lapsolver-1.1.0
   

3. 需修改的 3 個關鍵文件
   問題出在以下 CMake 配置文件中，需逐一調整版本聲明：

   • ./CMakeLists.txt（lapsolver 主配置）
   • ./pybind11/CMakeLists.txt（pybind11 模塊配置）
   • ./pybind11/tools/pybind11Tools.cmake（工具腳本配置）

步驟 3：修改 CMake 版本聲明（核心操作）

對上述 3 個文件分別執行以下修改（以 nano 編輯器為例）：

1. 修改 ./CMakeLists.txt

   nano CMakeLists.txt
   

   將第一行的版本聲明從低版本（如 3.1）改為 3.5：

   # 原內容：cmake_minimum_required(VERSION 3.1)
   cmake_minimum_required(VERSION 3.5)  # 修改后
   

   保存退出（Ctrl+O → 回車 → Ctrl+X）。

2. 修改 ./pybind11/CMakeLists.txt

   nano pybind11/CMakeLists.txt
   

   將第一行的版本聲明從 2.8.12 改為 3.5：

   # 原內容：cmake_minimum_required(VERSION 2.8.12)
   cmake_minimum_required(VERSION 3.5)  # 修改后
   

3. 修改 ./pybind11/tools/pybind11Tools.cmake

   nano pybind11/tools/pybind11Tools.cmake
   

   找到 cmake_minimum_required 所在行（通常在第 8 行），修改為：

   # 原內容：可能為低于 3.5 的版本（如 3.0）
   cmake_minimum_required(VERSION 3.5)  # 修改后
   

步驟 4：清除緩存并本地安裝

1. 清除歷史編譯緩存
   避免舊配置干擾，刪除臨時文件：

   rm -rf build/ _skbuild/ CMakeCache.txt CMakeFiles/
   

2. 強制兼容政策并安裝
   終端執行以下命令，通過環境變量指定 CMake 政策，然后從本地源碼安裝：

   export CMAKE_ARGS="-DCMAKE_POLICY_VERSION_MINIMUM=3.5"
   pip install . -i https://pypi.tuna.tsinghua.edu.cn/simple --use-pep517
   

步驟 5：驗證安裝結果

安裝完成后，終端執行以下命令，若輸出版本號則說明安裝成功：

python -c "import lapsolver; print('lapsolver 版本：', lapsolver.__version__)"

五、總結

lapsolver 是求解線性分配問題的高效工具，但由于其依賴 C++ 編譯和 pybind11 模塊，在高版本 CMake 環境中容易出現兼容性問題。解決的核心在于：

1. 升級 CMake 至 3.5+；
2. 修復源碼中所有 CMake 配置文件的版本聲明；
3. 清除緩存并通過本地編譯安裝。

通過本文的步驟，可在 macOS 系統中順利解決 lapsolver 的安裝難題，進而利用其高效的匹配算法解決資源分配、目標跟蹤等實際問題。