Encuentre la ruta de mayor pendiente junto con la longitud de la ruta en una matriz

7

Encontré este problema - Te dan una cuadrícula con números que representan la elevación en un punto en particular. Desde cada recuadro de la cuadrícula, puede ir hacia el norte, sur, este y oeste, pero solo si la elevación del área en la que está entrando es menor que en la que está, es decir, solo puede descender. Puede comenzar en cualquier parte del mapa y está buscando un punto de partida con el camino más largo hacia abajo, medido por la cantidad de casillas que visita. Y si hay varios caminos hacia abajo de la misma longitud, desea tomar uno con la caída vertical más pronunciada, es decir, la mayor diferencia entre su elevación inicial y su elevación final. Ex Grid:

4 8 7 3 
2 5 9 3 
6 3 2 5 
4 4 1 6

En este mapa en particular, el camino más largo hacia abajo es de longitud = 5 y es: 9-5-3-2-1.

Hay otro camino que también tiene la longitud cinco: 8-5-3-2-1. caer de 9 a 1 (8) es una caída más pronunciada que de 8 a 1 (7). WAP para encontrar la ruta más larga (y luego la más empinada).

He trabajado en Floyd Warshalls, DAG + Topological topting, traté de pensar en DFS, aunque en DP, varias cosas pero no puedo encontrar una manera de pensar. Cualquier puntero + pseudo código simple para el enfoque sería útil.

    
pregunta WeirdAl 04.01.2016 - 08:45

2 respuestas

10

Algunas observaciones sobre este problema.

  1. Está buscando la ruta más larga con la restricción dada, por lo que no es útil usar A * o Floyd-Warshall, que están diseñados para encontrar la ruta más corta.

  2. En casos extremos, la ruta podría contener todos los campos de la cuadrícula, por ejemplo:

    1 2 3
    8 9 4
    7 6 5
    

    (aquí, el camino forma una espiral, pero otras figuras son posibles.)

    Por lo tanto, un algoritmo ideal no puede ser mejor que O (n), que también tiene la misma complejidad que visitar una vez cada campo.

  3. Dado un campo F y sus campos circundantes N, E, S, W en la medida en que existen, podemos calcular la longitud de ruta L(F) como

           ⎧ 1 + F(M) if M exists
    L(F) = ⎨
           ⎩ 0        otherwise
    

    donde M ∈ {N, E, S, W} para que Value(M) < Value(F) y F(M) = max({F(X) | X ∈ {N, E, S, W}}) . Como pseudocódigo:

    def L(F):
      lower = {X for X in {N, E, S, W} if X.value < F.value}
      if lower.is_empty:
        return 0
      return 1 + max({ L(X) for X in lower})
    

    La prueba de corrección se deja como un ejercicio para el lector.

  4. La función L(F) se puede calcular utilizando la memorización. Es decir, construimos un caché para L(F) para que cada campo solo se calcule una vez. Al principio, cada cálculo puede implicar los cálculos para otros campos también, en el peor de los casos todos los campos. Por lo tanto, nuestro memoized L(F) tiene complejidad O (n) a O (1) dependiendo de si el caché ya contiene los valores necesarios. Pero, en promedio, toda la complejidad de la memoria caché es O (1) (cada valor se calcula una sola vez y solo se solicita un número constante de veces).

    Entonces, si iteramos sobre todos los campos y calculamos la longitud del camino para ese campo, esta iteración será O (n). Por lo tanto, este algoritmo con memoria es ideal!

  5. No podemos aplicar la programación dinámica, ya que no sabemos qué campos tendrían que calcularse primero. Bueno, podríamos ordenar todos los campos por su valor y comenzar a calcular el más bajo primero, pero eso terminaría siendo más caro y mucho más complicado que compilar la memoria caché con pereza.

  6. Al calcular L (F), también podemos mantener un seguimiento de la ruta que contiene algún campo y las rutas más largas actualmente. Todo esto no afectará la complejidad.

