Route inspection and travelling salesperson Flashcards
Studying this course? Keep your progress in one place.

Flip each card. Be honest: the ones you mark Not yet come back first.
13 cards
Tap a card to flip it. Swipe right if you knew it, left if not.
See all 13 cards
- What is route inspection?
- Finding the shortest route that traverses every arc at least once and returns to the start.
- What is the shortest closed route if all nodes are even?
- The total weight of all arcs.
- How many pairings of 4 odd nodes are there?
- Three.
- What is a semi-Eulerian network?
- One with exactly two odd nodes: a route using each arc once exists between those two nodes.
- Length of the shortest closed route with odd nodes?
- Total weight plus the least total of the shortest paths in a pairing of the odd nodes.
- Shortest route that need not close, with four odd nodes?
- Total weight plus the smallest shortest distance between a pair of odd nodes; start and finish at the other two.
- What is the classical TSP?
- Find the shortest tour visiting every node exactly once and returning, on a complete network.
- What does nearest neighbour give?
- A tour, so an upper bound for the shortest tour.
- How do you find a lower bound for the TSP?
- Delete a vertex, find the MST of the rest, add the two shortest arcs at the deleted vertex.
- Which lower bound is the best?
- The largest one.
- How do you write the interval for the optimal tour?
- Largest lower bound shortest tour smallest upper bound.
- How does the practical TSP differ from the classical one?
- Nodes may be visited more than once, and the network need not be complete; use shortest distances.
- Give two ways to refine a network model.
- Use times instead of distances, or use directed arcs for one-way roads.