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

Размещено на http://www.allbest.ru/

СОДЕРЖАНИЕ

СОДЕРЖАНИЕ

ВВЕДЕНИЕ

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

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

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

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

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

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

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

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

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

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

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

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

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

ЗАКЛЮЧЕНИЕ

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

ПРИЛОЖЕНИЕ А



ВВЕДЕНИЕ

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

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

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

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

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

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

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

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

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

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

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



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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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



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



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

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 - меню программы;

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

3 - барьер;

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

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

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

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

8 - путь;

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

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

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

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



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

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

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

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

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

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

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

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

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

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

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



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

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

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

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

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

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

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

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

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

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



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

Для заруска программы необходито запустить файл 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 с.

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

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

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

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

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

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

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

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

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

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



ПРИЛОЖЕНИЕ А

Листинг программы

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

<Window x:Class="Labirint.MainWindow"

xmlns="http://schemas.microsoft.com/winfx/2006/xaml/presentation"

xmlns:x="http://schemas.microsoft.com/winfx/2006/xaml"

Title="Поиск пути в лабиринте" 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>

using System;

using System.Collections.Generic;

using System.Linq;

using System.Text;

using System.Windows;

using System.Windows.Controls;

using System.Windows.Data;

using System.Windows.Documents;

using System.Windows.Input;

using System.Windows.Media;

using System.Windows.Media.Imaging;

using System.Windows.Navigation;

using System.Windows.Shapes;

using System.Threading;

using System.Windows.Threading;

using Labirint.DialogWindows;

namespace Labirint

{

/// <summary>

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

/// </summary>

public partial class MainWindow : Window

{

public MainWindow()

{

InitializeComponent();

}

private void button1_Click_1(object sender, RoutedEventArgs e)

{

try

{

LabirintSizeDialog d = new LabirintSizeDialog();

if (d.ShowDialog() == true)

labirinter1.CreateField(d.LWidth, d.LHeight);

}

catch

{

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

}

}

private void button2_Click(object sender, RoutedEventArgs e)

{

try

{

labirinter1.ClearLabirint();

WaySearch.Reset();

WaySearch.AStar(labirinter1);

}

catch(Exception ex)

{

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

}

}

private void button3_Click(object sender, RoutedEventArgs e)

{

labirinter1.ClearField();

}

private void button4_Click(object sender, RoutedEventArgs e)

{

labirinter1.ClearLabirint();

}

private void MenuItem_Click(object sender, RoutedEventArgs e)

{

foreach (MenuItem i in CreateLabirintMenuItem.Items)

i.IsChecked = false;

((MenuItem)sender).IsChecked = true;

labirinter1.SetStart = (bool)SetStartMenuItem.IsChecked;

labirinter1.SetEnd = (bool)SetEndMenuItem.IsChecked;

labirinter1.SetLabirint = (bool)SetBarrierMenuItem.IsChecked;

}

}

}

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

<UserControl x:Class="Labirint.UserControls.Labirinter"

xmlns="http://schemas.microsoft.com/winfx/2006/xaml/presentation"

xmlns:x="http://schemas.microsoft.com/winfx/2006/xaml"

xmlns:mc="http://schemas.openxmlformats.org/markup-compatibility/2006"

xmlns:d="http://schemas.microsoft.com/expression/blend/2008"

mc:Ignorable="d"

d:DesignHeight="300" d:DesignWidth="300">

<Grid Name="MainGrid"></Grid>

</UserControl>

using System;

using System.Collections.Generic;

using System.Linq;

using System.Text;

using System.Windows;

using System.Windows.Controls;

using System.Windows.Data;

using System.Windows.Documents;

using System.Windows.Input;

using System.Windows.Media;

using System.Windows.Media.Imaging;

using System.Windows.Navigation;

using System.Windows.Shapes;

namespace Labirint.UserControls

