количество отличных нециклических путей от [a, b] к [c, d]?
Я пишу sokoban решатель для забавы и практики, она использует простой алгоритм (что-то как BFS с небольшим количеством различия).
теперь я хочу оценить его время выполнения (O и омега). но потребность знать, как вычислить количество нециклических путей от вершины до другого в сети. на самом деле я хочу выражение, которое вычисляет количество допустимых путей между двумя вершинами 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
- Матрица 3x2 => 2 *** 2 ** пути => 4
- Матрица 3x3 => 2 *** 4 ** + 2 * 2 пути => 12
- Матрица 3x4 => 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-полные задачи имеют полностью полиномиальные рандомизированные схемы аппроксимации, а некоторые нет, но вы утверждаете, что не интересуетесь аппроксимацией. Возможно, есть способ воспользоваться сеточной структурой, например, для вычисления полинома Тутте, но у меня нет идей, как это сделать.
Подойдет ли матрица, показывающая края? Рассмотрите возможность построения матрицы, показывающей, где находятся края, т. Е. [a, b] = 1 <=> a-> b - ребро в графе, в противном случае - 0. Теперь возведите эту матрицу в различные степени, чтобы показать, сколько способов существует между вершинами за n шагов, а затем просуммируйте их, чтобы получить результат. Это всего лишь представление об одном способе решения проблемы, могут быть и другие способы сформулировать проблему.
Интересно, относится ли это к MathOverflow , в качестве другой идеи
Верно, что если у вас есть нулевая матрица, вы можете перестать возводить в степень, как в вашем случае, не так много мест, куда можно было бы пойти. 3, но пути от 1 до 3 будут прямыми и теми, которые проходят через 2, поэтому нужно сложить всего несколько матриц, прежде чем будет найдена вся нулевая матрица.
Я бы подумал, что должен быть способ вычислить границу, скажем, n ^ (n + 1), где n - количество вершин в графе, что указывало бы на точку остановки, поскольку к этой точке каждая вершина будут посещены один раз. Я не уверен, как решить проблему с циклическими путями, или можно ли предположить, что график не имеет циклов?
Есть похожая, но менее общая проблема в проекте Эйлера: http://projecteuler.net/index.php?section=problems&id=237
Я думаю, что некоторые из решений, описанных на форуме, могут быть расширены для решения вашего общего случая. Однако это довольно сложная проблема, особенно для вашего общего случая.
Чтобы получить доступ к их форумам, вам сначала нужно решить проблему. Я не буду публиковать здесь ответ и не буду ссылаться на определенный сайт, который содержит ответ, сайт, который вы можете легко найти в Google, выполнив поиск чего-то действительно очевидного.
Это открытый вопрос математики, имеющий прямое применение в химии и физике при использовании его для моделирования полимерных связей. Некоторые из самых ранних работ, выполненных в этом направлении, были выполнены во время Манхэттенского проекта (ядерная бомба Второй мировой войны).
Это более известно как проблема «Самопроизвольной ходьбы».
Я провел лето на математическом факультете своего университета, исследуя алгоритм Монте-Карло, называемый опорным алгоритмом, для аппроксимации параметров асимптотической подгонки числа самоизбегающих блужданий заданной длины n .
Пожалуйста, обратитесь к прекрасной книге Гордона Слейда под названием « Самопроизвольная прогулка », где подробно описаны методы, использованные для решения этой проблемы до сих пор.
Это очень сложная проблема, и мне интересно, какова ваша мотивация для ее рассмотрения. Возможно, вы сможете найти более простую модель для того, что вам нужно, потому что прогулки с самозащитой совсем не просты.