Django实现TSP最近邻算法：设置原点出现异常点问题排查

我正在开发基于最近邻法的旅行商问题（TSP）程序，采用Django框架。当前遇到的问题是：尝试将某一Coordinate对象设为计算原点时，程序反而添加了另一个无关点作为原点。试过多种设置方式、更换不同原点，也咨询过朋友，但均未解决。

相关代码如下：

calcRoute.py #

from django.db import models
from .models import Coordinate, SortedPoint
import math

class Point:
  def __init__(self, longitude, latitude, isPassed, isOrigin):
    self.longitude = longitude
    self.latitude = latitude
    self.isPassed = isPassed
    self.isOrigin = isOrigin

def haversine(lat1, lon1, lat2, lon2): # haversine formula to calculate distance between points on a globe
    # convert degrees to radians
    lat1, lon1, lat2, lon2 = map(math.radians, [lat1, lon1, lat2, lon2])

    # calculate distance
    dlat = lat2 - lat1
    dlon = lon2 - lon1
    a = math.sin(dlat/2)**2 + math.cos(lat1) * math.cos(lat2) * math.sin(dlon/2)**2
    c = 2 * math.asin(math.sqrt(a))
    r = 6378  # radius of earth in kilometers
    return c * r

def nearest_neighbor(points, origin): # return the nearest neighbor
  nearestNeighbor = None
  nearestDistance = float('inf')
  
  for point in points:
    # skip the origin point
    if point == origin:
      continue
      
    distance = haversine(origin.longitude, origin.latitude, point.longitude, point.latitude)
    
    if distance < nearestDistance:
      nearestNeighbor = point
      nearestDistance = distance
      
  return nearestNeighbor

def save_points(points): # save points to db
  for point in points:
    sorted_point = SortedPoint(longitude=point.longitude, latitude=point.latitude, isPassed=point.isPassed)
    sorted_point.save()

def calc_route():
  SortedPoint.objects.all().delete()
  # load coordinates from db
  coordinates = Coordinate.objects.all()
 
  points = [Point(coordinate.longitude, coordinate.latitude, False, coordinate.isOrigin) for coordinate in coordinates]
  origin = points[0]
  for i in range(len(points)):
    if points[i].isOrigin is True:
      origin = points[i]
  ending = origin
  passedPoints = [origin]
  currentPoint = origin
  points.remove(origin)

  while len(points) > 0:
    nearestNeighbor = nearest_neighbor(points, currentPoint)
    passedPoints.append(nearestNeighbor)
    points.remove(nearestNeighbor)
    currentPoint = nearestNeighbor

  # append origin to the list of passed points
  passedPoints.append(ending)
  save_points(passedPoints) #save

views.py #

def set_origin(request, id):
    point = SortedPoint.objects.get(id=id)
    point.isOrigin = True
    return redirect('editRoute')

@login_required(login_url='administration')
def update_coords(request):
    Coordinate.objects.all().delete()
    sorted_points = SortedPoint.objects.all()
    for sorted_point in sorted_points:
        coord = Coordinate(latitude=sorted_point.latitude, longitude=sorted_point.longitude, routeName=sorted_point.routeName, isPassed=sorted_point.isPassed, isOrigin=sorted_point.isOrigin)
        coord.save()
    
    calc_route()
    return redirect('editRoute')

models.py #

from django.db import models
# Create your models here.

class Coordinate(models.Model):
    latitude = models.FloatField()
    longitude = models.FloatField()
    routeName = models.CharField(max_length=200, default='abc')
    isPassed = models.BooleanField(default=False)
    isOrigin = models.BooleanField(default=False)

class SortedPoint(models.Model):
  longitude = models.FloatField()
  latitude = models.FloatField()
  routeName = models.CharField(max_length=200, default='abc')
  isPassed = models.BooleanField()
  isOrigin = models.BooleanField(default=False)

urls.py（urlpatterns内） #

path('edit-route/set_origin/<int:id>/', views.set_origin, name='set_origin'),
path('edit-route/update_coords/', views.update_coords, name='update_coords'),

1. 原点设置未持久化到数据库 #

set_origin视图中修改了SortedPoint的isOrigin属性，但未调用save()方法，导致修改仅停留在内存中，数据库内的isOrigin值并未更新。后续update_coords同步数据到Coordinate时，无法获取正确的原点标记。

修复代码：

def set_origin(request, id):
    # 清除所有点的原点标记，避免多个原点冲突
    SortedPoint.objects.update(isOrigin=False)
    point = SortedPoint.objects.get(id=id)
    point.isOrigin = True
    point.save()  # 将修改持久化到数据库
    return redirect('editRoute')

2. 保存路径时丢失原点标记 #

save_points函数创建SortedPoint对象时，未传入isOrigin字段，导致新保存的路径点全部默认isOrigin=False，引发数据不一致问题。

修复代码：

def save_points(points): # save points to db
  for point in points:
    sorted_point = SortedPoint(
        longitude=point.longitude, 
        latitude=point.latitude, 
        isPassed=point.isPassed,
        isOrigin=point.isOrigin  # 保存原点标记
    )
    sorted_point.save()

3. Haversine函数参数顺序错误 #

haversine函数定义的参数顺序为(lat1, lon1, lat2, lon2)，但nearest_neighbor调用时传入的是(origin.longitude, origin.latitude, ...)，经度与纬度顺序颠倒，导致距离计算完全错误，直接影响最近邻选择和路径生成。

修复代码：

def nearest_neighbor(points, current_point):
  nearestNeighbor = None
  nearestDistance = float('inf')
  
  for point in points:
    # 用坐标匹配替代对象引用比较，避免自定义类==判断失效
    if point.longitude == current_point.longitude and point.latitude == current_point.latitude:
      continue
      
    # 修正参数顺序：纬度在前，经度在后
    distance = haversine(current_point.latitude, current_point.longitude, point.latitude, point.longitude)
    
    if distance < nearestDistance:
      nearestNeighbor = point
      nearestDistance = distance
      
  return nearestNeighbor

4. 原点查找逻辑优化 #

原代码通过循环遍历查找原点，可改用next函数简化逻辑，同时确保无标记原点时默认取第一个点：

修复代码（calc_route函数内）：

# 替换原有的origin赋值逻辑
origin = next((p for p in points if p.isOrigin), points[0])

内容的提问来源于stack exchange，提问作者Michael V