| dbo:abstract
|
- En algoritmos gráficos, el problema de la amplitud es el problema de encontrar un camino entre dos vértices designados en un gráfico ponderado, maximizando el peso del borde de menor peso en la ruta. El problema del camino más ancho también se conoce como el cuello de botella, el problema del camino más corto o más bien, el máximo problema de este camino es la capacidad. Es posible adaptar la mayoría de los algoritmos del camino más corto para calcular trayectorias muy amplias mediante la modificación de las mismas para utilizar la distancia del cuello de botella en lugar de la longitud de la trayectoria. Sin embargo, en muchos casos incluso los algoritmos más rápidos son posibles. Por ejemplo, en un gráfico que represente las conexiones entre los routers de la Internet, el peso de una arista representa el ancho de banda de una conexión entre dos routers, el problema del camino más ancho es el problema de encontrar una ruta de extremo a extremo entre dos nodos que tengan el máximo ancho de banda posible. El peso más pequeño de la arista en este camino se conoce como la capacidad o ancho de banda de la ruta. Así como sus aplicaciones en el enrutamiento de red, el problema del camino más ancho es también un componente importante del método de Schulze para decidir el ganador de una elección de múltiples vías, y se ha aplicado a la composición digital vía análisis metabólico y cálculo de flujos máximos. Un problema relacionado, es el problema del camino minimax, el cual supone por el camino que minimiza el peso máximo de cualquiera de sus aristas. Tiene aplicaciones que incluyen la planificación del transporte. Cualquier algoritmo para el problema del camino más amplio puede ser transformado en un algoritmo para el problema del camino minimax, o viceversa, mediante la inversión del sentido de todas las comparaciones de peso realizadas por el algoritmo, o de manera equivalente mediante la sustitución de todo peso. (es)
- In graph algorithms, the widest path problem is the problem of finding a path between two designated vertices in a weighted graph, maximizing the weight of the minimum-weight edge in the path. The widest path problem is also known as the maximum capacity path problem. It is possible to adapt most shortest path algorithms to compute widest paths, by modifying them to use the bottleneck distance instead of path length. However, in many cases even faster algorithms are possible. For instance, in a graph that represents connections between routers in the Internet, where the weight of an edge represents the bandwidth of a connection between two routers, the widest path problem is the problem of finding an end-to-end path between two Internet nodes that has the maximum possible bandwidth. The smallest edge weight on this path is known as the capacity or bandwidth of the path. As well as its applications in network routing, the widest path problem is also an important component of the Schulze method for deciding the winner of a multiway election, and has been applied to digital compositing, metabolic pathway analysis, and the computation of maximum flows. A closely related problem, the minimax path problem or bottleneck shortest path problem asks for the path that minimizes the maximum weight of any of its edges. It has applications that include transportation planning. Any algorithm for the widest path problem can be transformed into an algorithm for the minimax path problem, or vice versa, by reversing the sense of all the weight comparisons performed by the algorithm, or equivalently by replacing every edge weight by its negation. (en)
- Задача о самом широком пути — это задача нахождения пути между двумя выбранными вершинами во взвешенном графе, максимизирующего вес минимального по весу ребра графа (если рассматривать вес ребра как ширину дороги, то задача стоит в выборе самой широкой дороги, связывающей две вершины). Задача о самом широком пути известна также как задача об узком месте или задача о пути с максимальной пропускной способностью. Можно приспособить алгоритмы кратчайшего пути для вычисления пропускной способности путём использования некоего специального значения вместо длины пути. Однако во многих случаях возможны более быстрые алгоритмы. Например, в графе, который представляет соединения между маршрутизаторами в интернете, в котором вес ребра представляет полосу пропускания соединения между двумя маршрутизаторами, задача о самом широком пути соответствует задаче поиска сквозного пути между двумя узлами интернета, который имеет максимально широкую полосу. Наименьший вес ребра на этом пути известен как ёмкость или ширина пути. Наравне с приложениями в маршрутизации в сети задача о самом широком пути является также важной компонентой метода Шульце определения победителя в многоходовых выборах, она была использована в цифровом совмещении изображений , и для вычисления максимальных потоков. Тесно связанная задача о минимаксном пути спрашивает о пути, который минимизирует максимальный вес любого из рёбер (можно интерпретировать как поиск самой ровной дороги, имеющей минимальные углы подъёма и спуска). Эта задача находит приложение в планировании дорожного движения. Любой алгоритм для задачи о самом широком пути может быть преобразован в алгоритм о минимаксном пути и, наоборот, путём обращения смысла всех сравнений весов, предпринимаемых в алгоритме, или, эквивалентно, путём замены весов на отрицательные значения. (ru)
|
| rdfs:comment
|
- En algoritmos gráficos, el problema de la amplitud es el problema de encontrar un camino entre dos vértices designados en un gráfico ponderado, maximizando el peso del borde de menor peso en la ruta. El problema del camino más ancho también se conoce como el cuello de botella, el problema del camino más corto o más bien, el máximo problema de este camino es la capacidad. Es posible adaptar la mayoría de los algoritmos del camino más corto para calcular trayectorias muy amplias mediante la modificación de las mismas para utilizar la distancia del cuello de botella en lugar de la longitud de la trayectoria. Sin embargo, en muchos casos incluso los algoritmos más rápidos son posibles. (es)
- In graph algorithms, the widest path problem is the problem of finding a path between two designated vertices in a weighted graph, maximizing the weight of the minimum-weight edge in the path. The widest path problem is also known as the maximum capacity path problem. It is possible to adapt most shortest path algorithms to compute widest paths, by modifying them to use the bottleneck distance instead of path length. However, in many cases even faster algorithms are possible. (en)
- Задача о самом широком пути — это задача нахождения пути между двумя выбранными вершинами во взвешенном графе, максимизирующего вес минимального по весу ребра графа (если рассматривать вес ребра как ширину дороги, то задача стоит в выборе самой широкой дороги, связывающей две вершины). Задача о самом широком пути известна также как задача об узком месте или задача о пути с максимальной пропускной способностью. Можно приспособить алгоритмы кратчайшего пути для вычисления пропускной способности путём использования некоего специального значения вместо длины пути. Однако во многих случаях возможны более быстрые алгоритмы. (ru)
|
