Технический контроль и диагностика систем ЛА

        display_tree(i, tab + 1)  # чем глубже рекурсия - тем шире табуляция

 

def draw_tree(count, tree, with_Toc=False):

    tr = nx.Graph()

    add_edge_to_tree(count, tree, tr, with_Toc)

    pos = nx.spring_layout(tr)

    colors = range(20)

    nx.draw(tr, pos, node_size=200, node_color='#A0CBE2', width=2,

            edge_cmap=plt.cm.Blues, with_labels=True)

    if with_Toc:

        file_name = 'solve_tree.png'

    else:

       file_name = 'variant_tree.png'

    plt.savefig(file_name)  # save as png

    sys.stdout.write('Рисунок ' + file_name + ' сохранен\n')

    # plt.show() # display

 

def list_to_str(list):

    """Функция принимает список и возвращает строку, созданную из списка"""

    string = ''

    for i in list:

        string += str(i)

    return string

 

def add_edge_to_tree(count, node, tr, with_Toc):

    if node.childs_numbers:

        for child in node.childs:

 

            if len(child.parents_numbers) != count:  # не будем рисовать последний узел

                if with_Toc:

                    node_name = 'Z' + str(node.number) + ' ' + list_to_str(

                        node.parents_numbers) + ' (' + str(node.Toc) + ')'

                    child_name = 'Z' + str(child.number) + ' ' + list_to_str(

                        child.parents_numbers) + ' (' + str(child.Toc) + ')'

                else:

                    node_name = list_to_str(node.parents_numbers)

                    child_name = list_to_str(child.parents_numbers)

 

                tr.add_edge(node_name, child_name)

                add_edge_to_tree(count, child, tr, with_Toc)

 

def read_data_from_file(file_name):

    """Функция чтения вводных данных из файла"""

    data = open(file_name)

    count = int(data.readline()[0])

        # первая строка файла должна содержать кол-во элементов

    tau = [int(x) for x in data.readline().split()[:count]]

    data.readline()  # пропускаем пустую строку

 

    t = []

    for i in xrange(count):

        t.append([int(x) for x in data.readline().split()[:count]])

    data.readline()  # пропускаем пустую строку

 

    link = []

    for i in xrange(count):

        link.append([int(x) for x in data.readline().split()[:count]])

 

    graph = []

    for i in xrange(count):

        graph.append(Node(i, tau[i]))

 

    for i in xrange(count):

        for j in xrange(count):

            if link[i][j]:

                graph[i].set_child(graph[j])

    data.close()

    return count, graph, t, tau

 

def calculate_b(count, tau, t):

    b = [-1] * count  # матрица для b. TODO найти более элегантное решение для заполнения матрицы

    for i in range(count):

        b[i] = [-1] * count

    for i in xrange(count):

        for j in xrange(count):

            if t[i][j] >= 0:

                if i < j:

                    b[i][j] = tau[i] + t[i][j]

    return b

 

def display_b(b):

    sys.stdout.write("Построим z-размерную матрицу bij:\n")

 

    for i in range(len(b)):

        for j in b[i]:

            if j == -1:

                temp = "-∞"

            else:

                temp = str(j)

            sys.stdout.write(temp + '\t')

        sys.stdout.write("\n")

    sys.stdout.write("\n")

 

def calculate_Tn(count, graph, tau, t, b):

    sys.stdout.write("Определим более раннее время начала модуля zk.\n")

    Tn = []

    for i in xrange(count):

        temp = []

        if i == 0:

            sys.stdout.write("Tn(z%d) = 0\n" % i)

            Tn.append(0)

            continue

        for parent in graph[i].parents:

            temp.append(Tn[parent.number] + b[parent.number][i])

            sys.stdout.write("Tn(z%d) = %d + %d = %d\n" % (i, Tn[parent.number], b[parent.number][i], Tn[parent.number] + b[parent.number][i]))

 

        if len(temp) > 1:

            sys.stdout.write("max(Tn(z%d)) = %d\n" % (i, max(temp)))

        Tn.append(max(temp))

    sys.stdout.write("\n")

    return Tn

 

def calculate_TL(count, graph, tau, t):

    sys.stdout.write(

        "Определим длины путей, которые ведут от вершины zk к миноранте.\n")

    TL = []

    for x in xrange(count):

        temp = []

        generate_path(

            graph[x], [], temp)  # находим все пути от узла i до последнего узла

 

        all_TL = []

        for i in temp:  # находим max

            sys.stdout.write("T(L*(z%d))" % x)

            sum_path = 0

            for j in xrange(len(i)):

                if i[j] != count - 1:

                    if j != 0:

                        sys.stdout.write(" + ")

                    else:

                        sys.stdout.write(" = ")

                    sum_path += tau[i[j]]  # сумма всех узлов

                    sum_path += t[i[j]][i[j + 1]]

                        #прибавляем веса связей между узлами

                    sys.stdout.write(

                        "%d + %d" % (tau[i[j]], t[i[j]][i[j + 1]]))

                else:

                    sys.stdout.write(" = %d\n" % sum_path)

 

            all_TL.append(sum_path)

        TL.append(max(all_TL))  # находим максимальное

        if len(all_TL) > 1:

            sys.stdout.write("max(T(L*(z%d))) = %d\n" % (x, max(all_TL)))

 

    sys.stdout.write("\n")

 

    return TL

 

