Научная литература
booksshare.net -> Добавить материал -> Математика -> -> "Математические методы и ЭВМ в историко-типологических исследованиях " -> 114

Математические методы и ЭВМ в историко-типологических исследованиях -

Ковальченко И.Д. Математические методы и ЭВМ в историко-типологических исследованиях — М.: Наука , 1989. — 271 c.
ISBN 5-02-009481-1
Скачать (прямая ссылка): matematmetodiissledovaniya1989.djvu
Предыдущая << 1 .. 108 109 110 111 112 113 < 114 > 115 116 117 118 119 120 .. 124 >> Следующая


Пусть задано начальное разбиение Ao на некотором подграфе Go- Достроение Ao до разбиения всего графа A(G), оптимального по критерию общей или «призначной» энтропии, происходит по схеме «ветвей и границ». Каждая вершина дерева поиска отвечает некоторому подграфу G1 с разбиением A1 = A(G1). Оценкой целевой функции на вершине с номером і будет величина Hj (или Hf). Для ветвления выбирается вершина с наименьшей оценкой. Пусть ее номер k и ей соответствует подграф Gk с разбиением (Gl, Gl, Gl). Выберем одну из вершин z графа G, не принадлежащую рассматриваемому подграфу. В окончательном разбиении (G1, G2, G0) для г допустимы три возможности: zeG',2eG2HzeG3. Соответственно рассмотрим три варианта разбиения графа Gk+i = GkU{z):

Очевидно, что если г инцидентно какой-либо вершине из G2, то разбиение (IV) недопустимо, и потому полагаем для него Я1 =-f-оо(Я2= + оо). В случае, если Z инцидентно некоторой вершине из Gi, недопустимо разбиение (V), а если вершины, инцидентные Z, есть и в Gl, и в Gf, то единственным рассматриваемым на следующем шаге разбиением с конечным значением критерия будет разбиение (VI).

В случае отсутствия начального разбиения в качестве начального необходимо перебрать все «минимальные варианты» разбиений, соответствующие парам несмежных вершин (Xi, Yj) графа G.

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

Будем обозначать через A(F) множество всех вершин графа G, инцидентных хотя бы одной из вершин из F, где F — подграф графа G. Пусть задано начальное разбиение (Go, Go, Go) некоторого графа Go, отвечающее следующим условиям: не существует Xi^Go и Yj^Go, таких, что (Xi, Yj)^ G, и множества A(Go) и j4(Go) не совпадают.

Опишем предлагаемый алгоритм «по индукции». Пусть на k-м шаге алгоритма получено разбиение A4 = (Gfe, Gl, Gf) подграфа Gk- На (?+1)-м шаге рассмотрим множества A(Gl) и A(Gl) ¦ Если A(Gi) = A(Gl)=O, алгоритм останавливается и получаем конечное разбиение

Во всех других случаях полагаем Bk = A(Gl) f\ A(Gl) и получаем следующее разбиение графа: Gk+i = GkUA(G1k)UA(Gl)-, Gl+1 = GkUA(Gl)-Bk- Gl+i = GlUA(Gl)-Bk-Gk+\ = GkUBk. Легко видеть, что алгоритм останавливается не более чем через т шагов, где т — число отличных от нуля элементов матрицы А.

