45 lines
1.5 KiB
Python
45 lines
1.5 KiB
Python
import math
|
|
import random
|
|
from model.base_model import Model
|
|
|
|
class MyDFSModel(Model):
|
|
def __init__(self):
|
|
super().__init__()
|
|
|
|
def init(self, nodes):
|
|
"""
|
|
Put your initialization here.
|
|
"""
|
|
super().init(nodes)
|
|
|
|
def fit(self, max_it=1000):
|
|
"""
|
|
Put your iteration process here.
|
|
"""
|
|
|
|
MST_solutions = []
|
|
# Depth First: Set one city as starting point, iterate to the end, then select next city as starting point.
|
|
for i in range(0, self.N):
|
|
solution = []
|
|
solution.append(i)
|
|
unvisited_list = list(range(0, self.N))
|
|
cur_city = i
|
|
# print("[starting]", i)
|
|
for steps in range(self.N - 1):
|
|
# print(unvisited_list)
|
|
unvisited_list.remove(cur_city)
|
|
closest_neighbour = -1
|
|
shortest_distance = math.inf
|
|
for j in unvisited_list:
|
|
if(self.dist(cur_city, j) < shortest_distance):
|
|
closest_neighbour = j
|
|
shortest_distance = self.dist(cur_city, j)
|
|
solution.append(closest_neighbour)
|
|
cur_city = closest_neighbour
|
|
MST_solutions.append(solution)
|
|
self.fitness_list.append(self.fitness(solution))
|
|
|
|
self.best_solution = MST_solutions[ self.fitness_list.index(min(self.fitness_list)) ]
|
|
|
|
return self.best_solution, self.fitness_list
|