Первый способ формализации задач
Смысл задачи при таком ее формализованном представлении состоит в том, чтобы перевести объект из заданного начального состояния хиач в одно из конечных состояний хкон, используя только разрешенные операции Оь 02, …, Оп. Когда конечные (целевые) состояния невозможно заранее указать явно, как в случае с игрой в шахматы или го, задаются целевые условия. Это — условия, однозначно определяющие, какие… Читать ещё >
Первый способ формализации задач (реферат, курсовая, диплом, контрольная)
Элементы х предметной области Xрассматриваются как состояния некоторого, возможно абстрактного, объекта. Среди всех состояний из множества X выделяются два вида состояний: одни называют начальными состояниями хнач, другие — конечными, или целевыми, состояниями хкон. Остальные состояния играют роль промежуточных состояний.
Над объектом производятся определенные операции, в результате которых объект переходит из одного состояния хеХ в другое уеХ. Набор разрешенных операций над состояниями (обозначим их О, Оъ …, 0″) считается конечным.
Смысл задачи при таком ее формализованном представлении состоит в том, чтобы перевести объект из заданного начального состояния хиач в одно из конечных состояний хкон, используя только разрешенные операции Оь 02, …, Оп. Когда конечные (целевые) состояния невозможно заранее указать явно, как в случае с игрой в шахматы или го, задаются целевые условия. Это — условия, однозначно определяющие, какие состояния следует считать конечными. Роль этих условий в шахматах играют те положения Правил игры в шахматы, в которых описываются ситуации окончания игры: мат, пат, вечный шах и др.
Соответствующая задача в замкнутой форме, т. е. задача, формализованная первым способом, представляется теперь так: найти такую последовательность.
разрешенных операций О, Оъ …, 0″, переводящую объект из заданного начального состояниях,^ водно из конечных состояний хКО|1. Или, если конечные состояния не заданы явно, указанная последовательность разрешенных операций должна переводить объект из заданного начального состояния хнач в состояние, удовлетворяющее целевым условиям.
В качестве примера такого способа представления (формализации) задачи рассмотрим игру «Пятнадцать». Имеется квадратное игровое поле размером 4×4.
и 15 квадратных фишек, пронумерованных числами от одного до пятнадцати.
Фишки размещаются в клетках игрового поля в некотором порядке, при этом одна клетка игрового поля оказывается незаполненной (пустой), например:
Требуется, перемещая фишки в пустую клетку и не отрывая при этом их от игрового поля, получить нужный порядок фишек, например, получить расположение фишек в порядке возрастания их номеров:
В этой задаче удобно перемещения пронумерованных клеток интерпретировать как перемещения пустой клетки.
Так что разрешенных операций оказывается всего четыре: движение пустой клетки вправо, влево, вниз и вверх. Обозначим эти операции R, L, D, U соответственно. В формализованном виде постановка задачи теперь имеет следующий вид: найти такую последовательность.
операций R, L, D, U движения пустой клетки, переводящих состояние хнач в конечное состояние хкои.
Таким образом, при первом способе формализации задачи должны быть заданы:
- 1) множество Р всех состояний, которое называют пространством состояний', в нем должно быть указано начальное состояние;
- 2) множество всех разрешенных операций О, 02,…, 0″ над состояниями;
- 3) множество всех конечных состояний; при невозможности задать эти состояния явно задаются условия, однозначно характеризующие целевые состояния — целевые условия.