¿Cómo eliminar algunas aristas de un entramado para obtener exactamente k caminos?

Question

Tenemos un $n$ por $n$ de la red. Queremos encontrar una manera de eliminar algunas aristas, de modo que haya exactamente $k$ caminos de $(1,1)$ a $(n,n)$ de longitud $2n-2$ . (esto significa que nuestros caminos deben ser NE). No sé qué tipo de respuesta podría tener, pero estaría bien, si pudiera encontrar un algoritmo para resolver el problema.( Puedo escribir un programa para trabajar usando ese algoritmo).

Una cosa a tener en cuenta, es que si fusionamos a celosías cuadradas como la de la imagen, para hacer un $n+m$ por $n+m$ Por ejemplo, si hay p formas de ir de A a B con una longitud mínima, y q formas de ir de B a C, entonces tenemos p*q para ir de A a C. Esto significa que si k es primo, la respuesta no puede descomponerse en dos celosías cuadradas más pequeñas como la de la imagen. Sin embargo, no sé cómo ayuda esto.

Answer 1

No siempre es posible encontrar una respuesta a este problema: por ejemplo, con $n = 5$ , hay 70 rutas NE en la red completa desde $(1,1)$ a $(5,5)$ y se pueden eliminar aristas de forma que haya 66, 68 o 69 caminos, pero no se pueden tener 67 caminos.

Podemos ver esto marcando cada arista en la red por el número de caminos que cruzan esa arista.

Podemos eliminar uno o dos caminos borrando las aristas de las esquinas superior izquierda o inferior derecha, pero cualquier otra arista eliminará al menos 4 caminos, por lo que no podemos acabar con 67 caminos.

En lugar de eliminando bordes, podemos considerar sistemáticamente construyendo y demostrar que siempre podemos tener exactamente $k$ caminos para cualquier $k$ hasta $\binom{n+2}{3}$ .

Podemos llegar a $n$ caminos con bastante facilidad de esta manera:

                                            _
        |           |           |          |_|
        |           |          _|          |_|
        |          _|         |_|          |_|
________|   ______|_|   ______|_|    ______|_|
    1          2           3     ...    n

Entonces, si miramos el número de caminos que lleva cada arista horizontal de la columna anterior, vemos que la arista superior añade 1 camino, la siguiente añade 2, y así sucesivamente:

Sumando cada una de estas aristas a su vez, podemos tener $n+1$ hasta $n+(n-1)$ caminos; entonces podemos rellenar de nuevo desde arriba para tener $n + (n-1) + 1$ hasta $n + (n-1) + (n-2)$ y así sucesivamente, hasta que después de sumar todas las aristas de esta columna, tenemos un total de $n + (n-1) + (n-2) + \dotsb + 1 = \binom{n+1}{2}$ caminos.

En la columna a la izquierda de ésta, añadiendo el borde superior se añade 1 camino; el siguiente añade 3; el siguiente añade 6; así:

Estas son las sucesivas números triangulares . Es un poco más complicado, pero se puede demostrar que tomando combinaciones de éstas, y posiblemente eliminando un camino al suprimir una arista en la esquina inferior derecha, se puede obtener cualquier número de caminos hasta sumar todas estas aristas, dando un total de $\binom{n+2}{3}$ caminos.

(En general, el número total de caminos en un segmento rectangular, con $i$ bordes en un lado y $j$ aristas en la otra, incluyendo todas sus aristas, es $\binom{i+j}{i}$ .)

Para conseguir que un algoritmo produzca un subconjunto de aristas con exactamente $k$ caminos, la forma más fácil que se me ocurre es volver a tu planteamiento original, es decir, eliminar los bordes. Un algoritmo codicioso con backtracking funcionará. Para cada arista, determina el número de caminos que la cruzan. A continuación, eliminar una arista con el mayor número de caminos de cruce que no deja menos de $k$ caminos. Continúe hasta que tenga $k$ caminos a la izquierda. Si todas las aristas restantes tienen demasiados caminos de cruce, entonces sustituye la última arista eliminada, y prueba con otra.

