Дипломная работа на тему «Преследование жертв автоматов-жертв автоматом-хищником с красками» (стр. 1 )

Филиал Московского государственного университета

имени в г. Ташкенте

Ситаблаев Энвер Диляверович

ДИПЛОМНАЯ РАБОТА

на тему «Преследование жертв автоматов-жертв автоматом-хищником с красками»

по направлению 010500 - «Прикладная математика и информатика»

КР рассмотрена и рекомендована к защите Зав. кафедрой «МаТИС» д. ф.-м. н., профессор _________ «___»____________2012 год

Научный руководитель: м. н.с. ______________ «___»_________2012 год

Ташкент 2012 Аннотация Изучается процесс преследования автоматами с красками («хищников») независимых друг от друга автоматов («жертв») на плоскости, а так же задача преследования одним автоматом-хищником с краской одного автомата-жертвы, без красок на одномерной ленте. Показано преимущество автоматов с красками над коллективами автоматов. В частности, ряд задач по поимке жертв на плоскости, которые в работах и были решены коллективами из трех автоматов-хищников, в данной работе решаются одним автоматом-хищником с красками. Показана возможность поимки одним автоматом-хищником с одной краской любой жертвы с несамопересекающейся траекторией, оставляющей след. Доказана лемма о существовании физически реализуемой траектории, которая не может быть реализована автоматам с краской на полосе.

Содержание

1.  Введение

2.  Основные понятия и результаты

3.  Доказательство вспомогательных лемм

4.  Доказательство основных результатов

5.  Список использованной литературы

Введение

Рассматривается автоматный аналог ситуации преследования хищниками жертв. Исследуется вопрос преследования одним автоматом хищником с краской независимых систем автоматов-жертв. Будем считать, что жертвы способны “видеть” хищника в некоторой своей окрестности, но “не видят” других жертв. Таким образом, жертвы образуют независимую систему.

в работе [2] показано, что для обхода плоскости нужно три автомата без красок, двое из которых – камни, т. е. не могут двигаться самостоятельно. Так же описаны малые коллективы автоматов без красок, которые обходят лабиринты разного типа. В данной работе построены автоматы с одной краской и одним состоянием, обходящие все рассмотренные в работе [2] лабиринты.

в работе [3] введен класс автоматов-жертв. Доказано, что поимка на плоскости всех жертв из этого класса может быть осуществлена коллективом из трех автоматов-хищников, но может быть осуществлена меньшим числом хищников без красок. В данной работе построен автомат–хищник с одной краской, ловящий на плоскости всех автоматов-жертв из класса.

Аналогично, в работе [2] показано, что один автомат-хищник без краски не способен осуществлять поимку заданного автомата-жертвы на плоскости. Для решения этой задачи в [2] используется коллектив из трех автоматов-хищников. В данной работе подобная задача решена при помощи одного хищника с краской, в предположении, что жертва, которую необходимо поймать, оставляет на плоскости след раз в несколько тактов. Построен автомат–хищник с одной краской, ловящий на плоскости фиксированный автомат-жертву, оставляющий такие следы.

В данной работе также построен автомат-хищник с одной краской, ловящий на плоскости любых автоматов-жертв, оставляющих след, с несамопересекающимися траекториями.

Основные понятия и результаты.

Будем использовать стандартные обозначения для множеств натуральных и целых чисел N и Z, соответственно. Положим N0 = N U{0}.Множество клеток, на которые плоскость разбивается целочисленной решеткой, обозначим через Z2, сопоставляя каждой клетке координаты ее нижнего левого угла. Назовем r-окрестностью клетки (x0,y0) множество D(x0,y0),r = { (x, y) є Z2 | (|x-x0|+|y-y0| ≤ r)}, где r є N0. Будем считать, что задана определенная нумерация клеток множества D(x0,y0),r.

Определим следующие лабиринты – подмножества Z2. = Z2, = {(x, y) | x є Z, y є N}, (l) = {(x, y) | 0 < y ≤ l, x, y є Z}, (l) = {(x, y) | 0 < y ≤ l, x, y є N}, = {(x, y) | x, y є N}, (l) = {(x, y) | 0 < y ≤ l, 0 < x ≤ l, x, y є N}.Здесь l є N.