(GlU{4 Gl, G0k), (Gl, GlU(4 G0k), (Gl, Gl, G2U{z}).

(IV) (V) (VI)

ПРИЛОЖЕНИЕ 4

ЭВРИСТИЧЕСКИЙ АЛГОРИТМ ПОСТРОЕНИЯ КЛАССИФИКАЦИИ

A(G)=(Gl, Gl, Gk, Gl).

244 ПРИЛОЖЕНИЕ 5

Классификация погребений с трупоположениями Черняховской культуры

Могильник Число объектов Число признаков Признаки* Коэффициент убедительности, нит Информативность, нит Расстояние между классами Неклассифицированные объекты, % Общие признаки, %
1-й группы 2-й группы
общая признанная
Косаново • 39 35 1, 4, 5, 8, 10, 14, 15, 6, 11, 19 18,84 71,4 66,6 1,354 10,0 31,0
17, 20, 22, 27, 30—32,
34, 40—42
Запорожская обл. 13 24 4, 8—10, 15, 17, 19, 3, 5, 20, 26, 30 12,30 38,1 33,0 1,614 8,0 33,0
24, 34, 36, 38
Киевская обл. (без Чер- 37 36 1, 4, 5, 8, 10, 11, 14, 6, 24 28,37 69,8 83,3 1,290 10,8 8,1
няхова) 17—20, 28—37, 40—42
Черняхов. Раскопки 21 27 4, 5, 19, 25, 27—32, 6, 6А, 9, 24 16,60 40,1 56,1 1,262 19,0 37,0
1961 — 1962 гг. 34, 41, 42
Данилова балка 10 20 1,4,5, 7, 10, 27, 28,40 6, 6А, 11, 14, 10,58 27,6 30,9 1,469 10,9 25,0
19, 24
Николаевская обл. 58 41 1, 4, 7, 10, 12, 13, 17, 6, 6А, 11, 14, 18 38,0 166,2 147,7 1,382 22,4 33,7
20, 21, 23, 29—36, 38,
40, 42
Ранжевое 20 28 4, 7, 10, 12, 27, 29, 5, 6, 6А, 11, 18, 17,25 66,7 62,5 1,561 15,0 35,7
31, 35 20, 25, 30, 33
Овчарня совхоза При- 54 35 1, 4, 5, 7, 12, 17, 20, 6, 6А, 11, 14, 24 46,90 156,5 151,7 1,299 22,2 31,4
днепровского 22, 27—32, 34, 36, 38, 40
Маслово Классификации с двумя группами не получено
Журавка Ольшанская 124 41 4, 7, 10, 20, 22, 23, 2, 6, 6А, 9, 11, 93,11 374,6 368,9 1,295 22,6 29,3
27—42 21, 24 Приложение 5. Окончание

ю о ю о Признаки* S Информатив- S S S от
а: Ol Я] X t U X о «и я ность, нит Расстояние между класса =S Я Np •А. ON Общие призн КИ, %
Могильник \о о о 4 U 5 :7 S Cu с о 4 о 5 T 1-й группы 2-й группы Коэффищ убедитель нит общая признанная Некласси« рованные объекты,'

Молдавия (без Будешт) 39 29 2, 4, 5, 7, 8, 10, И,
19, 20, 27—32, 34,
38, 40
Будешты 180 41 4, 5, 7, 11, 27- •36,
. 38, 40
Основной вариант общей 682 43 4, 7, 12, 23, 27- -36,
классификации 38, 40, 42
Альтернативный вариант 662 43 7, 10, 28, 29, 32, , 36,
общей классификации 37, 39, 42

* Расшифровка упоминаемых в таблице номеров: глубина захоронения: /—относительно неглубокое (менее 1 м), 2 — глубокое (более 2 м); ориентировка костяка: 3 - восток, 4 — север, 5 — северо-запад, 6— запад, 6А— юг, юго-запад, 7 — северо-восток; форма могилы: 8— овальная, 9 — овально-прямоугольная; 10—могила с ровным дном, 11 — со «ступенькой»; 12 — с подбоем, 13 — катакомба, 14 — применение дерева, 15 — применение камня, 16 — подмазка дна; /7—могилы, разрушенные в древности; положение
Предыдущая << 1 .. 108 109 110 111 112 113 < 114 > 115 116 117 118 119 120 .. 124 >> Следующая

Реклама

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed

Есть, чем поделиться? Отправьте
материал
нам
Авторские права © 2009 BooksShare.
Все права защищены.
Rambler's Top100

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed