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

Question

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

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

правильный путь:

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

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

альтернативный текст http://megapic.ir/images/f1hgyp5yxcu8887kfvkr.png

но это не так:

альтернативный текст http://megapic.ir/images/wnnif13ir5gaqwvnwk9d.png

Необходим метод определения количества всех ациклических путей между двумя вершинами a и b .

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

Answer 1

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

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

• Для матрицы 1x2 возможен только 1 путь
• матрица 2х2 => 2 *** 1 ** пути => 2
• матрица 3х2 => 2 *** 2 ** пути => 4
• матрица 3х3 => 2 *** 4 ** + 2 * 2 пути => 12
• матрица 3х4 => 2 *** 12 ** + 12 + 2 пути => 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 до нижнего правого угла, а затем использовать эту матрицу для быстрого поиска количества путей. Динамическое программирование (с использованием предыдущих вычисленных результатов) может немного ускорить процесс.

Answer 2

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

Answer 3

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

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

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

Answer 4

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

Она больше известна как проблема самообслуживания.

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

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

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

Answer 5

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

Интересно, относится ли это к MathOverflow , как еще одна идея

---

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

---

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