Longest path problem (original) (raw)
在图论和理论计算机科学中，最长路径问题是指在给定的图中找出长度最长的道路。一条不具有任何重复顶点的路径被称为简单路径。无权图中路径的长度就是边的数量，而有权图中路径长度是边权重之和。不同的是，与此相反的最短路径问题（不含负权环）可以在多项式时间内解决。而最长路径问题是NP困难的，这意味着除非P = NP，否则对应于任意的图，没有办法在多项式时间内解决该问题。更强的结果表明这个问题也難以近似地得出答案。但是，有一个线性时间的方法可以用于有向无环图，这对于发现调度问题中的关键路径有重要的作用。
| Property | Value |
|---|---|
| dbo:abstract | En teoria de grafs i ciència computacional teòrica, el problema del camí més llarg és el problema de trobar un camí simple de màxima longitud possible en un determinat graf. Un camí s'anomena simple si no té cap vèrtex repetit; la longitud d'un camí es pot mesurar pel seu nombre d'arestes, o (en grafs ponderats) per la suma dels pesos de les seves arestes. A diferència del problema del camí més curt, que es pot solucionar en temps polinòmic en grafs sense cicles negatius, aquest problema és NP-complet, la qual cosa vol dir que la solució òptima no es pot trobar a temps polinòmic a menys que P = NP. El problema del camí més llarg té una solució de programació dinàmica eficient en un graf dirigit acíclic utilitzant . També es pot solucionar en un graf dirigit acíclic invertint els pesos i utilitzant l'algorisme de Bellman-Ford (aquest enfocament no funciona en general perquè crea cicles de pes negatiu). (ca) Die Aufgabe, den einfachen Weg maximaler Länge in einem gegebenen Graphen zu finden, bezeichnet man in der Graphentheorie und der theoretischen Informatik als longest path problem (englisch für Problem des längsten Weges). Ein Weg heißt einfach, wenn er keinen Knoten mehrfach enthält. Die Länge des Weges kann auf zwei Arten gemessen werden: entweder durch die Anzahl der Kanten oder (in einem gewichteten Graphen) durch die Summe der Gewichte seiner Kanten. Im Gegensatz zum Problem des kürzesten Weges, welches sich in polynomieller Laufzeit lösen lässt, gehört das Problem des längsten Weges zu der Gruppe der NP-schweren Probleme. Dies bedeutet, dass es sich nicht in polynomieller Laufzeit lösen lässt, außer wenn P=NP wäre. Es kann gezeigt werden, dass auch eine Approximation schwierig ist.Das Problem kann jedoch für gerichtete, nicht-zyklische Graphen mithilfe einer topologischen Sortierung in linearer Zeit gelöst werden. Ein wichtiges Anwendungsgebiet ist das Finden des kritischen Weges in Planungsaufgaben. (de) En teoría de grafos, el problema del camino más largo es, dado un grafo, encontrar un camino simple de longitud máxima. A diferencia del problema del camino más corto, que se puede solucionar en tiempo polinómico en grafos sin ciclos negativos, este problema es NP-completo, lo que quiere decir que la solución óptima no se puede encontrar en tiempo polinómico a menos que P=NP. El problema del camino más largo tiene una solución de programación dinámica eficiente en un grafo dirigido acíclico utilizando ordenamiento topológico. También se puede solucionar en un grafo dirigido acíclico invirtiendo los pesos y utilizando el algoritmo de Bellman-Ford(este enfoque no funciona en general porque crea ciclos de peso negativo). * Datos: Q2916352 (es) In graph theory and theoretical computer science, the longest path problem is the problem of finding a simple path of maximum length in a given graph. A path is called simple if it does not have any repeated vertices; the length of a path may either be measured by its number of edges, or (in weighted graphs) by the sum of the weights of its edges. In contrast to the shortest path problem, which can be solved in polynomial time in graphs without negative-weight cycles, the longest path problem is NP-hard and the decision version of the problem, which asks whether a path exists of at least some given length, is NP-complete. This means that the decision problem cannot be solved in polynomial time for arbitrary graphs unless P = NP. Stronger hardness results are also known showing that it is difficult to approximate. However, it has a linear time solution for directed acyclic graphs, which has important applications in finding the critical path in scheduling problems. (en) En théorie des graphes et en informatique théorique, le problème de la plus longue chaîne (ou le problème du plus long chemin dans le cas d'un graphe orienté) consiste à déterminer la plus longue chaîne élémentaire dans un graphe. Une chaîne est élémentaire si elle ne passe pas deux fois par le même sommet. La longueur d'une chaîne peut être mesurée par le nombre d'arêtes qui la composent ou, dans le cas de graphes pondérés, par la somme des poids des arêtes du chemin. Contrairement au problème de plus court chemin, qui peut être résolu en temps polynomial dans les graphes sans cycle de poids négatif, le problème de la plus longue chaîne est NP-complet; il ne peut donc être résolu en temps polynomial, sauf si P=NP. Des résultats complémentaires montrent que, de plus, ce problème est également difficile à résoudre de manière approchée. En revanche, il a une complexité linéaire pour les graphes orientés acycliques, et il a alors des applications importantes, par exemple dans la détermination du chemin critique dans des problèmes d'ordonnancement, comme ils sont modélisés dans la méthode PERT par exemple. (fr) Em teoria dos grafos e ciência da computação teórica, o problema do caminho mais longo é encontrar um caminho simples de comprimento máximo num dado grafo. Um caminho é chamado simples se não tem nenhum vértice repetido; O comprimento de um caminho pode ser medido tanto pelo seu número de arestas, ou (em grafos ponderados) pela soma dos pesos das suas bordas. Em contraste com o problema do caminho mais curto, que pode ser resolvido em tempo polinomial em gráficos sem ciclos de peso negativo, o problema do caminho mais longo é NP-difícil, o que significa que ele não pode ser resolvido em tempo polinomial para grafos arbitrários a menos que P = NP. Fortes resultados difíceis são também conhecidos por mostrar que é difícil aproximar. No entanto, ele tem uma solução em tempo linear para grafos acíclicos direcionados, que tem importantes aplicações em encontrar o caminho crítico em problemas de agendamento. (pt) 在图论和理论计算机科学中，最长路径问题是指在给定的图中找出长度最长的道路。一条不具有任何重复顶点的路径被称为简单路径。无权图中路径的长度就是边的数量，而有权图中路径长度是边权重之和。不同的是，与此相反的最短路径问题（不含负权环）可以在多项式时间内解决。而最长路径问题是NP困难的，这意味着除非P = NP，否则对应于任意的图，没有办法在多项式时间内解决该问题。更强的结果表明这个问题也難以近似地得出答案。但是，有一个线性时间的方法可以用于有向无环图，这对于发现调度问题中的关键路径有重要的作用。 (zh) Задача о самом длинном пути — это задача поиска простого пути максимальной длины в заданном графе. Путь называется простым, если в нём нет повторных вершин. Длина пути может быть измерена либо числом рёбер, либо (в случае взвешенных графов) суммой весов его рёбер. В отличие от задачи кратчайшего пути, которая может быть решена за полиномиальное время на графах без циклов с отрицательным весом, задача нахождения самого длинного пути является NP-трудной и не может быть решена за полиномиальное время для произвольных графов, если только не P = NP. Принадлежность более тяжелому классу сложности также означает, что задачу трудно аппроксимировать. Однако задача решается за линейное время на ориентированных ациклических графах, которые имеют важное применение в задачах нахождения критического пути в задачах планирования. (ru) |
| dbo:wikiPageExternalLink | http://valis.cs.uiuc.edu/~sariel/misc/funny/longestpath.mp3 |
| dbo:wikiPageID | 18757567 (xsd:integer) |
| dbo:wikiPageLength | 22130 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1117230523 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Price's_model dbr:Topological_ordering dbr:Derek_J._de_Solla_Price dbr:Approximation_algorithm dbr:Hypercube_graph dbr:Decision_problem dbr:Depth-first_search dbr:Induced_path dbr:Ptolemaic_graph dbc:NP-complete_problems dbr:Color-coding dbr:Complete_graph dbr:Clique-width dbr:Graph_(discrete_mathematics) dbr:Graph_coloring dbr:NP-complete dbr:NP-hard dbr:Critical_path_method dbr:Linear_time dbr:Cactus_graph dbr:Shortest_path_problem dbr:Snake-in-the-box dbr:Comparability_graph dbr:Complement_graph dbr:Hamiltonian_path_problem dbr:Path_(graph_theory) dbr:Theoretical_computer_science dbc:Graph_algorithms dbc:Graph_distance dbr:Time_complexity dbr:Topological_sorting dbr:Travelling_salesman_problem dbr:Treewidth dbr:Weighted_graph dbr:Gallai–Hasse–Roy–Vitaver_theorem dbr:Hasse_diagram dbr:Layered_graph_drawing dbr:Trémaux_tree dbr:Daniel_J._Barrett dbr:Dynamic_programming dbc:Hamiltonian_paths_and_cycles dbr:Partially_ordered_set dbr:Graph_theory dbr:Interval_graph dbr:Bipartite_graph dbc:Computational_problems_in_graph_theory dbr:Block_graph dbr:Directed_acyclic_graph dbr:Distance-hereditary_graph dbc:Network_theory dbr:Planar_graph dbr:Split_graph dbr:Circle_graph dbr:Circular-arc_graph dbr:Citation_graph dbr:Polynomial_time dbr:Longest_uncrossed_knight's_path dbr:Vertex_(graph_theory) dbr:Permutation_graph dbr:Parameterized_complexity dbr:P_=_NP dbr:Path_decomposition |
| dbp:wikiPageUsesTemplate | dbt:Harvtxt dbt:Reflist dbt:Short_description |
| dct:subject | dbc:NP-complete_problems dbc:Graph_algorithms dbc:Graph_distance dbc:Hamiltonian_paths_and_cycles dbc:Computational_problems_in_graph_theory dbc:Network_theory |
| gold:hypernym | dbr:Problem |
| rdf:type | yago:WikicatComputationalProblemsInGraphTheory yago:WikicatNP-completeProblems yago:Abstraction100002137 yago:Act100030358 yago:Action100037396 yago:Activity100407535 yago:Algorithm105847438 yago:Attribute100024264 yago:Condition113920835 yago:Course100038262 yago:Difficulty114408086 yago:Event100029378 yago:Problem114410605 yago:Procedure101023820 yago:PsychologicalFeature100023100 yago:WikicatGraphAlgorithms yago:WikicatHamiltonianPathsAndCycles yago:YagoPermanentlyLocatedEntity dbo:Disease yago:Rule105846932 yago:State100024720 yago:Way100415676 |
| rdfs:comment | 在图论和理论计算机科学中，最长路径问题是指在给定的图中找出长度最长的道路。一条不具有任何重复顶点的路径被称为简单路径。无权图中路径的长度就是边的数量，而有权图中路径长度是边权重之和。不同的是，与此相反的最短路径问题（不含负权环）可以在多项式时间内解决。而最长路径问题是NP困难的，这意味着除非P = NP，否则对应于任意的图，没有办法在多项式时间内解决该问题。更强的结果表明这个问题也難以近似地得出答案。但是，有一个线性时间的方法可以用于有向无环图，这对于发现调度问题中的关键路径有重要的作用。 (zh) En teoria de grafs i ciència computacional teòrica, el problema del camí més llarg és el problema de trobar un camí simple de màxima longitud possible en un determinat graf. Un camí s'anomena simple si no té cap vèrtex repetit; la longitud d'un camí es pot mesurar pel seu nombre d'arestes, o (en grafs ponderats) per la suma dels pesos de les seves arestes. (ca) En teoría de grafos, el problema del camino más largo es, dado un grafo, encontrar un camino simple de longitud máxima. A diferencia del problema del camino más corto, que se puede solucionar en tiempo polinómico en grafos sin ciclos negativos, este problema es NP-completo, lo que quiere decir que la solución óptima no se puede encontrar en tiempo polinómico a menos que P=NP. * Datos: Q2916352 (es) Die Aufgabe, den einfachen Weg maximaler Länge in einem gegebenen Graphen zu finden, bezeichnet man in der Graphentheorie und der theoretischen Informatik als longest path problem (englisch für Problem des längsten Weges). Ein Weg heißt einfach, wenn er keinen Knoten mehrfach enthält. Die Länge des Weges kann auf zwei Arten gemessen werden: entweder durch die Anzahl der Kanten oder (in einem gewichteten Graphen) durch die Summe der Gewichte seiner Kanten. (de) In graph theory and theoretical computer science, the longest path problem is the problem of finding a simple path of maximum length in a given graph. A path is called simple if it does not have any repeated vertices; the length of a path may either be measured by its number of edges, or (in weighted graphs) by the sum of the weights of its edges. In contrast to the shortest path problem, which can be solved in polynomial time in graphs without negative-weight cycles, the longest path problem is NP-hard and the decision version of the problem, which asks whether a path exists of at least some given length, is NP-complete. This means that the decision problem cannot be solved in polynomial time for arbitrary graphs unless P = NP. Stronger hardness results are also known showing that it is d (en) En théorie des graphes et en informatique théorique, le problème de la plus longue chaîne (ou le problème du plus long chemin dans le cas d'un graphe orienté) consiste à déterminer la plus longue chaîne élémentaire dans un graphe. Une chaîne est élémentaire si elle ne passe pas deux fois par le même sommet. La longueur d'une chaîne peut être mesurée par le nombre d'arêtes qui la composent ou, dans le cas de graphes pondérés, par la somme des poids des arêtes du chemin. (fr) Em teoria dos grafos e ciência da computação teórica, o problema do caminho mais longo é encontrar um caminho simples de comprimento máximo num dado grafo. Um caminho é chamado simples se não tem nenhum vértice repetido; O comprimento de um caminho pode ser medido tanto pelo seu número de arestas, ou (em grafos ponderados) pela soma dos pesos das suas bordas. Em contraste com o problema do caminho mais curto, que pode ser resolvido em tempo polinomial em gráficos sem ciclos de peso negativo, o problema do caminho mais longo é NP-difícil, o que significa que ele não pode ser resolvido em tempo polinomial para grafos arbitrários a menos que P = NP. Fortes resultados difíceis são também conhecidos por mostrar que é difícil aproximar. No entanto, ele tem uma solução em tempo linear para grafos (pt) Задача о самом длинном пути — это задача поиска простого пути максимальной длины в заданном графе. Путь называется простым, если в нём нет повторных вершин. Длина пути может быть измерена либо числом рёбер, либо (в случае взвешенных графов) суммой весов его рёбер. В отличие от задачи кратчайшего пути, которая может быть решена за полиномиальное время на графах без циклов с отрицательным весом, задача нахождения самого длинного пути является NP-трудной и не может быть решена за полиномиальное время для произвольных графов, если только не P = NP. Принадлежность более тяжелому классу сложности также означает, что задачу трудно аппроксимировать. Однако задача решается за линейное время на ориентированных ациклических графах, которые имеют важное применение в задачах нахождения критического пут (ru) |
| rdfs:label | Problema del camí més llarg (ca) Längster Pfad (de) Problema del camino más largo (es) Problème de la plus longue chaîne (fr) Longest path problem (en) Problema do caminho mais longo (pt) Задача о самом длинном пути (ru) 最长路径问题 (zh) |
| owl:sameAs | freebase:Longest path problem wikidata:Longest path problem dbpedia-ca:Longest path problem dbpedia-de:Longest path problem dbpedia-es:Longest path problem dbpedia-fa:Longest path problem dbpedia-fr:Longest path problem dbpedia-he:Longest path problem http://hy.dbpedia.org/resource/Ամենաերկար_ճանապարհի_խնդիր dbpedia-pt:Longest path problem dbpedia-ru:Longest path problem dbpedia-sr:Longest path problem dbpedia-th:Longest path problem dbpedia-zh:Longest path problem https://global.dbpedia.org/id/2hnCX yago-res:Longest path problem |
| prov:wasDerivedFrom | wikipedia-en:Longest_path_problem?oldid=1117230523&ns=0 |
| foaf:isPrimaryTopicOf | wikipedia-en:Longest_path_problem |
| is dbo:wikiPageRedirects of | dbr:Approximate_solutions_of_the_longest_path_problem dbr:Approximation_algorithms_for_the_longest_path_problem dbr:Longest_path |
| is dbo:wikiPageWikiLink of | dbr:Science_Fell_in_Love,_So_I_Tried_to_Prove_It dbr:List_of_algorithms dbr:Mirsky's_theorem dbr:Price's_model dbr:Convex_Polytopes dbr:Optimal_substructure dbr:Approximate_solutions_of_the_longest_path_problem dbr:Approximation_algorithms_for_the_longest_path_problem dbr:Shortest_path_problem dbr:Path_(graph_theory) dbr:Topological_sorting dbr:Gallai–Hasse–Roy–Vitaver_theorem dbr:Transitive_reduction dbr:Daniel_J._Barrett dbr:List_of_NP-complete_problems dbr:Dijkstra's_algorithm dbr:Directed_acyclic_graph dbr:Longest_path |
| is foaf:primaryTopic of | wikipedia-en:Longest_path_problem |