Trovare il percorso con il massimo peso minimo

StackOverflow https://stackoverflow.com/questions/873126

Domanda

Sto cercando di capire un algoritmo per la ricerca di un percorso attraverso un grafo orientato. Non è un percorso convenzionale e non riesco a trovare alcun riferimento a qualcosa di simile questo essere fatto già.

Voglio trovare il percorso che ha il peso minimo al massimo.

vale a dire. Se vi sono due percorsi con pesi 10-> 1-> 10 e 2-> 2-> 2 allora il secondo percorso è considerato migliore del primo perché il peso minimo (2) è superiore al peso minimo della prima (1 ).

Se qualcuno può trovare un modo per fare questo, o semplicemente mi puntare nella direzione di qualche materiale di riferimento che sarebbe stato incredibilmente utile:)

EDIT :: Sembra ho dimenticato di dire che sto cercando di ottenere da un vertice specifico per un altro vertice specifica. Molto importante punto c'è: /

EDIT2 :: Come qualcuno qui sotto ha sottolineato, vorrei sottolineare che i pesi di bordo non sono negativi.

È stato utile?

Soluzione

del Prim o algoritmo nofollow noreferrer di Kruskal. Basta modificarli in modo che si fermano quando scoprono che i vertici di chiedere informazioni sono collegate.

EDIT: Mi chiedi per un minimo di massima, ma il tuo esempio sembra che si desidera la massima minima. In caso di minimo massimo l'algoritmo di Kruskal non funzionerà.

EDIT: L'esempio è a posto, il mio errore. Solo l'algoritmo di Prim lavorerà poi.

Altri suggerimenti

questa risposta e aggiungendo anche aggiungendo il mio prova di correttezza per l'algoritmo:

Vorrei usare una qualche variante del di Dijkstra . Ho preso la pseudo codice qui sotto direttamente da Wikipedia e cambiato solo 5 piccole cose:

  1. Rinominato dist a width (dalla linea 3 a)
  2. inizializzata ogni -infinity a infinity (linea 3)
  3. inizializzato la larghezza della sorgente di (s, a) = 300 (linea 8)
  4. Imposta il criterio finitura b (linea 14)
  5. Modificata la funzione di aggiornamento e il segno (linea 20 + 21) 

1  function Dijkstra(Graph, source):
2      for each vertex v in Graph:                                 // Initializations
3          width[v] := -infinity  ;                                // Unknown width function from 
4                                                                  // source to v
5          previous[v] := undefined ;                              // Previous node in optimal path
6      end for                                                     // from source
7      
8      width[source] := infinity ;                                 // Width from source to source
9      Q := the set of all nodes in Graph ;                        // All nodes in the graph are
10                                                                 // unoptimized – thus are in Q
11      while Q is not empty:                                      // The main loop
12          u := vertex in Q with largest width in width[] ;       // Source node in first case
13          remove u from Q ;
14          if width[u] = -infinity:
15              break ;                                            // all remaining vertices are
16          end if                                                 // inaccessible from source
17          
18          for each neighbor v of u:                              // where v has not yet been 
19                                                                 // removed from Q.
20              alt := max(width[v], min(width[u], width_between(u, v))) ;
21              if alt > width[v]:                                 // Relax (u,v,a)
22                  width[v] := alt ;
23                  previous[v] := u ;
24                  decrease-key v in Q;                           // Reorder v in the Queue
25              end if
26          end for
27      end while
28      return width;
29  endfunction

Alcuni (handwaving) spiegazione del perché questo funziona: si inizia con la fonte. Da lì, si dispone di capacità infinita di sé. Ora si controlla tutti i vicini della sorgente. Si assuma i bordi non tutti hanno la stessa capacità (nel tuo esempio, dicono (s, b)). Poi, non c'è modo migliore per raggiungere <=> poi via <=>, in modo da sapere la migliore capacità di caso di <=>. Si continua andando a migliori vicini di casa della serie nota di vertici, fino a raggiungere tutti i vertici.

La prova della correttezza di un algoritmo:

In qualsiasi fase dell'algoritmo, ci sarà 2 set di vertici A e B . I vertici in A saranno i vertici a cui è stato trovato il percorso massima capacità minima corretta. E della serie B ha i vertici a cui non abbiamo trovato la risposta.

induttivo Ipotesi : Ad ogni passo, tutti i vertici in serie A hanno i valori corretti di percorso massima capacità minima ad esse. vale a dire., tutte le iterazioni precedenti sono corrette.

Correzione del caso base : Quando l'insieme A ha solo il vertice S. Quindi il valore di S è l'infinito, che è corretto.

In iterazione corrente, abbiamo impostato

  

val [W] = max (val [W], min (val [V], width_between (V-W)))

Passo induttivo : Supponiamo, W è il vertice in serie B con la più grande val [W]. E W è eliminato dalla coda dalla coda e W è stata impostata la risposta val [W].

