Блог

Я пытаюсь протестировать свой код для решения задачи коммивояжера с помощью 2-аппроксимации с большим количеством вершин и не получаю никаких результатов. Для кода ниже я получаю правильный результат, но как только я добавляю еще одну вершину, я не получаю результата. Я не понимаю, почему у меня возникла эта проблема.

Ниже приведен мой код:

 import numpy as np
from collections import defaultdict
import heapq

class MinimumSpanningTree: 
  
        def __init__(self, edgeWeights, root):
            self.root = root 
            self.totalWeight = edgeWeights 
            self.minimumSpanningTree = self.PrimsAlgorithm()

        def PrimsAlgorithm(self):
           
            result = defaultdict(set) 
            
            verticesVisited = set([self.root])
          
            
            treeEdges = [(edgeWeight, self.root, secondVertex) for secondVertex, edgeWeight in enumerate(self.totalWeight[self.root])]
            heapq.heapify(treeEdges)
          
            while treeEdges:
                edgeWeights, vertex, nextVertex = heapq.heappop(treeEdges)
               
                if nextVertex not in verticesVisited:
                    verticesVisited.add(nextVertex)
                    result[vertex].add(nextVertex) 
                    #use for loop to declare visitNextVertex and enumerate over totalWeight[nextVertex]
                    for visitNextVertex, edgeWeights in enumerate(self.totalWeight[nextVertex]):
                       
                        if visitNextVertex not in verticesVisited:
                            heapq.heappush(treeEdges, (self.totalWeight[nextVertex][visitNextVertex], nextVertex, visitNextVertex))
            return result

        def mstPreOrder(self, root):
        
            childVertex = self.minimumSpanningTree[root]
        
            result = [root]
             
            for vertex in childVertex:
                
                result = result   self.mstPreOrder(vertex)
            return result 

class TravelingSalesmanProblem:
   
    def __init__(self, edgeWeight, preOrderMST, vertices):
        self.preOrderMST = preOrderMST   
        self.edgeWeight = edgeWeight 
        self.weightTraveled = self.PreOrderWeight(preOrderMST)
        self.vertices = vertices
    

    def PreOrderWeight(self, preOrderMST):
       
            result = 0
      
            for root in range(len(preOrderMST)):
                firstVertex = preOrderMST[root] 
                secondVertex = preOrderMST[(root 1)%len(preOrderMST)]
                result  = self.edgeWeight[firstVertex][secondVertex]
            return result

    def findTwoApproxSolution(self):
      
            numberOfVertices = len(self.preOrderMST)
           
            currentMST = self.preOrderMST
       
            originalDistance = self.weightTraveled  
       
            for a in range(numberOfVertices-2):
                for b in range(a 2, numberOfVertices):
                   
                    newpreOrderMST = np.copy(self.preOrderMST)
                    newpreOrderMST[(a 1)%numberOfVertices] = self.preOrderMST[b%numberOfVertices]
                   
                    tempEdge = a 2
                  
                    for c in range(b-1, a, -1):
                        newpreOrderMST[tempEdge%numberOfVertices] = self.preOrderMST[c%numberOfVertices]
                        
                        tempEdge  = 1
                
                    inequalityDistance = self.PreOrderWeight(newpreOrderMST)
                  
                    if inequalityDistance < originalDistance:
                        currentMST = np.copy(newpreOrderMST)
                        originalDistance = inequalityDistance
        
            if self.weightTraveled == originalDistance:
                return    
      
            self.preOrderMST = currentMST
          
            self.weightTraveled = originalDistance
            
            tour = list(map(lambda x: self.vertices[x], self.preOrderMST))
           
            print("The 2-Approximation Tour Of Vertices is:",tour)
            
            print("Total Weight For 2-Approximation Tour is:", self.weightTraveled)
            
            self.findTwoApproxSolution() 
            return tour,self.weightTraveled 


listOfVertices=[['A'],['B'],['C'],['D']]

edgeCost = [[0,10,15,20],[10,0,35,25],[15,35,0,30],[20,25,30,0]]

findMST = MinimumSpanningTree(edgeCost, 0) 

findMSTPreOrder = findMST.mstPreOrder(0) 
    

travelingSalesmanPreOrder = TravelingSalesmanProblem(edgeCost, findMSTPreOrder, listOfVertices)

travelingSalesmanPreOrder.findTwoApproxSolution()
 

Код для добавления дополнительных вершин (5 вершин)

 listOfVertices=[['A'],['B'],['C'],['D'],['E']]

edgeCost = [[0,3,4, 2,7],
[3,0,4,6 ,3],
[4,4,0,5,8],
[2,6,5,0,6],
[7,3,8,6,0],
]
 

Обновить:
Значение, возвращаемое для добавления 5-й вершины, равно None. Кроме того, если я использую его только для 3 вершин, он не возвращает ни одной. Я нахожу это очень странным и не понимаю, почему это работает только для 4 вершин

Я добавил вершину и получил результат:

 listOfVertices=[['A'],['B'],['C'],['D'],['E']]

edgeCost = [[0,10,15,20, 50],[10,0,35,25,50],[15,35,0,30,50],[20,25,30,0,50], [20,25,30,0,50]]
 

возвращенный

 The 2-Approximation Tour Of Vertices is: [['A'], ['B'], ['E'], ['D'], ['C']]
Total Weight For 2-Approximation Tour is: 105
 

Я думаю, что один из способов, чтобы ваш код не печатал результат, — это если он срабатывает при последнем вызове:

 if self.weightTraveled == originalDistance:
    return