vue实现tsp

Vue实现TSP（旅行商问题）算法

TSP（旅行商问题）是一个经典的组合优化问题，目标是找到访问所有城市并返回起点的最短路径。在Vue中实现TSP算法需要结合前端交互和算法逻辑。

基础实现步骤

安装必要依赖（如需要可视化）

npm install vue-chartjs chart.js

创建Vue组件结构

<template>
  <div>
    <div v-if="cities.length > 0">
      <canvas ref="tspCanvas"></canvas>
    </div>
    <button @click="generateRandomCities">生成随机城市</button>
    <button @click="solveTSP">计算最优路径</button>
  </div>
</template>

算法核心实现

实现暴力破解法（小规模城市）

methods: {
  calculateDistance(city1, city2) {
    return Math.sqrt(
      Math.pow(city1.x - city2.x, 2) + 
      Math.pow(city1.y - city2.y, 2)
    );
  },

  bruteForceTSP() {
    let minPath = [];
    let minDistance = Infinity;
    const permutations = this.permute([...Array(this.cities.length).keys()]);

    permutations.forEach(path => {
      let currentDistance = 0;
      for (let i = 0; i < path.length - 1; i++) {
        currentDistance += this.calculateDistance(
          this.cities[path[i]], 
          this.cities[path[i+1]]
        );
      }
      if (currentDistance < minDistance) {
        minDistance = currentDistance;
        minPath = path;
      }
    });

    return { path: minPath, distance: minDistance };
  }
}

优化算法实现

实现最近邻启发式算法（适合中等规模）

nearestNeighborTSP() {
  const unvisited = new Set([...Array(this.cities.length).keys()]);
  const path = [0];
  unvisited.delete(0);
  let totalDistance = 0;

  while (unvisited.size > 0) {
    let last = path[path.length - 1];
    let nearest = null;
    let minDist = Infinity;

    unvisited.forEach(cityIdx => {
      const dist = this.calculateDistance(
        this.cities[last], 
        this.cities[cityIdx]
      );
      if (dist < minDist) {
        minDist = dist;
        nearest = cityIdx;
      }
    });

    path.push(nearest);
    unvisited.delete(nearest);
    totalDistance += minDist;
  }

  totalDistance += this.calculateDistance(
    this.cities[path[path.length - 1]], 
    this.cities[path[0]]
  );

  return { path, distance: totalDistance };
}

可视化实现

使用Chart.js绘制路径

drawPath(solution) {
  const ctx = this.$refs.tspCanvas.getContext('2d');
  new Chart(ctx, {
    type: 'scatter',
    data: {
      datasets: [{
        label: '城市',
        data: this.cities.map(c => ({x: c.x, y: c.y})),
        backgroundColor: 'red',
        pointRadius: 6
      }, {
        label: '路径',
        data: solution.path.map(idx => this.cities[idx]),
        showLine: true,
        fill: false,
        borderColor: 'blue',
        pointRadius: 0
      }]
    },
    options: {
      scales: {
        x: { type: 'linear', position: 'bottom' },
        y: { type: 'linear' }
      }
    }
  });
}

性能优化建议

对于大规模城市集（>15个城市），应考虑更高级的算法：

• 遗传算法实现
• 模拟退火算法
• 蚁群算法

这些算法可以通过Web Worker在后台线程运行，避免阻塞UI。

完整组件示例

<script>
import { Chart } from 'chart.js';

export default {
  data() {
    return {
      cities: [],
      solution: null
    };
  },
  methods: {
    generateRandomCities() {
      this.cities = Array.from({length: 10}, () => ({
        x: Math.random() * 100,
        y: Math.random() * 100
      }));
    },
    solveTSP() {
      if (this.cities.length <= 10) {
        this.solution = this.bruteForceTSP();
      } else {
        this.solution = this.nearestNeighborTSP();
      }
      this.drawPath(this.solution);
    }
    // 其他方法同上...
  }
};
</script>

注意：实际项目中应根据城市数量选择合适的算法，暴力破解法只适用于非常小的城市集（<10个城市）。对于生产环境，建议使用WebAssembly或服务端计算来提高性能。