Количество различных ациклических путей от A[a,b] до A[c,d]?
Я пишу решатель Сокобана для развлечения и практики, он использует простой алгоритм (что-то вроде BFS с небольшой разницей).
Теперь я хочу оценить его время работы ( O и Omega). но нужно знать, как рассчитать количество ациклических путей от одной вершины к другой в сети. на самом деле я хочу выражение, которое вычисляет количество допустимых путей между двумя вершинами матрицы a m*n вершин.
действительный путь:
- посещает каждую вершину 0 или один раз.
- нет цепей
например, это правильный путь:
http://megapic.ir/images/f1hgyp5yxcu8887kfvkr.png
но это не так
http://megapic.ir/images/wnnif13ir5gaqwvnwk9d.png
Что необходимо, так это метод для определения количества всех ациклических путей между двумя вершинами a и b.
комментарии по методам решения и приемы приветствуются.
5 ответов
Не решение, но, возможно, вы можете подумать об этой идее немного дальше. Проблема в том, что вам нужно рассчитать также самый длинный путь, чтобы получить все пути. Самая длинная задача прохождения - NP-полная для общих графов, поэтому она будет очень долгой даже для относительно небольших графов (8x8 и более).
Представьте, что начальная вершина находится в верхнем левом углу, а конечная вершина находится в нижнем правом углу матрицы.
- Для матрицы 1x2 возможен только 1 путь
- Матрица 2x2 => 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 до нижнего правого угла, а затем использовать эту матрицу для быстрого поиска количества путей. Динамическое программирование (с использованием предыдущих вычисленных результатов) может немного ускорить процесс.
Общая проблема подсчета количества простых путей в графе является #P полной. Некоторые #P-полные задачи имеют полностью полиномиальные схемы рандомизированной аппроксимации, а некоторые нет, но вы утверждаете, что не заинтересованы в аппроксимации. Возможно, есть способ воспользоваться преимуществами структуры сетки, как и для вычисления полинома Тутте, но у меня нет идей, как это сделать.
Существует похожая, но менее общая проблема в проекте Euler: http://projecteuler.net/index.php?section=problems&id=237
Я думаю, что некоторые решения, описанные на форуме, могут быть расширены для решения вашего общего случая. Это довольно сложная проблема, особенно для вашего общего случая.
Чтобы получить доступ к своим форумам, сначала нужно решить проблему. Я не буду публиковать здесь ответ, а также не буду ссылаться на определенный сайт, на котором указан ответ, - сайт, который вы легко можете найти в Google, если найдете что-то действительно очевидное.
Это открытый вопрос в математике с непосредственным применением к химии и физике при его использовании для моделирования полимерных связей. Часть самой ранней работы, проделанной над этим, была сделана во время Манхэттенского проекта (Вторая мировая война по атомной бомбе).
Это больше известно как проблема Самопутешествия.
Я провел лето на своем факультете математики в университете, исследуя алгоритм Монте-Карло, называемый алгоритмом разворота, для аппроксимации параметров асимптотической подгонки числа самоходных прогулок заданной длины. n,
Пожалуйста, обратитесь к превосходной книге Гордона Слэйда под названием " Самостоятельная прогулка", где вы найдете подробное описание методов, используемых для решения этой проблемы.
Это очень сложная проблема, и мне интересно, какова ваша мотивация для ее рассмотрения. Возможно, вы можете найти более простую модель для того, что вы хотите, потому что самостоятельные прогулки совсем не просты.
Будет ли работать матрица, показывающая края? Рассмотрим построение матрицы, показывающей, где находятся ребра, т.е. [a,b]=1 <=> a->b - ребро в графе, в противном случае - 0. Теперь поднимите эту Матрицу до различных степеней, чтобы показать, сколько существует способов добраться между вершинами, используя n шагов, а затем суммируйте их, чтобы получить результат. Это всего лишь идея одного способа решения проблемы, могут быть и другие способы ее решения.
Интересно, если это относится к MathOverflow, как еще одна идея
Правда, если у вас есть нулевая матрица, вы можете перестать возводить в степень, как в вашем случае, не так много мест, где можно идти после 3, но пути с 1 по 3 будут прямыми, а пути, проходящие через 2, поэтому есть только несколько матриц, которые нужно сложить, прежде чем будет найден нулевой.
Я думаю, что должен быть способ вычислить границу, скажем, n^(n+1), где n - количество вершин в графе, которое будет указывать точку остановки, так как к этой точке каждая вершина будет посетил один раз. Я не уверен, как вывести циклические пути из проблемы, хотя, или можно предположить, что граф свободен от циклов?