| dbo:abstract
|
- Das Steinerbaumproblem, ein nach dem Schweizer Mathematiker Jakob Steiner benanntes mathematisches Problem, ist eine Verallgemeinerung des Problems des minimalen Spannbaums. Hier wie dort wird der kürzeste Graph gesucht, der endlich viele gegebene Punkte (die Terminale) miteinander verbindet und der auf diese Weise das kürzeste Wegenetz zwischen diesen Punkten bildet. Beim Problem des minimalen Spannbaums wird dieser Graph nur zwischen den Terminalen aufgespannt, beim Steinerbaumproblem kann man dagegen aus einer ebenfalls gegebenen Menge (den Nichtterminalen) endlich viele weitere Punkte (die Steinerpunkte) zu den Ausgangspunkten hinzufügen, die dann als zusätzliche Verzweigungen im Wegenetz dienen, um dieses dadurch weiter zu verkürzen. Das Ergebnis ist wie beim minimalen Spannbaum ein Baum. Die theoretische und praktische Schwierigkeit beim Lösen des Steinerbaumproblems besteht darin, eine geeignete Auswahl der Steinerpunkte zu treffen. Praktische Anwendung findet die Berechnung von Steinerbäumen unter anderem bei der Planung von Wege- und Telekommunikationsnetzen und dem Entwurf von integrierten Schaltkreisen. (de)
- El árbol de Steiner, nombrado en honor a Jakob Steiner, es un problema de optimización combinatoria consistente en buscar la interconexión más corta para un conjunto de elementos dado. Es superficialmente similar al problema del árbol recubridor mínimo: dado un conjunto V de puntos (vértices), interconectalos por la red gráfica de menor longitud, donde la longitud es la suma de las medidas de todos los lados. La diferencia entre el problema del árbol de Steiner y el del árbol recubridor es que, en el primero se pueden añadir vértices intermedios y lados extras al grafo con el fin de reducir la longitud del árbol recubridor. Los vértices introducidos para decrecer la longitud total de las conexiones son conocidos como . Ha sido demostrado que la conexión resultante es un árbol, llamado árbol de Steiner. Pueden existir varios árboles de Steiner para un conjunto dado de vértices iniciales. El árbol de Steiner tiene aplicaciones en el diseño de circuitos eléctricos y redes de telecomunicaciones. La mayoría de las versiones del problema de Steiner son NP-completo. De hecho uno de estos pertenece a la lista de 21 problemas NP-completos de Karp. Algunos casos restringidos pueden ser resueltos por tiempo polinómico, sin embargo en la práctica se usa la heurística en su lugar. (es)
- En algorithmique, le problème de l'arbre de Steiner est un problème d'optimisation combinatoire. Il porte le nom du mathématicien Jakob Steiner. Ce problème est proche du problème de l'arbre couvrant minimal et a des applications en conception de réseaux, notamment les circuits électroniques et les télécommunications. (fr)
- In combinatorial mathematics, the Steiner tree problem, or minimum Steiner tree problem, named after Jakob Steiner, is an umbrella term for a class of problems in combinatorial optimization. While Steiner tree problems may be formulated in a number of settings, they all require an optimal interconnect for a given set of objects and a predefined objective function. One well-known variant, which is often used synonymously with the term Steiner tree problem, is the Steiner tree problem in graphs. Given an undirected graph with non-negative edge weights and a subset of vertices, usually referred to as terminals, the Steiner tree problem in graphs requires a tree of minimum weight that contains all terminals (but may include additional vertices). Further well-known variants are the Euclidean Steiner tree problem and the rectilinear minimum Steiner tree problem. The Steiner tree problem in graphs can be seen as a generalization of two other famous combinatorial optimization problems: the (non-negative) shortest path problem and the minimum spanning tree problem. If a Steiner tree problem in graphs contains exactly two terminals, it reduces to finding the shortest path. If, on the other hand, all vertices are terminals, the Steiner tree problem in graphs is equivalent to the minimum spanning tree. However, while both the non-negative shortest path and the minimum spanning tree problem are solvable in polynomial time, the decision variant of the Steiner tree problem in graphs is NP-complete (which implies that the optimization variant is NP-hard); in fact, the decision variant was among Karp's original 21 NP-complete problems. The Steiner tree problem in graphs has applications in circuit layout or network design. However, practical applications usually require variations, giving rise to a multitude of Steiner tree problem variants. Most versions of the Steiner tree problem are NP-hard, but some restricted cases can be solved in polynomial time. Despite the pessimistic worst-case complexity, several Steiner tree problem variants, including the Steiner tree problem in graphs and the rectilinear Steiner tree problem, can be solved efficiently in practice, even for large-scale real-world problems. (en)
- シュタイナー木（Steiner tree）とは、エッジの集合Eとノードの集合Vから成る無向グラフG=(V,E)において、Vの部分集合Tが与えられたとき、Tに含まれるノードすべてを含む木のことである。定義より、T=Vのとき、シュタイナー木は全域木となることは明らかである。特に、エッジが重みづけされたグラフGにおいて、Tのシュタイナー木を構成するエッジの重みの総和が最も小さいシュタイナー木のことを（Minimum Steiner tree）と呼ぶ。最小シュタイナー木を求める問題はシュタイナー問題、 最短連結問題、最短ネットワーク問題などと呼ばれ、NP困難であることが知られている。最小シュタイナー木問題を解くアルゴリズムを「シュタイナー木アルゴリズム」と呼ぶ。シュタイナー木アルゴリズムの一例として、Dreyfus–Wagner法などがある。 (ja)
- Het (minimale) Steinerboomprobleem is een wiskundig probleem uit de grafentheorie. Het is een generalisatie van het probleem van de minimaal opspannende boom, waarin men voor een gegeven verzameling van punten in het tweedimensionele vlak een boom (een graaf zonder cycli) zoekt waarvan de knopen de gegeven punten zijn en waarvan de som van de lengten van de takken minimaal is. (nl)
- Drzewo Steinera dla ustalonego zbioru punktów to najmniejsza figura łącząca te punkty. Nazwa pochodzi od Jakoba Steinera. Znalezienie drzewa Steinera dla ustalonego zbioru punktów jest problemem NP-trudnym. (pl)
- O problema da árvore de Steiner, problema da auto-estrada, ou problema da árvore mínima de Steiner, denominado em referência a Jakob Steiner, é um problema de otimização combinatória, que pode ser formulado em uma série de configurações, com a parte comum, sendo que é necessário para encontrar a menor interconexão para um determinado conjunto de objetos. O problema da árvore de Steiner é superficialmente semelhante ao problema da árvore de extensão mínima: dado um conjunto V de pontos (vértices), interligá-los através de uma rede (grafo) de menor tamanho, onde o comprimento é a soma dos comprimentos de todas as arestas. A diferença entre o problema da árvore de Steiner e o problema da arvore de extensão minima é que, na árvore de Steiner, vertices intermediários e arestas intermediárias podem ser adicionados ao grafo, a fim de reduzir o comprimento da árvore de expansão. Esses novos vértices introduzidos para diminuir o comprimento total da ligação são conhecidos como pontos de Steiner ou vértices de Steiner. Foi provado que a ligação resultante é uma árvore, conhecida como a árvore de Steiner. Podem existir várias árvores de Steiner para um determinado conjunto de vértices iniciais. O problema da árvore de Steiner tem aplicações em layout de circuito ou em projeto de rede. A maioria das versões do problema da árvore de Steiner são NP-completos. Na verdade, um deles estava entre os 21 problemas originais NP-completos de Karp . Alguns casos restritos podem ser resolvidos em tempo polinomial. Na prática, são utilizadas heurísticas. (pt)
- Задача Штейнера о минимальном дереве состоит в поиске кратчайшей сети, соединяющей заданный конечный набор точек плоскости.Задача получила своё название в честь Якоба Штейнера (1796—1863). Альтерантивное условие задачи заключается в поиске минимального подграфа, соединяющего конечное число заданных вершин (терминалов) и образующего таким образом сеть кратчайших путей между этими вершниами. Задача является таким образом обобщением задачи поиска минимального остовного дерева. (ru)
- Задача Штейнера (Задача дерева Штейнера) полягає у пошуку мінімального дерева Штейнера — найкоротшої мережі, що з'єднує заданий скінченний набір точок площини. Свою назву отримала на честь Якоба Штейнера (1796–1863). (uk)
|
| rdfs:comment
|
- En algorithmique, le problème de l'arbre de Steiner est un problème d'optimisation combinatoire. Il porte le nom du mathématicien Jakob Steiner. Ce problème est proche du problème de l'arbre couvrant minimal et a des applications en conception de réseaux, notamment les circuits électroniques et les télécommunications. (fr)
- シュタイナー木（Steiner tree）とは、エッジの集合Eとノードの集合Vから成る無向グラフG=(V,E)において、Vの部分集合Tが与えられたとき、Tに含まれるノードすべてを含む木のことである。定義より、T=Vのとき、シュタイナー木は全域木となることは明らかである。特に、エッジが重みづけされたグラフGにおいて、Tのシュタイナー木を構成するエッジの重みの総和が最も小さいシュタイナー木のことを（Minimum Steiner tree）と呼ぶ。最小シュタイナー木を求める問題はシュタイナー問題、 最短連結問題、最短ネットワーク問題などと呼ばれ、NP困難であることが知られている。最小シュタイナー木問題を解くアルゴリズムを「シュタイナー木アルゴリズム」と呼ぶ。シュタイナー木アルゴリズムの一例として、Dreyfus–Wagner法などがある。 (ja)
- Het (minimale) Steinerboomprobleem is een wiskundig probleem uit de grafentheorie. Het is een generalisatie van het probleem van de minimaal opspannende boom, waarin men voor een gegeven verzameling van punten in het tweedimensionele vlak een boom (een graaf zonder cycli) zoekt waarvan de knopen de gegeven punten zijn en waarvan de som van de lengten van de takken minimaal is. (nl)
- Drzewo Steinera dla ustalonego zbioru punktów to najmniejsza figura łącząca te punkty. Nazwa pochodzi od Jakoba Steinera. Znalezienie drzewa Steinera dla ustalonego zbioru punktów jest problemem NP-trudnym. (pl)
- Задача Штейнера о минимальном дереве состоит в поиске кратчайшей сети, соединяющей заданный конечный набор точек плоскости.Задача получила своё название в честь Якоба Штейнера (1796—1863). Альтерантивное условие задачи заключается в поиске минимального подграфа, соединяющего конечное число заданных вершин (терминалов) и образующего таким образом сеть кратчайших путей между этими вершниами. Задача является таким образом обобщением задачи поиска минимального остовного дерева. (ru)
- Задача Штейнера (Задача дерева Штейнера) полягає у пошуку мінімального дерева Штейнера — найкоротшої мережі, що з'єднує заданий скінченний набір точок площини. Свою назву отримала на честь Якоба Штейнера (1796–1863). (uk)
- El árbol de Steiner, nombrado en honor a Jakob Steiner, es un problema de optimización combinatoria consistente en buscar la interconexión más corta para un conjunto de elementos dado. Es superficialmente similar al problema del árbol recubridor mínimo: dado un conjunto V de puntos (vértices), interconectalos por la red gráfica de menor longitud, donde la longitud es la suma de las medidas de todos los lados. (es)
- Das Steinerbaumproblem, ein nach dem Schweizer Mathematiker Jakob Steiner benanntes mathematisches Problem, ist eine Verallgemeinerung des Problems des minimalen Spannbaums. Hier wie dort wird der kürzeste Graph gesucht, der endlich viele gegebene Punkte (die Terminale) miteinander verbindet und der auf diese Weise das kürzeste Wegenetz zwischen diesen Punkten bildet. Beim Problem des minimalen Spannbaums wird dieser Graph nur zwischen den Terminalen aufgespannt, beim Steinerbaumproblem kann man dagegen aus einer ebenfalls gegebenen Menge (den Nichtterminalen) endlich viele weitere Punkte (die Steinerpunkte) zu den Ausgangspunkten hinzufügen, die dann als zusätzliche Verzweigungen im Wegenetz dienen, um dieses dadurch weiter zu verkürzen. Das Ergebnis ist wie beim minimalen Spannbaum ein B (de)
- In combinatorial mathematics, the Steiner tree problem, or minimum Steiner tree problem, named after Jakob Steiner, is an umbrella term for a class of problems in combinatorial optimization. While Steiner tree problems may be formulated in a number of settings, they all require an optimal interconnect for a given set of objects and a predefined objective function. One well-known variant, which is often used synonymously with the term Steiner tree problem, is the Steiner tree problem in graphs. Given an undirected graph with non-negative edge weights and a subset of vertices, usually referred to as terminals, the Steiner tree problem in graphs requires a tree of minimum weight that contains all terminals (but may include additional vertices). Further well-known variants are the Euclidean St (en)
- O problema da árvore de Steiner, problema da auto-estrada, ou problema da árvore mínima de Steiner, denominado em referência a Jakob Steiner, é um problema de otimização combinatória, que pode ser formulado em uma série de configurações, com a parte comum, sendo que é necessário para encontrar a menor interconexão para um determinado conjunto de objetos. (pt)
|
