numero di distinti percorsi aciclici da A [a, b] a A [c, d]?

Question

Sto scrivendo un solver Sokoban per divertimento e pratica, utilizza un semplice algoritmo (qualcosa come BFS con un po 'di differenza).

ora voglio valutare il suo tempo di esecuzione (O e omega). ma è necessario sapere come calcolare il conteggio dei percorsi aciclici da un vertice all'altro in una rete. in realtà voglio un'espressione che calcoli il conteggio di percorsi validi, tra due vertici di una m * n matrice di vertici.

un percorso valido:

• visite ciascun vertice 0 o una volta.
• non hanno circuiti

per esempio, questo è un percorso valido:

alt text http://megapic.ir/images/f1hgyp5yxcu8887kfvkr.png

ma non è questo:

alt text http://megapic.ir/images/wnnif13ir5gaqwvnwk9d.png

Ciò che serve è un metodo per trova il conteggio di tutti i percorsi aciclici tra i due vertici a e b.

commenti sulla risoluzione di metodi e trucchi sono i benvenuti.

Answer 1

Non una soluzione, ma forse puoi pensare questa idea un po 'oltre. Il problema è che dovrai calcolare anche il percorso più lungo possibile per ottenere tutti i percorsi. Lo longest path problem è NP completo per grafici generici, quindi otterrà un tempo molto lungo anche per i relativi grafici di piccole dimensioni (8x8 e superiori).

Imagine the start-vertice è in alto, a sinistra ed il vertice fine è nell'angolo in basso a destra della matrice.

• Per una matrice 1x2 c'è solo 1 possibilità percorso
• matrice 2x2 => 2 *** 1 ** percorsi => 2
• matrice 3x2 => 2 *** 2 ** percorsi = > 4
• matrice 3x3 => 2 *** 4 ** + 2 * 2 percorsi => 12
• matrice 3x4 => 2 *** 12 ** + 12 + 2 tracciati => 38

Ogni volta che ho unito i risultati del calcolo precedente per il numero corrente di percorsi. Potrebbe essere che ci sia una stretta formulario per un grafico come planare, forse c'è anche un sacco di teoria per questo, ma io sono troppo stupido per questo ...

È possibile utilizzare il seguente Java (scusate, mi non sono un C++ esperto: - /) snippet per calcolare i possibili percorsi per le matrici più grandi:

public static void main(String[] args) { 
    new Main(3, 2).start(); 
} 
int xSize; 
int ySize; 
boolean visited[][]; 

public Main(int maxX, int maxY) { 
    xSize = maxX; 
    ySize = maxY; 
    visited = new boolean[xSize][ySize]; 
} 

public void start() { 
    // path starts in the top left corner 
    int paths = nextCell(0, 0); 
    System.out.println(paths); 
} 

public int nextCell(int x, int y) { 
    // path should end in the lower right corner 
    if (x == xSize - 1 && y == ySize - 1) 
     return 1; 

    if (x < 0 || y < 0 || x >= xSize || y >= ySize || visited[x][y]) { 
     return 0; 
    } 

    visited[x][y] = true; 
    int c = 0; 
    c += nextCell(x + 1, y); 
    c += nextCell(x - 1, y); 
    c += nextCell(x, y + 1); 
    c += nextCell(x, y - 1); 
    visited[x][y] = false; 
    return c; 
} 

=>

• 4x4 => 184
• 5x5 => 8512
• 6x6 => 1262 816
• 7x7 (anche questo semplice caso prende un sacco di tempo!) => 575780564

Questo significa che si potrebbe (solo teoricamente) calcolare tutti i percorsi possibili da ogni posizione di una matrice MxM al più basso, a destra angolo e quindi utilizzare questa matrice per cercare rapidamente il numero di percorsi. Dynamic programming (utilizzando i risultati calcolati in precedenza) potrebbe velocizzare un po 'le cose.

Answer 2

Una matrice che mostra i bordi funziona? Considera la costruzione di una matrice che mostri dove sono i bordi, vale a dire. [a, b] = 1 < => a-> b è un bordo nel grafico, 0 altrimenti. Ora, porta questa Matrice a vari poteri per mostrare quanti modi esistono per ottenere tra i vertici usando n passi e poi sommarli per ottenere il risultato. Questa è solo un'idea di un modo per risolvere il problema, potrebbero esserci altri modi per inquadrare il problema.

Mi chiedo se questo appartiene a MathOverflow, come un'altra idea

---

vero, che una volta che si dispone di una matrice nulla si può fermare exponentiating come nel tuo caso, non ci sono molti posti dove andare dopo 3 , ma i percorsi da 1 a 3 sarebbero diretti e quelli che passano attraverso 2, quindi ci sono solo poche matrici da sommare prima che venga trovato tutto lo zero.

---

Penserei ci dovrebbe essere un modo per calcolare un vincolato di dire n^(n + 1), dove n è il numero di vertici nel grafico, che indicherebbe un punto di arresto come da tale punto, ogni vertice sarà stato visitato una sola volta. Non sono sicuro di come far uscire i problemi ciclici dal problema, o si può supporre che il grafico sia privo di cicli?

Answer 3

C'è un problema simile, ma meno generale sul progetto di Eulero: http://projecteuler.net/index.php?section=problems&id=237

penso che alcune delle soluzioni descritte nel forum non ci può essere esteso per risolvere il caso generale. È un problema piuttosto difficile, specialmente per il tuo caso generale.

Per accedere ai forum, è necessario prima risolvere il problema. Non invierò la risposta qui, né collegherò a un determinato sito che elenca la risposta, un sito che puoi facilmente trovare su google cercando qualcosa di veramente ovvio.

Answer 4

Il problema generale del conteggio del numero di percorsi semplici in un grafico è #P completato. Alcuni problemi # P-completi hanno schemi di approssimazione randomizzati completamente polinomiali, altri no, ma tu dichiari di non essere interessato ad un'approssimazione. Forse c'è un modo per sfruttare la struttura della griglia, così come c'è per il calcolo del polinomiale Tutte, ma non ho idee su come farlo.

Answer 5

Questa è una questione aperta in matematica con applicazione diretta alla chimica e fisica in uso per modellare legami polimerici. Alcune delle prime lavoro svolto su questo è stato fatto durante il progetto Manhattan (bomba nucleare della Seconda Guerra Mondiale.)

è meglio conosciuto come il Sé Evitare problema Walk.

Ho passato un'estate nel mio dipartimento di matematica universitaria alla ricerca di un algoritmo di monte-carlo chiamato algoritmo pivot per approssimare i parametri di adattamento asintotico del numero di Passi autoevidenti di una determinata lunghezza n.

Si prega di fare riferimento all'eccellente libro di Gordon Slade intitolato "The Self Avoiding Walk" per un'ampia copertura dei tipi di tecniche utilizzate per affrontare questo problema finora.

Questo è un problema molto complesso e mi chiedo quale sia la vostra motivazione per considerarlo. Forse puoi trovare un modello più semplice per quello che vuoi, perché le Self Avoiding Walks non sono affatto semplici.