مسألة الرحالة التاجر

أفضل جولة لحل مسألة مندوب المبيعات المسافر عبر أكبر 15 مدينة في ألمانيا. It is the shortest among 43 589 145 600[1] possible tours visiting each city exactly once.

في نظرية المخططات ونظرية التعقيد التحسيبي، تُعرف "مسألة مندوب المبيعات المسافر" أو "مشكلة التاجر الرحالة" Travelling salesman problem كما يلي:

يريد تاجر أن يقوم بجولة كاملة يزور خلالها مدنا حيث يمر بكل المدن مرة واحدة و وحيدة ثم يعود إلى مدينة الانطلاق. المشكلة هي ما هو أقصر طريق؟؟

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

حول المشكلة

مسألة التارجر المسافر المتماثلة بأربع مدن

رغم أن صيغة المشكلة تبدو بسيطة, إلا أن الحل صعب جدا, فكلما زاد عدد المدن زادت صعوبة المشكل: يحتاج الحاسوب إلى حوالي قرنين من الزمن لإيجاد أقصر مسار يمر على 100 مدينة

فهذه المشاكل تصنف ضمن المشاكل الصعبة، و بعبارة أكثر دقة: المشاكل الحدودية غير المحددة الكاملة NP-complet.


انظر أيضا

الهوامش

  1. ^ Take one city, and take all possible orders of the other 14 cities. Then divide by two because it does not matter in which direction in time they come after each other:

المصادر

  • Applegate, D. L.; Bixby, R. M.; Chvátal, V.; Cook, W. J. (2006), The Traveling Salesman Problem, ISBN 0691129932 .
  • Bellman, R. (1960), "Combinatorial Processes and Dynamic Programming", Combinatorial Analysis, Proceedings of Symposia in Applied Mathematics 10,, American Mathematical Society, pp. 217–249 .
  • Bellman, R. (1962), "Dynamic Programming Treatment of the Travelling Salesman Problem", J. Assoc. Comput. Mach. 9: 61–63, doi:10.1145/321105.321111 .
  • Christofides, N. (1976), Worst-case analysis of a new heuristic for the travelling salesman problem, Technical Report 388, Graduate School of Industrial Administration, Carnegie-Mellon University, Pittsburgh .
  • Hassin, R.; Rubinstein, S. (2000), "Better approximations for max TSP", Information Processing Letters 75: 181–186, doi:10.1016/S0020-0190(00)00097-1 .
  • Held, M.; Karp, R. M. (1962), "A Dynamic Programming Approach to Sequencing Problems", Journal of the Society for Industrial and Applied Mathematics 10 (1): 196–210, doi:10.1137/0110015 .
  • Kaplan, H.; Lewenstein, L.; Shafrir, N.; Sviridenko, M. (2004), "Approximation Algorithms for Asymmetric TSP by Decomposing Directed Regular Multigraphs", In Proc. 44th IEEE Symp. on Foundations of Comput. Sci., pp. 56–65 .
  • Karp, R.M. (1982), "Dynamic programming meets the principle of inclusion and exclusion", Oper. Res. Lett. 1: 49–51, doi:10.1016/0167-6377(82)90044-X .
  • Kohn, S.; Gottlieb, A.; Kohn, M. (1977), "A Generating Function Approach to the Traveling Salesman Problem", ACM Annual Conference, ACM Press, pp. 294–300 .
  • Kosaraju, S. R.; Park, J. K.; Stein, C. (1994), "Long tours and short superstrings'", Proc. 35th Ann. IEEE Symp. on Foundations of Comput. Sci., IEEE Computer Society, pp. 166–177 .
  • Orponen, P.; Mannila, H. (1987), "On approximation preserving reductions: Complete problems and robust measures'", Technical Report C-1987–28, Department of Computer Science, University of Helsinki .
  • Papadimitriou, C. H.; Yannakakis, M. (1993), "The traveling salesman problem with distances one and two", Math. Oper. Res. 18: 1–11, doi:10.1287/moor.18.1.1 .
  • Serdyukov, A. I. (1984), "An algorithm with an estimate for the traveling salesman problem of the maximum'", Upravlyaemye Sistemy 25: 80–86 .
  • Woeginger, G.J. (2003), "Exact Algorithms for NP-Hard Problems: A Survey", Combinatorial Optimization – Eureka, You Shrink! Lecture notes in computer science, vol. 2570, Springer, pp. 185–207 .

قراءات إضافية


. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

وصلات خارجية