Juntos, surge el siguiente enfoque:

  • cada campo en su matriz tiene tres propiedades: valor, longitud y siguiente campo en la ruta.
  • como detalle de la implementación, deberá averiguar cómo recuperar los campos vecinos para un campo determinado.
  • la longitud se calcula perezosamente.
  • cuando se selecciona el vecino M , el siguiente campo se establece en M . Esto podría ser problemático si más de un campo tiene las propiedades de M , por ejemplo. en esta matriz:

    1 2 3
    4 9 8
    5 8 9
    

    A partir de 9 s, no está claro de inmediato qué 8 debería formar parte de la ruta ideal. O implementa esto para hacer un seguimiento de todas las rutas posibles (lo que no afecta a la complejidad), o selecciona la ruta parcial con el descenso más pronunciado. Esto requerirá que camines ambos caminos, lo cual no es gratis sino O (n). Para evitar esto, puede memorizar la pendiente máxima como una propiedad adicional de cada campo.

    Por cierto, ese ejemplo muestra un caso donde hay dos soluciones 9-8-3-2-1 .

Pseudo-código:

record Field {
  value  : Int
  length : Count? = null
  next   : Field? = null
  slope  : Int?   = null
}

get-neighbours(f : Field): Set[Field] {
  ...
}

get-length(f : Field): Int {
  if f.length != null {
    return f.length
  }

  let next : Collection[Field] = get-neighbours(f)
    .where(x -> x.value < f.value) // must be smaller
    .max-by(x -> get-length(x)) // must have longest partial path
    .max-by(x -> x.slope) // prefer steepest path

  if next.is_empty {
    f.length = 0
    return f.length
  }

  let next = next.first // pick any field that satisfies all properties
  f.next = next
  f.slope = next.slope ?? f.value - next.value
  f.length = 1 + next.length
  return f.length
}

get-path(f: Field): Field generator {
  yield f
  if f.next != null {
    yield from get-path(f.next)
  }
}

let matrix : Array[height, Array[width, Field]] = {
  { Field(1), ... },
  ...,
}

// evaluate length for each field in matrix
// and keep track of longest paths

let mut longest = List()
let mut length = 0

for f in matrix {
  let l = get-lengh(f)
  if l > length {
    length = get-length(f)
    longest = List(f)
  }
  else if l == length {
    longest.add(f)
  }
}

// print out longest paths
for start in longest {
  println(List(get-path(start)))
}
    
respondido por el amon 04.01.2016 - 14:11
5

Un enfoque de programación dinámica debería funcionar.

Para cada celda:

  • Reduzca el problema de encontrar el mejor camino descendente (la pendiente más larga y empinada) desde allí hasta el problema de encontrar el mejor camino de cada uno de sus vecinos que sea más pequeño y luego agregue el paso a ese vecino para obtener el El mejor camino desde la celda en cuestión.

  • Memo (r) ize la mejor ruta de acceso de cada celda en el camino.

  • En realidad, no guarde una ruta explícita, solo guarde la siguiente celda en la ruta (de esa manera la ruta está ahí, solo implícitamente).

Eso debería ejecutarse en un tiempo lineal al tamaño de la matriz si lo haces correctamente ... a menos que no esté entendiendo el problema, por supuesto.

El código podría verse algo así como:

public class BestDynamicDescendingPathFinder {
    public static int[][] example = new int[][]{{4, 8, 7, 3},{2, 5, 9, 3},{6, 3, 2, 5},{4, 4, 1, 6}};

    public static void main(String[] args)
    {
        BestDynamicDescendingPathFinder finder = new BestDynamicDescendingPathFinder(example);
        System.out.println("Best overall: " + Arrays.toString(finder.find()));
        System.out.println("Best starting from some other cell: " + Arrays.toString(finder.unfoldBestPathFromCell(3, 3)));
    }

    private int[][] matrix;
    private PathInformation[][] informationForBestPathFromCellMemory;

    public BestDynamicDescendingPathFinder(int[][] aMatrix)
    {
        informationForBestPathFromCellMemory = new PathInformation[aMatrix.length][];
        matrix = new int[aMatrix.length][];

        for(int i = 0; i < aMatrix.length; i++)
        {
            informationForBestPathFromCellMemory[i] = new PathInformation[aMatrix[i].length];
            matrix[i] = new int[aMatrix[i].length];

            for(int j = 0; j < aMatrix[i].length; j++)
            {
                matrix[i][j] = aMatrix[i][j];
            }
        }
    }

    // find the best path by getting the best starting cell and unfolding the information for it
    public int[] find()
    {
        int currentBestStartingCellColumn = 0;
        int currentBestStartingCellRow = 0;
        for(int i = 0; i < matrix.length; i++)
        {
            for(int j = 0; j < matrix[i].length; j++)
            {
               if(getInformationForBestPathFromCell(i, j).compareTo(getInformationForBestPathFromCell(currentBestStartingCellColumn, currentBestStartingCellRow)) == 1){
                   currentBestStartingCellColumn = i;
                   currentBestStartingCellRow = j;
               }
            }
        }

        return unfoldBestPathFromCell(currentBestStartingCellColumn, currentBestStartingCellRow);
    }