def generate_path(node, path, temp):

    path.append(node.number)

    if len(node.childs):

        for child in node.childs:

            generate_path(child, copy.copy(path), temp)

    else:

        temp.append(path)

 

def display_data_table(count, tau, Tn, TL, t):

    sys.stdout.write('Полученные данные сведем в таблицу.\n')

    sys.stdout.write('z\tτ\tTn\tTL\tU\tt\n')

    U = []

    t_temp = []

    for i in range(len(t)):

        for j in range(len(t[i])):

            if t[i][j] != -1:

                U.append((i, j))

                t_temp.append(t[i][j])

 

    for i in range(len(U)):

        if i > len(tau) - 1:

            sys.stdout.write("\t\t\t\t%s\t%d\n" % (str(U[i]), t_temp[i]))

        else:

            sys.stdout.write("z%d\t%d\t%d\t%d\t%s\t%d\n" % (i, tau[

                             i], Tn[i], TL[i], str(U[i]), t_temp[i]))

 

    sys.stdout.write('\n')

 

def make_solve_tree(count, tree, Tn, TL, tau, t):

 

    global solve_table

    solve_table += 'S\tz\tN\tY\tt*\tTоц\n'

 

    solve_tree = copy.copy(tree)

    add_Toc_to_node(count, solve_tree, Tn, TL, tau, t)

    recursive_make_solve_tree(

        count, tree, Tn, TL, tau, t, solve_tree)

 

    return solve_tree

 

def recursive_make_solve_tree(count, tree, Tn, TL, tau, t, solve_tree):

    solve_tree.childs = copy.copy(tree.childs)

    solve_tree.childs_numbers = copy.copy(tree.childs_numbers)

 

    if len(solve_tree.childs) == 0:

        return

    for child in solve_tree.childs:

        add_Toc_to_node(count, child, Tn, TL, tau, t)

    temp = {}

 

    for child in solve_tree.childs:

        temp[child.Toc] = child.number

 

    for child in solve_tree.childs:

        if child.number == temp[min(temp.keys())]:  # если у потомка наименьший Toc

            for child_of_tree in tree.childs:

                if child_of_tree.number == temp[min(temp.keys())]:  # находим такой же потомок у главного дерева

                    recursive_make_solve_tree(count, child_of_tree,

                                              Tn, TL, tau, t, child)

        else:

            child.del_childs()

 

def add_Toc_to_node(count, node, Tn, TL, tau, t):

    if len(node.parents_numbers) == count:

        return

    t_star = 0

    for i in xrange(len(node.parents_numbers)):

        t_star += tau[node.parents_numbers[i]]  # сумма всех узлов

 

        if i < len(node.parents_numbers) - 1:

            if t[node.parents_numbers[i]][node.parents_numbers[i + 1]] >= 0:

                t_star += t[node.parents_numbers[i]][node.parents_numbers[

                    i + 1]]  # прибавляем веса связей между узлами

 

    temp = {}

 

    for child in node.childs:

        q = TL[child.number]

        if t_star < Tn[child.number]:

           q += Tn[child.number] - t_star

        temp[q] = child.number

    node.Toc = max(temp.keys()) + t_star

 

    global solve_table

    global S

    solve_table += "S" + str(S) + '\t' + "z" + str(node.number) + '\t' + list_to_str(node.childs_numbers) + '\t' + list_to_str(node.parents_numbers) + '\t' + str(t_star) + '\t' + str(node.Toc) + "\n"

    S += 1

 

def main():

    count, graph, t, tau = read_data_from_file("data")

    # draw_graph(graph)

    # первый этап

    tree = make_tree(graph)

    # display_tree(tree)

    # draw_tree(count, tree)

    #второй этап

    b = calculate_b(count, tau, t)

    display_b(b)

    #третий этап

    Tn = calculate_Tn(count, graph, tau, t, b)

    #четвертый этап

    TL = calculate_TL(count, graph, tau, t)

    display_data_table(count, tau, Tn, TL, t)

    #пятый этап

    solve_tree = make_solve_tree(count, tree, Tn, TL, tau, t)

    global solve_table

    sys.stdout.write("Оценки нижних границ:\n")

    sys.stdout.write(solve_table)

    # display_tree(solve_tree)

    draw_tree(count, solve_tree, True)

 

if __name__ == '__main__':

    main()

 

 

 

 

 

 

 

 

 

 

 

 

Приложение 2

Листинг программы на языке Python 2.7

# -*- coding: utf-8 -*-

 

import sys

import copy

 

