| dbo:abstract
|
- مسألة البائع المتجول (بالإنجليزية: Travelling salesman problem) هي إحدى أهم المسائل في علم التعقيد الحسابي ونظرية المخططات، ونص المسألة هو: وصل تاجر إلى دولة فيها n مدينة ويريد البائع أن يزور كل مدينة في الدولة مرة واحدة فقط وبأقل وقت سفر بين المدن. بالرغم من بساطة عرض المسألة فقد تبين أن هذه المسألة هي إحدى المسائل التي لا يُعرف لها خوارزمية تحلها بسرعة، أي أنه إذا كان هناك فقط 50 مدينة حينها يتطلب الأمر أكثر من ألف عام لايجاد الحل ! وقد وجدت هذه المسألة طريقها لنظرية التعقيد الحسابي حين أدرجها كارب في قائمته ال-21 لمسائل NP كاملة. (ar)
- El problema del viatjant de comerç és el problema d'optimització de trajectòries donat per l'enunciat següent: donat un conjunt de nodes, es tracta de trobar l'ordre de visites a seguir per tal de definir una trajectòria que passi un sol cop per a cada node i de manera que la distància total recorreguda sigui la més curta possible. S'usa en el sector públic per al disseny de xarxes de serveis i de transports i la planificació logística pública i privada. Es pot resoldre a mà amb la teoria de grafs i algunes matrius, però és més ràpid, sobretot si intervenen molts nodes o punts de pas, fer-ho amb un senzill programa informàtic. Es va plantejar, com el seu nom indica, per a planificar la millor ruta que hauria de fer un comerciant que volgués passar a veure una llista de clients. A més d'en l'enginyeria, s'estudia com a exemple també, tot i que sense aplicar-lo a la vida real, en altres camps que no hi tenen res a veure, com per exemple, a teoria de la informàtica. El problema del viatjant de comerç es presenta en moltes aplicacions pràctiques, per exemple en el disseny d'una línia de metro, en logística o en el disseny del circuit integrat de microxips. Encara apareix més sovint com a subproblema, per exemple en el problema de la distribució de mercaderia, en el problema de la planificació de la ruta per o per o en la seqüenciació del genoma. Els termes de "ciutat" i "distància" no s'han d'agafar al peu de la lletra. Per exemple, el concepte "ciutats" pot representar les ciutats dels clients a visitar o les cadenes d'ADN, mentre que la "distància" pot significar tant el temps que es triga a fer el viatge, els costos o el grau de concordança entre dues cadenes d'ADN. En moltes aplicacions pràctiques primer s'ha de tenir en les restriccions com les dels marges de temps o recursos restringits cosa que complica considerablement la solució del problema. El problema del viatjant de comerç pertany a la classe de problemes NP-complets de la teoria de complexitat computacional. Per tant es creu que el que cada dona com a solució òptima per aquest problema, en el millor dels casos té un creixement exponencial encara que depèn del nombre de ciutats. Per a poques ciutats, la quantitat que cal l'algorisme pot fer que el càlcul ja sigui impracticable degut a l'enormitat del temps de computació. (ca)
- Problém obchodního cestujícího (anglicky Travelling Salesman Problem – TSP) je obtížný diskrétní optimalizační problém, matematicky vyjadřující a zobecňující úlohu nalezení nejkratší možné cesty procházející všemi vrcholy ohodnoceného grafu. (cs)
- Το πρόβλημα του μετακινούμενου πωλητή (που ονομάζεται επίσης και πρόβλημα πλανόδιου πωλητή ή TSP) θέτει την ακόλουθη ερώτηση: "Λαμβάνοντας υπόψη μια λίστα με τις πόλεις και τις αποστάσεις μεταξύ κάθε ζεύγους πόλεων, ποια είναι η συντομότερη διαδρομή που επισκέπτεται κάθε πόλη και επιστρέφει την πόλη προέλευσης; " Πρόκειται για ένα NP-hardness πρόβλημα στη συνδυαστική βελτιστοποίηση, σημαντικό στην έρευνα των λειτουργιών και στη θεωρητική επιστήμη των υπολογιστών. Το πρόβλημα του αγοραστή που ταξιδεύει και το πρόβλημα της δρομολόγησης του οχήματος είναι και τα δύο γενικεύσεις του TSP. Στη , η έκδοση απόφασης του TSP (όπου δόθηκε ένα μήκος L, ο σκοπός είναι να αποφασίσει αν το γράφημα έχει περιοδεία το πολύ L) ανήκει στην τάξη NP-πλήρων προβλημάτων. Επομένως, είναι πιθανό ότι ο χειρότερος χρόνος εκτέλεσης για οποιονδήποτε αλγόριθμο για το TSP αυξάνεται πολυωνυμικά (αλλά όχι περισσότερο από εκθετικά) με τον αριθμό των πόλεων. Το πρόβλημα διατυπώθηκε για πρώτη φορά το 1930 και είναι ένα από τα πιο έντονα μελετημένα προβλήματα βελτιστοποίησης. Χρησιμοποιείται ως σημείο αναφοράς για πολλές μεθόδους βελτιστοποίησης. Αν και το πρόβλημα είναι υπολογιστικά δύσκολο, είναι γνωστοί πολλά θεωρητικοί και ακριβείς αλγόριθμοι, έτσι ώστε ορισμένες περιπτώσεις με δεκάδες χιλιάδες πόλεις να μπορούν να λυθούν πλήρως και ακόμη και προβλήματα με εκατομμύρια πόλεις μπορούν να προσεγγιστούν με ένα μικρό ποσοστό απόκλισης της τάξης του 1%. Το TSP έχει αρκετές εφαρμογές ακόμα και στην απλούστερη μορφή του, όπως ο σχεδιασμός, η εφοδιαστική και η κατασκευή μικροτσίπ. Ελαφρώς τροποποιημένο, εμφανίζεται ως υποπρόβλημα σε πολλές περιοχές, όπως το DNA sequencing. Σε αυτές τις εφαρμογές, η έννοια της πόλης αντιπροσωπεύει, για παράδειγμα, πελάτες, σημεία συγκόλλησης ή DNA fragments και η έννοια της απόστασης (distance) αντιπροσωπεύει τους χρόνους μετακίνησης ή το κόστος ή ένα μέτρο ομοιότητας μεταξύ DNA fragments. Το TSP εμφανίζεται επίσης στην αστρονομία, καθώς οι αστρονόμοι που παρατηρούν πολλές πηγές θα θέλουν να ελαχιστοποιήσουν το χρόνο που αφιερώνουν τη μετακίνηση του τηλεσκοπίου μεταξύ των πηγών. Σε πολλές εφαρμογές, μπορούν να επιβληθούν πρόσθετοι περιορισμοί, όπως περιορισμένοι πόροι ή χρονικά παράθυρα. (el)
- Das Problem des Handlungsreisenden (auch Botenproblem, Rundreiseproblem, engl. Traveling Salesman Problem oder Traveling Salesperson Problem (TSP)) ist ein kombinatorisches Optimierungsproblem des Operations Research und der theoretischen Informatik. Die Aufgabe besteht darin, eine Reihenfolge für den Besuch mehrerer Orte so zu wählen, dass keine Station außer der ersten mehr als einmal besucht wird, die gesamte Reisestrecke des Handlungsreisenden möglichst kurz und die erste Station gleich der letzten Station ist. Seit seiner ersten Erwähnung als mathematisches Problem im Jahre 1930 haben sich viele Forscher damit befasst und neue Optimierungsverfahren daran entwickelt und erprobt, die momentan auch für andere Optimierungsprobleme eingesetzt werden. Heute steht eine Vielzahl von heuristischen und exakten Methoden zur Verfügung, mit denen auch schwierige Fälle mit mehreren tausend Städten optimal gelöst wurden. Das Problem des Handlungsreisenden tritt schon in seiner Reinform in vielen praktischen Anwendungen auf, beispielsweise in der Tourenplanung, in der Logistik oder im Design von Mikrochips. Noch häufiger tritt es allerdings als Unterproblem auf, wie zum Beispiel bei der Verteilung von Waren, bei der Planung von Touren eines Kunden- oder Pannendienstes oder bei der Genom-Sequenzierung. Dabei sind die Begriffe „Stadt“ und „Entfernung“ nicht wörtlich zu nehmen, vielmehr repräsentieren die Städte beispielsweise zu besuchende Kunden, Bohrlöcher oder DNA-Teilstränge, während Entfernung für Reisezeit, Kosten oder den Grad der Übereinstimmung zweier DNA-Stränge steht. In vielen praktischen Anwendungen müssen zudem Zusatzbedingungen wie Zeitfenster oder eingeschränkte Ressourcen beachtet werden, was die Lösung des Problems erheblich erschwert. Das Problem des Handlungsreisenden ist ein NP-schweres Problem. Unter der bislang unbewiesenen Annahme, dass die Komplexitätsklassen P und NP verschieden sind, gilt demnach, dass kein Algorithmus existiert, der eine kürzeste Rundreise in polynomieller Worst-case-Laufzeit bestimmt. (de)
- El problema del vendedor viajero (problema del vendedor ambulante, problema del agente viajero o problema del viajante, PCP, TSP por sus siglas en inglés, Travelling Salesman Problem) responde a la siguiente pregunta: dada una lista de ciudades y las distancias entre cada par de ellas, ¿cuál es la ruta más corta posible que visita cada ciudad exactamente una vez y al finalizar regresa a la ciudad origen? Este es un problema NP-Hard dentro en la optimización combinatoria, muy importante en investigación operativa y en ciencias de la computación. El problema fue formulado por primera vez en 1930 y es uno de los problemas de optimización más estudiados. Es usado como prueba para muchos métodos de optimización. Aunque el problema es computacionalmente complejo, se conoce gran cantidad de heurísticas y métodos exactos, así que es posible resolver planteamientos concretos del problema desde cien hasta miles de ciudades. El TSP tiene diversas aplicaciones aún en su formulación más simple, tales como: la planificación, la logística y la fabricación de circuitos electrónicos. Un poco modificado, aparece como subproblema en muchos campos como la secuenciación de ADN. En esta aplicación, el concepto de “ciudad” representa, por ejemplo: clientes, puntos de soldadura o fragmentos de ADN y el concepto de “distancia” representa el tiempo de viaje o costo, o una medida de similitud entre los fragmentos de ADN. En muchas aplicaciones, restricciones adicionales como el límite de recurso o las ventanas de tiempo hacen el problema considerablemente difícil. El TSP es un caso especial de los Problemas del Comprador Viajante (travelling purchaser problem). En la teoría de la complejidad computacional, la versión de decisión del TSP (donde, dada una longitud “L”, el objetivo es decidir si el grafo tiene un camino menor o igual que L) pertenece a la clase de los problemas NP-completos. Por tanto, es probable que en el caso peor el tiempo de ejecución para cualquier algoritmo que resuelva el TSP aumente de forma exponencial con respecto al número de ciudades. (es)
- Ikerkuntza operatiboan, saltzaile ibiltariaren ebazkizunak hiri multzo baterako hiri guztiak behin bakarrik, abiapuntura itzuliz, zeharkatzen dituen ibilbide laburrena bilatzen duen ebazkizuna da jatorrian. Planteamendu honetaz gainera, logistikako ebazkizunetarako erabil daitekeena, ebazkizunak beste aplikazio asko ditu, ekoizpen prozesuen antolakuntzan, zirkuituen diseinuan, eta genomaren azterketan esaterako. Ebazkizunaren aldaera ezberdinak daude, esaterako ibilbide luzeeneko ebazkizuna eta hirien arteko distantziak simetrikoak ez direneko ebazkizuna (adibidez, A-B eta B-A distantziak berdinak ez direnean). Ebazkizunaren soluzioa hiri edo puntu multzo txiki baterako erraza den arren, nahikoa baita ibilbide posible guztiak aztertu eta guztira luzera txikiena duena aukeratzea, ebazkizuna oso konplexua da puntu kopurua handia denean. Adibidez, 80 punturako, permutazioen formula erabiliz, ibilbide posible guztien kopurua 80! (80 faktorial) da, unibertsoko atomo guztien kopurua baino handiagoa dena. Konputagailu batek ibilbide baten luzera kalkulatzeko mikrosegundo bakar bat emango balu ere, 3 segundo baino gehixeago beharko luke 10 hirietarako ebazkizunaren soluzioa aurkitzeko, minutu erdia baino gehixeago 11 hirietarako soluzioa aurkitzeko eta 77 146 urte 20 hirietarako soluzioa aurkitzeko. Adibidez, 12 hirien arteko ibilbide posible guztiak 479 milioi baino gehiago dira. deritzon fenomeno honek ekarritako konplexutasuna dela eta, ibilbide posible guztien guztirako distantziak erkatu ordez, ebazpen prozesu laburragoa eskatzen duten heuristika edo soluzio hurbilak edo gutxigorabeherakoak ematen dituzten prozedurak asmatzea. Ebazkizunaren soluzio hurbilak ematen dituen prozedura sinple bat da, non puntu bat bisitatu ondoren bisitatu beharreko hurrengo puntua bisitatu gabe geratzen den puntu gertuena den. Prozedura honek ordea puntuen arteko egiazko ibilbide laburrenetik urrun geratzen den soluzioak askotan ematen dituela egiaztatu da. Hurrengo gertuena algoritmoa algoritmo irenskorra da. (eu)
- En informatique, le problème du voyageur de commerce, ou problème du commis voyageur, est un problème d'optimisation qui consiste à déterminer, étant donné une liste de villes et les distances entre toutes les paires de villes, le plus court circuit qui passe par chaque ville une et une seule fois. Malgré la simplicité de l’énoncé, on ne connaît pas d'algorithme permettant de trouver une solution exacte rapidement dans tous les cas. Plus précisément, on ne connaît pas d'algorithme en temps polynomial, et la version décisionnelle du problème du voyageur de commerce (pour une distance D, existe-t-il un chemin plus court que D passant par toutes les villes et qui termine dans la ville de départ ?) est un problème NP-complet, ce qui est un indice de sa difficulté. C'est un problème algorithmique célèbre, qui a donné lieu à de nombreuses recherches et qui est souvent utilisé comme introduction à l'algorithmique ou à la théorie de la complexité. Il présente de nombreuses applications, que ce soit en planification, en logistique ou dans des domaines plus éloignés, comme la génétique (en remplaçant les villes par des gènes et la distance par la similarité). (fr)
- The travelling salesman problem (also called the travelling salesperson problem or TSP) asks the following question: "Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city exactly once and returns to the origin city?" It is an NP-hard problem in combinatorial optimization, important in theoretical computer science and operations research. The travelling purchaser problem and the vehicle routing problem are both generalizations of TSP. In the theory of computational complexity, the decision version of the TSP (where given a length L, the task is to decide whether the graph has a tour of at most L) belongs to the class of NP-complete problems. Thus, it is possible that the worst-case running time for any algorithm for the TSP increases superpolynomially (but no more than exponentially) with the number of cities. The problem was first formulated in 1930 and is one of the most intensively studied problems in optimization. It is used as a benchmark for many optimization methods. Even though the problem is computationally difficult, many heuristics and exact algorithms are known, so that some instances with tens of thousands of cities can be solved completely and even problems with millions of cities can be approximated within a small fraction of 1%. The TSP has several applications even in its purest formulation, such as planning, logistics, and the manufacture of microchips. Slightly modified, it appears as a sub-problem in many areas, such as DNA sequencing. In these applications, the concept city represents, for example, customers, soldering points, or DNA fragments, and the concept distance represents travelling times or cost, or a similarity measure between DNA fragments. The TSP also appears in astronomy, as astronomers observing many sources will want to minimize the time spent moving the telescope between the sources; in such problems, the TSP can be embedded inside an optimal control problem. In many applications, additional constraints such as limited resources or time windows may be imposed. (en)
- 외판원 문제(外販員問題, 영어: traveling salesman problem) 또는 순회 외판원 문제는 조합 최적화 문제의 일종이다. 줄여서 TSP라고도 쓴다. 이 문제는 NP-난해에 속하며, 흔히 계산 복잡도 이론에서 해를 구하기 어려운 문제의 대표적인 예로 많이 다룬다. (ko)
- Il problema del commesso viaggiatore è il più semplice fra i problemi di instradamento e di gestione dei processi. Viene spesso indicato con il suo nome inglese, traveling salesman problem o traveling salesperson problem, in acronimo TSP. (it)
- 巡回セールスマン問題（じゅんかいセールスマンもんだい、英: traveling salesman problem、TSP）は、都市の集合と各2都市間の移動コスト（たとえば距離）が与えられたとき、全ての都市をちょうど一度ずつ巡り出発地に戻る巡回路のうちで総移動コストが最小のものを求める（セールスマンが所定の複数の都市を1回だけ巡回する場合の最短経路を求める）組合せ最適化問題である。 (ja)
- Het handelsreizigersprobleem is een van de bekendste problemen in de informatica en het operationele onderzoek. Het wordt vaak TSP genoemd, een afkorting van de Engelse benaming travelling salesman problem. Het kan als volgt worden geformuleerd: Gegeven steden samen met de afstand tussen ieder paar van deze steden, vind dan de kortste weg die een keer langs iedere stad komt en eindigt bij de eerste stad. Het probleem is een onderdeel van de grafentheorie. Formeel is de invoer van het probleem een volledige, gewogen graaf. De oplossing van het probleem is een pad door de graaf dat iedere knoop precies één keer aandoet, begint en eindigt in dezelfde knoop, en een minimale totale lengte heeft. De eis dat elke knoop precies één keer doorlopen wordt, zorgt ervoor dat elke rondreis hetzelfde aantal stappen bevat, wat mogelijk is omdat de invoer een volledige graaf is, waarin elke knoop in één stap vanuit elke andere knoop bereikt kan worden. Elke samenhangende graaf kan volledig worden gemaakt door een (gewogen) transitieve afsluiting uit te voeren. (nl)
- Problem komiwojażera (ang. travelling salesman problem, TSP) – zagadnienie optymalizacyjne, polegające na znalezieniu minimalnego cyklu Hamiltona w pełnym grafie ważonym. Nazwa pochodzi od typowej ilustracji problemu, przedstawiającej go z punktu widzenia wędrownego sprzedawcy (komiwojażera): dane jest n miast, które komiwojażer ma odwiedzić, oraz odległość / cena podróży / czas podróży pomiędzy każdą parą miast. Celem jest znalezienie najkrótszej / najtańszej / najszybszej drogi łączącej wszystkie miasta, zaczynającej się i kończącej się w określonym punkcie. Symetryczny problem komiwojażera (STSP) polega na tym, że dla dowolnych miast A i B odległość z A do B jest taka sama jak z B do A. W asymetrycznym problemie komiwojażera (ATSP) odległości te mogą być różne. Główną trudnością problemu jest duża liczba danych do analizy. W przypadku symetrycznego problemu komiwojażera dla n miast liczba kombinacji wynosi , tak więc dla 20 miast uzyskujemy wynik Rozwinięciem problemu komiwojażera jest problem marszrutyzacji. (pl)
- O Problema do Caixeiro Viajante (PCV) é um problema que tenta determinar a menor rota para percorrer uma série de cidades (visitando uma única vez cada uma delas), retornando à cidade de origem. Ele é um problema de otimização NP-difícil inspirado na necessidade dos vendedores em realizar entregas em diversos locais (as cidades) percorrendo o menor caminho possível, reduzindo o tempo necessário para a viagem e os possíveis custos com transporte e combustível. (pt)
- Handelsresandeproblemet (engelska: the Traveling Salesman Problem, TSP) är ett matematiskt problem inom den del av optimeringsläran som behandlar optimering i grafer. Enkelt uttryckt går problemet ut på att hitta den kortaste vägen för en som ska besöka en uppsättning städer. Det kan emellertid istället gälla den snabbaste vägen eller den billigaste eller optimum enligt något annat kriterium. Frågeställningen är vanlig i GIS-analyser som hanterar ruttplaneringsproblem och nätverksanalyser. Handelsresandeproblemet formulerades första gången på 1850-talet av matematikerna William Rowan Hamilton och . (sv)
- Зада́ча комівояже́ра (комівояжер — бродячий торговець; англ. Travelling Salesman Problem, TSP; нім. Problem des Handlungsreisenden) полягає у знаходженні найвигіднішого маршруту, що проходить через вказані міста хоча б по одному разу. В умовах завдання вказуються критерій вигідності маршруту (найкоротший, найдешевший, сукупний критерій тощо) і відповідні матриці відстаней, вартості тощо. Зазвичай задано, що маршрут повинен проходити через кожне місто тільки один раз, в такому випадку розв'язок знаходиться серед гамільтонових циклів. Існує маса різновидів узагальненої постановки задачі, зокрема геометрична задача комівояжера (коли матриця відстаней відображає відстані між точками на площині), трикутна задача комівояжера (коли на матриці вартостей виконується нерівність трикутника), симетрична та асиметрична задачі комівояжера. Прості методи розв'язання задачі комівояжера: повний лексичний перебір, жадібні алгоритми (метод найближчого сусіда), метод включення найближчого міста, метод найдешевшого включення, метод мінімального кістяка дерева. На практиці застосовують різні модифікації ефективніших методів: метод гілок і меж і метод генетичних алгоритмів, а так само алгоритм мурашиної колонії. Всі ефективні (такі, що скорочують повний перебір) методи розв'язання задачі комівояжера — евристичні. У більшості евристичних методів знаходиться не найефективніший маршрут, а наближений розв'язок. Користуються популярністю так звані any-time алгоритми, тобто алгоритми, що поступово покращують деякий поточний наближений розв'язок. Задача комівояжера — NP-повна. Часто на ній проводять випробування нових підходів до евристичного скорочення повного перебору. (uk)
- Задача коммивояжёра (или TSP от англ. travelling salesman problem) — одна из самых известных задач комбинаторной оптимизации, заключающаяся в поиске самого выгодного , проходящего через указанные города хотя бы по одному разу с последующим возвратом в исходный город. В условиях задачи указываются критерий выгодности маршрута (кратчайший, самый дешёвый, совокупный критерий и тому подобное) и соответствующие матрицы расстояний, стоимости и тому подобного. Как правило, указывается, что маршрут должен проходить через каждый город только один раз — в таком случае выбор осуществляется среди гамильтоновых циклов. Существует несколько частных случаев общей постановки задачи, в частности, (также называемая планарной или евклидовой, когда матрица расстояний отражает расстояния между точками на плоскости), (когда на матрице стоимостей выполняется неравенство треугольника), и . Также существует обобщение задачи, так называемая обобщённая задача коммивояжёра. Оптимизационная постановка задачи относится к классу NP-трудных задач, впрочем, как и большинство её частных случаев. Версия «decision problem» (то есть такая, в которой ставится вопрос, существует ли маршрут не длиннее, чем заданное значение k) относится к классу NP-полных задач. Задача коммивояжёра относится к числу трансвычислительных: уже при относительно небольшом числе городов (>66) она не может быть решена методом перебора вариантов никакими теоретически мыслимыми компьютерами за время, меньшее нескольких миллиардов лет. (ru)
- （英語：Travelling salesman problem, TSP）是组合优化中的一个NP困难问题，在运筹学和理论计算机科学中非常重要。问题内容为“给定一系列城市和每对城市之间的距离，求解访问每一座城市一次并回到起始城市的最短回路。” TSP是与车辆路径问题的一种特殊情况。 作为计算复杂性理论中的一个典型的判定性问题，TSP的一个版本是给定一个图和长度 L，要求回答图中是否存在比 L 短的回路（英语：circuit或tour）。该问题被划分为NP完全问题。已知TSP算法最坏情况下的时间复杂度随着城市数量的增多而成超多项式（可能是）级别增长。 问题在1930年首次被形式化，并且是在最优化中研究最深入的问题之一。许多优化方法都用它作为一个基准。尽管问题在计算上很困难，但已经有了大量的启发式和精确方法，因此可以完全求解城市数量上万的实例，并且甚至能在误差1%范围内估计上百万个城市的问题。 甚至纯粹形式的TSP都有若干应用，如企划、物流、芯片制造。稍作修改，就是DNA测序等许多领域的一个子问题。在这些应用中，“城市”的概念用来表示客户、焊接点或DNA片段，而“距离”的概念表示旅行时间或成本或DNA片段之间的相似性度量。TSP还用在天文学中，观察很多光源的天文学家會希望减少在不同光源之间转动望远镜的时间。在许多应用場景中（如资源或时间窗口有限等等），可能会需要加入额外的约束條件。 (zh)
|
| rdfs:comment
|
- مسألة البائع المتجول (بالإنجليزية: Travelling salesman problem) هي إحدى أهم المسائل في علم التعقيد الحسابي ونظرية المخططات، ونص المسألة هو: وصل تاجر إلى دولة فيها n مدينة ويريد البائع أن يزور كل مدينة في الدولة مرة واحدة فقط وبأقل وقت سفر بين المدن. بالرغم من بساطة عرض المسألة فقد تبين أن هذه المسألة هي إحدى المسائل التي لا يُعرف لها خوارزمية تحلها بسرعة، أي أنه إذا كان هناك فقط 50 مدينة حينها يتطلب الأمر أكثر من ألف عام لايجاد الحل ! وقد وجدت هذه المسألة طريقها لنظرية التعقيد الحسابي حين أدرجها كارب في قائمته ال-21 لمسائل NP كاملة. (ar)
- Problém obchodního cestujícího (anglicky Travelling Salesman Problem – TSP) je obtížný diskrétní optimalizační problém, matematicky vyjadřující a zobecňující úlohu nalezení nejkratší možné cesty procházející všemi vrcholy ohodnoceného grafu. (cs)
- 외판원 문제(外販員問題, 영어: traveling salesman problem) 또는 순회 외판원 문제는 조합 최적화 문제의 일종이다. 줄여서 TSP라고도 쓴다. 이 문제는 NP-난해에 속하며, 흔히 계산 복잡도 이론에서 해를 구하기 어려운 문제의 대표적인 예로 많이 다룬다. (ko)
- Il problema del commesso viaggiatore è il più semplice fra i problemi di instradamento e di gestione dei processi. Viene spesso indicato con il suo nome inglese, traveling salesman problem o traveling salesperson problem, in acronimo TSP. (it)
- 巡回セールスマン問題（じゅんかいセールスマンもんだい、英: traveling salesman problem、TSP）は、都市の集合と各2都市間の移動コスト（たとえば距離）が与えられたとき、全ての都市をちょうど一度ずつ巡り出発地に戻る巡回路のうちで総移動コストが最小のものを求める（セールスマンが所定の複数の都市を1回だけ巡回する場合の最短経路を求める）組合せ最適化問題である。 (ja)
- O Problema do Caixeiro Viajante (PCV) é um problema que tenta determinar a menor rota para percorrer uma série de cidades (visitando uma única vez cada uma delas), retornando à cidade de origem. Ele é um problema de otimização NP-difícil inspirado na necessidade dos vendedores em realizar entregas em diversos locais (as cidades) percorrendo o menor caminho possível, reduzindo o tempo necessário para a viagem e os possíveis custos com transporte e combustível. (pt)
- （英語：Travelling salesman problem, TSP）是组合优化中的一个NP困难问题，在运筹学和理论计算机科学中非常重要。问题内容为“给定一系列城市和每对城市之间的距离，求解访问每一座城市一次并回到起始城市的最短回路。” TSP是与车辆路径问题的一种特殊情况。 作为计算复杂性理论中的一个典型的判定性问题，TSP的一个版本是给定一个图和长度 L，要求回答图中是否存在比 L 短的回路（英语：circuit或tour）。该问题被划分为NP完全问题。已知TSP算法最坏情况下的时间复杂度随着城市数量的增多而成超多项式（可能是）级别增长。 问题在1930年首次被形式化，并且是在最优化中研究最深入的问题之一。许多优化方法都用它作为一个基准。尽管问题在计算上很困难，但已经有了大量的启发式和精确方法，因此可以完全求解城市数量上万的实例，并且甚至能在误差1%范围内估计上百万个城市的问题。 甚至纯粹形式的TSP都有若干应用，如企划、物流、芯片制造。稍作修改，就是DNA测序等许多领域的一个子问题。在这些应用中，“城市”的概念用来表示客户、焊接点或DNA片段，而“距离”的概念表示旅行时间或成本或DNA片段之间的相似性度量。TSP还用在天文学中，观察很多光源的天文学家會希望减少在不同光源之间转动望远镜的时间。在许多应用場景中（如资源或时间窗口有限等等），可能会需要加入额外的约束條件。 (zh)
- El problema del viatjant de comerç és el problema d'optimització de trajectòries donat per l'enunciat següent: donat un conjunt de nodes, es tracta de trobar l'ordre de visites a seguir per tal de definir una trajectòria que passi un sol cop per a cada node i de manera que la distància total recorreguda sigui la més curta possible. S'usa en el sector públic per al disseny de xarxes de serveis i de transports i la planificació logística pública i privada. Es pot resoldre a mà amb la teoria de grafs i algunes matrius, però és més ràpid, sobretot si intervenen molts nodes o punts de pas, fer-ho amb un senzill programa informàtic. Es va plantejar, com el seu nom indica, per a planificar la millor ruta que hauria de fer un comerciant que volgués passar a veure una llista de clients. A més d'en (ca)
- Το πρόβλημα του μετακινούμενου πωλητή (που ονομάζεται επίσης και πρόβλημα πλανόδιου πωλητή ή TSP) θέτει την ακόλουθη ερώτηση: "Λαμβάνοντας υπόψη μια λίστα με τις πόλεις και τις αποστάσεις μεταξύ κάθε ζεύγους πόλεων, ποια είναι η συντομότερη διαδρομή που επισκέπτεται κάθε πόλη και επιστρέφει την πόλη προέλευσης; " Πρόκειται για ένα NP-hardness πρόβλημα στη συνδυαστική βελτιστοποίηση, σημαντικό στην έρευνα των λειτουργιών και στη θεωρητική επιστήμη των υπολογιστών. Το πρόβλημα του αγοραστή που ταξιδεύει και το πρόβλημα της δρομολόγησης του οχήματος είναι και τα δύο γενικεύσεις του TSP. (el)
- Das Problem des Handlungsreisenden (auch Botenproblem, Rundreiseproblem, engl. Traveling Salesman Problem oder Traveling Salesperson Problem (TSP)) ist ein kombinatorisches Optimierungsproblem des Operations Research und der theoretischen Informatik. Die Aufgabe besteht darin, eine Reihenfolge für den Besuch mehrerer Orte so zu wählen, dass keine Station außer der ersten mehr als einmal besucht wird, die gesamte Reisestrecke des Handlungsreisenden möglichst kurz und die erste Station gleich der letzten Station ist. (de)
- Ikerkuntza operatiboan, saltzaile ibiltariaren ebazkizunak hiri multzo baterako hiri guztiak behin bakarrik, abiapuntura itzuliz, zeharkatzen dituen ibilbide laburrena bilatzen duen ebazkizuna da jatorrian. Planteamendu honetaz gainera, logistikako ebazkizunetarako erabil daitekeena, ebazkizunak beste aplikazio asko ditu, ekoizpen prozesuen antolakuntzan, zirkuituen diseinuan, eta genomaren azterketan esaterako. Ebazkizunaren aldaera ezberdinak daude, esaterako ibilbide luzeeneko ebazkizuna eta hirien arteko distantziak simetrikoak ez direneko ebazkizuna (adibidez, A-B eta B-A distantziak berdinak ez direnean). (eu)
- El problema del vendedor viajero (problema del vendedor ambulante, problema del agente viajero o problema del viajante, PCP, TSP por sus siglas en inglés, Travelling Salesman Problem) responde a la siguiente pregunta: dada una lista de ciudades y las distancias entre cada par de ellas, ¿cuál es la ruta más corta posible que visita cada ciudad exactamente una vez y al finalizar regresa a la ciudad origen? Este es un problema NP-Hard dentro en la optimización combinatoria, muy importante en investigación operativa y en ciencias de la computación. (es)
- En informatique, le problème du voyageur de commerce, ou problème du commis voyageur, est un problème d'optimisation qui consiste à déterminer, étant donné une liste de villes et les distances entre toutes les paires de villes, le plus court circuit qui passe par chaque ville une et une seule fois. (fr)
- The travelling salesman problem (also called the travelling salesperson problem or TSP) asks the following question: "Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city exactly once and returns to the origin city?" It is an NP-hard problem in combinatorial optimization, important in theoretical computer science and operations research. The travelling purchaser problem and the vehicle routing problem are both generalizations of TSP. (en)
- Het handelsreizigersprobleem is een van de bekendste problemen in de informatica en het operationele onderzoek. Het wordt vaak TSP genoemd, een afkorting van de Engelse benaming travelling salesman problem. Het kan als volgt worden geformuleerd: Gegeven steden samen met de afstand tussen ieder paar van deze steden, vind dan de kortste weg die een keer langs iedere stad komt en eindigt bij de eerste stad. Het probleem is een onderdeel van de grafentheorie. (nl)
- Problem komiwojażera (ang. travelling salesman problem, TSP) – zagadnienie optymalizacyjne, polegające na znalezieniu minimalnego cyklu Hamiltona w pełnym grafie ważonym. Nazwa pochodzi od typowej ilustracji problemu, przedstawiającej go z punktu widzenia wędrownego sprzedawcy (komiwojażera): dane jest n miast, które komiwojażer ma odwiedzić, oraz odległość / cena podróży / czas podróży pomiędzy każdą parą miast. Celem jest znalezienie najkrótszej / najtańszej / najszybszej drogi łączącej wszystkie miasta, zaczynającej się i kończącej się w określonym punkcie. (pl)
- Задача коммивояжёра (или TSP от англ. travelling salesman problem) — одна из самых известных задач комбинаторной оптимизации, заключающаяся в поиске самого выгодного , проходящего через указанные города хотя бы по одному разу с последующим возвратом в исходный город. В условиях задачи указываются критерий выгодности маршрута (кратчайший, самый дешёвый, совокупный критерий и тому подобное) и соответствующие матрицы расстояний, стоимости и тому подобного. Как правило, указывается, что маршрут должен проходить через каждый город только один раз — в таком случае выбор осуществляется среди гамильтоновых циклов. Существует несколько частных случаев общей постановки задачи, в частности, (также называемая планарной или евклидовой, когда матрица расстояний отражает расстояния между точками на плос (ru)
- Handelsresandeproblemet (engelska: the Traveling Salesman Problem, TSP) är ett matematiskt problem inom den del av optimeringsläran som behandlar optimering i grafer. Enkelt uttryckt går problemet ut på att hitta den kortaste vägen för en som ska besöka en uppsättning städer. Det kan emellertid istället gälla den snabbaste vägen eller den billigaste eller optimum enligt något annat kriterium. Frågeställningen är vanlig i GIS-analyser som hanterar ruttplaneringsproblem och nätverksanalyser. (sv)
- Зада́ча комівояже́ра (комівояжер — бродячий торговець; англ. Travelling Salesman Problem, TSP; нім. Problem des Handlungsreisenden) полягає у знаходженні найвигіднішого маршруту, що проходить через вказані міста хоча б по одному разу. В умовах завдання вказуються критерій вигідності маршруту (найкоротший, найдешевший, сукупний критерій тощо) і відповідні матриці відстаней, вартості тощо. Зазвичай задано, що маршрут повинен проходити через кожне місто тільки один раз, в такому випадку розв'язок знаходиться серед гамільтонових циклів. (uk)
|
