Задача о преступниках

В. C. Любченко
© 2003 г.

Программа, демонстрирующая решение описываемой задачи (45 кб)

Формулировка задачи

Десять преступников сидят в одиночных камерах. В первый день надзиратель дает им возможность поговорить между собой. Далее в каждый из следующих дней он выбирает одного из преступников и ведет в карцер. В карцере есть лампочка. Она может быть включена или выключена. Преступник, находясь в карцере, может изменить состояние лампочки, а может и не изменять. В один из дней один из преступников может сообщить надзирателю, что все уже были в карцере. Тогда, если он сказал правду, то всех выпускают, в противном случае всех казнят. Гарантируется, что если никто не будет говорить надзирателю, что все уже были, каждый побывает в карцере бесконечное количество раз.

Как нужно действовать преступникам?

О модели задачи

Итак, нам необходимо решить задачу, которая относится к классу параллельных задач. В ней в явной форме имеется множество параллельно работающих активных объектов. Среди них есть объекты, необходимость которых определяется самим условием задачи, а их активность - их сущностью. Это преступники и надзиратель. Кроме них, мы введем в имитационную модель задачи еще пару активных объектов, которые помогут нам решить задачу.

Замечание. Необходимо учесть, что, создавая далее модель задачи, мы в данном случае еще не знаем самого его решения. Его нам предстоит получить в процессе имитационного моделирования, определяя то или иное поведение (алгоритмическую модель) активных объектов модели задачи.

Среди активных дополнительных объектов первый объект условно назовем офицером. Он будет определять момент, когда все преступники побывают в карцере. Он также будет контролировать число циклов посещений карцера, где цикл - период времени посещения всеми преступниками карцера, в течение которого хотя бы один из преступников посетил карцер не более одного раза. Чтобы задача не зациклилась, офицер по истечении некоторого числа циклов своим состоянием будет сигнализировать о необходимости ее завершения. В это же состояние он перейдет, когда кто-то из преступников примет на себя решение дать ответ надзирателю. Второй объект, назовем его "протокол", будет записывать текущие внутренние состояния объектов в текстовый файл.

Используя файл протокола, мы будем анализировать процесс формирования решения при любом его исходе - положительном, когда кто-то сказал "да" или отрицательном, когда задача завершилась по истечении заданного числа циклов, но при этом почему-то ни кто из преступников не взял на себя ответственность за жизнь остальных.

Структурная модель задачи

Структурная модель программы задачи о преступниках представлена на рис.1 листа 1 проекта. На ней блок Overseer представляет модель надзирателя, блоки с именем Criminal - преступники, PunishmentCell - карцер. Все они входят в структурный блок верхнего уровня, представляющий в целом модель тюрьмы - Prison. Блок Officer - офицер, введенный дополнительно, выполняет контролирующие функции. Другой дополнительный блок - WriteStates будет на каждом шаге имитационного моделирования сохранять состояние объектов в текстовом файле.

Лист 1 (начало)

Структурная модель

Рис.1. Структурная модель задачи о преступниках

Краткое описание

1. Назначение
На рис.1. представлена структурная модель задачи имитационного моделирования поведения объектов, входящих в задачу о преступниках. В задачу в дополнение к объектам моделирующих поведение преступников, надзирателя и карцер, в задачу введен блок офицера, выполняющего функции контроля, и блок, протоколирующий внутренние состояния объектов.

2. Перечень блоков
Overseer - модель надзирателя;
Criminal 1, 2, … N - модели преступников;
Officer - модель офицера;
WriteStates - блок протокола;
Примечание. Блоки Officer и WriteStates дополнительные. Первый введен для контроля над посещением карцера, второй - для визуализации решения задачи.

3. Функционирование модели
Объекты модели функционируют параллельно. Надзиратель, получив команду, запускает процесс имитационного моделирования, выбирая преступников и направляя их в карцер. Преступник направляется в карцер только тогда, когда последний свободен. Попав в карцер, преступник выполняет действия в соответствии со своим алгоритмом поведения. Он может включить/выключить лампочку, а также в какой-то момент дать ответ на вопрос - все ли преступники побывали в карцере.

