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