Este algoritmo no tiene nada de particularmente inteligente o eficiente, pero está garantizado que encontrará una solución si es que existe. (Y es mucho más eficiente que el más brutal de los posibles algoritmos de fuerza bruta, es decir, comprobar cada posible subconjunto de aristas, lo que probablemente llevaría una década de cálculo incluso para $n = 6$ .)

Aquí hay una implementación en Python (escrita para Python 2.7.) Para calcular el número de rutas de cruce de una arista, se lleva la cuenta del número de rutas de cada vértice a todos los vértices al noreste del mismo. El número de rutas de cruce de una arista desde $(i,j)$ a $(k,l)$ es el número de rutas de $(1,1)$ a $(i,j)$ , veces el número de rutas de $(k,l)$ a $(n,n)$ . Cuando se elimina esta arista, el número de rutas cambia de cada vértice al suroeste de $(i,j)$ a cada vértice al noreste de $(k,l)$ . En concreto, el número de rutas que ya no están disponibles desde un vértice $v$ suroeste de $(i,j)$ a un vértice $w$ al noreste de $(k,l)$ es (el número de rutas de $v$ a $(i,j)$ ) por (el número de rutas de $(k,l)$ a $w$ ).

Para facilitar la implementación, los índices de los vértices van desde $(0,0)$ a $(n-1,n-1)$ en lugar de $(1,1)$ a $(n,n)$ .

import numpy as np
from scipy.misc import comb

class LatticePaths(object):
    def __init__(self, N):
        self.N = N
        pathct = np.vectorize(lambda i, j : comb(i+j, i, exact=True), otypes=[object])
        self.verts = [[pathct(*np.indices((N-r,N-c))) for c in range(N)] for r in range(N)]
        self.edges = [e for i in range(N) for j in range(N-1)
                        for e in [((i,j),(i,j+1)), ((j,i),(j+1,i))]]

    def npaths(self, edge):
        '''Number of paths crossing "edge", which is given as a pair of pairs
        ((i,j), (i+1,j)) or ((i,j), (i,j+1)). It is not checked if edge is really an edge.'''
        tor, toc = edge[1]
        return self.verts[0][0][edge[0]] * self.verts[tor][toc][-1,-1]

    def totpaths(self):
        '''The total number of paths from (0,0) to (N-1,N-1) in the lattice.'''
        return self.verts[0][0][-1,-1]

    def deledge(self, killedge):
        '''Remove the given edge from the lattice, updating the number of paths
        between each pair of vertices.'''
        self.edges.remove(killedge)
        (fror,froc), (tor,toc) = killedge
        #iterate over vertices 'below' killedge.from:
        for r in range(fror + 1):
            for c in range(froc + 1):
                self.verts[r][c][tor-r:,toc-c:] -= self.verts[r][c][fror-r,froc-c]*self.verts[tor][toc]

    def restore(self, edge):
        self.edges.append(edge)
        (fror,froc), (tor,toc) = edge
        for r in range(fror + 1):
            for c in range(froc + 1):
                self.verts[r][c][tor-r:,toc-c:] += self.verts[r][c][fror-r,froc-c]*self.verts[tor][toc]

    def __str__(self):
        s = ''
        for r in reversed(range(self.N)):
            for c in range(self.N):
                s += '|' if ((r,c),(r+1,c)) in self.edges and self.npaths(((r,c),(r+1,c))) else ' '
                s += '_' if ((r,c),(r,c+1)) in self.edges and self.npaths(((r,c),(r,c+1))) else ' '
            s += '\n'
        return s

def findpaths(N, K):
    '''Find a subset of the edges in the integer lattice from (0,0) to (N-1,N-1)
    so that there are a total of K distinct NE paths from (0,0) to (N-1,N-1).'''
    LP = LatticePaths(N)
    nRemove = LP.totpaths() - K 
    delsum = 0
    backstack = []
    while delsum < nRemove:
        edglst = sorted((e for e in LP.edges if 1 <= LP.npaths(e) <= nRemove - delsum), key=LP.npaths)
        while backstack and not edglst:
# edglst is empty; there are no suitable edges; backtrack
            #print "BACKTRACKING"
            edglst = backstack.pop()
            delsum -= LP.npaths(edglst[-1])
            LP.restore(edglst.pop())
        if not edglst: # backtracked to beginning
            break
        np = LP.npaths(edglst[-1])
        #print "Chose", np, "edge"
        backstack.append(edglst)
        LP.deledge(edglst[-1])
        delsum += np
    if delsum == nRemove:
        print LP
    else:
        print "No solution"

Este es el resultado de todos los números posibles $k$ cuando $n = 4$ .

           _ _ _    _ _ _      _ _    _ _ _        _        _  
          |        |_|       _|      |_|       _ _|     _ _|   
          |        |        |_|      |_|      |_|_|    |_|_|   
          |        |        |_|      |_|      |_|      |_|_|   
    0        1        2        3        4        5        6    
  _ _ _    _ _ _      _ _    _ _ _    _ _ _    _ _ _    _ _ _  
 |_|_|    | |_|     _|_|    |_|_|    |_|_ _|  |_|_ _|  |_|_ _| 
 |_|      |_|_|    |_|_|    |_|_|    |_|_ _|  |_|_|_|  |_|_|_| 
 |_|      |_|_|    |_|_|    |_|_|    |_|_|_|  |_|_ _|  |_|_|   
    7        8        9        10       11       12       13   
  _ _ _      _ _    _ _ _    _ _ _      _ _    _ _ _    _ _ _  
 |_|_ _|   _|_|_|  |_|_|_|  |_|_|_|   _|_|_|  |_|_|_|  |_|_|_| 
 |_|_|_|  |_|_|    |_|_|    |_|_|_|  |_|_|_|  |_|_|_|  |_|_|_| 
 |_|_|_|  |_|_|    |_|_|    |_|_ _|  |_|_|    |_|_|    |_|_|_| 
    14       15       16       17       18       19       20   

Funciona razonablemente rápido para entradas de hasta unos $n = 60$ en mi ordenador.

Apéndice sobre los números triangulares

Anteriormente, teníamos una colección de aristas tal que la adición del $i$ el creado $T_i$ muchos caminos, donde $T_i$ es el $i$ y afirmamos que sumando varias combinaciones de éstas, y posiblemente eliminando un camino (borrando una arista no relacionada), podríamos obtener cualquier número desde 1 hasta la suma de todas las aristas, $\sum_{i=1}^h T_i$ .

Podemos demostrarlo por inducción. Primero necesitamos un par de datos sobre los números triangulares:

Lema 1 . Después del tercer número triangular $T_3 = 6$ podemos decir $i + 1 < T_i$ , por inducción (el índice $i$ crece en uno cada vez, mientras que $T_i$ crece por $i$ cada vez).

Lema 2 . Después del cuarto número triangular $T_4 = 10$ , $T_m$ es siempre menor que la suma de los números triangulares más pequeños. Esto se deduce de la inducción: si $T_{m-1} \leq \sum_{i=1}^{m-2} T_i$ , entonces $T_m = T_{m-1} + m$ es menor que $\sum_{i=1}^{m-1} T_i$ ya que $m < T_{m-1}$ (por el lema 1.)

Para demostrar la afirmación, podemos mostrar cómo hacer los casos pequeños: $$ \begin{array}{rcccccccccc} \text{number} & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10\\ \text{combo} & 1 & 3 - 1 & 3 & 1 + 3 & 6 - 1 & 6 & 1 + 6 & 3 + 6 - 1 & 3 + 6 & 1 + 3 + 6 \end{array} $$ Ahora supongamos que para algunos $m \geq 3$ podemos escribir cualquier número desde 1 hasta $\sum_{i=1}^m T_i$ de esta manera. Entonces, añadiendo $T_{m+1}$ a cada una de estas combinaciones, podemos obtener cada número de $T_{m+1} + 1$ hasta $T_{m+1} + \sum_{i=1}^m T_i$ . Ya que por el Lemma 2, $T_{m+1} \leq \sum_{i=1}^m T_i$ , estos dos conjuntos dan lugar a todos los números del 1 al $\sum_{i=1}^{m+1} T_i$ como se ha reclamado.