Задача о минимальном покрытии

Задача о минимальном покрытии

СОДЕРЖАНИЕ

СОДЕРЖАНИЕ

ВВЕДЕНИЕ

ПОСТАНОВКА ЗАДАЧИ

. АЛГОРИТМ РЕШЕНИЯ ЗАДАЧИ

.1 Общие сведения

.2 Пошаговое описание алгоритма

.3 Блок схема алгоритма

. АРХИТЕКТУРА ПРИЛОЖЕНИЯ

.1 Структура приложения

.2 Классы для поиска пути в лабиринте

. ГРАФИЧЕСКИЙ ИНТЕРФЕЙС ПОЛЬЗОВАТЕЛЯ

. ТЕСТИРОВАНИЕ ПРОГРАММЫ

.1 Тестирование нахождения кратчайшего пути в лабиринте

.2 Тестирование поведения программы при отсутствии пути в лабиринте

. ДЕМОНСТРАЦИЯ РАБОТЫ ПРОГРАММЫ

ЗАКЛЮЧЕНИЕ

СПИСОК ИСПОЛЬЗУЕМЫХ ИСТОЧНИКОВ

ПРИЛОЖЕНИЕ А

ВВЕДЕНИЕ

Поиск A* (произносится «А звезда» или «А стар», от англ. A star) - в информатике и математике, алгоритм поиска по первому наилучшему совпадению на графе, который находит маршрут с наименьшей стоимостью от одной вершины (начальной) к другой (целевой, конечной).

Порядок обхода вершин определяется эвристической функцией «расстояние + стоимость» (обычно обозначаемой как f(x)). Эта функция - сумма двух других: функции стоимости достижения рассматриваемой вершины (x) из начальной (обычно обозначается как g(x) и может быть как эвристической, так и нет) и эвристической оценкой расстояния от рассматриваемой вершины к конечной (обозначается как h(x)).

Функция h(x) должна быть допустимой эвристической оценкой, то есть не должна переоценивать расстояния к целевой вершине. Например, для задачи маршрутизации h(x) может представлять собой расстояние до цели по прямой линии, так как это физически наименьшее возможное расстояние между двумя точками.

Этот алгоритм был впервые описан в 1968 году Питером Хартом, Нильсом Нильсоном и Бертрамом Рафаэлем. Это по сути было расширение алгоритма Дейкстры, созданного в 1959 году. Он достигал более высокой производительности (по времени) с помощью эвристики. В их работе он упоминается как «алгоритм A». Но так как он вычисляет лучший маршрут для заданной эвристики, он был назван A*.

ПОСТАНОВКА ЗАДАЧИ

Необходимо разработать программу, которая позволит:

-       создавать лабиринт;

-       редактировать лабиринт;

-       найти кратчайший путь в созданном лабиринте.

Поиск пути необходимо осуществлять с помощью алгоритма A*. Передвигаться можно только по вертикали и горизонтали.

Управление программой должно осуществляться с помощью меню.

. АЛГОРИТМ РЕШЕНИЯ ЗАДАЧИ

1.1 Общие сведения

* пошагово просматривает все пути, ведущие от начальной вершины в конечную, пока не найдёт минимальный. Как и все информированные алгоритмы поиска, он просматривает сначала те маршруты, которые «кажутся» ведущими к цели. От жадного алгоритма (который тоже является алгоритмом поиска по первому лучшему совпадению) его отличает то, что при выборе вершины он учитывает, помимо прочего, весь пройденный до неё путь (составляющая g(x) - это стоимость пути от начальной вершины, а не от предыдущей, как в жадном алгоритме). В начале работы просматриваются узлы, смежные с начальным; выбирается тот из них, который имеет минимальное значение f(x), после чего этот узел раскрывается. На каждом этапе алгоритм оперирует с множеством путей из начальной точки до всех ещё не раскрытых (листовых) вершин графа («множеством частных решений»), которое размещается в очереди с приоритетом. Приоритет пути определяется по значению f(x) = g(x) + h(x). Алгоритм продолжает свою работу до тех пор, пока значение f(x) целевой вершины не окажется меньшим, чем любое значение в очереди (либо пока всё дерево не будет просмотрено). Из множественных решений выбирается решение с наименьшей стоимостью.

1.2 Пошаговое описание алгоритма

граф совпадение алгоритм лабиринт

1. Помещаем в открытый список стартовый узел.

