Problema de l'amplitut

Archiu:Caps block 0 Graphs-undirected-weighted.svg

En este gràfic, el camí més ample de Maldon a Feering té un ample de banda de 29, i pansa a través de Clacton, Tiptree, Harwich, i Blaxill.

En algoritmes gràfics, el problema de l'amplitut és el problema de trobar un camí entre dos vèrtiços designats en un gràfic ponderat, maximizar el pes de la vora de menor pes en la ruta. El problema del camí més ample també es coneix com el coll de botella, el problema del camí més curt o més be, el màxim problema d'este camí és la capacitat. És possible adaptar la majoria dels algoritmes del camí més curt per a calcular trayectòries molt àmplies per mig de la modificació de les mateixes per a utilisar la distància del coll de botella en lloc de la llongitut de la trayectòria. No obstant, en molts casos inclús els algoritmes més ràpits són possibles.

Per eixemple, en un gràfic que represente les conexions entre els routers de l'Internet, el pes d'una aresta representa l'ample de banda d'una conexió entre dos routers, el problema del camí més ample és el problema de trobar una ruta d'extrem a extrem entre dos nodos que tinguen el màxim ample de banda possible. El pes més chicotet de l'aresta en este camí es coneix com la capacitat o ample de banda de la ruta. Aixina com les seues aplicacions en el enrutamiento de ret, el problema del camí més ample és també un component important del método de Schulze per a decidir el guanyador d'una elecció de múltiples vies, i s'ha aplicat a la composició digital via anàlisis metabòlic i càlcul de fluix màxims.

Un problema relacionat, és el problema del camí minimax, el qual supon pel camí que minimisa el pes màxim de qualsevol de les seues arestes. Té aplicacions que inclouen la planificació del transport. Qualsevol algoritme per al problema del camí més ampli pot ser transformat en un algoritme per al problema del camí minimax, o viceversa, per mig de l'inversió del sentit de totes les comparacions de pes realisades per l'algoritme, o de manera equivalent per mig de la substitució de tot pes.

Gràfiques indirectes

En una gràfica indirecta, un camí ampli es pot trobar com el camí entre els dos vèrtiços en l'arbre en expansió màxima de la gràfica i un camí minimax es pot trobar com el camí entre els dos vèrtiços en l'arbre en expansió mínima.

En qualsevol gràfic, dirigit o no dirigit, hi ha un senzill algoritme per a trobar un camí més ample una volta que el pes de la seua aresta mínima siga conegut: només es tenen que borrar totes les arestes més chicotetes i eliminar qualsevol camí entre les arestes restants per mig de la busca en esgambi o profunditat de la primera busca. Sobre la base d'esta prova, també existix un algoritme de temps llineal per a trobar un camí s-t més ampli en una gràfica no dirigida, que no utilisa l'arbre de màxima expansió. L'idea principal del algoritme consistix en aplicar l'algoritme de ruta d'investigació en temps llineal en el pes de l'aresta mijana en el gràfic i a continuació, eliminar tots les arestes més chicotetes o contraure tots les arestes de major tamany en funció si un camí no existix i recursarlo en el gràfic més chicotet que resulta.Fernandez, Garfinkel y Arbiol (1998) utilisen els camins més curts de coll de botella no dirigits en la finalitat de formar les fotografies aérees compostes que combinen vàries imàgens d'àrees de superposició. En el subproblema al que s'aplica el problema del camí més ample hi ha dos imàgens que ya s'han transformat en un sistema de coordenades comuna; la tasca restant és seleccionar una costura, una curva que passa a través de la regió de solapamiento i dividix una de les dos imàgens de l'atra. Els píxels en un costat de la costura es poden copiar d'una de les imàgens, i els píxels en l'atre costat de la costura es copiaran des de l'atra image. A diferència d'atres métodos, ací s'està fotografiant la composició promig dels píxels en abdós imàgens, lo que produïx una image fotogràfica vàlida de totes les parts de la regió. Pesen les arestes d'un gràfic de la ret per un càlcul numèric nos aproxima a cóm visualment apareix una costura a través de la mateixa aresta i trobaria un camí més curt de coll de botella per a estos pesos. L'us d'este camí com la costura, en lloc d'un camí més curt i convencional, provoca que el seu sistema trobe una costura que és difícil de discernir en tots els seus punts, en lloc de permetre un canvi de major visibilitat en una part de l'image o menor la visibilitat en atres llocs.

