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

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

Domanda

Sto scrivendo un risolutore di Sokoban per il divertimento e la pratica, si utilizza un semplice algoritmo (qualcosa di simile a BFS con un po 'di differenza).

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

un percorso valido:

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

Per esempio, questo è un percorso valido:

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

, ma questo non è:

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

Ciò che è necessario è un metodo per trovare il conto di tutti i percorsi aciclici tra i due vertici a e b .

commenti su solving metodi e trucchi vengono accolti.

È stato utile?

Soluzione

Non è una soluzione, ma forse si può pensare questa idea un po 'più. Il problema è che avrete bisogno di calcolare anche il percorso più lungo possibile per ottenere tutti i percorsi. Il più lungo percorso problema è NP completo per i grafici generali, in modo da otterrà un tempo molto lungo, anche per piccole grafici relativi (8x8 e maggiori).

Imagine the start-vertice è in alto, a sinistra ed il vertice finale è 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 tracciati => 12
  • matrice 3x4 => 2 *** 12 ** + 12 + 2 tracciati => 38

Ogni volta che ho combinato i risultati del calcolo precedente per l'attuale numero 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 (mi dispiace, io non sono un esperto di C ++: - /) frammento di calcolare percorsi possibili 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 => 1.262.816
  • 7x7 (anche questo semplice caso prende un sacco di tempo!) => 575.780.564

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

Altri suggerimenti

Il problema generale di contare il numero di percorsi semplici in un grafico è #P completa. Alcuni problemi # P-completo hanno schemi di approssimazione randomizzati completamente polinomiale, e alcuni non lo fanno, ma sostengono di non essere interessato a un'approssimazione. Forse c'è un modo per sfruttare la struttura a griglia, in quanto v'è per calcolare il polinomio Tutte, ma non hanno alcuna idea su come fare questo.

C'è un problema simile, ma meno generale sul progetto di Eulero: http: // Project Euler .net / index.php? sezione = problemi & id = 237

Credo che alcune delle soluzioni descritte nel forum non ci può essere esteso per risolvere il caso generale. E 'un problema piuttosto difficile, però, soprattutto per il caso generale.

Per ottenere l'accesso ai loro forum, è necessario prima risolvere il problema. Non voglio postare la risposta qui, nè un collegamento a un certo sito che elenca la risposta, un sito che si può facilmente trovare su google la ricerca di qualcosa di davvero evidente.

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.)

E 'meglio conosciuto come il Sé Evitare problema Walk.

Ho passato un'estate al mio dipartimento di matematica universitari alla ricerca di un algoritmo Monte Carlo chiamato l'algoritmo di rotazione per approssimare i parametri della forma asintotica del numero di passeggiate Self-Evitando di una data n lunghezza.

Si prega di fare riferimento al libro eccellente di Gordon Slade dal titolo " Il Sé Evitando camminata " per una copertura estesa dei tipi di tecniche utilizzate per affrontare questo problema così lontano.

Questo è un problema molto complesso e mi chiedo che cosa il vostro motivazione può essere per considerarlo. Forse si può trovare un modello più semplice per ciò che si vuole, perché Appartamenti Evitare passeggiate non sono affatto semplice.

Sarebbe una matrice che mostra il lavoro bordi? Considerare la costruzione di una matrice che mostra dove i bordi sono, vale a dire. [A, b] = 1 <=> a-> b è un vantaggio nel grafico, 0 altrimenti. Ora, sollevare la Matrix per vari poteri per mostrare quanti modi esistono per ottenere tra i vertici utilizzando n passi e poi sommare loro per ottenere il risultato. Questo è solo un'idea di un modo per risolvere il problema, ci possono essere 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 il 3, ma i percorsi da 1 a 3 sarebbe quello diretto e quello che passa attraverso 2, così ci sono solo alcune matrici per aggiungere insieme prima che il tutto a zero si è trovato.

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 quel punto, ogni vertice saranno stati visitati una volta. Non sono sicuro di come ottenere i percorsi ciclici fuori dal problema, però, o si può Presumo che il grafico è libero di cicli?

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