Самая длинная возрастающая последовательность 2D матричная рекурсия

Question

Мне было предложено новое домашнее задание, которое, по меньшей мере, было несколько разочаровывающим. По сути, у меня есть создать двумерный массив целых чисел следующим образом:

97 47 56 36 60 31 57 54 12 55 
35 57 41 13 82 80 71 93 31 62 
89 36 98 75 91 46 95 53 37 99 
25 45 26 17 15 82 80 73 96 17 
75 22 63 96 96 36 64 31 99 86 
12 80 42 74 54 14 93 17 14 55 
14 15 20 71 34 50 22 60 32 41 
90 69 44 52 54 73 20 12 55 52 
39 33 25 31 76 45 44 84 90 52 
94 35 55 24 41 63 87 93 79 24

и я должен написать рекурсивный метод или функцию, как вы хотите, чтобы вычислить самую длинную возрастающую подпоследовательность. В этом примере самая длинная увеличивающаяся подпоследовательность следующая:

(5,0)   with value 12
(6,0)   with value 14
(6,1)   with value 15
(6,2)   with value 20
(7,2)   with value 44
(7,3)   with value 52
(7,4)   with value 54
(6,3)   with value 71
(5,3)   with value 74
(4,3)   with value 96

Итак, я должен не только проверять значения N, S, E, W на строго большие значения, но я также должен учитывать диагонали. Я провел обширные исследования того, как решить эту проблему рекурсивно, однако мне не повезло, и рекурсия - мой самый слабый предмет (да, я знаю, насколько мощным он может быть в определенных ситуациях). Я видел что-то подобное, где кто-то упоминал акриловую графику, но это не то, что я ищу.

До сих пор я в основном дополнял свой 2D-массив нулями, чтобы мне не приходилось беспокоиться об ограничении, и я использую вложенные циклы for для обхода 2D-массива. Внутри этих циклов я в основном проверяю, имеют ли N, NE, E, SE, S, SW, W, NW большее значение, чем текущий элемент. Извините, если я вас расстроил, это моя первая попытка публикации. Если вам нужно, чтобы я опубликовал код, я сделаю это. Большое спасибо за ваше время!

Answer 1

Обновление

Недавно я изучил динамическое программирование и нашел лучший алгоритм для этого вопроса.

Алгоритм прост: найдите самую длинную длину для каждой точки и запишите результат в двумерный массив, чтобы нам не нужно было снова вычислять самую длинную длину для некоторых точек.

int original[m][n] = {...};
int longest[m][n] = {0};

int find() {
    int max = 0;
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            int current = findfor(i, j);
            if (current > max) { max = current; }
        }
    }
    return max;
}

int findfor(int i, int j) {
    if (longest[i][j] == 0) {
        int max = 0;
        for (int k = -1; k <= 1; k++) {
            for (int l = -1; l <= 1; l++) {
                if (!(k == 0 && l == 0) &&
                    i + k >= 0 && i + k < m &&
                    j + l >= 0 && j + l < n &&
                    original[i + k][j + l] > original[i][j]
                   )
                    int current = findfor(i + k, j + l);
                    if (current > max) { max = current; }
                }
            }
        }
        longest[i][j] = max + 1;
    }
    return longest[i][j];
}    

---

Рекурсия

1) начать с точки (и этот шаг должен быть сделан для всех необходимых точек)

2) если окружающая точка не больше, этот путь заканчивается; else выберите большую окружающую точку, чтобы продолжить путь, и перейдите к 2).

2.1) если (оконченный) путь длиннее записанного самого длинного пути, замените себя на самый длинный.

---

Подсказка

(меньше вычислений, но больше кодирования)

Для самого длинного пути, начальной точкой которого будет точка локального минимума, а конечной точкой будет точка локального максимума.

Местный минимум, меньше (или равен) всем (максимум) 8 окружающим точкам.

Локальный максимум, превышающий (или равный) все (максимум) 8 окружающих точек.

Доказательство

Если путь не начинается с локального минимума, то начальная точка должна быть больше, чем хотя бы окружающая точка, и, следовательно, путь может быть расширен. Отклонить! Таким образом, путь должен начинаться с локального минимума. Похоже по той причине, что заканчивается локальный максимум.

---

псевдокод

for all local minimum
  do a recursive_search

recursive_search (point)
  if point is local maximum
    end, and compare (and substitute if necessary) longest
  else
    for all greater surrounding points
      do a recursive_search

Answer 2

Другой подход: сортировка записей матрицы по значению в них.Итерация от самого большого до самого маленького.Для каждой записи вычислите самый длинный путь в постоянное время: самый длинный путь равен 1 + максимум по самым длинным путям для более крупных соседей (которые уже были вычислены).

Общее время: O (mn log (mn)) для сортировки записей матрицы, плюс O (mn) для поиска самых длинных путей.