Si tots els pesos de les arestes d'un gràfic no dirigit són positius, llavors les distàncies minimax entre parells de punts (els pesos màxims de les arestes de camins minimax) formen un ultramétrico; pel contrari cada espai ultramétrico finito ve de distàncies minimax d'esta manera. Una estructura de senyes construïda a partir de l'arbre d'expansió mínim permet que la distància Minimax entre qualsevol parell de les vèrtiços que es deu consultar,. siga per mig de la consultes de ancestro comuna més baix en un arbre cartesiano. La raïl de l'arbre cartesiano representa el mínim pes que travessa l'aresta de l'arbre, i les sub-branques de la raïl són arbres cartesianos de forma recursiva construïts a partir dels subárboles d'expansió mínima formada per l'eliminació de l'aresta més pesada. Els fulls de l'arbre cartesiano representen els vèrtiços del gràfic d'entrada, i la distància entre dos vèrtiços minimax és igual al pes del nodo de l'arbre cartesiano que a la seua volta és el seu ancestro comú més baix. Una volta que els brodes arbre d'expansió mínim s'han ordenat, l'arbre cartesiano es pot construir en el temps llineal.

Gràfiques directes

En els gràfics dirigits, la solució màxima d'arbre d'expansió no es pot utilisar. En lloc d'això, es coneixen varis algoritmes diferents; L'elecció de quin algoritme per a usar depén en si d'un vèrtiç d'inici o destí d'una ruta que és fixa, o si s'usen rutes d'accés per a molts vèrtiços d'inici els destins deuen trobar-se al mateix temps.

Per a tot parell

El problema del camí per a tots els parells més amples té aplicacions en el método de Schulze que elegix un guanyador en les eleccions de múltiples vies en les que els electors ordenen als candidats en orde de preferència. El método Schulze construïx un gràfic dirigit complet en el que els vèrtiços representen els candidats i cada dos vèrtiços estan conectats per una vora. Cada vora és dirigida des del guanyador al perdedor d'un combat per parelles entre els dos candidats que es conecta, i s'etiqueta en el marge de la victòria d'eixe concurs. A continuació, el método calcula trayectòries més àmplies entre tots els parells de vèrtiços, i el guanyador és el candidat el vèrtiç del qual té camins més amples a cada oponent que a l'inversa. Els resultats d'una elecció que utilisen este método són consistents en el método Condorcet . El candidat que guanya tots els concursos per parelles gana automàticament tota l'elecció - pero per lo general permet un guanyador per a ser seleccionats, inclús en situacions en les que el método Concorcet falla. El método Schulze ha segut utilisat per vàries organisacions, entre elles la Fundació Wikimedia.

Per a calcular els esgambi de ruta més àmplies per a tots els parells de nodos d'un grafo dirigit dens, tals com els que sorgixen en l'aplicació de votació, l'enfocament asintóticamente més ràpit conegut pren temps O (n (3 + ω) / 2) a on ω és l'exponent de la multiplicació de matrius ràpit. L'us dels algoritmes més coneguts per a la multiplicació de matrius, esta volta en destí es convertix en O (n2.688). En canvi, l'implementació de referència per al método de Schulze utilisa una versió modificada de l'algoritme més simple Floyd-Warshall, lo que du temps O (n3). Per a grafos dispersos, que pot ser més eficient per a aplicar repetidament un algoritme de ruta més àmplia d'una sola font.

Única font