. Основной цикл (пока открытый список не пуст).

. Берем из открытого списка верхний узел.

. Если этот узел равен конечному, то строим путь и выходим из основного цикла.

. Обрабатываем линки выбранного узла. Для каждого соседа:

проверяем его на проходимость, для конкретного юнита, если непроходим, то, понятное дело, переходим к следующему соседу;

вычисляем оценку пути от стартового узла через текущий до соседа;

ищем соседа в открытом и закрытом списках, если найден, то сравниваем его оценку пути от стартового узла с вычисленной, если его оценка лучше то идем к следующему соседу, в противном случае удаляем узел из соответствующего списка, пересчитываем оценку пути до конечного узла и помещаем этого соседа в open список, в соответствующее место;

. Помещаем текущий узел в закрытый список.

. Переходим к п.3 (конец основного цикла).

1.3 Блок схема алгоритма

На рисунке 1 приведена блок-схема алгоритма А*.

Блок-схема алгоритма А*

. АРХИТЕКТУРА ПРИЛОЖЕНИЯ

2.1 Структура приложения

Для решения поставленной задачи была выбрана архитектура однопользовательского настольного приложения, которая позволяет обеспечить эффективное взаимодействие пользовалеля и программы.

Программа состоит из основного окна, в котором имеется функционал для создания, редактирования и редактирования лабиринтов, а так же поиска пути в них.

Для создания и отображения лабиринтов используется пользовательский элемент управления Labirinter. В этом элементе управления имеется функционал для работы с лабиринтами.

Лабиринт стстоит из элементов типа Rectangle.

2.2 Классы для поиска пути в лабиринте

Поиск пути в лабиринте осуществляется с помошью двух классов: Node и WaySearch. Класс Node является эквивалентом одной ячейки лабиринта, будь то барьер, или пустая клетка.

В классе waySerach хранятся статические методы для поиска пути:

-       public static void AStar(Labirinter labirinter1) - поиск пути

-       static IEnumerable<Node> GetNearNodes(Node node) - получение доступных полей

-       static void UpdateOpen(Node node)- обновление открытого списка для указанного узла

-       static void GetPath(Node start) -получение пути

3. ГРАФИЧЕСКИЙ ИНТЕРФЕЙС ПОЛЬЗОВАТЕЛЯ

Интерфейс программы представлен на рисунках 2 и 3

Основное окно программы

- меню программы;

- пустое поле;

- барьер;

- точка выхода;

- пройденная точка;

- доступноя точка;

- путь;

Рисунок 1. –        Окно для создания поля.

- поле для ввода длины;

- поле для вводаширины;

- кнопки для подтверждения и отмены.

4. ТЕСТИРОВАНИЕ ПРОГРАММЫ

4.1 Тестирование нахождения кратчайшего пути в лабиринте

Шаги тестового случая:

-       Создать поле;

-       Установить точку входа;

-       Установить точку выхода;

-       Установить барьеры;

-       Начать поиск пути

Результат теста:

Рисунок 2. –        Результат теста 1

Тест пройден успешно.

4.2 Тестирование поведения программы при отсутствии пути в лабиринте

Шаги тестового случая:

-       Создать поле;

-       Установить точку входа;

-       Установить точку выхода;

-       Установить барьеры, такчтбы пути не было;

-       Начать поиск пути

Результат теста:

Рисунок 3. –        Результат теста 2

Тест пройден успешно.

. ДЕМОНСТРАЦИЯ РАБОТЫ ПРОГРАММЫ

Для заруска программы необходито запустить файл Labirint.exe.

Поле запуск программы появится окно, предстваленное на рисунке 6.

Рисунок 4. –        Окно при запуске программы

Для создания поля необходимо выбрать пункт меню Поле->Создать поле в оявившемся окне ввести размеры поля и нажать кнопку «ОК». Пример созданного поля на рисунке 7.

Рисунок 5. –        Пример работы программы

Для установки точки входа в лабиринт необходимо выбрать пункт меню Лабиринт-> создание лабиринта-> установить начало и кликнуть мышью по любой понравившейся клетке. Пример установки точки входа приведен на рисунке 8.

Рисунок 6. –        Установка точки входа

Для установки точки выхода из лабиринта необходимо выбрать пункт меню Лабиринт-> создание лабиринта-> установить конец и кликнуть мышью по любой понравившейся серой клетке . Пример установки точки выхода приведен на рисунке 9.

Рисунок 7. –        Установка точки выхода

Для установки барьеров необходимо выбрать пункт меню Лабиринт-> создание лабиринта-> установить барьеры и кликнуть мышью по любым серым клеткам которые должны стать барьерами . Пример установки барьеров приведен на рисунке 10.

Рисунок 8. –        Установка барьеров

Для поиска пути необходимо выбрать пункт меню Поиск пути-> найти путь. Пример найденного пути приведен на рисунке 11.

Рисунок 9. –        Найденный путь

ЗАКЛЮЧЕНИЕ

В данной курсовой работе разработаны база данных и приложение для поиска пути в лабиринте с помощью алгоритма A*. Для создания программы использовались Microsoft VisualStudio 2010, язык программирования C#, технология Windows Presentation Foundation.

Приложение отвечает всем требованиям, указанным в постановке задачи и является программным средством, полностью готовым к применению, и имеет русскоязычный, интуитивно понятный интерфейс, что делает его достаточно удобным в использовании. Существуют проверки вводимых данных для всех полей программы.

По результатам тестирования приложения можно сказать, что оно работает корректно, отлавливает возможные ошибки пользователя, обрабатывает исключительные ситуации, не допуская при этом краха системы.

Разработанный продукт готов к эксплуатации, однако он еще может расширяться, например, путем ввода дополнительных возможностей.

СПИСОК ИСПОЛЬЗУЕМЫХ ИСТОЧНИКОВ

1.       Герберт, Ш. «Полный справочник по C#, 7-е издание.» / Ш. Герберт - Пер. с англ. СПб.: Питер; М.: Издательский дом «Вильямс», 2007. - 1068 с.

.        Мэтью Мак-Дональд «WPF: Windows Presentation Foundation в .NET 4.0 с примерами на C# 2010» / Мак-Дональд М. - СПб.: Вильямс, 2011. - 1020с.

3.       Веб сайт «Википедия» http://ru.wikipedia.org/wiki/Алгоритм_поиска_A*

4.       Басакер Р., Саати Е. Конечные графы и сети. М.: Наука, 1974. - 368 с.

.        Рейнгольд Э., Нивергельт Ю., Део Н. Комбинаторные алгоритмы. Теория и практика. М.: Мир, 1980. - 476 с.

.        Нильсон Н. Искусственный интеллект. Методы поиска решений. М: Мир, 1973. - 274 с.

.        Гурский, Н.Н. Моделирование и оптимизация колебаний многоопорных машин: монография / Н.Н. Гурский, Р.И. Фурунжиев. - Минск: БНТУ, 2008. - 296 с.

.        Прихожий А.А. Модель и алгоритм оптимизации назначения объектов на узлы распределенной информационно-вычислительной системы // Информатика. - 2010. №4.

.        Раскин Л.Г. Анализ сложных систем и элементы теории оптимального управления. М.: Сов. Радио, 1976. - 344 с.

.        Габасов Р., Кириллова Ф.М. Методы оптимизации. Мн.: БГУ, 1975. - 280.

.        Балашевич В.А. Основы математического программирования. Мн.: Вышэйшая школа, 1985. - 173 с.

ПРИЛОЖЕНИЕ А

Код основного окна программы

<Window x:Class="Labirint.MainWindow"="http://schemas.microsoft.com/winfx/2006/xaml/presentation":x="http://schemas.microsoft.com/winfx/2006/xaml"="Поиск пути в лабиринте" Height="645" Width="600" xmlns:my="clr-namespace:Labirint.UserControls">

<Grid>

<Grid.RowDefinitions>

<RowDefinition />

</Grid.RowDefinitions>

<Grid.ColumnDefinitions>

<ColumnDefinition Width="*" />

</Grid.ColumnDefinitions>

<Grid Background="{x:Null}">

<Grid Name="grid3">

<Grid.RowDefinitions>

<RowDefinition Height="30" />

<RowDefinition />

</Grid.RowDefinitions>

<Viewbox Margin="0" Grid.Row="1">

<my:Labirinter x:Name="labirinter1" Width="300" Height="300" Margin="0" Grid.Row="1"></my:Labirinter>

</Viewbox>

<Menu Name="menu1" Background="White" FontSize="14">

<MenuItem Header="Поле">

<MenuItem Header="Создать поле" Click="button1_Click_1" />

<MenuItem Header="Очистить поле" Click="button3_Click" />

</MenuItem>

<MenuItem Header="Лабиринт">

<MenuItem Name="CreateLabirintMenuItem" Header="Создание лабиринта">

<MenuItem Name="SetStartMenuItem" Header="Установить начало" IsCheckable="True" Click="MenuItem_Click" />

<MenuItem Name="SetEndMenuItem" Header="Установить конец" IsCheckable="True" Click="MenuItem_Click" />

<MenuItem Name="SetBarrierMenuItem" Header="Установить барьеры" IsCheckable="True" Click="MenuItem_Click" />

<MenuItem Name="SetNothingMenuItem" Header="Никаких действий" IsCheckable="True" IsChecked="True" Click="MenuItem_Click" />

</MenuItem>

<MenuItem Header="Очистить лабиринт" Click="button4_Click" />

</MenuItem>

<MenuItem Header="Поиск пути">

<MenuItem Header="Найти путь" Click="button2_Click" />

</MenuItem>

</Menu>

</Grid>

</Grid>

</Grid>

</Window>System;System.Collections.Generic;System.Linq;System.Text;System.Windows;System.Windows.Controls;System.Windows.Data;System.Windows.Documents;System.Windows.Input;System.Windows.Media;System.Windows.Media.Imaging;System.Windows.Navigation;System.Windows.Shapes;System.Threading;System.Windows.Threading;Labirint.DialogWindows;Labirint

{

/// <summary>

/// Логика взаимодействия для MainWindow.xaml

/// </summary>partial class MainWindow : Window

{MainWindow()

{();

}void button1_Click_1(object sender, RoutedEventArgs e)

{

{d = new LabirintSizeDialog();(d.ShowDialog() == true).CreateField(d.LWidth, d.LHeight);

}

{.Show("Введите верные размеры. Размер должен быть целым числом больше 0", "Ошибка", MessageBoxButton.OK, MessageBoxImage.Error);

}

}void button2_Click(object sender, RoutedEventArgs e)

{

{.ClearLabirint();.Reset();.AStar(labirinter1);

}(Exception ex)

{.Show(ex.Message, "Ошибка", MessageBoxButton.OK, MessageBoxImage.Error);

}

}void button3_Click(object sender, RoutedEventArgs e)

{.ClearField();

}void button4_Click(object sender, RoutedEventArgs e)

{.ClearLabirint();

}void MenuItem_Click(object sender, RoutedEventArgs e)

{(MenuItem i in CreateLabirintMenuItem.Items).IsChecked = false;

((MenuItem)sender).IsChecked = true;.SetStart = (bool)SetStartMenuItem.IsChecked;.SetEnd = (bool)SetEndMenuItem.IsChecked;.SetLabirint = (bool)SetBarrierMenuItem.IsChecked;

}

}

}

Код компонента для работы с лабиринтом

<UserControl x:Class="Labirint.UserControls.Labirinter"="http://schemas.microsoft.com/winfx/2006/xaml/presentation":x="http://schemas.microsoft.com/winfx/2006/xaml":mc="http://schemas.openxmlformats.org/markup-compatibility/2006":d="http://schemas.microsoft.com/expression/blend/2008":Ignorable="d":DesignHeight="300" d:DesignWidth="300">

</UserControl>System;System.Collections.Generic;System.Linq;System.Text;System.Windows;System.Windows.Controls;System.Windows.Data;System.Windows.Documents;System.Windows.Input;System.Windows.Media;System.Windows.Media.Imaging;System.Windows.Navigation;System.Windows.Shapes;Labirint.UserControls

