given a graph and a number K, select K nodes in the graph so that the the shortest path visiting those K nodes is as long as possible. the path may go through other nodes along the way.
the traveling salesman problem (TSP) is typically formulated as visiting all the nodes in a graph. we have introduced the additional combinatorial complexity of first selecting the subset of K nodes, making this a minimax problem.
variant: require that the path start at a given node. variant: circuit.
inspired by Zelda BOTW: where should 900 Koroks be placed to maximize difficulty for speedrunners? probably many extremal points, though we have not defined what an "extremal" node is in a graph.
No comments :
Post a Comment