Answer 3

Я знаю, что это очень старый вопрос, но я читаю книгу Любомира Станчева под названием «Изучение Java через игры», и проект главы 14 - это точный двумерный массив целых чисел. Задача состоит в том, чтобы найти самую длинную возрастающую последовательность, но только в двух направлениях: юг и восток, без диагоналей или чего-либо еще. Тем не менее, мне потребовались часы, чтобы понять логику, также не привыкшую к рекурсии. Я упростил задачу, создав вспомогательные методы, которые проверяют, является ли следующий индекс действительным в этом направлении (то есть не выходит за пределы и превышает текущее значение). Затем я поместил базовый случай в начало метода, когда нет следующего возможного индекса. Сложной задачей является присвоение переменной String, поэтому каждый раз, когда метод использует рекурсию, индексы сохраняются в String. Я решил это с помощью метода String.length () для сравнения длины каждой последовательности, когда существует более одного возможного пути. При наличии базовой логики для расширения метода все, что ему требуется, - это создание дополнительных вспомогательных методов в нужном направлении и добавление этих направлений в логику.

public static boolean isRightLegal(int[][] array, int row, int column) {
    //if we are at the last column
    if (column >= array[row].length - 1) {
        return false;
    }
    //if we are not at the one before last
    if ((column + 1) < array[row].length) {
        //if the current number is greater than the next
        if (array[row][column] > array[row][column + 1]) {
            return false;
        }
    }
    return true;
}

public static boolean isDownLegal(int[][] array, int row, int column) {
    //if we are at the last row
    if (row >= array.length - 1) {
        return false;
    }
    //if we are not at the one before last
    if ((row + 1) < array.length) {
        //if the current number is greater than the next
        if (array[row][column] > array[row + 1][column]) {
            return false;
        }
    }   
    return true;
}

public static String recursiveSequence(int[][] array, int row, int column, String path) {
    //base case: when we reach the end of the sequence
    if (! isDownLegal(array, row, column) && ! isRightLegal(array, row, column)) {
        return "(" + row + "," + column + ") ";
    }
    path = "(" + row + "," + column + ") ";
    //if both paths are valid
    if (isDownLegal(array, row, column) && isRightLegal(array, row, column)) {
        //calculate each sequence and pick the longest one
        if (recursiveSequence(array, (row + 1), column, path).length() > recursiveSequence(array, row, (column + 1), path).length()) {
            path += recursiveSequence(array, (row + 1), column, path);
        } else {
            path += recursiveSequence(array, row, (column + 1), path);
        }
        return path;
    }
    //if only the down path is valid
    if (isDownLegal(array, row, column)) {
        path += recursiveSequence(array, (row + 1), column, path);
    }
    //if only the right path is valid
    if (isRightLegal(array, row, column)) {
        path += recursiveSequence(array, row, (column + 1), path);
    }
    return path;
}

}

Answer 4

Java полное решение Он возвращает пути в консоль и возвращает самую длинную последовательность, но вы можете немного изменить этот код, и вы получите самый длинный путь также

public class HedgehogProblemSolver {

private int rowCount;
private int columnCount;
private int[][] fieldArray;
private int maxApplesCount = 0;

public HedgehogProblemSolver(int inputArray[][]) {
    this.fieldArray = inputArray;
    rowCount = inputArray.length;
    columnCount = inputArray[0].length;
}

public int solveProblem() {
    findPathRecursive(0, 0, "", 0);
    System.out.println("Max apple count: " + maxApplesCount);
    return maxApplesCount;
}

private void findPathRecursive(int row, int column, String path, int applesCount) {
    if (row == rowCount - 1) {
        //last row
        for (int i = column; i < columnCount; i++) {
            //just go right until last column
            path += "-[" + fieldArray[row][i]  + "](" + row + ", " + i + ")";
            applesCount += fieldArray[row][i];
        }
        pathResult(path, applesCount);
        return;
    }
    if (column == columnCount - 1) {
        //last column
        for (int i = row; i <= rowCount - 1; i++) {
            //just go down until last row
            path += "-[" + fieldArray[i][column] + "](" + i + ", " + column + ")";
            applesCount += fieldArray[i][column];
        }
        pathResult(path, applesCount);
        return;
    }

    path = path + "-[" + fieldArray[row][column] + "](" + row + ", " + column + ")";
    applesCount += fieldArray[row][column];

    //go down
    findPathRecursive(row + 1, column, path, applesCount);
    //go right
    findPathRecursive(row, column + 1, path, applesCount);
}

private void pathResult(String path, int applesCount) {
    System.out.println("Path: " + path + "; apples: " + applesCount);
    if (applesCount > maxApplesCount) {
        maxApplesCount = applesCount;
    }
}

}