Офицер следит за тем, чтобы процесс моделирования не стал бесконечным. Он, имея доступ к соответствующей информации, отсчитывает заранее определенное количество циклов посещения преступниками карцера и сообщает о том что их число истекло остальным объектам (надзирателю).

В процессе моделирования все промежуточные состояния объектов на каждом такте модельного времени протоколируются созданным специально созданным для этого объектом. Он функционирует параллельно остальным объектам, составляющим модель. Заметим, что этот объект будет также выполнять в процессе протоколирования обработку поступающей к нему информации и дополнять протокол своим комментарием, помогающим в последующем провести анализ протокола работы модели.

Лист 1 (окончание)

В соответствии с условием задачи каждый преступник имеет связь с карцером: он может его занять (даже на какое время, определяемое сроком его наказания), включить/выключить лампочку в карцере. Надзиратель может выбрать любого из преступников и поместить в карцер. При этом он направляет в карцер только в том случае, когда последний свободен. Кроме того, надзирателю поступает команда из внешней среды, и его же состояние отражает момент завершения процесса моделирования.

Модель взаимодействия структурных блоков

Модель взаимодействия объектов представлена на рис. 1 листа 2 проекта. В соответствии с ней надзиратель, получив команду, выбирает преступника и, если карцер свободен, отправляет его в карцер (посылая сообщение объекту Go). Одновременно с этим этот же номер передается модели карцера для включения его в список преступников побывавших в карцере (сообщение Add). Параллельно надзиратель анализирует текущее состояние офицера (истекло ли число циклов посещений карцера?) и свойство Yes карцера (его истинное значение означает, что кто-то дал ответ "да").

Лист 2 (начало)

Модель взаимодействия

Рис.1. Модель взаимодействия объектов модели задачи о преступниках

Краткое описание

1. Назначение
Определяет перечень связей и сигналов, определяющих протокол взаимодействия объектов в задаче о преступниках.

2. Перечень связей блоков

Блок PuhishmentCell - карцер:

• свойство Yes (true - дан ответ "да")
• Size - число разных преступников в списке посетителей карцера

Overseer - надзиратель:

• дает команду Go - идти в карцер выбранному стрелку
• Add - включить номер преступника в список посетивших карцер
• 00 - заключительное состояние модели (процесс моделирования завершен)

Criminal 1 (cutout) 1-й преступник - "выключатель":

• Yes - ответ "да";
• "выкл" - выключить лампу.

Crimina2-N (normal) 2…N-й преступники:

• "вкл" - включить лампу.

Officer (офицер):

• состояние "e" - количество циклов истекло
• Clear - очистить список посетителей карцера (инициировать новый цикл)

Примечание 1. Связи, обозначенные пунктиром, определяют передачу имени текущего внутреннего состояния объектов.

Примечание 2. Модель карцера включает список посетителей карцера. Он содержит номера (без повторов) преступников посетивших карцер.

3. Функционирование модели

Протокол обмена сигналами и информацией состоит в следующем.

1. Надзиратель, получив команду, начинает выбирать преступника и, если карцер свободен, дает команду идти в карцер. Сразу с этим посылается и номер преступника для включения его в список посетителей карцера - метод Add модели карцера Параллельно с этим надзиратель анализирует текущее состояние офицера (истекло ли число циклов посещений карцера?) и свойство Yes карцера (его истинное значение означает, что кто-то дал ответ "да").
2. Преступник, получив команду идти в карцер, занимает его, устанавливая свойство карцера Occupy (при выходе он сбросит признак занятости карцера). При этом первый преступник, только выключает лампочку - "выкл", а остальные только включают лампочку - "вкл". Первый преступник, исходя из числа выключения лампочки, определяя число преступников посетивших карцер, выдает сигнал Yes.
3. Офицер, исходя из количества элементов в списке посетителей карцера, производит подсчет циклов посещения карцера. Когда размер списка (Size) становится равным числу преступников, он очищается (Clear), а значение счетчика циклов увеличивается на единицу.
4. Объект ведения протокола только запоминает текущее состояние связанных с ним объектов, никак не влияя на их работу.