Ora, abbiamo bisogno di dimostrare che ogni altro percorso S-W ha una larghezza <= val [W]. Questo sarà sempre vero perché tutti gli altri modi di raggiungere W passerà attraverso qualche altro vertice (chiamare X) della serie B.

E per tutti gli altri vertici X in serie B, val [X] <= val [W]

Pertanto, qualsiasi altro percorso di W sarà limitata dalla val [X], che non è mai superiore a val [W].

Così la stima corrente di val [W] è ottimale e quindi l'algoritmo calcola i valori corretti per tutti i vertici.

Si potrebbe anche usare la "ricerca binaria sulla risposta" paradigma. Cioè, fare una ricerca binaria sui pesi, test per ogni peso w se è possibile trovare un percorso nel grafico usando solo i bordi del peso maggiore di O(|E|*log(max W)).

Il più grande O(|E|log |V|) per il quale è possibile (trovato attraverso la ricerca binaria) dà la risposta. Si noti che è necessario solo per verificare l'esistenza di un percorso, quindi basta un O (| E |) in ampiezza / profondità prima ricerca, non un percorso più breve. Quindi è <=> in tutto, paragonabile al Dijkstra / Kruskal / Prim di <=> (e non riesco a vedere subito una prova di quelli, anche).

Questo può essere risolto utilizzando un algoritmo stile BFS, tuttavia è necessario due varianti:

  • Invece di marcatura ogni nodo come "visitato", si contrassegna con il minimo peso lungo il percorso che hai preso per raggiungerla.

Ad esempio, se I e J sono vicini, che ha valore w1, e il peso del bordo tra questi è w2, quindi J = min (w1, w2).

  • Se si raggiunge un nodo marcato con un valore W1, potrebbe essere necessario osservazione e di processo che di nuovo, se l'assegnazione di un nuovo w2 valore (e w2> W1). Questo è necessario per essere sicuri di ottenere il massimo di tutti i minimi.

Ad esempio, se io e J sono vicini di casa, mi ha valore W1, J ha valore w2, e il peso del bordo tra loro è w3, quindi se min (w2, w3)> W1 è necessario notare J e di processo tutti sono di nuovo vicini.

Non sono sicuro che Prim funzionerà qui. Prendete questo controesempio: 

V = {1, 2, 3, 4}

E = {(1, 2), (2, 3), (1, 4), (4, 2)}

weight function w:
  w((1,2)) = .1, 
  w((2,3)) = .3
  w((1,4)) = .2
  w((4,2)) = .25

Se si applica Prim per trovare il percorso maxmin 1-3, a partire dal 1 selezionerà il 1 --> 2 --> 3 percorso, mentre la distanza maxmin è raggiunto per il sentiero che sale a 4.

Ok, rispondendo alla mia domanda proprio qui solo per cercare di ottenere un po 'di feedback che ho avuto sulla soluzione provvisoria ho lavorato prima di pubblicare qui:

Ogni nodo memorizza un "frammento percorso", questo è l'intero percorso sé finora.

0) impostare vertice corrente alla partenza vertice
1) Generare tutti i frammenti di percorso di questo vertice e aggiungerli a una coda di priorità
2) Prendere il frammento fuori la parte superiore della coda di priorità, e impostare il vertice corrente al vertice finale di quel percorso
3) Se il vertice corrente è il vertice di destinazione, quindi restituire il percorso
4) goto 1

Non sono sicuro che questo sarà trovare il percorso migliore, però, penso che la condizione di uscita nella fase tre è un po 'ambiziosa. Non riesco a pensare ad una migliore condizione di uscita, però, dal momento che questo algoritmo non stretti vertici (un vertice possibile fare riferimento in altrettanti frammenti percorso come gli piace) non si può solo aspettare fino a quando tutti i vertici sono chiusi (come Dijkstra di per esempio)

È comunque possibile utilizzare di Dijkstra!

Invece di usare +, utilizzare l'operatore min ().
Inoltre, ti consigliamo di orientare il cumulo / priority_queue in modo che le cose più grandi sono sulla parte superiore.

Qualcosa del genere dovrebbe funzionare: (probabilmente ho perso alcuni dettagli di implementazione) 

let pq = priority queue of <node, minimum edge>, sorted by min. edge descending
push (start, infinity) on queue
mark start as visited
while !queue.empty:
   current = pq.top()
   pq.pop()
   for all neighbors of current.node:
      if neighbor has not been visited
          pq.decrease_key(neighbor, min(current.weight, edge.weight))

E 'garantito che ogni volta che si arriva a un nodo hai seguito un percorso ottimale (in quanto a trovare tutte le possibilità in ordine decrescente, e non si può mai migliorare il vostro percorso con l'aggiunta di un bordo)

I limiti di tempo sono le stesse di Dijkstra -. O (Vlog (E))

EDIT: oh l'attesa, questo è fondamentalmente ciò che hai postato. LOL.

Autorizzato sotto: CC-BY-SA insieme a attribuzione
Non affiliato a StackOverflow
scroll top