Эти лабиринты назовем соответственно, плоскостью, полуплоскостью, l-полосой и l-полосой, квадрантом и l-квадрантом.

Рассмотрим автоматный аналог ситуации преследования хищниками своих жертв. В качестве пространства преследования будем рассматривать лабиринт L, являющийся одним из лабиринтов , , (l), (l), , (l). Хищник и жертвы представляются в виде автоматов, которые находясь в какой-либо клетке лабиринта, умеют обозревать некоторую её окрестность, и, в зависимости от вида (конфигурации) этой окрестности и своего состояния, способны перемещаться в другую клетку лабиринта. Поведение каждого автомата определяется его начальным расположением в лабиринте, его «физическими параметрами» - обзором и скоростью, а также его внутренней логикой. Определим хищников и жертв более формально.

Под автоматом будем понимать инициальный конечный автомат вида Ά=(A, Q,B,φ,ψ,q0), где A-входной, B-выходной, Q-внутренний алфавиты автомата Ά, φ:QxA→ Q и ψ:QxA→B – функции переходов и выходов Ά, соответственно, q0єQ – его начальное состояние. Алфавит A определяет возможности Ά “видеть” происходящее вокруг, а алфавит B - его возможности перемещаться. Алфавит Q и функции φ и ψ задают внутреннюю логику автомата Ά.

Под автоматом с краской будем понимать семерку вида Ά с =(A, Q,B, С,φ,ψ,q0), где A-входной, B-выходной, Q-внутренний алфавиты автомата Ά с, С – множество красок, φ:QxA→ Q и ψ:QxA→BxC – функции переходов и выходов Ά с, соответственно, q0єQ – его начальное состояние.

Выходной алфавит B, автомата Ά с есть множество пар вида (, ), где є, єC.

Рассмотрим автомат Ά с, перемещающийся по Z2. Выходным алфавитом Ά с является множество B = , где параметр VєN называется скоростью автомата Ά с.

Следующие определения будем считать верными для автоматов и для автоматов с краской.

Входной алфавит A зависит от параметра RєN (R≥V), называемого обзором автомата Ά с и способа взаимодействия Ά с с другими автоматами. Возможны два случая такого взаимодействия:

1) Ά с является элементом независимой системы автоматов;

2) Ά с является элементом коллектива автоматов.

Автомат с краской со скоростью V и обзором R будем обозначать как Ά с (R, V). Пусть Ά с (R, V) находится в клетке (x0,y0). Множество D(x0,y0),V называется окрестностью хода Ά с, а множество D(x0,y0),R – зоной обзора Ά с.

Будем говорить, что автомат обходит плоскость, если для любой клетки u плоскости существует такт t, такой что клетка u попадает в зону обзора автомата.

Рассмотрим две системы автоматов Wc(R, V) (хищник) и U=(U1,…,Un)(R’,V’) (жертвы), где R и R’ - обзоры, а V и V’ – скорости хищника и жертв, соответственно. Здесь U – независимая система автоматов.

Положим N’ =(R’ +1)2 +(R’)2 – размер зоны обзора жертвы. Для каждого i =1,…,n строку (a1,…,aN’), такую, что для любого k =1,…,N’

 

1, если в k-й клетке зоны обзора Ui находится хищник;

ak =

0, иначе;

назовем Ui - конфигурацией. Каждая Ui –конфигурация однозначно задает клетки зоны обзора Ui, в которых находится хищник.

Положим N =(R +1)2 +(R)2 – размер зоны обзора хищника. Cтроку (a1,…,aN), такую, что для любого k =1,…,N

 

1, если в k-й клетке зоны обзора W находится жертва;

ak =

0, белый цвет;

2..m+1, окрашена в один из цветов 1..m

назовем W-конфигурацией. W–конфигурация однозначно задает клетки зоны обзора W, в которых находится жертва.

Расположения на плоскости жертв и хищника и состояния хищников однозначно задают все Ui – конфигурации и Wс - конфигурация. Множество всех Ui – конфигураций при всевозможных расположениях жертв и хищника и состояний хищника обозначим как F’. Аналогично, Wс – конфигураций обозначим как F. Входным алфавитом каждой жертвы Ui является множество всех пар вида (F1,F2),где F1є({0}UF’), а F2єF’. Входным алфавитом хищника Wс является множество всех пар вида (F1,F2), где F1, F2єF.