    // unfold the best path (starting) from a cell by walking the PathInformation structures in memory
    private int[] unfoldBestPathFromCell(int colNum, int rowNum)
    {
        PathInformation currentCellInformation = getInformationForBestPathFromCell(colNum, rowNum);
        int[] path = new int[currentCellInformation.length];
        path[0] = matrix[colNum][rowNum];
        int idx = 1;

        while(currentCellInformation.length > 1)
        {
            path[idx] = matrix[currentCellInformation.nextCellColumn][currentCellInformation.nextCellRow];
            idx++;
            currentCellInformation = getInformationForBestPathFromCell(currentCellInformation.nextCellColumn, currentCellInformation.nextCellRow);
        }

        return path;
    }

    // get the information for the best path (starting) from a cell: from memory if available or calculate otherwise
    private PathInformation getInformationForBestPathFromCell(int colNum, int rowNum)
    {
        if(informationForBestPathFromCellMemory[colNum][rowNum] == null)
        {
            informationForBestPathFromCellMemory[colNum][rowNum] = calculateInformationForBestPathFromCell(colNum, rowNum);
        }
        return informationForBestPathFromCellMemory[colNum][rowNum];
    }

    // calculate the information for the best path (starting) from a cell by using the information for best paths from neighboring cells
    private PathInformation calculateInformationForBestPathFromCell(int colNum, int rowNum)
    {
        List<PathInformation> possiblePathsFromCell = new ArrayList<PathInformation>();
        if(colNum != 0 && matrix[colNum - 1][rowNum] < matrix[colNum][rowNum])
        {
            PathInformation p = getInformationForBestPathFromCell(colNum - 1, rowNum);
            possiblePathsFromCell.add(new PathInformation(p.length + 1, matrix[colNum][rowNum], p.endValue, colNum - 1, rowNum));
        }

        if(colNum != matrix.length - 1 && matrix[colNum + 1][rowNum] < matrix[colNum][rowNum])
        {
            PathInformation p = getInformationForBestPathFromCell(colNum + 1, rowNum);
            possiblePathsFromCell.add(new PathInformation(p.length + 1, matrix[colNum][rowNum], p.endValue, colNum + 1, rowNum));
        }

        if(rowNum != 0 && matrix[colNum][rowNum - 1] < matrix[colNum][rowNum])
        {
            PathInformation p = getInformationForBestPathFromCell(colNum, rowNum - 1);
            possiblePathsFromCell.add(new PathInformation(p.length + 1, matrix[colNum][rowNum], p.endValue, colNum, rowNum - 1));
        }

        if(rowNum != matrix[colNum].length -1 && matrix[colNum][rowNum + 1] < matrix[colNum][rowNum])
        {
            PathInformation p = getInformationForBestPathFromCell(colNum, rowNum + 1);
            possiblePathsFromCell.add(new PathInformation(p.length + 1, matrix[colNum][rowNum], p.endValue, colNum, rowNum + 1));
        }

        if(possiblePathsFromCell.isEmpty())
        {
            return new PathInformation(1, matrix[colNum][rowNum], matrix[colNum][rowNum], -1, -1);   
        }

        return Collections.max(possiblePathsFromCell);
    }
}

public class PathInformation implements Comparable<PathInformation>
{
    int length;
    int startValue;
    int endValue; 
    int nextCellColumn;
    int nextCellRow;

    public PathInformation(int length, int startValue, int endValue, int nextCellColumn, int nextCellRow) 
    {
        this.length = length;
        this.startValue = startValue;
        this.endValue = endValue;
        this.nextCellColumn = nextCellColumn;
        this.nextCellRow = nextCellRow;
    }

    @Override
    public int compareTo(PathInformation other) {
        if(this.length < other.length || (this.length == other.length && this.startValue - this.endValue < other.startValue - other.endValue)){
            return -1;
        }
        if(this.length > other.length || (this.length == other.length && this.startValue - this.endValue > other.startValue - other.endValue)){
            return 1;
        }
        return 0;
    }
}
    
respondido por el Hirle 04.01.2016 - 14:05

Lea otras preguntas en las etiquetas