Лист 2 (окончание)

Примечание. Сигнал "00" надзирателя отражает момент завершения работы модели.

Преступник же, получив приказ идти в карцер, занимает его, устанавливая свойство Occupy в состояние true (при выходе из карцера преступник сбрасывает признак занятости карцера). При этом существует разница в протоколе взаимодействия с моделью карцера первого преступника и остальных: первый только выключает лампочку, а остальные только включают ее (кто и когда - определяется моделями их поведения). И только первый преступник определяет число преступников посетивших карцер и соответственно отвечает за их жизнь, выдавая сигнал Yes.

Офицер, исходя из количества элементов в списке посетителей карцера, производит подсчет циклов посещения карцера. Когда размер списка (Size) становится равным числу преступников, он очищается (Clear), а значение счетчика циклов увеличивается.

Объект ведения протокола работы модели имеет доступ ко всем объектам модели, запоминая их состояние в текстовом файле. В нем при этом отображаются не только внутренние состояния активных объектов, но и состояния любых других интересующих нас объектов (например, состояние лампочки и/или номер выбранного преступника на текущем такте моделирования, которому отдается приказ идти в карцер).

Модель карцера

Модель карцера представляет лист 3 проекта. Видно, что карцер содержит модель лампочки, свойство отражающее занятость карцера и свойство, которое устанавливается в истинное состояние, если кто-то из преступников принял решение дать ответ надзирателю.

Лист 3 (начало)

Блок PunishmentCell (модель карцера)

Рис.1. Модель карцера - PunishmentCell

Краткое описание

1. Назначение
Представляет собой модель карцера, в котором отбывают наказание преступники.

2. Функционирование

Модель содержит свойства: 1) моделирующее состояние лампочки, 2) отражающее состояние занятости карцера, 3) ответ преступника, 4) список, содержащий номера преступников, которые побывали в карцере.

Преступники могут включать/выключать лампочку и, находясь в карцере, устанавливают признак его занятости, а при выходе его очищают. Список посетителей карцера создан в помощь поиска решения. Он содержит номера преступников, которые были направлены в карцер. Добавить элемент (номер преступника) в список можно с помощью метода Add, число преступников, которые побывали в карцере, возвращает метод Size, а с помощью метода Clear список очищается, т.е. приводится в исходное состояние.

Лист 3 (окончание)

С целью оказать помощь в поиске решения, в модель введен список, содержащий номера преступников направленных надзирателем в карцер. По его размеру можно судить о числе разных преступников, которые в течение процесса моделирования были в карцере. При желании можно узнать и их номера. Добавить номер преступника в список, узнать размер списка, привести его в исходное состояние (очистить) можно, используя соответствующие методы управления списков - Add, Size, Clear.

Модель надзирателя

Модель надзирателя, который направляет преступника в карцер, представлена на лист 4 проекта. Где рис 1а представляет структурную модель управляющего блока (УБ), таблица 1 - свойства и методы объекта, рис. 1в - граф модели конечного автомата (КА) алгоритмической модели, таблица 2 - предикаты и действия (элементы, входящие в табл.1 и табл.2, составляют вместе операционный блок (ОБ) модели).

Лист 4 (начало)

Объект Overseer ("надзиратель")

Рис.1. Модель блока Overseer

Краткое описание

1. Назначение
Моделирует поведение надзирателя.

2. Базовые классы
LFsaAppl (базовый автоматный класс).

3. Связи
Имеет связь с моделями офицера (предикат x2), карцера (предикаты x3, x5), тюрьмы (см. действия y4, y2, y5), выбранным преступником (см. действие y3).

4. Функционирование

