Подсчет отдельных ациклических путей от [a, b] до [c, d]?

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

Вопрос

Я пишу Сокобан -решатель для развлечения и практики, он использует простой алгоритм (что -то вроде BFS с небольшой разницей).

Теперь я хочу оценить его время работы (O и Omega). но нужно знать, как рассчитать количество ациклических путей от вершины к другой в сети. На самом деле я хочу выражение, которое вычисляет подсчет допустимых путей между двумя вершинами матрицы AM*N вершин.

Допустимый путь:

  • посещает каждую вершину 0 или один раз.
  • нет схем

Например, это действительный путь:

Alt Text http://megapic.ir/images/f1hgyp5yxcu8887kfvkr.png

Но это не:

Alt Text http://megapic.ir/images/wnnif13ir5gaqwvnwk9d.png

Что нужно, так это метод найти подсчет всех ациклических путей между двумя вершинами а а также беременный.

Комментарии по решению методов и трюков приветствуются.

Это было полезно?

Решение

Не решение, но, возможно, вы можете подумать, что эта идея немного дальше. Проблема в том, что вам нужно рассчитать также самый длинный путь, чтобы получить все пути. А Самая длинная проблема пути является ли NP завершено для общих графиков, поэтому он получит очень много времени даже для относительных небольших графиков (8x8 и больше).

Представьте, что Start-Vertex находится в верхней части, левый угол, а конечная вершина находится в нижнем правом углу матрицы.

  • Для матрицы 1x2 есть только 1 возможный путь
  • 2x2 matrix => 2 *** 1 ** paths => 2
  • 3x2 matrix => 2 *** 2 ** paths => 4
  • 3x3 matrix => 2 *** 4 ** + 2*2 PATHS => 12
  • 3x4 Matrix => 2 *** 12 ** + 12 + 2 PATHS => 38

Каждый раз, когда я объединял результаты предыдущего расчета для текущего количества путей. Может случиться так, что для такого плоского графика есть близкая форма, возможно, для этого есть даже много теории, но я слишком глуп для этого ...

Вы можете использовать следующий фрагмент Java (извините, я не эксперт C ++:-/) для расчета возможных путей для больших матриц:

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 (даже этот простой случай занимает много времени!) => 575780564

Это означает, что вы можете (только теоретически) вычислить все возможные пути из любого положения матрицы MXM до нижнего, правого угла, а затем использовать эту матрицу, чтобы быстро искать количество путей. Динамическое программирование (Используя предыдущие вычисленные результаты) может немного ускорить ситуацию.

Другие советы

Общая проблема подсчета количества простых путей на графике завершена. Некоторые проблемы #P-Complete имеют полностью полиномиальные рандомизированные схемы приближения, а некоторые нет, но вы утверждаете, что не заинтересованы в приближении. Возможно, есть способ воспользоваться структурой сетки, как и для вычисления полинома Tutte, но у меня нет никаких идей о том, как это сделать.

Существует аналогичная, но менее общая проблема в проекте Euler: http://projecteuler.net/index.php?section=problems&id=237

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

Чтобы получить доступ к их форумах, вам сначала нужно решить проблему. Я не буду размещать ответ здесь и не ссылаюсь на определенный сайт, который перечисляет ответ, сайт, который вы можете легко найти в Google, поиск чего -то действительно очевидного.

Это открытый вопрос в математике с прямым применением химии и физики при использовании его для моделирования полимерных связей. Некоторые из самых ранних работ, проделанных над этим, были проведены во время проекта Манхэттена (ядерная бомба Второй мировой войны.)

Это более известно как проблема, избегающую самостоятельного избегания.

Я провел лето в своем университетском факультете математики, исследуя алгоритм Монте-Карло, называемый алгоритмом Pivot, чтобы приблизительно параметры асимптотической соответствия количества самообожных прогулок данной длины n.

Пожалуйста, обратитесь к отличной книге Гордона Слэйда под названием "Самостоятельная прогулка«Для обширного охвата типов методов, используемых для решения этой проблемы до сих пор.

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

Будет ли матрица, показывающая края работать? Подумайте о создании матрицы, показывающей, где есть края, т.е. [a, b] = 1 <=> a-> b-это преимущество на графике, 0 в противном случае. Теперь поднимите эту матрицу на различные полномочия, чтобы показать, сколько способов получить между вершинами, используя n шагов, а затем суммируйте их, чтобы получить результат. Это просто идея одного способа решения проблемы, могут быть и другие способы создать проблему.

Интересно, принадлежит ли это Mathoverflow, как другая идея

Правда, что после того, как у вас будет нулевая матрица, вы можете прекратить экспоненты, так как в вашем случае не так много мест, где можно пойти после 3, но пути от 1 до 3 были бы прямыми, и тем, кто проходит 2, так что Есть только несколько матриц, которые можно сложить вместе, прежде чем будет найдено все ноль.

Я думаю, что должен быть способ вычислить границу, скажем, n^(n+1), где n - количество вершин на графике, что указывает на точку остановки, поскольку к этому моменту каждая вершина будет посетил один раз. Я не уверен, как вытащить циклические пути из проблемы, или можно предположить, что график свободен от циклов?

Лицензировано под: CC-BY-SA с атрибуция
Не связан с StackOverflow
scroll top