Come descrivere un insieme di percorsi in un grafico con il minor numero di nodi possibile?

Question

Come descrivere un insieme di percorsi in un grafico con il minor numero di nodi possibile?

#1 da (3 voti)

6

Ho modellato un problema come un grafico composto da molti alberi. Alcuni dei nodi nel grafico possono appartenere a più di un albero. Sto cercando di descrivere un sottoinsieme di percorsi nel grafico con il minor numero possibile di nodi per archiviarli in modo efficiente. Tutti i percorsi partono da una radice e terminano in un nodo foglia.

Di seguito sono riportati alcuni esempi:

Supponiamo che il sottoinsieme di percorsi scelti tutto inizi dal nodo radice R. Quindi, posso descrivere tutti questi percorsi con "tutti i percorsi che iniziano da R". Determina in modo univoco i percorsi selezionati. Quindi ho solo bisogno di memorizzare R e un flag che specifica che questo nodo è una radice.
Uno scenario simile, ma nel caso in cui tutti i percorsi terminino in un nodo foglia specifico L. Possono essere descritti con "tutti i percorsi che terminano a L". Quindi ho solo bisogno di memorizzare L e un flag che specifica che questo nodo è una foglia.
Uno scenario simile, ma nel caso in cui tutti i percorsi attraversino uno specifico nodo intermedio I. Possono essere descritti con "tutti i percorsi che attraversano I". Quindi ho solo bisogno di memorizzare I e un flag che specifica che questo nodo è un nodo intermedio.

Il problema potrebbe diventare più complicato se i percorsi devono essere descritti con qualcosa di più di un semplice root / foglia / nodo intermedio. Ad esempio, potrei dover specificare molte radici, foglie e nodi intermedi. Tuttavia, voglio che la descrizione contenga il minor numero possibile di nodi.

C'è qualche algoritmo / euristica noto che posso applicare al mio problema?

Grazie mille.

trees graph

posta Mahdi 29.06.2016 - 19:16

fonte

1 risposta

Leggi altre domande sui tag trees graph

Best practice per il progetto di versioning dopo l'aggiornamento delle dipendenze PHP Framework per RESTful Web Service [chiuso]

score 3 · Answer 1

Stai provando a risolvere il problema di compressione (dal modo in cui è descritto). Ciò è stato dimostrato impossibile nel caso generale. A meno che tu non sappia qualcosa sui tuoi dati, come ad esempio un tipo di modello che si verifica che puoi rimuovere, sei bloccato.

Per dimostrare che si tratta del problema di compressione, assegniamo a ciascun nodo radice un numero che inizia da 0 e termina sul totale -1. Faremo lo stesso con i nodi foglia: iniziare da 0 e numerarli fino al totale - 1. Poiché si hanno alberi, ogni percorso può essere identificato in modo univoco dalla sua origine e dalla sua destinazione, quindi una coppia dell'ID del nodo radice e l'ID del nodo foglia.

Per memorizzarlo in modo efficiente puoi unire i due numeri usando: rootNumber * numero di nodi foglia + numero foglia. Quindi ora hai solo un numero intero. Memorizza tutti gli interi in una sequenza e ottieni (efficacemente) un numero casuale lungo.

Nel tuo esempio dei possibili modi di comprimere lo spazio di archiviazione, contrassegnando "tutti i percorsi iniziano con" e "tutti i nodi terminano" sono casi specifici e, a meno che non siano più probabili di qualsiasi altra configurazione, l'identificazione del caso è di no beneficio (per capire perché questo è il caso, investigare la codifica di Huffman).

Come per "Tutti i percorsi attraversano un nodo intermedio", beh questo è analogo al fatto che il numero finalmente calcolato ha un fattore, cioè "Tutti i numeri sono divisibili per due". È qualcosa che è intrinseco al sistema con cui si ha a che fare (la Divisibilità fa parte del sistema numerico). Anche questo non aiuta, a meno che, di nuovo, il tuo sistema abbia qualche bias (cioè pattern) nel modo in cui i percorsi sono creati.

Se sono veramente casuali, non c'è modo di comprimere i dati.