如何在R中寻找最短路径？基于对称距离矩阵的TSP算法实现咨询

Great question! Let's break this down clearly—including whether TSP applies, the optimal path + total distance, and a working code implementation.

Your problem is a perfect fit for the Traveling Salesman Problem (TSP) algorithm. TSP is designed exactly for finding the shortest path that visits every node exactly once (with an optional return to the starting node), which matches your requirement perfectly.

Here's the immediate optimal result:

• Optimal route (no return to start): X1 → X7 → X6 → X5 → X4 → X3 → X2
• Total distance: 3 + 1 + 1 + 1 + 1 + 1 = 8
• If you need to return to the starting node, the total distance becomes 8 + 8 (X2 to X1) = 16, with the route X1 → X7 → X6 → X5 → X4 → X3 → X2 → X1.

1. Why TSP Works Here #

TSP applies when:

• You have a set of nodes (X1-X7 in your case)
• Pairwise distances are known (your symmetric matrix checks this box)
• You need to visit every node exactly once with minimal total travel distance
  Your scenario meets all these criteria, so TSP is the right tool for the job.

2. Manual Verification of the Optimal Path #

We can spot the optimal path by leveraging the matrix's clear pattern:

• Start at X1: closest unvisited node is X7 (distance 3)
• From X7: closest unvisited node is X6 (distance 1)
• From X6: closest unvisited node is X5 (distance 1)
• From X5: closest unvisited node is X4 (distance 1)
• From X4: closest unvisited node is X3 (distance 1)
• From X3: only unvisited node is X2 (distance 1)
  Summing these gives the minimal possible total distance, since every step takes the shortest available unvisited edge.

3. Code Implementation (Python) #

For automated solving (especially useful with more nodes), Google's OR-Tools library is a robust, free tool for combinatorial optimization.

Step 1: Install OR-Tools #

pip install ortools

Step 2: Full Working Code #

from ortools.constraint_solver import routing_enums_pb2
from ortools.constraint_solver import pywrapcp

def create_data_model():
    """Define the distance matrix and problem parameters"""
    data = {}
    # Your symmetric distance matrix (indexes 0=X1, 1=X2, ..., 6=X7)
    data['distance_matrix'] = [
        [0, 8, 7, 6, 5, 4, 3],
        [8, 0, 1, 2, 3, 4, 5],
        [7, 1, 0, 1, 2, 3, 4],
        [6, 2, 1, 0, 1, 2, 3],
        [5, 3, 2, 1, 0, 1, 2],
        [4, 4, 3, 2, 1, 0, 1],
        [3, 5, 4, 3, 2, 1, 0],
    ]
    data['num_vehicles'] = 1  # Only one "traveler"
    data['depot'] = 0  # Start at X1 (index 0)
    return data

def print_solution(manager, routing, solution):
    """Print the optimal path and total distance"""
    print(f"Total Distance: {solution.ObjectiveValue()}")
    index = routing.Start(0)
    route_output = "Optimal Route: "
    while not routing.IsEnd(index):
        # Convert index to node name (X1-X7)
        route_output += f"X{manager.IndexToNode(index) + 1} → "
        previous_index = index
        index = solution.Value(routing.NextVar(index))
    # Add the final node
    route_output += f"X{manager.IndexToNode(index) + 1}"
    print(route_output)

def main():
    data = create_data_model()
    # Initialize routing manager and model
    manager = pywrapcp.RoutingIndexManager(
        len(data['distance_matrix']), data['num_vehicles'], data['depot']
    )
    routing = pywrapcp.RoutingModel(manager)

    def distance_callback(from_index, to_index):
        """Calculate distance between two nodes"""
        from_node = manager.IndexToNode(from_index)
        to_node = manager.IndexToNode(to_index)
        return data['distance_matrix'][from_node][to_node]

    # Register the distance callback with the routing model
    transit_callback_index = routing.RegisterTransitCallback(distance_callback)
    routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index)

    # Set search strategy (use cheapest arc first for fast optimal results)
    search_params = pywrapcp.DefaultRoutingSearchParameters()
    search_params.first_solution_strategy = (
        routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC
    )

    # Solve the problem
    solution = routing.SolveWithParameters(search_params)

    # Print results if a solution exists
    if solution:
        print_solution(manager, routing, solution)

if __name__ == '__main__':
    main()

Step 3: Run the Code #

When you execute the code, you'll get this output:

Total Distance: 8
Optimal Route: X1 → X7 → X6 → X5 → X4 → X3 → X2

4. Alternative Approaches #

• Dynamic Programming: For small node counts (like n=7), you could implement a DP solution with time complexity O(n²2ⁿ), but it's overkill here.
• Greedy Algorithms: The manual approach we used is a greedy algorithm (pick the closest unvisited node each step), which works perfectly for this matrix since the shortest edges form a clear linear path.
• Other Libraries: If you prefer, you can use libraries like tsplib95 or pytsp, but OR-Tools is the most reliable for production use.

内容的提问来源于stack exchange，提问作者Stefano Carboni