Идея проста. Наблюдаем последовательность состояний. И требуется оценить насколько эта последовательность предсказуема.
Пусть с равной вероятностью следуют состояния 1 и 2. Этой последовательностью может быть [ 1, 2, 1, 1, 2, 2, 1, 2, 2, 1]. Можем ли мы однозначно предугадать следующее состояние? По этой информации - нет.
Теперь допустим, что есть ещё одна последовательность [3, 4, 4, 3, 3, 4, 3, 3, 4], синхронная первой. Её можно интерпретировать так:
3:1->2 (если 3, то 1 переходит в 2)
4:2->1 (если 4, то 2 переходит в 1)
4:1->1 (если 4, то 1 переходит в 1)
3:2->2 (если 3, то 2 переходит в 2).
[1, 2, 1, 1, 2, 2, 1, 2, 2, 1]
[3, 4, 4, 3, 3, 4, 3, 3, 4, ]Мы по прежнему не знаем каким будет состояние после состояния 1 (последнее в списке). Но, если будет известно, что следующим после 4 будет 3, то последует 2.
Очеловечим рассуждения. Представим себе, что вошли в комнату и целью является включить свет. Обозначим: 1 - свет не горит, 2 - свет горит. Меняем состояние выключателя на включение 5 и на выключение 6). Пусть эта последовательность такова [5, 6, 5, 6, 5, 6, 5, 6, 5].
[1, 2, 1, 1, 2, 2, 1, 2, 2, 1]
[5, 6, 5, 6, 5, 6, 5, 6, 5, ]Имеем при действии 5 (включить): состояние 1 переходит в состояние 2 (свет есть); но также состояние 1 перейдёт в состояние 1 (света нет) при этом же действии, т.е. 5:1->2|1. Что это значит? То, что смена состояний выключателя не приводит однозначно к целевому состоянию.
Вопрос: может этим выключателем является нечто иное? Им может быть, например: 3 - книжка на нижней полке. 4 - она же на верхней полке.
Так как же, не зная заранее что на что влияет, количественно оценить предсказуемость следующих состояний? Введём коэффициент однозначности. Отнесем количество переходов, как если бы все переходы были однозначны, к всем случившимся. Чем он ближе к единице, тем более предсказуема сменяемость состояний. Тем с меньшим количеством ошибок можно проложить оптимальный маршрут к целевому состоянию.
#ДОПОЛНЕНИЕ к первоначальному варианту статьи
#Если за смену состояний взять первую последовательность:
[1, 2, 1, 1, 2, 2, 1, 2, 2, 1]
[3, 4, 4, 3, 3, 4, 3, 3, 4, ]
graph = {
1: [[2, 3], [1, 4]], # 2=3(1) 1=4(1)
2: [[1, 4], [2, 3]] # 1=4(2) 2=2(3)
} #ku=4/4 имеем 100% детерминировнный
#Также за смену состояний возьмем первую последовательность:
[1, 2, 1, 1, 2, 2, 1, 2, 2, 1]
[5, 6, 5, 6, 5, 6, 5, 6, 5, ]
graph = {
1: [[2|1, 5], [2, 6]], # 2|1=5(1) 2=6(1)
2: [[1|2, 6], [2|1, 5]] # 1|2=6(2) 2|1=5(2)
} #ku=4/7 имеем большую долю неоднозначности
Ниже код программы, который по имеющимся отдельным наблюдениям, может этот коэффициент однозначности рассчитывать для разных гипотез.
За объект исследования возьмем граф с некоторой неоднозначностью (из состояния 4 следует как состояние 5, так и состояние 1 при одном и том же действии 11).
Ниже красным - коэффициент однозначности оригинала. Зеленая (первая) гипотеза явно проигрывает синей (второй), поскольку ее коэффициент однозначности меньше.
Далее, учитывая вторую гипотезу, можно уже прокладывать маршруты к целевому состоянию.
import random
import matplotlib.pyplot as plt
import numpy as np
class Hd():
def __init__(self, graph):
self.graph = graph
def rnd_get(self, v):
return random.choice(v.split("|"))
def show(self, graph):
for x in graph:
print(x, ":", graph[x])
def get_ku(self, graph):
'''return (коэффициент однозначности, размер)'''
n = 0; u = 0
for x in graph:
for y in graph[x]:
if y[0]:
u += y[0].count("|")
n += 1
if n != 0:
return (round(1- u/(n+u), 3), n+u)
else:
return (None, None)
def get_states(self, x, f_list = [], n=10):
x_list = []
x_list.append(x)
if f_list != []:
for f in f_list:
xf = [xf for xf in g[x] if xf[1] == f]
if not xf:
x_list.append(''); f_list[len(x_list)-2] = ''
return (x_list, f_list[:len(x_list)-1])
x = self.rnd_get(xf[0][0])
x_list.append(x)
else:
for i in range(n):
if not self.graph[x]:
x_list.append(''); f_list.append('')
break
t = random.choice(self.graph[x])
f = t[1]
x = random.choice(t[0].split('|'))
x_list.append(x); f_list.append(f)
if len(f_list) == len(x_list) -1:
return (x_list, f_list)
else:
return ([], [])
def get_yfx(self, f_list, x_list, t = True):
if len(x_list) == len(f_list):
x_list.append('')
path = []
for i in range(len(f_list)):
path.append((x_list[i], f_list[i], x_list[i+1]))
if t:
return path #(x, f, next_x)
else:
p = []
for xfy in path:
if xfy[2] != '':
p.append(xfy[2]+'='+xfy[1]+'('+xfy[0]+')')
return p
def flow(self, path, rnd=False):
if not path: return []
fl = []
for p in path:
if not rnd:
fl.append(p[:-1])
else:
pr = list(p[:-1])
random.shuffle(pr)
fl.append(tuple(pr))
return fl
def fORx(self, flow, f=0):
'''index: f=0, x=1 or x=0, f=1'''
def add_empty():
empty = []
for k in graph:
for x in graph[k]:
z = list(set(x[0].split('|')) - set(list(graph.keys())))
if z:
empty.append(z[0])
return empty
if not flow: return []
graph = {}
fli = flow[0]
for t in flow[1:]:
if f == 0:
if fli[1] not in graph:
graph[fli[1]] = []
r = [(i, xf) for i,xf in enumerate(graph[fli[1]]) if xf[1] == fli[0]]
if r:
if t[1] not in r[0][1][0]:
x_new = r[0][1][0] + "|" + t[1]
if x_new != '':
graph[fli[1]][r[0][0]] = (x_new, r[0][1][1])
if not r:
if t[1] != '':
graph[fli[1]].append((t[1], fli[0]))
if f == 1:
if fli[0] not in graph:
graph[fli[0]] = []
r = [(i, xf) for i,xf in enumerate(graph[fli[0]]) if xf[1] == fli[1]]
if r:
if t[0] not in r[0][1][0]:
x_new = r[0][1][0] + "|" + t[0]
if x_new != '':
graph[fli[0]][r[0][0]] = (x_new, r[0][1][1])
if not r:
if t[0] != '':
graph[fli[0]].append((t[0], fli[1]))
fli = t
em = add_empty()
if em:
graph[em[0]] = []
return graph
def merge(self, g1, g2):
def find_index():
for i in range(len(graph[k])):
if graph[k][i][1] == x[1]:
return i
return -1
all_keys = set(list(g1.keys()) + list(g2.keys()))
graph = {}
for k in all_keys:
if k not in graph:
if k in g1:
graph[k] = g1[k]
else:
graph[k] = g2[k]
if k in g2:
for x in g2[k]:
ind = find_index()
if ind != -1:
if x[0] != []:
t1 = x[0].split('|')
if graph[k][ind] != -1:
t2 = graph[k][ind][0].split('|')
z = "|".join(set(t1+t2))
xf = [z, graph[k][ind][1]]
graph[k][ind] = xf
else:
graph[k].append(x)
return graph
#--------- main ---------#
if __name__ == "__main__":
g = {
"1": [["2", "11"], ["10", "15"]],
"2": [["3", "11"], ["9", "12"]],
"3": [["4", "11"], ["2", "13"], ["6", "12"]],
"4": [["5|1", "11"]],
"5": [["6", "11"]],
"6": [["7", "11"]],
"7": [["8", "11"], ["5", "12"]],
"8": [["9", "11"]],
#"9": [['1|5', '11']],
'9':[],
"10":[["5", "15"]]
}
hd = Hd(g)
r_ = hd.get_ku(hd.graph)
print("Исходный граф: Коэффициент однозначности ku = ", r_[0])
hd.show(hd.graph); print()
epochs = 50
ku_list = [[],[]]
gf = [{}, {}]
for i in range(epochs):
print("\n_____ЭПОХА = ", i+1)
x = random.choice(list(g.keys())); print("начинаем с состояния ", x)
#x = '1'
x_list, f_list = hd.get_states(x, [], n=20)
path = hd.get_yfx(f_list, x_list)
path_yfx = hd.get_yfx(f_list, x_list, t = False)
'''if path_yfx:
print("y=f(x) :", *path_yfx)
pass'''
print(" Наблюдение")
for fl in hd.flow(path, rnd=False):
print(*fl)
print("\n гипотеза 1: ")
gn = hd.fORx(hd.flow(path), f=0)
hd.show(gn)
gf[0] = hd.merge(gf[0], gn)
r = hd.get_ku(gf[0])
print("\nКоэффициент однозначности ku = ", r[0])
ku_list[0].append(r[0])
hd.show(gf[0])
print()
print("\n гипотеза 2: ")
gn = hd.fORx(hd.flow(path), f=1)
hd.show(gn)
gf[1] = hd.merge(gf[1], gn)
r = hd.get_ku(gf[1])
print("\nКоэффициент однозначности ku = ", r[0])
ku_list[1].append(r[0])
hd.show(gf[1])
print()
fig, ax = plt.subplots()
ax.plot([i+1 for i in range(epochs)], ku_list[0], marker="*", color='g')
ax.plot([i+1 for i in range(epochs)], ku_list[1], marker="+", color='b')
ax.plot([i+1 for i in range(epochs)], [r_[0]]*epochs, color='r')
ax.set_xlabel('эпоха')
ax.set_ylabel('коэффициент однозначности')
plt.show()