{

/// <summary>

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

/// </summary>

public partial class Labirinter : UserControl

{

int rectSize = 20;

Dictionary<string, Brush> brushes = new Dictionary<string, Brush>();

public Dictionary<string, Brush> Brushes

{

get { return brushes; }

private set { brushes = value; }

}

public Node Start

{

get;

private set;

}

public Node End

{

get;

private set;

}

public bool SetLabirint

{

get;

set;

}

public bool SetStart

{

get;

set;

}

public bool SetEnd

{

get;

set;

}

public int LRowCount

{

get;

private set;

}

public int LColumnCount

{

get;

private set;

}

public List<Node> Lbr

{

get;

private set;

}

public IEnumerable<Node> Barriers

{

get

{

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

}

}

public Labirinter()

{

InitializeComponent();

brushes.Add("Start", new SolidColorBrush(Colors.Yellow));

brushes.Add("End", new SolidColorBrush(Colors.Green));

brushes.Add("Free", new SolidColorBrush(Colors.WhiteSmoke));

brushes.Add("Barrier", new SolidColorBrush(Colors.Red));

brushes.Add("Close", new SolidColorBrush(Colors.Gray));

brushes.Add("Open", new SolidColorBrush(Colors.LightGray));

brushes.Add("Path", new SolidColorBrush(Colors.GreenYellow));

}

public void ChangeStates(Node n,string state)

{

if (!(n == Start || n == End))

n.Value.Fill = Brushes[state];

}

public void CreateField(int rowCount, int columnCount)

{

WaySearch.Reset();

MainGrid.Children.Clear();

Lbr = new List<Node>(rowCount * columnCount);

Lbr.Clear();

LRowCount = rowCount;

this.Height = LRowCount * (rectSize + 1);

MainGrid.RowDefinitions.Clear();

for (int i = 0; i < LRowCount; i++)

MainGrid.RowDefinitions.Add(new RowDefinition());

LColumnCount = columnCount;

this.Width = LColumnCount * (rectSize + 1);

MainGrid.ColumnDefinitions.Clear();

for (int i = 0; i < LColumnCount; i++)

MainGrid.ColumnDefinitions.Add(new ColumnDefinition());

for(int i=0;i<LRowCount;i++)

for (int j = 0; j < LColumnCount; j++)

{

Node n = new Node(

new Rectangle()

{

Height = rectSize,

Width = rectSize,

Fill = Brushes["Free"],

HorizontalAlignment = HorizontalAlignment.Center,

VerticalAlignment = VerticalAlignment.Center,

StrokeThickness=1,

Margin=new Thickness(0)

},i,j);

Grid.SetRow(n.Value, i);

Grid.SetColumn(n.Value, j);

MainGrid.Children.Add(n.Value);

n.Value.MouseEnter += new MouseEventHandler(Lbr_MouseEnter);

n.Value.MouseDown += new MouseButtonEventHandler(Lbr_MouseDown);

Lbr.Add(n);

}

}

public void ClearField()

{

WaySearch.Reset();

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

}

public void ClearLabirint()

{

WaySearch.Reset();

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

}

void Lbr_MouseEnter(object sender, MouseEventArgs e)

{

if (SetLabirint == true)

{

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

{

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

}

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

{

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

}

}

if (SetStart)

{

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

{

if (Start != null)

Start.Value.Fill = Brushes["Free"];

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

Start = (Lbr.First(n=>n.Value==(Rectangle)sender));

}

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

{

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

Start = null;

}

}

if (SetEnd)

{

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

{

if (End != null)

End.Value.Fill = Brushes["Free"];

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

End = (Lbr.First(n => n.Value == (Rectangle)sender));

}

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

{

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

End = null;

}

}

}

void Lbr_MouseDown(object sender, MouseButtonEventArgs e)

{

if (SetLabirint == true)

{

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

{

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

}

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

{

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

}

}

if (SetStart)

{

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

{

if (Start != null)

Start.Value.Fill = Brushes["Free"];

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

Start = (Lbr.First(n => n.Value == (Rectangle)sender));

}

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

{

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

Start = null;

}

}

if (SetEnd)

{

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

{

if (End != null)

End.Value.Fill = Brushes["Free"];

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

End = (Lbr.First(n => n.Value == (Rectangle)sender));

}

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

{

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

End = null;

}

}

}

}

}

Класс узла лабиринта

using System;

using System.Collections.Generic;

using System.Linq;

using System.Text;

using System.Windows.Shapes;

namespace Labirint

{

public class Node

{

public Rectangle Value

{

get;

private set;

}

public Node Parent

{

get;

set;

}

public int Row

{

get;

private set;

}

public int Column

{

get;

private set;

}

public double Transit

{

get;

set;

}

public double Distance

{

get;

set;

}

public double Weight

{

get

{

return Transit + Distance;

}

}

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

{

Value = value;

Row = i;

Column = j;

Transit = 0;

Distance = 0;

Parent = null;

}

}

}

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

using System;

using System.Collections.Generic;

using System.Linq;

using System.Text;

using Labirint.UserControls;

using System.Windows.Shapes;

using System.Threading;

using System.Windows.Media;

using System.Windows.Media.Imaging;

namespace Labirint

{

static class WaySearch

{

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

static Node Start;

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

static Node End;

static Labirinter labirinter; //лабиринт

static IEnumerable<Node> barriers; //коллекция перград

static List<Node> open = new List<Node>(); //открытые узлы

static List<Node> close = new List<Node>();//закрытые узлы

/// <summary>

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

/// </summary>

/// <param name="labirinter1"></param>

public static void AStar(Labirinter labirinter1)

{

WaySearch.labirinter = labirinter1;

if (labirinter.Start == null)

throw new ArgumentException("Лабиринт должен сожержать точку входа");

Start = labirinter.Start;

if (labirinter.End == null)

throw new ArgumentException("Лабиринт должен сожержать точку выхода");

End = labirinter.End;

barriers = labirinter.Barriers;

GetPath(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==null || close.Contains(n) || barriers.Contains(n) || n == node)));

return labirinter.Lbr.Where(n =>

((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));

}

//добавление полей в открытый список

static void UpdateOpen(Node node)

{

foreach (Node n in GetNearNodes(node))

{

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

{

n.Parent = node;

n.Transit = n.Parent.Transit+Math.Sqrt((n.Row - node.Row) * (n.Row - node.Row) + (n.Column - node.Column) * (n.Column - node.Column));

n.Distance = Math.Sqrt((n.Row - End.Row) * (n.Row - End.Row) + (n.Column - End.Column) * (n.Column - End.Column));

open.Add(n);

labirinter.ChangeStates(n,"Open");

}

else

{

double 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));

double newTransit = node.Transit + Math.Sqrt((n.Row - node.Row) * (n.Row - node.Row) + (n.Column - node.Column) * (n.Column - node.Column));

if (newTransit < oldTransit && node != null)

{

n.Transit = newTransit;

n.Parent = node;

}

}

}

}

//получение пути

static void GetPath(Node start)

{

if (open.Contains(End))

return;

open.Remove(start);

close.Add(start);

labirinter.ChangeStates(start,"Close");

UpdateOpen(start);

try

{

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

}

catch

{

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

}

}

//отрисовка пути

static void DrawPath(Node end)

{

if (end.Parent == null)

return;

labirinter.ChangeStates(end, "Path");

DrawPath(end.Parent);

}

//сброс

public static void Reset()

{

Start = null;

End = null;

labirinter=null;

barriers=null;

open.Clear();

close.Clear();

}

Размещено на Allbest.ru