Không phải là giải pháp nhưng có thể bạn có thể nghĩ ý tưởng này thêm một chút nữa. Vấn đề là bạn sẽ cần phải tính toán con đường dài nhất có thể để có được tất cả các đường dẫn. longest path problem là NP hoàn chỉnh cho đồ thị chung, do đó, nó sẽ có được một thời gian rất dài ngay cả đối với các đồ thị nhỏ tương đối (8x8 và lớn hơn).
Hãy tưởng tượng đỉnh bắt đầu nằm ở góc trên cùng bên trái và đỉnh cuối ở góc dưới bên phải của ma trận.
- Đối với một ma trận 1x2 chỉ có 1 con đường có thể
- 2x2 ma trận => 2 *** 1 ** đường dẫn => 2
- 3x2 ma trận => 2 *** 2 ** đường dẫn = > 4
- 3x3 ma trận => 2 *** 4 ** + 2 * 2 đường dẫn => 12
- 3x4 ma trận => 2 *** 12 ** + 12 + 2 đường dẫn => 38
Mỗi lần tôi kết hợp các kết quả từ phép tính trước đó cho số đường dẫn hiện tại. Nó có thể là có một công thức gần gũi cho một biểu đồ phẳng như vậy, có lẽ thậm chí còn có rất nhiều lý thuyết cho điều đó, nhưng tôi quá ngu ngốc cho điều đó ...
Bạn có thể sử dụng Java sau đây (xin lỗi, tôi không phải là một C++ chuyên gia: - /) đoạn mã để tính toán đường đi có thể cho ma trận lớn hơn:
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 => 1262 816
- 7x7 (ngay cả trường hợp đơn giản này mất rất nhiều thời gian!) => 575780564
Điều này có nghĩa bạn có thể (chỉ có trên lý thuyết) tính toán tất cả các con đường có thể từ bất kỳ vị trí của một ma trận MXM để thấp hơn, phải không góc và sau đó sử dụng ma trận này để nhanh chóng tra cứu số lượng đường dẫn. Dynamic programming (sử dụng kết quả tính toán trước đó) có thể tăng tốc độ một chút.
Số lượng đường dẫn có thể sẽ lớn hơn rất nhiều so với số đường dẫn được BFS xem xét vì vậy tôi không thấy nó sẽ giúp ích như thế nào. Một BFS liên tục kết hợp các đường dẫn tương tự với nhau làm giảm độ phức tạp. Độ phức tạp của BFS là O (| V | + | E |). – fgb
Bạn có muốn danh sách tất cả các đường dẫn hoặc chỉ số lượng đường dẫn không? Nếu bạn muốn số lượng đường dẫn, bạn sẽ giải quyết cho một xấp xỉ? – user287792
Tôi không muốn danh sách của họ. tôi muốn tính số lượng chúng mà không tính chúng. –