sigma_default = [0.1, 0.2, 0.3, 0.4, 0.5]

p_default = [

    [0.99893,        0.99930,        0.99945,        0.99955,        0.99960,        0.99963,        0.99967,        0.99970,        0.99971,

        0.99973,        0.99974,        0.99975],

    [0.99784,        0.99859,        0.99886,        0.99901,        0.99915,        0.99923,        0.99931,        0.99933,        0.99937,

        0.99942,        0.99945,        0.99948],

    [0.99634,        0.99775,        0.99821,        0.99846,        0.99868,        0.99879,        0.99890,        0.99895,        0.99901,

        0.99909,        0.99914,        0.99918],

    [0.99419,        0.99669,        0.99748,        0.99785,        0.99816,        0.99833,        0.99849,        0.99859,

        0.99867,        0.99876,        0.99882,        0.99887],

    [0.99110,        0.99533,        0.99657,        0.99714,        0.99756,        0.99780,        0.99801,        0.99818,

        0.99828,        0.99839,        0.99848,        0.99854]]

def get_p(sigma):

    p = [[] for i in sigma]

    for i in range(len(sigma)):

        p[i] = p_default[sigma_default.index(sigma[i])]

    return p

 

def get_psi(i, j, p, t):

    a = p[j][i]

    if i == 0:

        b = 0

    else:

        b = p[j][i - 1]

    try:

        return (a - b) / (b * t[j])

    except ZeroDivisionError:

        return -1

 

def get_table_psi(p, t):

    table_psi = []

    for i in range(len(p[0])):

        table_psi.append([0 for x in t])

        for j in range(len(t)):

            table_psi[i][j] = get_psi(i, j, p, t)

    return table_psi

 

def get_max_value(list):

    max_value = 0

    i_max = 0

    j_max = 0

 

    for i in range(len(list)):

        for j in range(len(list[i])):

            if list[i][j] > max_value:

                max_value = list[i][j]

                i_max = i

                j_max = j

    return i_max, j_max

 

def list_to_str(list):

    s = ''

    for i in list:

        s += str(i) + "\t"

    return s

 

def get_max_table(p, t, psi):

    count = 1

    multi = 1

    for i in p:

        multi *= i[0]

    P = [multi]

    T = [sum(t)]

    temp_table = []

    max_table = [[1 for i in psi[0]]]

    temp = []

    sys.stdout.write("N\tn\tΨ\tmax\n")

    for i in range(len(psi)):

        temp_table.append(copy.copy(psi[i]))

        a = get_max_value(temp_table)[0]

        b = get_max_value(temp_table)[1]

        if temp_table[a][b] == -1:

            continue

        sys.stdout.write(

            "%d\t%d\t%d\t%2.8f\n" % (count, a + 1, b + 1, temp_table[a][b]))

        temp.append(temp_table[a][b])

        count += 1

        temp_table[a][b] = 0

        max_table[-1][b] += 1

        max_table.append(copy.copy(max_table[-1]))

        P.append(P[-1] * p[b][a] / p[b][a - 1])

        T.append(T[-1] + t[b])

    while P[-1] < 0.992 and T[-1] < 600:

        a = get_max_value(temp_table)[0]

        b = get_max_value(temp_table)[1]

        if temp_table[a][b] == -1:

            continue

        sys.stdout.write(

            "%d\t%d\t%d\t%2.8f\n" % (count, a + 1, b + 1, temp_table[a][b]))

        temp.append(temp_table[a][b])

        count += 1

        temp_table[a][b] = 0

        max_table[-1][b] += 1

        max_table.append(copy.copy(max_table[-1]))

        P.append(P[-1] * p[b][a] / p[b][a - 1])

        T.append(T[-1] + t[b])

    sys.stdout.write("\n")

    sys.stdout.write("N\tn1\tn2\tn3\tn4\tn5\tP(N)\t\tT(N)\n")

    for i in range(len(max_table) - 1):

        sys.stdout.write("%d\t%s%4.5f\t\t%d мин %dсек\n" % (

            i + 1, list_to_str(max_table[i]), P[i + 1], T[i + 1] / 60, T[i + 1] % 60))

    sys.stdout.write("\n")

    sys.stdout.write('n\tΨ1(ni)\t\tΨ2(ni)\t\tΨ3(ni)\t\tΨ4(ni)\t\tΨ5(ni)\n')

    for i in range(len(p[0])):

        sys.stdout.write("%d\t" % (i + 1))

        for j in range(len(t)):

            if psi[i][j] == -1 or psi[i][j] not in temp:

                sys.stdout.write('---------\t')

            else:

                sys.stdout.write('%4.7f\t' % psi[i][j])

        sys.stdout.write("\n")

 

def main():

    sigma = [0.3, 0.2, 0.4, 0.1, 0.5]

    t = [30, 5, 15, 20, 50]

    p = get_p(sigma)

    psi = get_table_psi(p, t)

    get_max_table(p, t, psi)

 

if __name__ == '__main__':

    main()