LKH(Lin-Kernighan-Helsgaun)算法是一種用於解決旅行商問題(TSP)的啟發式算法。它通過交換路線上的城市對來最佳化當前的解決方案，這種方法稱為k-opt交換。在LKH算法中，k-opt交換通常指的是從解決方案中移除k條邊，並以新的方式重新連線它們，以獲得一個可能更好的解決方案。
算法的核心在於路徑調換法和深度優先搜尋策略，調換過程通常只需兩徑調換，有時也會用到三徑調換或四徑調換。算法的過程是從一個隨機生成的初始解開始，然後不斷通過k-opt交換來尋找更短的路徑。若新的路徑長度比原路徑短，則接受這個新的路徑；若長度相同或更長，則放棄這個路徑。
LKH算法的特點是能夠有效地找到TSP問題的近似最優解。儘管它不能保證找到絕對最優解，但它能夠在合理的時間內找到非常接近最優的解。這種算法對於處理大規模的TSP問題特別有效，能夠在短時間內提供高質量的解。