4.1. Роли состояний:
Состояние "с" - состояние ожидание команды извне; состояние "G" - при переходе из этого состояния выдается команда выбранному преступнику; "r" - здесь делается проверка на число циклов и если не все пройдены, то, если карцер свободен, выбирается новый преступник; состояние "p" - проверяется, есть ли преступник с выбранным номером (по наличию указателя на него).

4.2. Алгоритм работы:
Надзиратель, получив команду, переходит в состояние "G". При этом выполняет действие y5, где формирует номер файла протокола (nNumFile), который будет определятся текущей секундой и генерирует случайный номер, привязанный к данной секунде. Далее из состояния "G" на переходе в состояние "r" в действии y2 генерируется случайный номер преступника. В состоянии "r" проверяется счетчик циклов и анализируется ответ. Если нет ответа и/или не превышено число циклов, то запрашивается на переходе в состояние "p" указатель на преступника со сгенерированным номером. В состоянии "p" указатель анализируется. Если он получен, то на переходе в состояние "G" преступнику отдается распоряжение следовать в карцер. Если указатель отсутствует, то генерируется новый номер преступника.
Завершение работы происходит при переходе в состояние "00", когда имеется ответ или когда число циклов посещения карцера превысило заранее заданное число.

Лист 4 (окончание)

Примечание 1. В нашем случае алгоритмическая модель активного объекта представлена в общем случае классом, порожденным от базового автоматного класса LFsaAppl. На структурном уровне jyf состоит из суммы блоков - УБ и ОБ. При этом модель УБ представлена моделью конечного автомата, а ОБ - это множество функций/методов (в УБ методы подразделяются на множества предикатов и действий) и данных/свойств того или иного типа.

Примечание 2. Предикат (см. x2), связанный с состоянием автомата, подключенного к входному каналу рассматриваемого автомата, принимает значение "истина" или "ложь" в зависимости от того в каком из состояний находится подключенный автомат.

В дополнение к информации, описывающей модель надзирателя, приведем аналитическую форму КА модели (способ, эквивалентный графической форме представления автоматной модели):

Overseer:

c = {G(x1/y5)},
r = {p(x2^x5/y4) , 00(^x2/-), 00(x5/-)},
p = {G(x1x4/y3), r(^x4/y2)},
G = {r(-/y2)}.

В модели по умолчанию реализуется стратегия равновероятного выбора преступников. Использование собственного (класса надзирателя) метода Random, вместо библиотечной функции random, привязывает вызов преступника к текущей секунде. Так как скорость работы модели большая, то так реализуется многократный вызов одного и тоже преступника (на Pentim 4 2433 МГц.это соответствует более 4000 вызовам в секунду и файлу протокола объемом более 12 Мб (обычно это примерно 19 Кб)!).

Модели преступников

Решение, предложенное Игорем Дехтяренко, заключается в следующем: один из преступников только выключает свет, а остальные только включают его[2]. Преступник-выключатель подсчитывает выключения и на основании их количества делает вывод о числе "нормальных преступников" отбывших наказание.

Описанные выше два вида поведения преступников представлены в задаче соответственно двумя типами моделей - FCriminalCutout и FСriminalNormal. Эти классы производные от класса FCriminal, который собственно и есть модель обычного преступника.

Модель преступника Criminal представлена на лист 5 проекта. Аналитическая форма КА модели преступника будет следующей:

Criminal:

T = {p(x1/y1)},
p = {z(x2/y6) , z(^x2^x4/y2y6) , z(^x2x4/y6)},
z = {T(-/y5)}.

Лист 5 (начало)

Объект Criminal ("преступник")

Рис.1. Модель блока Criminal

Краткое описание

1. Назначение
Моделирует поведение преступника.

2. Базовые классы
LFsaAppl (базовый автоматный класс)

3. Связи
Имеет связь с моделью карцера (предикаты x2, действия y2) - проверяет состояние лампочки, включает лампочку.

4. Функционирование