Si les vores estan ordenades pels seus pesos, a continuació, una versió modificada del algoritme de Dijkstra pot calcular els colls de botella entre un vèrtiç d'inici designat i cada atre vèrtiç en el gràfic en temps llineal. L'idea clau darrere de l'aument de velocitat sobre una versió convencional de l'algoritme de Dijkstra és que la seqüència de coll de botella es distancia de cada vèrtiç, en l'orde en que els vèrtiços són considerats per este algoritme, és una subsecuencia monòtona de la seqüència ordenada de pesos de les arestes; Per lo tant, la coa de prioritat de l'algoritme de Dijkstra pot ser reemplaçat per una matriu indexada pels números d'1 a m (el número d'arestes en el gràfic), a on cèlula d'agrupació i conté els vèrtiços que la seua distancia coll de botella és el pes de la vora en la posició i en l'orde de classificació. Este método permet que el problema del camí més ample a ser resolt tan ràpidament com a classificació; per eixemple, si els pesos de les arestes es representen com a número entero, llavors el temps dels llímits per a un número entero orde una llista d'número entero, m s'aplicaria també a este problema.

Una sola font i destí únic

Berman y Handler (1987) sugerixen que els vehículs de servici i vehículs d'emergència deuen utilisar rutes minimax, en retornar d'una visita de servici a la seua base. En esta aplicació, el temps per a tornar és menys important que el temps de resposta si una atra cridada de servici es produïx mentres el vehícul està en el procés de tornada. Per mig de l'us d'un camí Minimax, a on el pes d'una ventaja és el temps màxim de viage des d'un punt en la vora de la més lluntana cridada de servici possible, es pot planificar una ruta que minimise el retardo màxim possible entre la recepció d'una cridada de servici i l'arribada d'un vehícul per a respondre.Ullah, Lee y Hassoun (2009) utilisen camins maxmin per a modelar les cadenes de reaccions dominants en les rets metabòliques; En el seu model, el pes d'una vora és l'energia lliure de la reacció metabòlica representada per la vora.

Una atra aplicació dels camins més amples sorgix en l'algoritme de Ford-Fulkerson per al problema de fluix màxim. Repetidament aumentar un fluix a lo llarc d'una ruta de capacitat màxima en la ret residual del fluix conduïx a un chicotet bot, O (m log O), en el número d'auments necessaris per a trobar un fluix màxim; ací, les capacitats de vora se supon que són número entero que són en la majoria de U. No obstant, este anàlisis no depén de trobar un camí que té el màxim exacte de la capacitat; qualsevol camí la capacitat del qual està dins d'un factor constant dels màxims basta. La combinació d'esta idea d'aproximació en el método d'aument del camí més curt de l'algoritme Edmonds-Karp conduïx a un algoritme de fluix màxim en el temps O (mn log T) que s'eixecuta.

És possible trobar camins de màxima capacitat i camins minimax en una sola font i un sol destí molt eficient, inclús en models de computació que només permeten comparacions dels pesos de les arestes del grafo d'entrada i no aritmètica sobre ells. L'algoritme manté un conjunt S d'arestes que se sap que contenen la vora del coll de botella de la ruta òptima; Inicialment, S és el conjunt de tots els brodes m de la gràfica. En cada iteración de l'algoritme, es dividix S en una seqüència ordenada de subconjunts S1, S2, ... d'aproximadament el mateix tamany; el número de subconjunts en esta partició s'elegix de tal manera que tots els punts de divisió entre els subconjunts es poden trobar per repetit mijana-troballa en temps O (m). L'algoritme després reweights cada vora de la gràfica per l'índex del subconjunt que conté la vora, i utilisa l'algoritme de Dijkstra modificat en les gràfiques reponderadas; sobre la base dels resultats d'este càlcul, es pot determinar en temps llineal que dels subconjunts conté el pes brode coll de botella. A continuació, substituint S pel subconjunt del mateix que ha determinat per a contindre el pes coll de botella i s'inicia la següent iteración en este nou conjunt S. El número de subconjunts en el que S es pot dividir aumenta exponencialment en cada pas, per lo que el número de iteraciones és proporcional a la funció de logaritmo iterado, O (Plantilla: Log-starn), i el temps total és O (m Plantilla: Log-starn). En un model de càlcul, en el cada pes de vora és un número entero de la màquina, l'us de bisecció repetit en este algoritme pot ser substituïda per una tècnica de divisió de llista d'Han i Thorup (2002), permetent que S es dividixca en O (√m) conjunts més menuts de Si en un sol pas i que conduïxen a un temps global llineal unit.