cuenta de rutas acíclicas distintas de A [a, b] a A [c, d]?

Question

Estoy escribiendo un solucionador de sokoban para la diversión y la práctica, utiliza un algoritmo simple (algo así como BFS con un poco de diferencia).

ahora quiero estimar su tiempo de ejecución (O y omega). pero necesita saber cómo calcular el recuento de rutas acíclicas de un vértice a otro en una red. en realidad quiero una expresión que calcula el recuento de las rutas válidas, entre dos vértices de una matriz m * n de vértices.

una ruta válida:

• visitas cada vértice 0 o una vez.
• no tienen circuitos

por ejemplo, esta es una ruta válida:

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

pero esto no es:

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

Lo que se necesita es un método para encuentra la cuenta de todas las rutas acíclicas entre los dos vértices a y b.

comentarios sobre la resolución de métodos y trucos son bienvenidos.

Answer 1

No es una solución, pero tal vez pueda pensar esta idea un poco más. El problema es que también necesitará calcular la ruta más larga posible para obtener todas las rutas. El longest path problem es NP completo para gráficos generales, por lo que tardará mucho tiempo incluso en gráficos pequeños relativos (8x8 y mayores).

Imagine que el vértice de inicio está en la esquina superior izquierda, y el vértice final está en la esquina inferior derecha de la matriz.

• Para una matriz 1x2 sólo hay 1 posible camino
• matriz 2x2 => 2 *** 1 ** caminos => 2
• matriz 3x2 => 2 *** 2 ** caminos = > 4
• matriz 3x3 => 2 *** 4 ** + 2 * 2 caminos => 12
• matriz 3x4 => 2 *** 12 ** + 12 + 2 caminos => 38

Cada vez que combiné los resultados del cálculo anterior para el número actual de rutas. Podría ser que hay una fórmula cercana para un gráfico tan plano, tal vez incluso hay mucha teoría para eso, pero soy demasiado estúpido para eso ...

Puedes usar la siguiente Java (lo siento, no soy un ++ experto c: - /) de fragmento de código para calcular los posibles caminos para matrices más grandes:

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 (aunque este caso simple toma mucho tiempo!) => 575780564

Esto significa que podría (sólo teóricamente) calcular todas las posibles rutas desde cualquier posición de una matriz MxM en la parte inferior, a la derecha esquina y luego usar esta matriz para buscar rápidamente el número de caminos. Dynamic programming (usando resultados calculados previamente) podría acelerar un poco las cosas.

Answer 2

¿Funcionaría una matriz mostrando los bordes? Considere construir una Matriz que muestre dónde están los bordes, es decir. [a, b] = 1 < => a-> b es un borde en el gráfico, 0 en caso contrario. Ahora, eleve esta Matriz a varias potencias para mostrar cuántas formas existen para obtener los vértices utilizando n pasos y luego sumarlos para obtener el resultado. Esta es solo una idea de una forma de resolver el problema, puede haber otras formas de enmarcar el problema.

Me pregunto si esto pertenece en MathOverflow, como otra idea

---

Es cierto que una vez que tenga una matriz cero que podría dejar de exponenciación como en su caso, no hay muchos lugares para ir después de las 3 , pero los caminos del 1 al 3 serían el directo y el que pasa por el 2, por lo que solo hay unas pocas matrices para sumar antes de encontrar el cero absoluto.

---

yo creo que debe haber una forma de calcular una cota de, digamos, n^(n + 1), donde n es el número de vértices en el gráfico, que podrían indicar un punto de parada ya que en ese punto, cada vértice habrá sido visitado una vez. Sin embargo, no estoy seguro de cómo sacar los caminos cíclicos del problema, ¿o se puede suponer que el gráfico está libre de ciclos?

Answer 3

Hay un problema similar, pero menos general en el proyecto de Euler: http://projecteuler.net/index.php?section=problems&id=237

Creo que algunas de las soluciones descritas en el foro no se puede extender a resolver su caso general. Sin embargo, es un problema bastante difícil, especialmente para su caso general.

Para tener acceso a sus foros, primero necesita resolver el problema. No publicaré la respuesta aquí, ni vincularé a un determinado sitio que enumera la respuesta, un sitio que puedes encontrar fácilmente en Google buscando algo realmente obvio.

Answer 4

El problema general de contar el número de caminos simples en un gráfico es #P completo. Algunos problemas # P-complete tienen esquemas de aproximación aleatorizados totalmente polinomiales, y otros no, pero usted afirma que no está interesado en una aproximación. Quizás haya una forma de aprovechar la estructura de la cuadrícula, como lo es para computar el polinomio de Tutte, pero no tengo ninguna idea sobre cómo hacerlo.

Answer 5

Esta es una pregunta abierta en Matemáticas con aplicación directa a la química y la física al usarla para modelar enlaces de polímeros. Algunos de los primeros trabajos realizados sobre este tema se realizaron durante el proyecto de Manhattan (bomba nuclear Segunda Guerra Mundial).

Es mejor conocido como el problema de la caminata autoevaluante.

Pasé un verano en el departamento de matemáticas de mi universidad investigando un algoritmo monte-carlo llamado el algoritmo de pivote para aproximar los parámetros del ajuste asintótico del número de caminatas de auto-evitación de una longitud dada n.

Por favor, consulte el excelente libro de Gordon Slade titulado "The Self Avoiding Walk" para una amplia cobertura de los tipos de técnicas utilizadas para abordar este problema hasta el momento.

Este es un problema muy complejo y me pregunto cuál es su motivación para considerarlo. Tal vez puedas encontrar un modelo más simple para lo que quieres, porque las caminatas autoevaluativas no son simples en absoluto.