¿Recuento de caminos acíclicos distintos de A[a,b] a A[c,d]?

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

Pregunta

Estoy escribiendo un solucionador de sokoban para divertirme y practicar, 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 necesito saber cómo calcular el recuento de caminos acíclicos de un vértice a otro en una red.De hecho, quiero una expresión que calcule el recuento de caminos válidos, entre dos vértices de una matriz de vértices m*n.

un camino válido:

  • visita cada vértice 0 o una vez.
  • no tener circuitos

por ejemplo esta es una ruta válida:

texto alternativo http://megapic.ir/images/f1hgyp5yxcu8887kfvkr.png

pero esto no es:

texto alternativo http://megapic.ir/images/wnnif13ir5gaqwvnwk9d.png

Lo que se necesita es un método para encontrar el recuento de todos los caminos acíclicos entre los dos vértices. a y b.

Se aceptan comentarios sobre métodos y trucos de resolución.

¿Fue útil?

Solución

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

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

  • Para una matriz de 1x2 solo hay 1 camino posible
  • 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 combiné los resultados del cálculo anterior para el número actual de rutas.Podría ser que exista una fórmula cercana para un gráfico tan plano, tal vez incluso haya mucha teoría para eso, pero soy demasiado estúpido para eso...

Puede utilizar el siguiente fragmento de Java (lo siento, no soy un experto en C++ :-/) para calcular posibles rutas 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 => 1262816
  • 7x7 (¡incluso este caso simple lleva mucho tiempo!) => 575780564

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

Otros consejos

El problema general de contar el número de caminos simples en un gráfico es #P completa. Algunos problemas # P-completo tienen esquemas de aproximación totalmente aleatorios polinómicas, y otros no, pero que no pretenden estar interesado en una aproximación. Tal vez hay una manera de tomar ventaja de la estructura de la red, ya que no es para calcular el polinomio de Tutte, pero no tengo ninguna idea de cómo hacer esto.

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

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

Para obtener acceso a sus foros, primero tiene que resolver el problema. No se podrá enviar la respuesta aquí, ni un enlace a un sitio determinado que las listas de la respuesta, un sitio que se puede encontrar fácilmente en Google mediante la búsqueda de algo muy obvio.

Esta es una cuestión abierta en Matemáticas con aplicación directa a la química y física en su uso para modelar enlaces del polímero. Algunos de los primeros trabajos realizados en esto se hizo durante el proyecto Manhattan (bomba nuclear Segunda Guerra Mundial.)

Es mejor conocido como el Ser Evitar el problema Walk.

Me pasó un verano en mi departamento de matemáticas de la universidad la investigación de un algoritmo de Montecarlo llamado el algoritmo de pivote para aproximarse a los parámetros de la forma asintótica de la cantidad de auto-Evitar paseos de un n longitud dada.

Por favor, consulte el excelente libro de Gordon Slade titulado " El camino autoevitante " para una amplia cobertura de los tipos de técnicas utilizadas para abordar este problema por lo tanto lejos.

Este es un problema muy complejo y me pregunto lo que su motivación puede ser por considerarla. Tal vez pueda encontrar un modelo más simple de lo que desea, porque Auto Evitar Las caminatas no son simples en absoluto.

¿Una matriz que muestra el trabajo bordes? Considerar la construcción de una matriz de proyección donde los bordes son, es decir. [A, b] = 1 <=> a-> b es un borde en el gráfico, 0 en caso contrario. Ahora, levante esta matriz para diferentes potencias para mostrar cuántas maneras existen para conseguir entre los vértices utilizando n pasos y luego sumarlos para obtener el resultado. Esto es sólo 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 de 1 a 3 sería el directo y el que pasa por 2, por lo que sólo hay unos pocos matrices para añadir juntos antes de la toda cero uno se encuentra.

Yo pensaría que no debe haber una forma de calcular una cota de, por ejemplo n ^ (n + 1), donde n es el número de vértices en el gráfico, que indicaría un punto de parada como en ese momento, todos los vértices se han visitado una vez. No estoy seguro de cómo obtener las trayectorias cíclicas salir del problema sin embargo, o puede uno suponer que el gráfico está libre de ciclos?

Licenciado bajo: CC-BY-SA con atribución
No afiliado a StackOverflow
scroll top