close

Вход

Забыли?

вход по аккаунту

?

report RGR

код для вставкиСкачать
 Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования
Уфимский государственный авиационный технический университет
Кафедра вычислительной математики и кибернетики
Расчетно-графическая работа по курсу
"Теория вычислительных процессов и структур"
Тема: "Моделирование работы сетей Петри. Анализ свойств сетей Петри"
Группа ПО-335тФ.И.О.ПодписьДатаОценкаСтудентАнастасиев С. С.ПринялЗотова О. Ф.
Уфа-2012
1. Цель работы
Целью работы является моделирование работы сетей Петри и анализ их свойств на основе дерева достижимости.
2. Постановка задачи
Реализовать построение дерева достижимости (ДД), а также анализ следующих свойств сети на основе ДД:
* безопасность,
* k-ограниченность,
* строгое сохранение,
* сохранение по отношению к вектору взвешивания (вычисление вектора взвешивания),
* устойчивость (только для ограниченных сетей).
Придумать пример сети Петри, моделирующей работу некоторой реальной системы или приложения. Построить ДД, проверить свойства сети.
3. Алгоритм построения дерева достижимости
Используемые структуры (классы)
Структура дерева поделена на 3 части: узел, уровень и само дерево (класс дерева был создан т.к. программа поддерживает возможность работы с несколькими деревьями одновременно, т.е. фактически используется список указателей на каждое дерево).
Описание узла дерева - ReachabilityTreeLevelNode
public class ReachabilityTreeLevelNode
{
public PNTransition trans; // по какому переходу был создал узел
private Dictionary<PNObject, int> _marks = new Dictionary<PNObject,int>();
private List<PetriNetKernel.Activate_Transition> _enable_trans = new List<PetriNetKernel.Activate_Transition>(); //список доступных переходов public ReachabilityTreeLevelNode before_node; // указатель на родительский узел
public Point coords = new Point(0, 0); public string status = ""; // статус узла (терминальный или дублирующий используется при отрисовке дерева)
public void check_omega()
{
...
}
public List<PetriNetKernel.Activate_Transition> ETransition
{
get
{
return _enable_trans;
}
set
{
_enable_trans = value;
}
}
public static void SetMarks(Dictionary<PNObject, int> marks)
{
foreach (var i in marks)
try
{
((PNPosition)i.Key).Tokens = (int)i.Value;
}
catch (Exception e)
{
MessageBox.Show(e.Message, "Error", MessageBoxButtons.OK, MessageBoxIcon.Error);
}
}
public ReachabilityTreeLevelNode(Dictionary<PNObject, int> m)
{
_marks = m;
}
public ReachabilityTreeLevelNode Copy()
{
return new ReachabilityTreeLevelNode(_marks);
}
public void Assign(Dictionary<PNObject, int> m)
{
_marks = m;
}
public void Clear()
{
_marks.Clear();
}
}
Описание реализации проверки на омега символ.
public void check_omega()
{
if (before_node != null) // если есть предшествующий узел, т.е. если этот узел не первый
{
List<PNPosition> lst = new List<PNPosition>(); // формируем список всех позиций в нашей сети
foreach (var i in conf_class.lists_objects[MainForm.active_tab])
{
if (((PNObject)i).Type == 1)
lst.Add((PNPosition)i);
}
int sum_before_marks = 0, sum_cur_marks = 0; //сумма маркировки текущего узла и маркировки родительского узла
foreach (var i in lst) // находим сумму текущего и родительского узла
{
if (_marks[i] != -1 && before_node.Marks[i] != -1)
{
sum_before_marks += before_node.Marks[i];
sum_cur_marks += _marks[i];
}
}
if (sum_cur_marks > sum_before_marks) //если сумма текущего узла больше родительского
{
foreach (var i in lst)// ,то ищем какая именно позиция имеет больше токенов
{
if (_marks[i] > before_node.Marks[i])// сравниваем число токенов позиции текущего узла и родительского
{
if (CalculateIOArch(i))
{
_marks[i] = -1; // помечаем его как омега
ReachabilityTree.safe = false; // сразу же отмечаем, что сеть сохраняющей не является
ReachabilityTree.restriction = false; //сеть не является ограниченной
}
}
}
}
}
}
Описание уровня
public class ReachabilityTreeLevel
{
private uint _size_node; // размер узлов, фактически - размер вектора маркировки
private ReachabilityTreeLevel before_level; // предыдущий уровень
private List<ReachabilityTreeLevelNode> _nodes = new List<ReachabilityTreeLevelNode>(); // список всеех узлов на уровне
public ReachabilityTreeLevel(ReachabilityTreeLevel before)
{
before_level = before;
}
public int Count
{
get
{
return _nodes.Count;
}
}
public uint Node
{
get
{
return _size_node;
}
set
{
_size_node = value;
}
}
public void Add(ReachabilityTreeLevelNode node)
{
_nodes.Add(node);
}
public System.Collections.IEnumerator GetEnumerator()
{
for (int i = 0; i < _nodes.Count; i++)
{
yield return _nodes[i];
}
}
public ReachabilityTreeLevelNode this[int i]
{
get
{
if (i > -1)
return _nodes[i];
else
return null;
}
set
{
if (i > -1)
_nodes[i] = value;
}
}
public void Clear()
{
foreach (ReachabilityTreeLevelNode i in _nodes)
i.Clear();
}
}
Описание алгоритма построение дерева
public static void Make()
{
stability = true;
restriction = true;
restriction_level = 0;
PNTransition trans;
conf_class.trees[MainForm.active_tab] = new ReachabilityTree();
SetOfMarkings list_different_marks = new SetOfMarkings();
Dictionary<PNObject, int> InitialyMarks = new Dictionary<PNObject,int>(); //begining marks SaveMarks(ref InitialyMarks); //save marks
list_different_marks.Add(InitialyMarks);
PetriNetKernel.list_of_enable_trans.Clear();
PetriNetKernel.sequence_trans.Clear();
Dictionary<PNObject, int> mark = new Dictionary<PNObject, int>();
List<PetriNetKernel.Activate_Transition> list_for_stability = new List<PetriNetKernel.Activate_Transition>();
Queue<PetriNetKernel.Activate_Transition> enable_transitions = new Queue<PetriNetKernel.Activate_Transition>(); //for left enable transition
PetriNetKernel.search_enable_trans();//
Queue<PetriNetKernel.Activate_Transition> enable_trans_cur_node = new Queue<PetriNetKernel.Activate_Transition>();
ReachabilityTreeLevel new_level = new ReachabilityTreeLevel(null);
ReachabilityTreeLevelNode new_node = new ReachabilityTreeLevelNode(InitialyMarks);//load first node of tree
new_level.Add(new_node);//add to first level of tree
foreach (PetriNetKernel.Activate_Transition i in PetriNetKernel.list_of_enable_trans)
{
enable_transitions.Enqueue(i);
new_node.ETransition.Add(i);
//list_for_stability.Add(i);
}
conf_class.trees[MainForm.active_tab].Add(new_level);//add first level to lists of levels while (enable_transitions.Count != 0)
{
new_level = new ReachabilityTreeLevel(conf_class.trees[MainForm.active_tab].Top());
foreach (ReachabilityTreeLevelNode iterator in conf_class.trees[MainForm.active_tab][conf_class.trees[MainForm.active_tab].Count - 1])
{
iterator.SetMark();
//PetriNetKernel.search_enable_trans();
foreach (PetriNetKernel.Activate_Transition i in iterator.ETransition)
{
enable_trans_cur_node.Enqueue(i);
}
PetriNetKernel.Activate_Transition tmp;
//PetriNetKernel.search_enable_trans();
while (enable_trans_cur_node.Count != 0)
{
tmp = enable_trans_cur_node.Dequeue();
//list_for_stability.Remove(tmp);
PetriNetKernel.do_transition(tmp);
trans = enable_transitions.Dequeue().trans;
//PetriNetKernel.search_enable_trans();
mark = new Dictionary<PNObject, int>();
SaveMarks(ref mark);
new_node = new ReachabilityTreeLevelNode();
new_node.Assign(mark);
new_level.Add(new_node);
new_node.before_node = iterator;
new_node.check_omega();
new_node.trans = trans;
if (!list_different_marks.Check(mark))
{
//new_node.SetMark();
list_different_marks.Add(mark);
PetriNetKernel.search_enable_trans();
//}
foreach (PetriNetKernel.Activate_Transition i in PetriNetKernel.list_of_enable_trans)
{
enable_transitions.Enqueue(i);
new_node.ETransition.Add(i);
}
if (PetriNetKernel.list_of_enable_trans.Count == 0)
new_node.status = "(т)";
}
else
{
new_node.status = "(д)";
}
iterator.SetMark();
}
}
conf_class.trees[MainForm.active_tab].Add(new_level);
}
conf_class.trees[MainForm.active_tab][0][0].SetMark();
Draw();
}
Описание работы с программой
После запуска программы необходимо создать новую сеть или загрузить существующую: 1. Создание новой сети.
2. Загрузка уже существующей.
Выберем новую сеть; появится вкладка с областью для создания сети.
Здесь имеем панель инструментов, имеющая следующие режимы и функциональные кнопки (перечисление слева направо):
1. режим выбора, используется для изменения расположения позиций и переходов, а так же задания конкретного значения фишек и веса связи;
2. режим создания позиции;
3. режим создания перехода;
4. режим создания связи между позицией и переходом;
5. режим задания фишек у позиции;
6. режим удаления элементов сети (позиции, связи или перехода)
7. кнопка отмены действия (ctrl + Z);
8. кнопка повтора действия (в том числе повтора отменённого действия) (ctrl + Y);
9. режим запуска сети;
10. режим паузы;
11. кнопка остановки сети.
Итак, используя 6 первых режимов, создадим сеть. Для режимов задания позиций и переходов мы просто нажимаем (левой кнопкой мыши) на иконку режима затем на область рисования. Для задания связи мы подобным образом выбираем режим рисования, затем, левой кнопкой мыши выбираем исходящий элемент сети (позиция или переход) и элемент назначения (позиция или переход). Вес связи регулируется выделением связи и щелчком по колёсику мыши (в режиме выделения).
В режиме задания фишек, назначаем начальную маркировку сети. Для этого щёлкаем по позиции левой кнопкой столько раз, сколько фишек она должна содержать или же переходим в режим выделения и щелкаем колёсиком по позиции и задаём конкретное значение.
Для моделирования работы сети нужно выбрать меню "Управление" -> "Режим": "Автоматический" или "Пошаговый". После чего станут доступны режимы "Запуск", "Пауза", "Стоп" на панели инструментов. Затем нажимаем кнопку "Запуск" и сеть начнёт работать и продолжит её пока не будет нажата кнопки "Пауза" или "Стоп" или же пока в сети не будет доступных переходов (о чём программа сообщит всплывающим сообщением).
Визуализация построения усечённого дерева достижимости.
Выбираем меню "Управление" -> "Построить УДД". После чего, в окне слева во вкладке "УДД" отобразиться дерево текущей сети Петри (текущая сеть Петри это та, вкладка которой, справа, является активной).
Так выглядит УДД для нашей сети.
Проверка свойств сети и визуализация решения СЛАУ задачи сохранения.
Выбираем меню "Управление" -> "Свойства сети". В левом окне во вкладке "Свойства" отобразятся результаты. Окно "Свойства" для нашей сети.
Заключение
Была смоделирована работа сетей Петри и проанализированы свойства конкретной сети на основе дерева достижимости. Реализовано построение усечённого дерева достижимости (УДД), а также анализ следующих свойств сети на основе УДД:
* безопасность,
* k-ограниченность,
* строгое сохранение,
* сохранение по отношению к вектору взвешивания (вычисление вектора взвешивания),
* устойчивость (только для ограниченных сетей).
Самое сложное в реализации программы - было визуализация построения УДД и решения СЛАУ (особенно). Т.к. при решении этой задачи необходимо было отображать так, чтобы все надписи были видны, а отображаемые данные находились в центре области рисования.
Несмотря на сложности, с которыми пришлось столкнуться, задача была решена.
15
Документ
Категория
Рефераты
Просмотров
15
Размер файла
306 Кб
Теги
report, rgr
1/--страниц
Пожаловаться на содержимое документа