4.1. Роли состояний:
Состояние "Т" - находится в своей камере и ждет команду идти в карцер; состояние "p" - находится в карцере и принимает решение, что делать с лампочкой; состояние "z" - в это состояние попадает после реализации задержки, моделирующей время нахождения в карцере.

4.2. Алгоритм работы:
Преступник в состоянии "Т", находясь в камере, в случае получения приказа идти в карцер направляется в него, попадая при этом в состояние "p". Попав в это состояние (установив при переходе в него признак занятости карцера - y1) преступник анализирует ситуацию. Если лампочка горит, то просто отсиживает свой срок, переходя в состояние "z". Если лампочка не горит, то при первом своем посещении он зажигает ее при последующих - не трогает. Отсидев в карцере, он возвращается в камеру - состояние "Т" (устанавливая признак занятости карцера в состояние "свободно")

Лист 5 (окончание)

Из модели следует, что преступник включает лампочку только при первом посещении карцера. Находясь в карцере, он устанавливает признак занятости, а покидая - сбрасывает. Кроме того, в действии y6 с помощью автоматной библиотечной функции FDelayCLK(n) реализуется задержка преступника на n тактов автоматного времени (n - случайная величина, зависящая от номера преступника).

Модель "нормального" преступника CriminalNormal, производного от модели Criminal, представлена на листе 6 проекта. Она полностью повторяют модель базового класса.

Лист 6 (начало)

Объект CriminalNormal ("нормальный преступник")

Рис.1. Модель блока CriminalNormal

Краткое описание

1. Назначение
Моделирует поведение "обычного" преступника, который только включает лампочку .

2. Базовые классы
FCriminal (преступник)

Примечание. Связи, поведение и др. свойства полностью соответствуют базовому классу (см. лист 5 проекта). Класс создан в основном только для того, чтобы разделить преступников по поведению.

Лист 6 (окончание)

Модель преступника-выключателя CriminalСutout представлена на лист 7 проекта. Эта модель уже имеет поведение, которое отличается от базовой модели. Несколько изменен и дополнен перечень ее предикатов и действий. Аналитическая форма КА модели преступника будет следующей:

CriminalСutout:

T = {p(x1/y1)},
p = {z(x2/y6) , z(x2x3/y2y3y6) , y(x2^x3/y2y3)},
y = {z(-/y3y6)}.
z = {T(^x4/y5), yes(x4/y4y5)}.
yes = {T(-/y5)}.

Этот преступник только выключает лампочку. По условию решения каждое выключение определяется, как посещение одним из преступников карцера. Причем, при своем первом выключении преступник-выключатель наращивает счетчик посетителей на две единицы, переходя при этом через состояние "y", в остальных случаях - на единицу. Нарастив значение счетчика до значения, которое равно числу преступников в тюрьме, модель переходит в состояние "yes", что и является решением поставленной задачи.

Лист 7 (начало)

Объект CriminalCutout ("преступник-выключатель")

Рис.1. Модель блока CriminalСutout

Краткое описание

1. Назначение
Моделирует поведение преступника, который ведет подсчет преступников, посетивших карцер.

2. Базовые классы
FCriminal (преступник)

3. Связи
Соответствуют связям базового объекта.

4. Функционирование

4.1. Роли состояний (см. состояния базового класса):
Состояние "y" - в него модель переходит при первом выключении горящей лампочки; состояние "yes" - состояние ответа надзирателю.

4.2. Алгоритм работы:
Поведение данного преступника отличается от поведения базового класса. Во-первых, преступник не включает, а только выключает свет. Каждое выключение сопровождается увеличением счетчика nCriminals (действие y3). При первом посещении, если свет горит, действие y3 выполняется дважды: за себя и преступника, который зажег свет (в исходном состоянии свет выключен). Когда значение этого счетчика станет равным числу преступников, происходит переход в состояние "yes", которое соответствует ситуации, когда все преступники побывали в карцере (предикат x4 - истина).
Замечание. После того, как автомат попадает в состояние "yes", следующее направление преступника в карцер приводит к завершению его работы, т.к. в соответствии с условием задачи преступники должны быть или освобождены или казнены.

