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 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.

Property Value
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 dóna 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 zadanými body na mapě. (cs)
  • 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)
  • 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 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 many applications, additional constraints such as limited resources or time windows may be imposed. (en)
  • , 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)
  • El problema del vendedor viajero, problema del vendedor ambulante, problema del agente viajero o problema del viajante (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 la investigación de operaciones y en la ciencia 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, una gran cantidad de heurísticas y métodos exactos son conocidos, de manera que, algunas instancias desde cien hasta miles de ciudades pueden ser resueltas. El TSP tiene diversas aplicaciones aún en su formulación más simple, tales como: la planificación, la logística y en la fabricación de circuitos electrónicos. Un poco modificado, aparece como: un sub-problema en muchas áreas, como en la secuencia 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, dado un largo “L”, la tarea es decidir cuál grafo tiene un camino menor 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)
  • En informatique, le problème du voyageur de commerce, ou problème du commis voyageur, est un problème d'optimisation qui, étant donné une liste de villes, et des distances entre toutes les paires de villes, détermine un plus court chemin qui visite chaque ville une et une seule fois et qui termine dans la ville de départ. Malgré la simplicité de son énoncé, il s'agit d'un problème d'optimisation pour lequel on ne connait pas d'algorithme permettant de trouver une solution exacte rapidement dans tous les cas. Plus précisément, on ne connait pas d'algorithme en temps polynomial, et sa version décisionnelle (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 généré beaucoup de 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 et en logistique, ou bien 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)
  • Il problema del commesso viaggiatore è il più semplice fra i problemi di routing e di scheduling. Esso viene spesso indicato con il suo nome inglese, Travelling Salesman Problem, da cui la sigla TSP. (it)
  • 巡回セールスマン問題(じゅんかいセールスマンもんだい、英: traveling salesman problem、TSP)は、都市の集合と各2都市間の移動コスト(たとえば距離)が与えられたとき、全ての都市をちょうど一度ずつ巡り出発地に戻る巡回路のうちで総移動コストが最小のものを求める(セールスマンが所定の複数の都市を1回だけ巡回する場合の最短経路を求める)組合せ最適化問題である。 (ja)
  • 외판원 문제(外販員問題, 영어: traveling salesman problem) 또는 순회 외판원 문제는 조합 최적화 문제의 일종이다. 줄여서 TSP라고도 쓴다. 이 문제는 NP-난해에 속하며, 흔히 계산 복잡도 이론에서 해를 구하기 어려운 문제의 대표적인 예로 많이 다룬다. (ko)
  • 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: Het probleem is een onderdeel van de grafentheorie. Het algoritme dat de berekening uitvoert om deze weg te vinden wordt bijvoorbeeld bij het ontwerpen van printplaten gebruikt. De rechtstreekse manier om dit op te lossen is alle mogelijke routes na te gaan en ze te vergelijken, maar aangezien het aantal combinaties bedraagt wordt dit snel onmogelijk voor meer dan ca. 25 steden. Er bestaan wel efficiënte algoritmes die een goede oplossing geven, maar of deze de beste is valt niet met zekerheid te zeggen. In 1998 berekenden wiskundigen van de Universiteit van Princeton de exacte oplossing voor 15.112 steden in Duitsland. De oplossing kostte 22,6 jaar computertijdequivalent op een enkele Alpha-processor van 500 MHz. Maar de berekeningen werden op een netwerk van 110 processors uitgevoerd. In mei 2004 is de oplossing voor het handelsreizigersprobleem met een afstand van ongeveer 72.500 km gevonden voor de 24.978 plaatsen in Zweden. Het handelsreizigersprobleem is NP-moeilijk. De beslissingsvariant van het probleem (gegeven de onderlinge afstanden tussen de steden, bestaat er een oplossing die korter is dan een gegeven maximum afstand?) is NP-volledig. Het probleem lijkt op het Chinese postbodeprobleem. Bij het handelsreizigersprobleem moeten echter alle plaatsen worden aangedaan, terwijl bij het Chinese postbodeprobleem alle wegen tussen de verschillende plaatsen moeten zijn gebruikt. Het Chinese postbodeprobleem is niet NP-moeilijk. (nl)
  • 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)
  • 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)
  • Handelsresandeproblemet (engelska: the Traveling Salesman Problem, TSP) är ett så kallat optimeringsproblem 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)
  • (最短路径问题)(英語:travelling salesman problem, TSP)是这样一个问题:给定一系列城市和每对城市之间的距离,求解访问每一座城市一次并回到起始城市的最短回路。它是组合优化中的一个NP困难问题,在运筹学和理论计算机科学中非常重要。 TSP是与车辆路径问题的一种特殊情况。 作为计算复杂性理论中的一个典型的判定性问题,TSP的一个版本是给定一个图和长度 L,要求回答图中是否存在比 L 短的回路(英语:circuit或tour)。该问题被划分为NP完全问题。已知TSP算法最坏情况下的随着城市数量的增多而成超多项式(可能是)级别增长。 问题在1930年首次被形式化,并且是在最优化中研究最深入的问题之一。许多优化方法都用它作为一个基准。尽管问题在计算上很困难,但已经有了大量的启发式和精确方法,因此可以完全求解城市数量上万的实例,并且甚至能在误差1%范围内估计上百万个城市的问题。 甚至纯粹形式的TSP都有若干应用,如企划、物流、芯片制造。稍作修改,就是DNA测序等许多领域的一个子问题。在这些应用中,“城市”的概念用来表示客户、焊接点或DNA片段,而“距离”的概念表示旅行时间或成本或DNA片段之间的相似性度量。TSP还用在天文学中,观察很多源的天文学家希望减少在源之间转动望远镜的时间。许多应用(如资源或时间窗口有限)中,可能会加入额外的约束。 (zh)
