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

Ответ 1

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

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

• Для матрицы 1x2 существует только один возможный путь
• 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 (извините, я не эксперт С++: -/), чтобы рассчитать возможные пути для больших матриц:

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

Ответ 2

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

Ответ 3

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

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

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

Ответ 4

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

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

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

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

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

Ответ 5

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

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

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

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