Лист 7 (окончание)

Лист 8 (начало)

Объект Officer ("офицер")

Рис.1. Модель блока Officer

Краткое описание

1. Назначение
Офицер - ведет контроль посещений карцера.

2. Базовые классы
LFsaAppl

3. Связи
Имеет связь с моделью карцера.

4. Функционирование

4.1. Роли состояний:
Состояние "s" - ведет подсчет циклов; состояние "e" - циклы отработаны.

4.2. Алгоритм работы:
В состоянии "s" офицер контролирует размер списка и счетчик циклов. Если размер списка становится равен числу преступников (x1 - "истина"), то список очищается, а счетчик циклов наращивается на единицу - действие y1. Если значение счетчика циклов достигло максимального значения (x2 - "истина"), то автомат переходит в состояние "e".

Лист 8 (окончание)

Модель блока протокола

Модель структурного блока WriteStates, реализующего функции запоминания текущего внутреннего состояния программных объектов, представлена на листе 9 проекта. Ее переход из начального состояния "ws" в состояние "w0" происходит, если создана модель тюрьмы. При этом запускается действие y1, которое открывает файл протокола. Затем, в состоянии "w0" до тех пор, пока модель надзирателя не окажется в заключительном состоянии "00", в цикле формируются строки протокола (действие y2).

Лист 9 (начало)

Объект WriteStates ("протокол")

Рис.1. Модель блока WriteStates

Краткое описание

1. Назначение
Офицер - ведет контроль посещений карцера.

2. Базовые классы
LFsaAppl

3. Связи
Имеет связь с моделью надзирателя.

4. Функционирование

4.1. Роли состояний:
Состояние "ws" - начальное состояние; состояние "w0" - формирование строк протокола.

4.2. Алгоритм работы:
Если указатель на модель тюрьмы не NULL, то на переходе в состояние "w0" открывается файл протокола. Затем, в состоянии "w0" до тех пор, пока модель надзирателя не окажется в своем заключительном состоянии "00", в цикле формируются строки протокола.

Примечание 1. Действие y1 реализует и небольшой анализ состояний модели на текущем шаге моделирования. Это:

1. Если одновременно несколько преступников находятся в состоянии "p" (это означает, что преступник находится в карцере), то в протокол выводится сообщение "толпа".
2. В целях большей наглядности горящая лампочка в протоколе изображается символом - "*", выключенная - ".".
3. Если надзиратель находится в состоянии "G", то выводится дополнительно номер преступника. Это тот преступник, которому в этот момент дается распоряжение следовать в карцер.
4. Если состояние преступника "yes", то в протокол дополнительно выводиться сообщение "yes!!!".

Примечание 2. Перед закрытием файла протокола в действии y3 сначала выводится статистическая информация - сколько раз каждый из преступников побывал в карцере.

Лист 9 (окончание)

В процессе создания протокола действие y2 выполняет и небольшой анализ состояний модели на текущем шаге моделирования. Это (см. пример протокола, представленного на лист 12 проекта):

1. В целях наглядности лампочка в протоколе изображается символом: "*" - включена, "." - выключена.
2. Если одновременно несколько преступников находятся в состоянии "p", а это означает, что несколько преступников одновременно находится в карцере, в протокол выводится сообщение "толпа".
3. Для шага моделирования, в котором надзиратель находится в состоянии "G", выводится номер преступника. Это как раз тот преступник, которому в этот момент дается распоряжение следовать в карцер.
4. Если состояние преступника "yes", то в и протокол дополнительно выводиться сообщение "yes!!!".

Перед закрытием файла протокола в действии y3 сначала выводится статистическая информация - сколько раз каждый из преступников побывал в карцере.

Модель тюрьмы