dbo:thumbnail
dbo:wikiPageExternalLink
dbo:wikiPageID
  • 31248 (xsd:integer)
dbo:wikiPageLength
  • 81341 (xsd:integer)
dbo:wikiPageRevisionID
  • 985440031 (xsd:integer)
dbo:wikiPageWikiLink
dbp:date
  • 2013-12-17 (xsd:date)
dbp:title
  • Traveling Salesman Problem (en)
dbp:url
dbp:wikiPageUsesTemplate
dct:isPartOf
dct:subject
rdf:type
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 zadanými body na mapě. (cs)
  • Il problema del commesso viaggiatore è il più semplice fra i problemi di routing e di scheduling. Esso viene spesso indicato con il suo nome inglese, Travelling Salesman Problem, da cui la sigla TSP. (it)
  • 巡回セールスマン問題(じゅんかいセールスマンもんだい、英: traveling salesman problem、TSP)は、都市の集合と各2都市間の移動コスト(たとえば距離)が与えられたとき、全ての都市をちょうど一度ずつ巡り出発地に戻る巡回路のうちで総移動コストが最小のものを求める(セールスマンが所定の複数の都市を1回だけ巡回する場合の最短経路を求める)組合せ最適化問題である。 (ja)
  • 외판원 문제(外販員問題, 영어: traveling salesman problem) 또는 순회 외판원 문제는 조합 최적화 문제의 일종이다. 줄여서 TSP라고도 쓴다. 이 문제는 NP-난해에 속하며, 흔히 계산 복잡도 이론에서 해를 구하기 어려운 문제의 대표적인 예로 많이 다룬다. (ko)
  • 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)
  • 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)
  • 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 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)
  • , 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 (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 la investigación de operaciones y en la ciencia 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, étant donné une liste de villes, et des distances entre toutes les paires de villes, détermine un plus court chemin qui visite chaque ville une et une seule fois et qui termine dans la ville de départ. (fr)
  • 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)
  • 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: Het handelsreizigersprobleem is NP-moeilijk. De beslissingsvariant van het probleem (gegeven de onderlinge afstanden tussen de steden, bestaat er een oplossing die korter is dan een gegeven maximum afstand?) is NP-volledig. (nl)
  • Handelsresandeproblemet (engelska: the Traveling Salesman Problem, TSP) är ett så kallat optimeringsproblem 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)
rdfs:label
  • Travelling salesman problem (en)
  • مسألة البائع المتجول (ar)
  • Problema del viatjant de comerç (ca)
  • Problém obchodního cestujícího (cs)
  • Problem des Handlungsreisenden (de)
  • Problema del viajante (es)
  • Saltzaile ibiltariaren ebazkizun (eu)
  • Problème du voyageur de commerce (fr)
  • Problema del commesso viaggiatore (it)
  • 巡回セールスマン問題 (ja)
  • 외판원 문제 (ko)
  • Problem komiwojażera (pl)
  • Handelsreizigersprobleem (nl)
  • Problema do caixeiro-viajante (pt)
  • Задача комівояжера (uk)
  • Handelsresandeproblemet (sv)
  • 旅行推销员问题 (zh)
owl:sameAs
skos:closeMatch
prov:wasDerivedFrom
foaf:depiction
foaf:isPrimaryTopicOf
is dbo:wikiPageDisambiguates of
is dbo:wikiPageRedirects of
is dbo:wikiPageWikiLink of
is foaf:primaryTopic of