About: Travelling salesman problem     Goto   Sponge   NotDistinct   Permalink

An Entity of Type : yago:WikicatNP-completeProblems, within Data Space : dbpedia.org associated with source document(s)
QRcode icon
http://dbpedia.org/describe/?url=http%3A%2F%2Fdbpedia.org%2Fresource%2FTravelling_salesman_problem

The travelling salesman problem (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 operations research and theoretical computer science. TSP is a special case of the travelling purchaser problem and the vehicle routing problem.

AttributesValues
rdf:type
rdfs:label
  • Travelling salesman problem
  • مسألة البائع المتجول
  • Problem des Handlungsreisenden
  • Problema del viajante
  • Problème du voyageur de commerce
  • Problema del commesso viaggiatore
  • 巡回セールスマン問題
  • Handelsreizigersprobleem
  • Problem komiwojażera
  • Problema do caixeiro-viajante
  • Задача коммивояжёра
  • 旅行推销员问题
rdfs:comment
  • مسألة البائع المتجول (بالإنجليزية: Travelling salesman problem) هي إحدى أهم المسائل في علم التعقيد الحسابي ونظرية المخططات، ونص المسألة هو : وصل تاجر إلى دولة فيها n مدينة ويريد البائع أن يزور كل مدينة في الدولة مرة واحدة فقط وبأقل وقت سفر بين المدن. بالرغم من بساطة عرض المسألة فقد تبين أن هذه المسألة هي أحد المسائل التي لا يُعرف لها خوارزمية تحلها بسرعة, أي أنه اذا كان هناك فقط 50 مدينة حينها يتطلب الأمر أكثر من ألف عام لايجاد الحل ! وقد وجدت هذه المسألة طريقها لنظرية التعقيد الحسابي حين أدرجها كارب في قائمته ال-21 لمسائل NP كاملة.
  • 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.
  • 巡回セールスマン問題(じゅんかいセールスマンもんだい、英: traveling salesman problem、TSP)は、都市の集合と各2都市間の移動コスト(たとえば距離)が与えられたとき、全ての都市をちょうど一度ずつ巡り出発地に戻る巡回路の総移動コストが最小のものを求める(セールスマンが所定の複数の都市を1回だけ巡回する場合の最短経路を求める)組合せ最適化問題である。
  • 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.
  • 旅行推销员问题(英语:Travelling salesman problem, TSP)是这样一个问题:给定一系列城市和每对城市之间的距离,求解访问每一座城市一次并回到起始城市的最短回路。它是组合优化中的一个NP困难问题,在运筹学和理论计算机科学中非常重要。 TSP是旅行购买者问题与车辆路径问题的一种特殊情况。 在计算复杂性理论中,TSP的做决定版本(其中,给定长度 L,任务是决定图中是否有路径比 L 还要短)属于NP完全问题。因此随着城市数量的增多,任何TSP算法最坏情况下的运行时间都有可能随着城市数量的增多超多项式(可能是指数)级别增长。 问题在1930年首次被形式化,并且是在最优化中研究最深入的问题之一。许多优化方法都用它作为一个基准。尽管问题在计算上很困难,但已经有了大量的启发式和精确方法,因此可以完全求解城市数量上万的实例,并且甚至能在误差1%范围内估计上百万个城市的问题。 甚至纯粹形式的TSP都有若干应用,如企划、物流、芯片制造。稍作修改,就是DNA测序等许多领域的一个子问题。在这些应用中,“城市”的概念用来表示客户、焊接点或DNA片段,而“距离”的概念表示旅行时间或成本或DNA片段之间的相似性度量。TSP还用在天文学中,观察很多源的天文学家希望减少在源之间转动望远镜的时间。许多应用(如资源或时间窗口有限)中,可能会加入额外的约束。
  • The travelling salesman problem (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 operations research and theoretical computer science. TSP is a special case of the travelling purchaser problem and the vehicle routing problem.
  • 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 die gesamte Reisestrecke des Handlungsreisenden möglichst kurz und die erste Station gleich der letzten Station ist.
  • El Problema del Agente Viajero (TSP por sus siglas en inglés) o problema del viajante, 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 regresa a la ciudad origen? Este es un problema NP-duro dentro en la optimización combinatoria, muy importante en la investigación de operaciones y en la ciencia de la computación.
  • 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.
  • Het handelsreizigersprobleem (TSP, travelling salesman problem) is een van de bekendste problemen in de computerwetenschap en operationeel onderzoek. Het kan als volgt worden geformuleerd: Als er n steden gegeven zijn die een handelsreiziger moet bezoeken, samen met de afstand tussen ieder paar van deze steden, vind dan de kortste weg die kan worden gebruikt, waarbij iedere stad precies één keer wordt bezocht. Het probleem is een onderdeel van de grafentheorie.
  • 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.
  • Задача коммивояжёра (англ. Travelling salesman problem, сокращённо TSP) — одна из самых известных задач комбинаторной оптимизации, заключающаяся в отыскании самого выгодного маршрута, проходящего через указанные города хотя бы по одному разу с последующим возвратом в исходный город. В условиях задачи указываются критерий выгодности маршрута (кратчайший, самый дешёвый, совокупный критерий и тому подобное) и соответствующие матрицы расстояний, стоимости и тому подобного. Как правило, указывается, что маршрут должен проходить через каждый город только один раз — в таком случае выбор осуществляется среди гамильтоновых циклов. Существует несколько частных случаев общей постановки задачи, в частности геометрическая задача коммивояжёра (также называемая планарной или евклидовой, когда матрица рас
sameAs
dct:subject
Wikipage page ID
Wikipage revision ID
Link from a Wikipage to another Wikipage
Faceted Search & Find service v1.17_git39 as of Aug 09 2019


Alternative Linked Data Documents: PivotViewer | iSPARQL | ODE     Content Formats:       RDF       ODATA       Microdata      About   
This material is Open Knowledge   W3C Semantic Web Technology [RDF Data] Valid XHTML + RDFa
OpenLink Virtuoso version 07.20.3235 as of Sep 1 2020, on Linux (x86_64-generic-linux-glibc25), Single-Server Edition (61 GB total memory)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2020 OpenLink Software