“traveling salesman problem”的意思、由来-百科全书

traveling salesman problem

mathematics

an optimization problem in graph theory in which the nodes (cities) of a graph are connected by directed edges (routes), where the weight of an edge indicates the distance between two cities. The problem is to find a path that visits each city once, returns to the starting city, and minimizes the distance traveled. The only known general solution algorithm that guarantees the shortest path requires a solution time that grows exponentially with the problem size (i.e., the number of cities). This is an example of an NP-complete problem (from nonpolynomial), for which no known efficient (i.e., polynomial time) algorithm exists.

词条	traveling salesman problem
释义	traveling salesman problem mathematics an optimization problem in graph theory in which the nodes (cities) of a graph are connected by directed edges (routes), where the weight of an edge indicates the distance between two cities. The problem is to find a path that visits each city once, returns to the starting city, and minimizes the distance traveled. The only known general solution algorithm that guarantees the shortest path requires a solution time that grows exponentially with the problem size (i.e., the number of cities). This is an example of an NP-complete problem (from nonpolynomial), for which no known efficient (i.e., polynomial time) algorithm exists.
随便看	John George I of Saxony John George IV John George Lambton, 1st earl of Durham John George Lambton Durham, 1st earl of John Gerard John Gibson John Gibson Lockhart John Gilbert John Gill John Glas John Glassco John Gneisenau Neihardt John Goodman John Goodricke John Goodsir John Goodwin John Gorrie John, Gospel According to John Gotti John Gould John Gower John Graham Chambers John Graunt John Graves Simcoe John Greaves