Модель тюрьмы - объект класса CPrison - представляет лист 10 проекта. Она включает в себя модель надзирателя и модели преступников, также в нее входит и модель карцера. Используя свойства модели, можно задать любое число преступников, а не только то число, которое оговорено в условии задачи. Посылая модели сообщения можно запустить процесс имитационного моделирования (метод - Command), создать и удалить объекты, которые составляют задачу и т.д. и т.п. При создании объекта, моделирующего тюрьму, ему передается также указатель на автоматную среду, в которую будут загружены все активные модели - автоматные модели объектов задачи.

Лист 10 (начало)

Объект CPrison (модель тюрьмы)

Рис.1. Модель тюрьмы - CPrison

Краткое описание

1. Назначение
Представляет собой модель тюрьмы.

2. Базовые классы
Нет.

3. Связи
Внешняя среда определяет число преступников (свойство - nNumberOfCriminals), инициирует объекты (метод - CreateObjects) и запускает процесс решения (метод - Command).

4. Функционирование

Модель содержит свойства: 1) определяющее число преступников в тюрьме, 2) указатели на объекты, моделирующие офицера, надзирателя, 3) массив объектов моделей преступников, 4) модель карцера 5) указатель на автоматную среду, в которую будут помещены все активные объекты модели.

С помощью методов объекта можно создать/удалить объекты, входящие в имитационную модель задачи, есть метод, возвращающий по номеру преступника указатель на него из массива, который их содержит.

Послав объекту сообщение Command, мы тем самым начинаем процесс моделирования решения.

Лист 10 (окончание)

Головной объект программы

Головной объект имитационной модели решения задачи о преступниках - объект класса CNetFsaPrison - представляет лист 11 проекта. В состав этого объекта входит модель тюрьмы и модель блока протокола. На этом уровне управление процессом моделирования заключается в создании модели задачи с помощью метода Create, запуска процесса моделирования последовательностью вызова методов Command и OnIdle. При этом момент завершение работы метода OnIdle определяет момент завершения решения задачи (см. также листинг 1 на листе 11).

Лист 11 (начало)

Объект CNetFsaPrison (головной объект-приложение)

Рис.1. Головной объект - CNetFsaPrison

Краткое описание

1. Назначение
Содержит объекты - два основных объекта: модель задачи и объект, реализующий процесс протоколирования решения (записывающего в файл имена внутренних состояний активных объектов задачи).

2. Базовые классы
CArrayNetFsa - класс параллельной автоматной среды.

3. Связи
Создание нужного количества объектов, управление процессом моделирования и запуск цикла моделирования осуществляются через соответствующие методы объекта (подробнее см. п.4 - функционирование).

4. Функционирование

Для решения задачи необходимо выполнить следующую последовательность вызова методов.

1. Вызвать метод Create, с помощью которого определить число преступников в задаче.
2. Для установки признака запуска решения вызвать метод Commnd.
3. Вызвать метод OnIdle, который выполнит весь цикл моделирования решения задачи (выход из него произойдет при условии завершения процесса, моделирующего надзирателя).

Пример последовательности выполнения данных шагов показан в листинге 1.

int main(int argc, char* argv[])
{
    if (argc != 2) return 0;
    int nR = atoi(argv[1]);

    CNetFsaPrison CNFPrison;    // объект-приложение
    CNFPrison.Create(nR);        // создать заданное число преступников
    CNFPrison.Command();        // создать заданное число преступников
    CNFPrison.OnIdle();        // выполнение процесса морделирования
    return 0;
} 

Листинг 1. Головной модуль программы.

Лист 11 (окончание)

О решении

Рассмотренная в проекте имитационная модель задачи о преступниках находит решение лишь при известном начальном состоянии лампочки. От него зависит поведение преступника-выключателя. При этом сама модель УБ модели преступника не изменяется, а меняется только код предиката x4 (см. код реализации класса FCriminalCutout).

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

Литература

1. Шамгунов Н. Задачи на сообразительность (задача №6). http://is.ifmo.ru/?i0=reflections&i1=problems

2. Тема "ПарПр: Задача о преступниках" в Форуме сайта SoftCraft. Сообщение № 23. http://www.softcraft.ru/topic.shtml?key=70

