Курсовая работа по «Техническому контролю и диагностике систем ЛА»

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Приложение 1

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

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

import sys

import copy

import matplotlib.pyplot as plt

import networkx as nx

 

solve_table = ''

S = 0

 

class Node:

    """Узел графа"""

    def __init__(self, number, tau=0):

        self.number = number  # номер узла

        self.tau = tau  # вес узла

        self.Toc = 0

        self.childs = []  # узлы-потомки

        self.childs_numbers = []  # номер узлов-потомков

        self.parents = []  # узлы-родители

        self.parents_numbers = []  # номера узлов-родителей

 

    def set_child(self, child):  # mass - это t между узлами

        """Добавить к узлу потомков"""

        #TODO добавить проверку типа

 

        self.childs.append(child)  # добавляем потомка

        self.childs_numbers.append(child.number)  # добавляем номер потомка

        child.set_parent(self)  # добавляем потомку родителя

 

    def del_childs(self):

        self.childs = []

        self.childs_numbers = []

 

    def set_parent(self, parent):

        """Добавить к узлу родителя"""

        #TODO добавить проверку типа

        self.parents.append(parent)  # Добавляем родителя

        self.parents_numbers.append(parent.number)  # Добавляем номер родителя

 

def display_graph(graph):

    """Выводит граф на экран"""

    for node in graph:

        sys.stdout.write(

            "Number: " + str(node.number) + "\tTau: " + str(node.tau))

 

        sys.stdout.write("\tParents:")

        if len(node.parents):

            for parent in node.parents:

                sys.stdout.write("\t\t", parent.number)

        else:

            sys.stdout.write("\t\tNone")

 

        sys.stdout.write("\tChilds:")

        if len(node.childs):

            for child in node.childs:

                sys.stdout.write("\t\t", child.number)

        else:

            sys.stdout.write("\t\tNone")

 

def draw_graph(graph):

    gr = nx.Graph()

    for i in graph:

        for j in i.childs:

            gr.add_edge(str(i.number), str(j.number))

    pos = nx.spring_layout(gr)

    colors = range(20)

    nx.draw(gr, pos, node_size=700, node_color='#A0CBE2', width=4,

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

    file_name = "graph.png"

    plt.savefig(file_name)  # save as png

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

    # plt.show() # display

 

def make_tree(graph):

    """Функция для построения дерева"""

    tree = Node(0)

    tree.set_parent(Node(0))

    make_next_node(tree, graph)

    return tree

 

def make_next_node(tree, graph):

    """Рекурсивная  функция для вычисления потомков узла"""

    possible_next_nodes = copy.copy(

        graph)  # с самого начала все узлы могут быть следующими

 

    for i in tree.parents_numbers:

        possible_next_nodes[i] = None  # отсекаем уже использованные узлы

 

    for possible_node in range(len(possible_next_nodes)):  # цикл по всем возможным следующим узлам

        if possible_next_nodes[possible_node] is not None:

            for parents_number in possible_next_nodes[possible_node].parents_numbers:  # цикл по всем родителям узла

                if not parents_number in tree.parents_numbers:  # если родитель узла еще не был в дереве, то мы этот узел пока использовать не можем

                    possible_next_nodes[possible_node] = None

                    break  # если хотя бы одного родителя нет, то дальше и проверять не стоит

 

    for possible_node in range(len(possible_next_nodes)):  # цикл по всем возможным следующим узлам

        if possible_next_nodes[possible_node] is not None:

            tree.set_child(Node(possible_node))

    for child in tree.childs:  # добавим каждому потомку родителей родителя

        child.parents = copy.copy(tree.parents)

        child.parents_numbers = copy.copy(tree.parents_numbers)

 

        child.set_parent(

            Node(child.number))  # не забываем добавить самого себя

    for child in tree.childs:

        make_next_node(child, graph)  # рекурсивно пробегаем по всем потомкам

 

def display_tree(tree, tab=0):

    """Функция вывода дерева"""

    sys.stdout.write(tab * '\t' + str(tree.number) + '\n')

    for i in tree.childs:

        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]))