{

/// <summary>

/// Логика взаимодействия для Labirinter.xaml

/// </summary>partial class Labirinter : UserControl

{rectSize = 20;<string, Brush> brushes = new Dictionary<string, Brush>();Dictionary<string, Brush> Brushes

{{ return brushes; }set { brushes = value; }

}Node Start

{;set;

}Node End

{;set;

}bool SetLabirint

{;;

}bool SetStart

{;;

}bool SetEnd

{;;

}int LRowCount

{;set;

}int LColumnCount

{;set;

}List<Node> Lbr

{;set;

}IEnumerable<Node> Barriers

{

{Lbr.Where(n => n.Value.Fill == Brushes["Barrier"]);

}

}Labirinter()

{();.Add("Start", new SolidColorBrush(Colors.Yellow));.Add("End", new SolidColorBrush(Colors.Green));.Add("Free", new SolidColorBrush(Colors.WhiteSmoke));.Add("Barrier", new SolidColorBrush(Colors.Red));.Add("Close", new SolidColorBrush(Colors.Gray));.Add("Open", new SolidColorBrush(Colors.LightGray));.Add("Path", new SolidColorBrush(Colors.GreenYellow));

}void ChangeStates(Node n,string state)

{(!(n == Start || n == End)).Value.Fill = Brushes[state];

}void CreateField(int rowCount, int columnCount)

{.Reset();.Children.Clear();= new List<Node>(rowCount * columnCount);.Clear();= rowCount;.Height = LRowCount * (rectSize + 1);.RowDefinitions.Clear();(int i = 0; i < LRowCount; i++).RowDefinitions.Add(new RowDefinition());= columnCount;.Width = LColumnCount * (rectSize + 1);.ColumnDefinitions.Clear();(int i = 0; i < LColumnCount; i++).ColumnDefinitions.Add(new ColumnDefinition());(int i=0;i<LRowCount;i++)(int j = 0; j < LColumnCount; j++)

{n = new Node(Rectangle()

{= rectSize,= rectSize,= Brushes["Free"],= HorizontalAlignment.Center,= VerticalAlignment.Center,=1,=new Thickness(0)

},i,j);.SetRow(n.Value, i);.SetColumn(n.Value, j);.Children.Add(n.Value);.Value.MouseEnter += new MouseEventHandler(Lbr_MouseEnter);.Value.MouseDown += new MouseButtonEventHandler(Lbr_MouseDown);.Add(n);

}

}void ClearField()

{.Reset();.ForEach(n => n.Value.Fill=Brushes["Free"]);

}void ClearLabirint()

{.Reset();.Where(node => node.Value.Fill != Brushes["Barrier"]).ToList().ForEach(n => ChangeStates(n, "Free"));

}Lbr_MouseEnter(object sender, MouseEventArgs e)

{(SetLabirint == true)

{(Mouse.LeftButton == MouseButtonState.Pressed && ((Rectangle)sender).Fill == Brushes["Free"])

{

((Rectangle)sender).Fill = Brushes["Barrier"];

}(Mouse.RightButton == MouseButtonState.Pressed && ((Rectangle)sender).Fill == Brushes["Barrier"])

{

((Rectangle)sender).Fill = Brushes["Free"];

}

}(SetStart)

{(e.LeftButton == MouseButtonState.Pressed && ((Rectangle)sender).Fill == Brushes["Free"])

{(Start != null).Value.Fill = Brushes["Free"];

((Rectangle)sender).Fill = Brushes["Start"];= (Lbr.First(n=>n.Value==(Rectangle)sender));

}(e.RightButton == MouseButtonState.Pressed && ((Rectangle)sender).Fill == Brushes["Start"])

{

((Rectangle)sender).Fill = Brushes["Free"];= null;

}

}(SetEnd)

{(e.LeftButton == MouseButtonState.Pressed && ((Rectangle)sender).Fill == Brushes["Free"])

{(End != null).Value.Fill = Brushes["Free"];

((Rectangle)sender).Fill = Brushes["End"];= (Lbr.First(n => n.Value == (Rectangle)sender));

}(e.RightButton == MouseButtonState.Pressed && ((Rectangle)sender).Fill == Brushes["End"])

{

((Rectangle)sender).Fill = Brushes["Free"];= null;

}

}

}Lbr_MouseDown(object sender, MouseButtonEventArgs e)

{(SetLabirint == true)

{(e.LeftButton == MouseButtonState.Pressed && ((Rectangle)sender).Fill == Brushes["Free"])

((Rectangle)sender).Fill = Brushes["Barrier"];

}(e.RightButton == MouseButtonState.Pressed && ((Rectangle)sender).Fill == Brushes["Barrier"])

{

((Rectangle)sender).Fill = Brushes["Free"];

}

}(SetStart)

{(e.LeftButton == MouseButtonState.Pressed && ((Rectangle)sender).Fill == Brushes["Free"])

{(Start != null).Value.Fill = Brushes["Free"];

((Rectangle)sender).Fill = Brushes["Start"];= (Lbr.First(n => n.Value == (Rectangle)sender));

}(e.RightButton == MouseButtonState.Pressed && ((Rectangle)sender).Fill == Brushes["Start"])

{

((Rectangle)sender).Fill = Brushes["Free"];= null;

}

}(SetEnd)

{(e.LeftButton == MouseButtonState.Pressed && ((Rectangle)sender).Fill == Brushes["Free"])

{(End != null).Value.Fill = Brushes["Free"];

((Rectangle)sender).Fill = Brushes["End"];= (Lbr.First(n => n.Value == (Rectangle)sender));

}(e.RightButton == MouseButtonState.Pressed && ((Rectangle)sender).Fill == Brushes["End"])

{

((Rectangle)sender).Fill = Brushes["Free"];= null;

}

}

}

}

}

