| 词条 | Traveling purchaser problem |
| 释义 |
The traveling purchaser problem (TPP) is an NP-hard problem studied in theoretical computer science. Given a list of marketplaces, the cost of travelling between different marketplaces, and a list of available goods together with the price of each such good at each marketplace, the task is to find, for a given list of articles, the route with the minimum combined cost of purchases and traveling. The traveling salesman problem (TSP) is a special case of this problem. Relation to traveling salesman problem (TSP)The problem can be seen as a generalization of the traveling salesman problem, i.e. each article is available at one market only and each market sells only one item. Since TSP is NP-hard, TPP is NP-hard.[1] Solving TPPApproaches for solving the traveling purchaser problem include dynamic programming[2] and tabu search algorithms.[3] See also
References1. ^Heuristics for the traveling purchaser problem 2. ^A Dynamic Programming Approach for a Travelling Purchaser Problem With Additional Constraints 3. ^A Tabu Search Approach for solving the Travelling Purchase Problem 2 : NP-complete problems|Travelling salesman problem |
| 随便看 |
|
开放百科全书收录14589846条英语、德语、日语等多语种百科知识，基本涵盖了大多数领域的百科知识，是一部内容自由、开放的电子版国际百科全书。