Лабораторная работа №1 (Лабораторные работы (2007))

Лабораторная работа №1 по курсу

«Теория игр и исследование операций»

Выполнил : студент группы А-13-03
Орлов Алексей Васильевич

Москва 2007

Содержание

Постановка задачи ……………………………………………………………… 3

Описание предметной области………………………………………………. 3

Описание табличной модели ………………………………………………… 5

Пример работы…………………………………………………………………… 9

Приложение……………………………………………………………………… 10

Постановка задачи

Сформировать модель принятия решений в виде совокупности таблиц решений и написать модуль-интерпретатор для данной модели.

Описание предметной области

Данная модель имитирует поведение животных кошки и мыши в условиях замкнутого пространства, характеризуемое также наличием всевозможных стен и укрытий, со следующими допущениями:

• модель поведения кошки существенно упрощена по сравнению с моделью поведения мыши.

• было промоделировано только зрение из всех возможных чувств животных.

• Мышь и кот делают свои шаги по-очереди.

Конечное состояние достигается в случае, когда кошка ловит мышь.

Окно программы-интерпретатора:

Описание табличной модели

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

Таблица №1 (МЫШЬ)

Мышь может двигаться только на одну клетку по вертикали или горизонтали, а также может ждать (не передвигаться).

Шаг мыши в какую-либо сторону зависит от того, видит ли ее кошка и какие вокруг нее препятствия. Логика такова, что мышь всегда старается спрятаться от кошки за препятствие и переждать.

Таблица №2 (КОШКА)

Кошка может двигаться только на одну клетку по вертикали или горизонтали. Всегда движется.

Шаг кошки в какую-либо сторону зависит от того, видит ли она мышь и какие вокруг нее препятствия. Логика такова, что если мышь в поле зрения, то кошка пытается по кратчайшему пути ее догнать. Если мышь не в поле зрения, то кошка, сохраняя направление последнего перемещения, когда мышь была в поле зрения, продолжает движение вперед.

Оптимизированная трансляция

Таблица №1

Таблица №2

Пример работы

Приложение

модуль-интерпретатор был реализован на языке Borland C++

//---------------------------------------------------------------------------

#include <vcl.h>

#include <math.h>

#include <stdlib.h>

#include <time.h>

#pragma hdrstop

#include "Unit1.h"

//---------------------------------------------------------------------------

#pragma package(smart_init)

#pragma link "CSPIN"

#pragma resource "*.dfm"

#define USERMESSAGE "MyMessage"

#define YES 1

#define NO -1

#define CONDITIONS 0

#define ACTIONS 1

#define ZH 11

#define ZW 13

#define Zwall -1

#define Zgrass 0

#define Zcat 1

#define Zmouse 2

#define up 0

#define left 1

#define right 2

#define down 3

#define MYTRUE 1

#define MYFALSE 0

#define Pause 100

// начальные позиции мыши и кота на поле (0<=X<=ZH-1,0<=Y<=ZW-1): (1,3) & (4,7)

int MouseInitPosX = 1;

int MouseInitPosY = 3;

int CatInitPosX = 4;

int CatInitPosY = 7;

// пауза по кнопке, мс

int pause = Pause;

class MyMouse

{

protected:

int PosX;

int PosY;

int TimesBeSaw;

int Direct;

public:

int GetPosX() {return PosX;}

void SetPosX(int X, int I);

int GetPosY() {return PosY;}

void SetPosY(int Y, int I);

int GetTimesBeSaw() {return TimesBeSaw;}

void SetTimesBeSaw(int T) {TimesBeSaw=T;}

int GetDirect() {return Direct;}

void SetDirect(int dir);

// условия

int FirstTime() {int gtbs=GetTimesBeSaw(); if (gtbs==1) return YES; else return NO;}

int FiveTimes() {int gtbs=GetTimesBeSaw(); if (gtbs<=-10) return YES; else return NO;}

int MWall_InFront();

int MWall_Left();

int MWall_Right();

int MWall_LB();

int MWall_RB();

// действия

void DoSave();

void DoLeft();

void DoRight();

void DoForward();

void DoRandom();

void DoBack();

};

class MyCat

{

protected:

int PosX;

int PosY;

int Direct;

public:

int GetPosX() {return PosX;}

void SetPosX(int X, int I);

int GetPosY() {return PosY;}

void SetPosY(int Y, int I);

int GetDirect() {return Direct;}

void SetDirect(int dir);

// условия

int CWall_InFront();

int SeeMouse();

int NearMouse();

// действия

void DoForward();

void DoMouse();

void DoRandom();

};

// Объявления типов

MyMouse Mouse1;

MyCat Cat1;

TForm1 *Form1;

int Zone[ZH][ZW], *pZone=(int *)Zone;

TImage *IZone[ZH][ZW];

//---------------------------------------------------------------------------

__fastcall TForm1::TForm1(TComponent* Owner): TForm(Owner)

