So I was getting the errors mentioned in a different topic about suboptimal performance, but now I’m just getting:
There was an error grading your submission. Details:
'str' object has no attribute 'args'
The test, however, passes for unittests.test_tsp_medium_graph(Graph_Advanced)
I encountered that issue a few times, but was able to ignore it and it eventually went away as I worked through the four functions. Maybe the process of solving the problems helped to fix it, not sure.
You can’t attach images until you have enough forum posts to earn some amount of trust on the platform.
Hi everyone, I suspect the tsp_medium_graph grader is broken. I am going to live with the 75% and I passed the whole course with 100% except for this. The error is the same despite the fact that I have tried many methods of optimizations:
I am sharing my code here and everyone can decide on why my code did not work against the unit test.
def tsp_medium_graph(self, start_vertex: int) -> tuple[float, list[int]]:
"""
Solve the Traveling Salesman Problem for medium (~300 node) graphs. The goal is to improve
upon the nearest neighbor solution using 2-opt optimization, executing in less than 1.3 seconds.
This version runs the nearest neighbor search from multiple start points in parallel.
"""
# Precompute edge weights for faster lookup
vertices = list(self.graph.keys())
n = len(vertices)
edge_weights = {(i, j): self._get_edge_weight(vertices[i], vertices[j]) for i in range(n) for j in range(n) if i != j}
# Nearest neighbor heuristic for a single start point
def nearest_neighbor(start: int):
path = [start]
unvisited = set(vertices)
unvisited.remove(start)
total_distance = 0
current = start
while unvisited:
next_vertex = min(unvisited, key=lambda vertex: edge_weights.get((current, vertex), float('inf')))
total_distance += edge_weights.get((current, next_vertex), float('inf'))
path.append(next_vertex)
unvisited.remove(next_vertex)
current = next_vertex
total_distance += edge_weights.get((current, start), float('inf')) # Return to start
path.append(start)
return total_distance, path
# Run nearest neighbor from 3 different start points in parallel
start_points = random.sample(vertices, 3) # Try 3 different starting points to save time
results = Parallel(n_jobs=-1)(delayed(nearest_neighbor)(start) for start in start_points)
# Select the best nearest neighbor solution
best_distance, best_path = min(results, key=lambda x: x[0])
# Apply 2-opt optimization to improve the solution
def two_opt(route: list[int], max_iterations: int = 50) -> list[int]:
best = route
iterations = 0
improved = True
while improved and iterations < max_iterations:
iterations += 1
improved = False
# Batch random edge swaps rather than checking all pairs
for _ in range(5): # Limit to 5 random swaps per iteration
i, j = sorted(random.sample(range(1, len(route) - 1), 2))
if j - i == 1: continue # Skip adjacent nodes
new_route = route[:i] + route[i:j][::-1] + route[j:]
if self._tour_cost(new_route) < self._tour_cost(best):
best = new_route
improved = True
if not improved:
break # Early exit if no improvement
return best
# Perform 2-opt optimization on the best nearest neighbor result
optimized_path = two_opt(best_path, max_iterations=50) # Further reduced iterations for speed
optimized_dist = self._tour_cost(optimized_path)
return optimized_dist, optimized_path
# Helper function to calculate the total cost of a given tour
def _tour_cost(self, path: list[int]) -> float:
"""
Helper function to calculate the total cost of a given tour.
"""
total_distance = 0
for i in range(len(path) - 1):
total_distance += self._get_edge_weight(path[i], path[i+1])
return total_distance
Ok later I try, seriously Gen AI still not up to par yet. Only 1 year plus old.
I find the coding stuff more for Comp Science background required to read, understand and troubleshooting the codes. For all 3 courses.
It reminds of Uni Colorado Boulder Data Structures and Algorithms specialisation in Coursera.
I understand that the grader for tsp_medium_graph() was updated yesterday to fix an issue (as reported in some other threads).
Thank you all for your inputs, I will investigate it. As soon as I have an answer I get back to you.
Hi @Bernard_Leong,
There is a couple of issues with your code. I see that you import joblib, using Parallel and delayed functions, this is not allowed in this assignment, you should stick with the libraries that are lodade in the assignment. This is crucial as the autograder loads the library prior to parsing your solution, so any other library will break the autograder. Also, it looks like you have added some new attributes to the Graph class, which should not be done. I will improve the language in the assignment in this way.
That said, could you please send me your notebook privately? I would like to take a look. Thanks!
@Peter_Litvak, could you also send me your notebook?
Thanks,
Lucas
Sorry, I didn’t save it
nevermind, I re-opened it and the code seems to be there
A question to clarify:
Run the code below to test the tsp_medium_graph on complete (fully connected) graphs with 300 nodes. The requirements for passing this exercise are:
The tsp_medium_graph comment wrote:
“”"
Solve the Travelling Salesman Problem for a medium (~100 node) complete graph starting from a specified node.
Expected to perform better than tsp_large_graph. Must run under 1 second.
Parameters:
start: The starting node.
Returns:
A tuple containing the total distance of the tour and a list of nodes representing the tour path.
“”"
Which is correct? 100 nodes or 300 nodes? Thanks.
Hi Lucas,
Thank you for your note. I have sent you the notebook privately.
Bernard
For visibility,
Some errors were caused by importing joblib to the solution, which should not be done. In fact it shouldn’t be imported any library rather than the ones contained in the notebook. I will improve the text to advise learners to do so.
Thanks for flagging this! It is actually 300 nodes. The text is fixed.
I am having trouble with this, too. My intuition wants me to think I messed up the “Your code here” tag for the tsp_medium_graph" because my code passes until the last unitest. At this point I get the following:
`Failed test case: Your Graph class does not contain a method called tsp_medium_graph.
Expected: A Graph with a method called tsp_medium_graph
Got: No tsp_medium_graph method detected`
that is kind of telling since there is definitely an instance of code for this method … is there something we can reset to make sure there is a valid test?
Possibly you zapped the metadata that tells the grader to pay attention to the cell that contains that function.