Trova il percorso della discesa più ripida insieme alla lunghezza del percorso in una matrice

Alcune osservazioni su questo problema.

1. Stai cercando il percorso più lungo con il vincolo dato, quindi non è utile usare A * o Floyd-Warshall che sono progettati per trovare il percorso più breve.

2. In casi estremi, il percorso potrebbe contenere tutti i campi della griglia, ad esempio:

   1 2 3
   8 9 4
   7 6 5
   

   (qui, il percorso forma una spirale, ma sono possibili altre figure.)

   Pertanto, un algoritmo ideale non può essere migliore di O (n), che è anche la stessa complessità di visitare ogni campo una volta.

3. Dato un campo F e i suoi campi circostanti N, E, S, W per quanto esistono, possiamo calcolare la lunghezza del percorso L(F) come

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

   dove M ∈ {N, E, S, W} in modo che Value(M) < Value(F) e F(M) = max({F(X) | X ∈ {N, E, S, W}}) . Come pseudo-codice:

   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 prova della correttezza è lasciata come esercizio al lettore.

4. La funzione L(F) può essere calcolata usando la memoizzazione. Cioè, costruiamo una cache per L(F) in modo che ogni campo venga calcolato solo una volta. All'inizio, ogni calcolo potrebbe coinvolgere anche i calcoli per altri campi, nel caso peggiore tutti i campi. Pertanto, il nostro% co_de memoized ha una complessità da O (n) a O (1) a seconda che la cache contenga già i valori necessari. Ma in media l'intera complessità della cache è O (1) (ogni valore è calcolato una sola volta e viene richiesto solo un numero costante di volte).

   Quindi, se iteriamo su tutti i campi e calcoliamo la lunghezza del percorso per quel campo, questa iterazione sarà O (n). Pertanto, questo algoritmo con la memoizzazione è l'ideale!

5. Non possiamo applicare la programmazione dinamica, poiché non sappiamo quali campi debbano essere calcolati per primi. Bene, potremmo ordinare tutti i campi in base al loro valore e iniziare a calcolare il più basso per primo, ma questo finirebbe per essere più costoso e molto più complicato della costruzione della cache pigramente.

6. Durante il calcolo di L (F), possiamo anche in qualche modo tenere traccia del percorso che contiene alcuni campi e dei percorsi attualmente più lunghi. Tutto ciò non influirà sulla complessità.

Insieme emerge il seguente approccio:

• ogni campo della matrice ha tre proprietà: valore, lunghezza e campo successivo nel percorso.
• come dettaglio di implementazione, dovrai capire come recuperare i campi adiacenti per un determinato campo.
• la lunghezza viene calcolata pigramente.

• quando è selezionato L(F) neighbor, il campo successivo è impostato su M . Ciò potrebbe essere problematico se più di un campo ha le proprietà di M , ad es. in questa matrice:

  1 2 3
  4 9 8
  5 8 9
  

  Partendo da M s, non è immediatamente chiaro quale 9 debba essere parte del percorso ideale. O lo si implementa per tenere traccia di tutti i possibili percorsi (che non influisce sulla complessità) o si seleziona il percorso parziale con la discesa più ripida. Questo richiederà di percorrere entrambi i percorsi che non sono liberi ma O (n). Per evitare ciò, puoi memoizzare la pendenza massima come proprietà aggiuntiva di ciascun campo.

  A proposito, quell'esempio mostra un caso in cui ci sono due soluzioni 8 .

pseudo-codice:

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

Un approccio di programmazione dinamica dovrebbe funzionare.

Per ogni cella:

• Riduci il problema di trovare il percorso discendente migliore (più lungo, più ripido) da lì al problema di trovare il percorso migliore da ciascuno dei suoi vicini che è più piccolo e quindi aggiungere il passaggio a quel vicino per ottenere il miglior percorso dalla cella in questione.

• Memo (r) ize il percorso migliore da ogni cella lungo il percorso.

• In realtà non salva un percorso esplicito, salva solo la cella successiva sul percorso (in questo modo il percorso è lì, solo implicitamente).

Dovrebbe essere eseguito in tempo lineare rispetto alla dimensione della matrice se lo fai correttamente ... a meno che non mi fraintenda il problema, naturalmente.

Il codice potrebbe essere simile a:

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;
    }
}