{

}

//---------------------------------------------------------------------------

void __fastcall TForm1::FormCreate(TObject *Sender)

{

OurMessage = RegisterWindowMessage(USERMESSAGE);

init();

}

//---------------------------------------------------------------------------

void __fastcall TForm1::WndProc(Messages::TMessage &Message)

{

if(Message.Msg == OurMessage)

{

Sleep(pause);

Message.Result = DoGame(Message.WParamHi,Message.WParamLo,Message.LParam);

}

else

TCustomForm::WndProc(Message);

}

//---------------------------------------------------------------------------

int TForm1::DoGame(Word WParamHi, Word WParamLo, int LParam)

{

switch(WParamHi)

{

case CONDITIONS: // Условия

switch(WParamLo) // Таблицы

{

case 1: // Таблица 1 - МЫШЬ

switch(LParam) // Номер условия

{

case 1: // Условие 1 - "Первый раз попалась на глаза коту?"

if (Mouse1.FirstTime()==YES) {Form1->Memo1->Lines->Add("MOUSE cond 1 - true");return MYTRUE;}

else {Form1->Memo1->Lines->Add("MOUSE cond 1 - false");return MYFALSE;}

case 2: // Условие 2 - "прямо стена?"

if (Mouse1.MWall_InFront()==YES) {Form1->Memo1->Lines->Add("MOUSE cond 2 - true");return MYTRUE;}

else {Form1->Memo1->Lines->Add("MOUSE cond 2 - false");return MYFALSE;}

case 3: // Условие 3 - "слева стена?"

if (Mouse1.MWall_Left()==YES) {Form1->Memo1->Lines->Add("MOUSE cond 3 - true");return MYTRUE;}

else {Form1->Memo1->Lines->Add("MOUSE cond 3 - false");return MYFALSE;}

case 4: // Условие 4 - "справа стена?"

if (Mouse1.MWall_Right()==YES) {Form1->Memo1->Lines->Add("MOUSE cond 4 - true");return MYTRUE;}

else {Form1->Memo1->Lines->Add("MOUSE cond 4 - false");return MYFALSE;}

case 5: // Условие 5 - "слева-сзади стена?"

if (Mouse1.MWall_LB()==YES) {Form1->Memo1->Lines->Add("MOUSE cond 5 - true");return MYTRUE;}

else {Form1->Memo1->Lines->Add("MOUSE cond 5 - false");return MYFALSE;}

case 6: // Условие 6 - "справа-сзади стена?"

if (Mouse1.MWall_RB()==YES) {Form1->Memo1->Lines->Add("MOUSE cond 6 - true");return MYTRUE;}

else {Form1->Memo1->Lines->Add("MOUSE cond 6 - false");return MYFALSE;}

case 7: // Условие 7 - "уже 10 шагов кот не видит мышь?"

if (Mouse1.FiveTimes()==YES) {Form1->Memo1->Lines->Add("MOUSE cond 7 - true");return MYTRUE;}

else {Form1->Memo1->Lines->Add("MOUSE cond 7 - false");return MYFALSE;}

}

break;

case 2: // Таблица 2 - КОТ

switch(LParam) // Номер условия

{

case 1: // Условие 1 - "мышь в поле зрения?"

{int T=Mouse1.GetTimesBeSaw();

if (Cat1.SeeMouse()==YES)

{

Form1->Memo1->Lines->Add("CAT cond 1 - true");

if (T>0) Mouse1.SetTimesBeSaw(T+1);

else Mouse1.SetTimesBeSaw(1);

return MYTRUE;

}

else

{

Form1->Memo1->Lines->Add("CAT cond 1 - false");

if (T>0) Mouse1.SetTimesBeSaw(-1);

else Mouse1.SetTimesBeSaw(T-1);

return MYFALSE;

}}

case 2: // Условие 2 - "прямо стена?"

if (Cat1.CWall_InFront()==YES) {Form1->Memo1->Lines->Add("CAT cond 2 - true");return MYTRUE;}

else {Form1->Memo1->Lines->Add("CAT cond 2 - false");return MYFALSE;}

case 3: // Условие З - "мышь рядом с котом?"

if (Cat1.NearMouse()==YES) {Form1->Memo1->Lines->Add("CAT cond 3 - true");return MYTRUE;}

else {Form1->Memo1->Lines->Add("CAT cond 3 - false");return MYFALSE;}

}

break;

}

break;

/////////////////////////////////////////////////////////////////

case ACTIONS: // Действия

switch(WParamLo) // Таблицы

{

case 1: // Таблица 1 - МЫШЬ

switch(LParam) // Номер действия

{

case 1: // Действие 1 - "любой возможный шаг "от кота"

Mouse1.DoSave();

Form1->Memo1->Lines->Add("MOUSE action 1");

return MYTRUE;

case 2: // Действие 2 - "шаг влево"