Класс узла лабиринтаSystem;System.Collections.Generic;System.Linq;System.Text;System.Windows.Shapes;Labirint

{class Node

{Rectangle Value

{;set;

}Node Parent

{;;

}int Row

{;set;

}int Column

{;set;

}double Transit

{;;

}double Distance

{;;

}double Weight

{

{Transit + Distance;

}

}Node(Rectangle value, int i, int j)

{= value;= i;= j;

Transit = 0;= 0;= null;

}

}

}

Класс для поиска пути в лабиринте

using System;System.Collections.Generic;System.Linq;System.Text;Labirint.UserControls;System.Windows.Shapes;System.Threading;System.Windows.Media;System.Windows.Media.Imaging;Labirint

{class WaySearch

{

//точка входа

static Node Start;

//точка выхода

static Node End;Labirinter labirinter; //лабиринтIEnumerable<Node> barriers; //коллекция перградList<Node> open = new List<Node>(); //открытые узлыList<Node> close = new List<Node>();//закрытые узлы

/// <summary>

/// поиск пути методом А*

/// </summary>

/// <param name="labirinter1"></param>static void AStar(Labirinter labirinter1)

{.labirinter = labirinter1;(labirinter.Start == null)new ArgumentException("Лабиринт должен сожержать точку входа");= labirinter.Start;(labirinter.End == null)new ArgumentException("Лабиринт должен сожержать точку выхода");= labirinter.End;= labirinter.Barriers;(Start);

DrawPath(End);

}

//получение доступных полей

static IEnumerable<Node> GetNearNodes(Node node)

{

//return labirinter.Lbr.Where(n=>

// ((n.Row == node.Row + 1 || n.Row == node.Row - 1 || n.Row == node.Row) &&

// (n.Column == node.Column + 1 || n.Column == node.Column - 1 || n.Column == node.Column) &&

((n.Row==node.Row+1 && n.Column==node.Column) || (n.Row==node.Row-1 && n.Column==node.Column) ||

(n.Row==node.Row && n.Column==node.Column +1) || (n.Row==node.Row && n.Column==node.Column - 1)) &&

!(n == null || close.Contains(n) || barriers.Contains(n) || n == node));

}

//добавление полей в открытый списокvoid UpdateOpen(Node node)

{(Node n in GetNearNodes(node))

{(!open.Contains(n) && node!=null)

{.Parent = node;.Transit = n.Parent.Transit+Math.Sqrt((n.Row - node.Row) * (n.Row - node.Row) + (n.Column - node.Column) * (n.Column - node.Column));.Distance = Math.Sqrt((n.Row - End.Row) * (n.Row - End.Row) + (n.Column - End.Column) * (n.Column - End.Column));.Add(n);.ChangeStates(n,"Open");

}

{oldTransit=n.Parent.Transit+Math.Sqrt((n.Row - n.Parent.Row) * (n.Row - n.Parent.Row) + (n.Column - n.Parent.Column) * (n.Column - n.Parent.Column));newTransit = node.Transit + Math.Sqrt((n.Row - node.Row) * (n.Row - node.Row) + (n.Column - node.Column) * (n.Column - node.Column));(newTransit < oldTransit && node != null)

{.Transit = newTransit;.Parent = node;

}

}

}

}

//получение путиvoid GetPath(Node start)

{(open.Contains(End));.Remove(start);.Add(start);.ChangeStates(start,"Close");(start);

{(open.OrderBy(n => n.Weight).First());

}

{ new Exception("Невозможно найти путь");

}

}

//отрисовка путиvoid DrawPath(Node end)

{(end.Parent == null);.ChangeStates(end, "Path");(end.Parent);

}

//сбросstatic void Reset()

{= null;= null;=null;=null;.Clear();.Clear();

}