Traveling Salesman Problem

In the traveling salesman project given under the Greedy Algorithms lesson, there is no solution to the exercise to cross check my result.

import random
from random import randrange
from Graph import Graph
from Vertex import Vertex

def print_graph(graph):
  for vertex in graph.graph_dict:
    print("")
    print(vertex + " connected to")
    vertex_neighbors = graph.graph_dict[vertex].edges
    if len(vertex_neighbors) == 0:
      print("No edges!")
    for adjacent_vertex in vertex_neighbors:
      print("=> " + adjacent_vertex)

def build_tsp_graph(directed):
  g = Graph(directed)
  vertices = []
  for val in ['a', 'b', 'c', 'd']:
    vertex = Vertex(val)
    vertices.append(vertex)
    g.add_vertex(vertex)

  g.add_edge(vertices[0], vertices[1], 3)
  g.add_edge(vertices[0], vertices[2], 4)
  g.add_edge(vertices[0], vertices[3], 5)
  g.add_edge(vertices[1], vertices[0], 3)
  g.add_edge(vertices[1], vertices[2], 2)
  g.add_edge(vertices[1], vertices[3], 6)
  g.add_edge(vertices[2], vertices[0], 4)
  g.add_edge(vertices[2], vertices[1], 2)
  g.add_edge(vertices[2], vertices[3], 1)
  g.add_edge(vertices[3], vertices[0], 5)
  g.add_edge(vertices[3], vertices[1], 6)
  g.add_edge(vertices[3], vertices[2], 1)
  return g

# Define your functions below:
def visited_all_nodes(visited_vertices):
  for vertex in visited_vertices:
    if visited_vertices[vertex] == "unvisited":
      return False
  return True

def traveling_salesperson(graph):
  ts_path = ""
  visited_vertices = {vertex: "unvisited" for vertex in graph.graph_dict}
  current_vertex = random.choice(list(graph.graph_dict))
  visited_vertices[current_vertex] = "visited"
  ts_path += current_vertex
  visited_all_vertices = visited_all_nodes(visited_vertices)
  while not visited_all_vertices:
    current_vertex_edges = graph.graph_dict[current_vertex].get_edges()
    current_vertex_edge_weights = {}
    for edge in current_vertex_edges:
      current_vertex_edge_weights[edge] = graph.graph_dict[current_vertex].get_edge_weight(edge)
    found_next_vertex = False
    next_vertex = ""
    while not found_next_vertex:
      if current_vertex_edge_weights is None:
        break
      next_vertex = min(current_vertex_edge_weights, key = current_vertex_edge_weights.get)
      if visited_vertices[next_vertex] == "visited":
        current_vertex_edge_weights.pop(next_vertex)
      else:
        found_next_vertex = True
    if current_vertex_edge_weights is None:
      visited_all_vertices = True
    else:
      current_vertex = next_vertex
      visited_vertices[current_vertex] = "visited"
      ts_path += current_vertex
    visited_all_vertices = visited_all_nodes(visited_vertices)
  print(ts_path)

graph = build_tsp_graph(False)
traveling_salesperson(graph)

This is my code and I’m getting different outputs as paths for the result. For example, one such output is abcd. However, the problem requires to travel back to the origin. I don’t think that part of the problem is solved in the project. Can someone please clarify?

Hi,

This is a great practice problem. At this point in complexity, I think it’s really important to have the planning stage really tight and write and test the code to reflect that.

So for example, it’s 100% worthwhile to write out the algorithm on paper and make notes on each step as to what kind of tests need to happen to verify that it is working. (And even just “run” the code on paper). This way, if your final output is incorrect, you have much more control about finding out where specifically it falls apart.

In terms for additional resources, there are a lot of good youtube videos and websites that detail out the concepts of this problem.

1 Like

This topic was automatically closed 41 days after the last reply. New replies are no longer allowed.