count of distinct acyclic paths from A[a,b] to A[c,d]?
- by Sorush Rabiee
I'm writing a sokoban solver for fun and practice, it uses a simple algorithm (something like BFS with a bit of difference).
now i want to estimate its running time ( O and omega). but need to know how to calculate count of acyclic paths from a vertex to another in a network.
actually I want an expression that calculates count of valid paths, between two vertices of a m*n matrix of vertices.
a valid path:
visits each vertex 0 or one times.
have no circuits
for example this is a valid path:
but this is not:
What is needed is a method to find count of all acyclic paths between the two vertices a and b.
comments on solving methods and tricks are welcomed.
