Pfadlängenbeschränkungen

Pfadlängenbeschränkung bezeichnet in der Graphentheorie eine Bedingung, nach der nur Pfade zwischen zwei Knoten zugelassen sind, deren Gesamtlänge eine vorgegebene Obergrenze nicht überschreitet. Die Pfadlänge wird üblicherweise als Summe der Kantengewichte entlang eines Pfads definiert, wobei die Kantengewichtung positive Kosten oder Entfernungen darstellen kann. In Anwendungen wird häufig an zwei Pegeln unterschieden: dem Primärziel, das oft die Minimierung der Pfadlänge ist, und der Beschränkung, die sicherstellt, dass der Pfad eine maximale Länge nicht überschreitet.

Formalisierung: Gegeben sei ein gewichteter Graph G=(V,E) mit nichtnegativen Kantengewichten w(e)≥0, ein Startknoten s∈V, ein Zielknoten t∈V und eine Obergrenze L≥0. Ein Pfad p von s nach t ist zulässig, wenn die Pfadlänge len(p)=∑e∈p w(e) ≤ L. In vielen problematischen Kontexten wird zusätzlich ein zweites Ziel maximiert oder minimiert, während die Länge unter der Begrenzung bleibt.

Verwandte Probleme: Die Pfadlängenbeschränkung ist Kern eines constrained shortest path problems (CSP) oder eines multi-constrained path problems (MCP). Hierbei wird neben der Pfadlänge oft eine oder mehrere weitere Ressourcen berücksichtigt, zum Beispiel Zeit, Energie oder Kosten. Die Problematik besteht darin, den shortest-path-Charakter unter Berücksichtigung der Beschränkungen zu erreichen.

Komplexität und Algorithmen: Allgemein ist das Problem NP-hart, besonders wenn mehrere Beschränkungen berücksichtigt werden. Bei einer einzigen Ressource gibt es jedoch pseudo-polynomiale dynamische Programmierungsmöglichkeiten, Label-Setting- oder Lagrange-Relaxation-Ansätze, die in praxisnahen Anwendungen oft ausreichen. In speziellen Graphklassen oder bei festen Gewichten lassen sich effizientere Algorithmen finden.

Anwendungen: Pfadlängenbeschränkungen finden Anwendung in Netzwerk-Routing mit Delay-Budgets, Fahrzeugnavigation mit Zeit- oder Kraftstofflimits, Robotik-Pfadplanung unter Energiebeschränkungen sowie Logistik- und Ressourcenplanung, wo Pfade zwar optimal sein sollen, aber bestimmte Höchstlängen nicht überschreiten dürfen.