Below is a python function to generate Markov path (the travelling salesman
problem).
def generate_travel_path(markov_matrix, n):
assert markov_matrix.shape[0] == markov_matrix.shape[1]
assert n <= markov_matrix.shape[0]
p = markov_matrix.copy()
path = [0] * n
for k in range(1, n):
k1 = path[k-1]
row_sums = 1 / (1 - p[:, k1])
p *= row_sums[:, np.newaxis]
p[:, k1] = 0
path[k] = np.random.multinomial(1, p[k1, :]).argmax()
assert len(set(path)) == n
return path
markov_matrix is a predefined Markov transition matrix. The code generates
a path starting from node zero and visit every node once based on this
matrix.
However I feel the function is quite slow. Below is the line-by-line
profile with a 53x53 markov_matrix:
Timer unit: 3.49943e-07 s
Total time: 0.00551195 sFile: <ipython-input-29-37e4c9b5469e>Function:
generate_travel_path at line 1Line # Hits Time Per Hit
% Time Line
Contents==============================================================
1 def
generate_travel_path(markov_matrix, n):
2 1 31 31.0 0.2 assert
markov_matrix.shape[0] == markov_matrix.shape[1]
3 1 12 12.0 0.1 assert n <=
markov_matrix.shape[0]
4
5 1 99 99.0 0.6 p = markov_matrix.copy()
6 1 12 12.0 0.1 path = [0] * n
7 53 416 7.8 2.6 for k in range(1, n):
8 52 299 5.8 1.9 k1 = path[k-1]
9 52 3677 70.7 23.3 row_sums = 1
/ (1 - p[:, k1])
10 52 4811 92.5 30.5 p = p *
row_sums[:, np.newaxis]
11 52 1449 27.9 9.2 p[:, k1] = 0
12 52 4890 94.0 31.0 path[k] =
np.random.multinomial(1, p[k1, :]).argmax()
13
14 1 51 51.0 0.3 assert len(set(path)) == n
15 1 4 4.0 0.0 return path
If I ran this function 25000 times, it will take me more than 125
seconds. Any headroom to improve the speed?
Below is a simple function to generate a Markov matrix.
def initial_trans_matrix(n):
x = np.ones((n, n)) / (n - 1)
np.fill_diagonal(x, 0.0)
return x
_______________________________________________
NumPy-Discussion mailing list
NumPy-Discussion@scipy.org
http://mail.scipy.org/mailman/listinfo/numpy-discussion
