связь с верхней клеткой
direction['up'] = (row-1, col)
if row+1 < size and lattice[row+1][col] != 0: #
связь с нижней клеткой
direction['down'] = (row+1, col) ways[(row, col)] = direction
return ways
# проверка существования пути от первого столбца до последнего в квадратной решетке
def exist_path_first_to_last_col(lattice): size = len(lattice)
start = [(row, 0) for row in range(size) if lattice[row][0] !=
0]
# print('', *start, sep='\n')
end = [(row, size-1) for row in range(size) if lattice[row][size-1] != 0]
# print('', *end, sep='\n') ways = graph_ways(lattice) for start_head in start:
head = start_head visited = [] path = [head]
while head not in end: direct = ways[head]
for dir in direct.keys():
if direct[dir] not in visited: path.append(direct[dir]) visited.append(direct[dir]) head = direct[dir] continue
if head in direct.values(): continue elif head == start_head: break
else: path.pop(len(path)-1)
head = path[len(path)-1] if head in end: return True
return False
# нахождение зависимости вероятности существования пути между первым и последним столбцами решетки от вероятности закрашивания клетки
def probab_exist_path_first_to_last_col(sample_size, N = 10): probab_exist_path = pd.DataFrame([], columns=['p','N', 'M',
'sample size', 'success way','probability']) for p in [i/100 for i in range(0, 101, 5)]:
probab = 0
for iter in range(sample_size):
lattice = get_square_lattice_by_algorithm_10(N, p) probab = probab +
exist_path_first_to_last_col(lattice) probab_exist_path.loc[len(probab_exist_path)] = [p, N,
math.ceil(p * N**2 / 4), sample_size, probab, probab/sample_size]
21
plot_info(data=probab_exist_path
,xdata='p', ydata='probability'
,title='''График зависимости вероятности
существования пути между первым и последним столбцами решетки
от вероятности закрашивания клетки'''
,xlabel='Вероятность закрашивания клетки'
,ylabel='Вероятность существования пути'
,type=0
,xstep = 0.1, ystep = 0.05)
return probab_exist_path
def menu(): N = 10
print('Размер сетки N =', N, end='\n')
p = rd.choice([i/100 for i in range(0, 101, 5)]) print('Коэф. вероятности p =', p, end='\n')
adjacency_matrix = get_adjacency_matrix_by_algorithm(get_square_lattice_by_algorith m_10, p, N)
print('\nМатрица смежности:', adjacency_matrix, sep='\n') view_graph(adjacency_matrix)
degree_spectrum = get_graph_degree_spectrum(adjacency_matrix) print('\nCпектр степеней графа:', degree_spectrum, sep='\n')
probab_exist_path = probab_exist_path_first_to_last_col(10000)
print('\nЗависимость вероятности существования пути между\ первым и последним столбцами решетки от вероятности закрашивания клетки:', probab_exist_path, sep='\n')
if __name__ == "__main__": menu()
22