Практическая работа по "Информационным технологиям в цифровой экономике"

МИНИСТЕРСТВО НАУКИ И ВЫСШЕГО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ
Федеральное государственное бюджетное образовательное учреждение высшего образования

«Сибирский государственный университет науки и технологий
имени академика М.Ф. Решетнева»

Практическая работа

По дисциплине: «Информационные технологии в цифровой экономике»

Выполнил:

студент группы

БИСЗ19-01, Гусева Ильи Аркадьевича

Проверил:

Лопатин Павел Константинович

Красноярск 2020

1. Задача:

Разработать программу на языке python 3.4.3 планирования пути робота среди точек сетки 360 на 360 из точки g0 в точку gt на основе алгоритма поиска в глубину. При запуске программы пользователь указывает координаты начальной точки робота (g0), целевой точки (gt) и запрещенных точек (точки по которым робот не может идти). Если пути нет, программа должна это обнаружить, если же путь существует, программа должна его показать.

2. Текст программы:

import numpy as np

from bisect import bisect_left

import matplotlib.pyplot as plt

def xy2number(xy, n):

    return xy[0]*n + xy[1]

def number2npxy(m, n):

    return np.array([m // n, m % n])

def binary_search(lst, elem):

    pos = bisect_left(lst, elem)

    return pos != len(lst) and lst[pos]==elem

def get_path(startxy, finishxy, blocks, n, savename='tmp'):

    start, finish = xy2number(startxy, n), xy2number(finishxy, n)

    grid, graph = get_grid_graph(blocks, n)

    visited = np.zeros(n * n)

    path = [start]

    time = [0]

    stack = [start]

    tstack= [0]

    ti = 0

    while len(stack) > 0:

        v = stack.pop()

        t = tstack.pop()

        while time and time[-1] >= t:

            time.pop()

            path.pop()

        path.append(v)

        time.append(t)

        ti += 1

        if not visited[v]:

            nodes = [e for e in graph[v] if not visited[e]]

            nodes = sorted(nodes, key=lambda e: np.inner(number2npxy(e, n),

                                                         number2npxy(finish, n)-number2npxy(v, n)))

            stack.extend(nodes)

            tstack.extend([ti] * len(nodes))

            visited[v] = 1

        if v == finish:

            break

    if len(stack)==0:

        print('No path')

        print('Image creating')

        draw(grid, startxy, finishxy, [], savename=savename)

        return None

    else:

        print('Path finded')

        print('Image creating')

        path = list(map(lambda x: number2npxy(x, n), path))

        draw(grid, startxy, finishxy, path, savename=savename)

        return path