Практическая работа №15 Решение матричных игр в чистых стратегиях
Решение матричной игры:
1 показать существование или отсутствие чистых оптимальных стратегий
2 выполнить возможные упрощения платёжных матриц
Вариант 1
Вариант 2
Вариант 3
Вариант 4
Вариант 5
Вариант 6
Вариант 7
Вариант 8
Вариант 9
Вариант 10
Вариант 11
Вариант 12
Вариант 13
Вариант 14
Вариант 15
Вариант 16
Вариант 17
Вариант 18
Вариант 19
Вариант 20
Вариант 21
Вариант 22
Вариант 23
Вариант 24
Вариант 25
Практическая работа №16 Графический метод решения матричных игр.
Произвести возможные упрощения следующих платёжных матриц и найти решения игр, используя графический метод решения.
Вариант 1
Вариант 2
Вариант 3
Вариант 4
Вариант 5
Вариант 6
Вариант 7
Вариант 8
Вариант 9
Вариант 10
Вариант 11
Вариант 12
Вариант 13
Вариант 14
Вариант 15
Вариант 16
Вариант 17
Вариант 18
Вариант 19
Вариант 20
Вариант 21
Вариант 22
Вариант 23
Вариант 24
Вариант 25
Вариант 26
Вариант 27
Вариант 28
Вариант 29
Вариант 30
Практическая работа №17
Приближенный метод решения матричных игр
Задание: В матричной игре получить приближения цены игры и оптимальных смешанных стратегий, выполнив 20 итераций.
Вариант 1
Вариант 2
Вариант 3
Вариант 4
Вариант 5
Вариант 6
Вариант 7
Вариант 8
Вариант 9
Вариант 10
Лабораторная работа №1
Построение остовного дерева минимального веса
Составить программу нахождения остовного дерева минимального веса по алгоритмам Прим и Краскал.
Указание: для написания программы целесообразно использовать теоретический материал и программную реализацию изложенную ниже.
Каркас минимального веса. Метод Дж. Краскала.
Дано. Связный неориентированный граф G=<V,E>. Ребра имеют вес. Граф описывается перечнем ребер с указанием их веса. Массив Р (Array[1..3,1..N*(N-1) Div 2] Of Integer). Результат. Каркас с минимальным суммарным весом Q=<V,T>, где T<zE.
Пример. Граф и процесс построения каркаса по методу Крас-кала.
Шаг 1. Начать с графа Q, содержащего N вершин и не имеющего ребер.
Шаг 2. Упорядочить ребра графа G в порядке неубывания их
весов.
Шаг 3. Начав с первого ребра в этом перечне, добавлять ребра в граф Q, соблюдая условие: добавление не должно приводить к появлению цикла в Q.
рис.1
Шаг 4. Повторять шаг 3 до тех пор, пока число ребер в Q не станет равным N-1. Получившееся дерево является каркасом минимального веса.
Какие структуры данных требуются для реализации шага 3? Стандартным в программировании методом является введение массива меток вершин графа (Мark:Array[ 1..N] Of Integer). Начальные значения элементов массива равны номерам соответствующих вершин (Mark[i]=i для i от 1 до N). Ребро выбирается в каркас в том случае, если вершины, соединяемые им, имеют разные значения меток. В этом случае циклы не образуются. Для примера, приведенного выше, процесс изменения Mark показан в таблице 1.
Таблица 1
Номер итерации |
Ребро |
Значения элементов Маrк |
Начальное значение |
- |
[1,2,3,4,5] |
1 |
<1,4> |
[1,2,3,1,5] |
2 |
<4,5> |
[1,2,3,1,1] |
3 |
<2,3> |
[1,2,2,1,1] |
4 |
<2,5> |
[1,1,1.1,1] |
И логика этого фрагмента.
Procedure Chang_Mark (1 ,т: Integer) ;
{*Массив Mark глобальный.*}
Var ift:Integer;
Begin
If m<l Then
Begin t:=l;l :=m;m:=t
End;
For i:=l To N Do If Mark[i]=m
Then Mark[i] :=1;
End;
Фрагмент основной части логики.
Program Tree;
Const N=..;
Var P:Array[1. . 3,1. .N* (N-1) Div 2] Of Integer; Mark:Array[1..N] Of Integer; k,i,t:Integer;
M:Integer;{*Количество ребер графа.*}
Begin
<ввод описания графа - массив Р>;
<сортировка массива Р по значениям весов ребер>;
For i:=l То N Do
Mark[i] :=i; k:=0;t:=M;
While k<N-l Do
Begin i:=l;
While (i<=t) And (Mark[P[1,i]] =Mark[P[2,i]])And <P[l,i]<>0) Do
Inc(i); Inc (k) ;
<Запоминание ребра каркаса>; Change_Mark(Mark[P[l,i]],Mark[P[2,i}]); End;
End;