Лист 12 (начало)

Протокол 1. Пример решения задачи о преступниках

Число преступников:10                                
Отображается:                                        
1.Шаг моделирования                                    
2.Состояние офицера                                    
3.Состояния преступников                                
4.Состояние лампочки (*-горит, . - потушена                
5.Номер цикла (цикл - все преступники побывали в карцере)    
6.Номер преступника, отправленного в карцер                
   1:r,T,Т,Т,Т,Т,Т,Т,Т,Т,Т,*,0,                        
   2:p,T,Т,Т,Т,Т,Т,Т,Т,Т,Т,*,0,                        
   3:G,T,Т,Т,Т,Т,Т,Т,Т,Т,Т,*,0,6                        
   4:r,T,Т,Т,Т,Т,p,Т,Т,Т,Т,*,0,                        
   5:p,T,Т,Т,Т,Т,p,Т,Т,Т,Т,*,0,                        
…                                                
  42:p,T,Т,Т,Т,Т,Т,Т,Т,Т,Т,*,0,                        
  43:G,T,Т,Т,Т,Т,Т,Т,Т,Т,Т,*,0,1                        
  44:r,p,Т,Т,Т,Т,Т,Т,Т,Т,Т,*,0,                        
  45:p,y,Т,Т,Т,Т,Т,Т,Т,Т,Т,.,0,                        
  46:p,z,Т,Т,Т,Т,Т,Т,Т,Т,Т,.,0,                        
  47:p,T,Т,Т,Т,Т,Т,Т,Т,Т,Т,.,0,                        
  48:G,T,Т,Т,Т,Т,Т,Т,Т,Т,Т,.,0,4                        
  49:r,T,Т,Т,p,Т,Т,Т,Т,Т,Т,.,0,                        
  50:p,T,Т,Т,p,Т,Т,Т,Т,Т,Т,*,0,                        
…                                                
 535:p,T,Т,Т,Т,Т,Т,z,Т,Т,Т,*,3,                        
 536:p,T,Т,Т,Т,Т,Т,Т,Т,Т,Т,*,3,                        
 537:G,T,Т,Т,Т,Т,Т,Т,Т,Т,Т,*,3,9                        
 538:r,T,Т,Т,Т,Т,Т,Т,Т,p,Т,*,3,                        
 539:p,T,Т,Т,Т,Т,Т,Т,Т,p,Т,*,3,                        
 540:p,T,Т,Т,Т,Т,Т,Т,Т,p,Т,*,3,                        
 541:p,T,Т,Т,Т,Т,Т,Т,Т,p,Т,*,3,                        
 542:p,T,Т,Т,Т,Т,Т,Т,Т,p,Т,*,3,                        
 543:p,T,Т,Т,Т,Т,Т,Т,Т,p,Т,*,3,                        
 544:p,T,Т,Т,Т,Т,Т,Т,Т,p,Т,*,3,                        
 545:p,T,Т,Т,Т,Т,Т,Т,Т,z,Т,*,3,                        
 546:p,T,Т,Т,Т,Т,Т,Т,Т,Т,Т,*,3,                        
 547:G,T,Т,Т,Т,Т,Т,Т,Т,Т,Т,*,3,1                        
 548:r,p,Т,Т,Т,Т,Т,Т,Т,Т,Т,*,3,                        
 549:p,z,Т,Т,Т,Т,Т,Т,Т,Т,Т,.,3,                        
 550:p,yes,Т,Т,Т,Т,Т,Т,Т,Т,Т,.,3,   yes!!!!                
 551:G,T,Т,Т,Т,Т,Т,Т,Т,Т,Т,.,3,3                        
 552:r,00,Т,p,Т,Т,Т,Т,Т,Т,Т,.,3,                        
 553:00,                                            
Посещения карцера (преступник-число,):                    
 1-14, 2- 3, 3- 3, 4- 8, 5-15, 6- 9, 7- 6, 8-10, 9-12,10- 5,

Лист 12 (окончание)