Пошук оптимальних шляхів у дереві рішень
Пропонується методика прогнозування розвитку нестабільних процесів за допомогою методу дерева рішень на основі експертної інформації відносно розвитку окремих параметрів, що впливають на результат прогнозу. Описуються методи пошуку оптимальних шляхів у дереві. Предлагается методика прогнозирования р...
Gespeichert in:
| Datum: | 2004 |
|---|---|
| 1. Verfasser: | |
| Format: | Artikel |
| Sprache: | Ukrainian |
| Veröffentlicht: |
Інститут проблем математичних машин і систем НАН України
2004
|
| Schlagworte: | |
| Online Zugang: | https://nasplib.isofts.kiev.ua/handle/123456789/83881 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Zitieren: | Пошук оптимальних шляхів у дереві рішень / М.В. Панченко // Мат. машини і системи. — 2004. — № 1. — С. 122-132. — Бібліогр.: 9 назв. — укр. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
nasplib_isofts_kiev_ua-123456789-83881 |
|---|---|
| record_format |
dspace |
| spelling |
Панченко, М.В. 2015-06-27T18:33:28Z 2015-06-27T18:33:28Z 2004 Пошук оптимальних шляхів у дереві рішень / М.В. Панченко // Мат. машини і системи. — 2004. — № 1. — С. 122-132. — Бібліогр.: 9 назв. — укр. 1028-9763 https://nasplib.isofts.kiev.ua/handle/123456789/83881 044.896 Пропонується методика прогнозування розвитку нестабільних процесів за допомогою методу дерева рішень на основі експертної інформації відносно розвитку окремих параметрів, що впливають на результат прогнозу. Описуються методи пошуку оптимальних шляхів у дереві. Предлагается методика прогнозирования развития нестабильных процессов с помощью метода дерева решений на основе экспертной информации относительно развития отдельных параметров, которые влияют на результат прогноза. Описываются методы поиска оптимальных путей в дереве. The methodic of prediction of the unstable processes with the help of the method of the tree of decisions on the base expert information concerning development of the separate parameters, which influence on the result of prediction is proposed. The methods of searching optimal ways in the tree of decisions are described. uk Інститут проблем математичних машин і систем НАН України Програмно-технічні комплекси Пошук оптимальних шляхів у дереві рішень Поиск оптимальных путей в дереве решений Searching optimumal ways in a tree of the decisions Article published earlier |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| title |
Пошук оптимальних шляхів у дереві рішень |
| spellingShingle |
Пошук оптимальних шляхів у дереві рішень Панченко, М.В. Програмно-технічні комплекси |
| title_short |
Пошук оптимальних шляхів у дереві рішень |
| title_full |
Пошук оптимальних шляхів у дереві рішень |
| title_fullStr |
Пошук оптимальних шляхів у дереві рішень |
| title_full_unstemmed |
Пошук оптимальних шляхів у дереві рішень |
| title_sort |
пошук оптимальних шляхів у дереві рішень |
| author |
Панченко, М.В. |
| author_facet |
Панченко, М.В. |
| topic |
Програмно-технічні комплекси |
| topic_facet |
Програмно-технічні комплекси |
| publishDate |
2004 |
| language |
Ukrainian |
| publisher |
Інститут проблем математичних машин і систем НАН України |
| format |
Article |
| title_alt |
Поиск оптимальных путей в дереве решений Searching optimumal ways in a tree of the decisions |
| description |
Пропонується методика прогнозування розвитку нестабільних процесів за допомогою методу дерева рішень на основі експертної інформації відносно розвитку окремих параметрів, що впливають на результат прогнозу. Описуються методи пошуку оптимальних шляхів у дереві.
Предлагается методика прогнозирования развития нестабильных процессов с помощью метода дерева решений на основе экспертной информации относительно развития отдельных параметров, которые влияют на результат прогноза. Описываются методы поиска оптимальных путей в дереве.
The methodic of prediction of the unstable processes with the help of the method of the tree of decisions on the base expert information concerning development of the separate parameters, which influence on the result of prediction is proposed. The methods of searching optimal ways in the tree of decisions are described.
|
| issn |
1028-9763 |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/83881 |
| citation_txt |
Пошук оптимальних шляхів у дереві рішень / М.В. Панченко // Мат. машини і системи. — 2004. — № 1. — С. 122-132. — Бібліогр.: 9 назв. — укр. |
| work_keys_str_mv |
AT pančenkomv pošukoptimalʹnihšlâhívuderevíríšenʹ AT pančenkomv poiskoptimalʹnyhputeivdereverešenii AT pančenkomv searchingoptimumalwaysinatreeofthedecisions |
| first_indexed |
2025-11-25T20:34:28Z |
| last_indexed |
2025-11-25T20:34:28Z |
| _version_ |
1850523257533366272 |
| fulltext |
ISSN 1028-9763. Математичні машини і системи, 2004, № 1
122
УДК 004.896
М.В. ПАНЧЕНКО
ПОШУК ОПТИМАЛЬНИХ ШЛЯХІВ У ДЕРЕВІ РІШЕНЬ
1. Вступ
Розвиток сучасного виробництва, науки і всього суспільства загалом можна охарактеризувати як
нелінійний та стрибкоподібний. Це обумовлено широким впровадженням сучасних технологій,
“технологізацією” виробництва і, як наслідок, підвищенням продуктивності праці, темпів глобалізації
світової економіки. Наслідком цього є виникнення нових ризиків та нестабільних умов для роботи
великих компаній, що пов′язано з неможливістю передбачити зміни на ринках праці, ресурсів та
товарів. Тому в сучасних умовах дедалі актуальнішим стає нове завдання – репрезентувати
майбутнє, яке не може інтерпретуватися як звичайне продовження минулого у зв′язку з тим, що це
майбутнє набуває істотно відмінних форм і структур.
Універсальних та досконалих підходів для розв′язання цієї проблеми на сьогодні не існує. Є
лише спроби будувати можливі сценарії розвитку тих чи інших явищ у майбутньому. Для цього
використовуються різноманітні методи якісного характеру, які базуються на використанні експертної
інформації. При їх використанні постає проблема інтерпретації нечіткої експертної інформації.
Також при обробці великого об′єму експертної інформації виникає проблема великої розмірності.
Разом з тим аналіз сучасного стану досліджень в галузі створення систем прогнозування
нестабільних процесів свідчить про наявність таких проблем:
– жоден з існуючих якісних методів сам не може бути застосований для розв′язання
наближених до реальності задач;
– проблема обробки нечітких даних при використанні різноманітних ієрархічних та сітьових
структур для зберігання експертної інформації;
– недостатня дослідженість проблеми великої розмірності, яка виникає при значному обсязі
експертних даних.
Метою роботи є розробка інструментарію для створення проблемно-орієнтованих систем
підтримки прийняття рішень, які можуть бути ефективно застосовані для прогнозування поведінки
нестабільних процесів.
У роботі [1] дан опис інструментальної системи розробки програмних систем підтримки
прийняття рішень, орієнтованої на дослідження нестабільних процесів, які складно прогнозувати за
допомогою звичайних методів математичної статистики та регресійного аналізу [3]. В основі
системи лежить метод дерева рішення, що є одним з “найадекватніших” методів представлення
експертної інформації [2]. Основні недоліки цього методу – “прокляття розмірності”, яке
посилюється у випадку задання інцедентностей у “нечіткій” формі (тобто експерт оцінює можливість
переходу з вершини до вершини у дереві рішення за допомогою функції належності або вектора).
У даній роботі описуються та досліджуються математичні засоби (методи і алгоритми), які
дозволяють, з одного боку, позбутися “прокляття розмірності”, а, з іншого, – розв′язувати конкретні
ISSN 1028-9763. Математичні машини і системи, 2004, № 1 123
практичні задачі. В основі алгоритмів, які пропонуються, лежать методи послідовного аналізу
варіантів та вектора спаду [9].
2. Методи пошуку у дереві з чітко заданими дугами
Для представлення зібраної експертної інформації використовується метод дерева рішень. Такий
вибір зумовлений можливістю більшої деталізації предметної області, що дозволяє підбирати групи
більш вузькоспеціалізованих та кваліфікованих експертів. Аналіз зібраної інформації полягає у
знаходженні оптимальних шляхів у побудованому дереві.
Якщо необхідно знайти шляхи у дереві рішень, що з’єднують певні вершини з найменшою
вагою, то використовується метод послідовного аналізу варіантів на основі методу Дейкстри [8]. Він
застосовується для пошуку найкоротшого шляху із вершини s у вершину t .
Крок 1. Перед початком виконання алгоритму всі вершини та дуги не пофарбовані. Кожній
вершині при виконанні алгоритму присвоюється число )(xd , що дорівнює довжині найкоротшого
шляху з s в x , який включає тільки пофарбовані вершини.
0)( =sd та ∞=)(xd для всіх sx ≠ . Пофарбувати вершину s та покласти sy = ( y – остання із
пофарбованих вершин).
Крок 2. Для кожної непофарбованої вершини x перерахувати величину )(xd таким чином:
)},()(),(min{)( xyaydxdxd += .
Якщо ∞=)(xd для всіх непофарбованих вершин x , закінчити процедуру алгоритму: у
вихідному графі відсутні шляхи з вершини s у непофарбовані вершини. Інакше пофарбувати ту з
вершин x , для якої величина )(xd є найменшою. Крім того, пофарбувати дугу , яка веде в обрану
на даному кроці вершину x . Покласти xy = .
Крок 3. Якщо ty = , завершити процедуру: найкоротший шлях із s в t знайдено (це єдиний
шлях із s в t , що складається з пофарбованих дуг). Інакше перейти до кроку 2.
Для знаходження шляхів з найбільшою вагою застосовується метод, розроблений на основі
алгоритму Форда [7] (алгоритму пошуку найкоротших шляхів у графі з від′ємними дугами).
Алгоритм пошуку найдовшого (наймовірнішого) шляху. Потрібно знайти найдовший шлях з
вершини s у вершину t .
Крок 1. Фарбуємо вершину s. Покладемо syxdsd =−∞== ,)(,0)( .
Крок 2. Для всіх вершин (включаючи і непофарбовані) перераховуємо
)}.,()(),(max{)( xyaydxdxd +=
Якщо −∞=)(xd для всіх непофарбованих вершин x та вершина t не пофарбована,
закінчити процедуру алгоритму: у вихідному графі відсутні шляхи з вершини s у непофарбовані
вершини. Інакше пофарбувати ту з непофарбованих вершин x , для якої величина )(xd є
найбільшою. Крім того, пофарбувати дугу , яка веде в обрану на даному кроці вершину x . Покласти
ISSN 1028-9763. Математичні машини і системи, 2004, № 1
124
xy = . Якщо d(x) для пофарбованої вершини x збільшується, то розфарбовуємо її та відповідну
дугу.
Крок 3. Якщо для всіх непофарбованих вершин −∞=)(xd та вершина t пофарбована, то
найдовший шлях знайдено, закінчити роботу алгоритму.
Твердження 1. Час роботи даного алгоритму в найгіршому випадку становить )5,1( 3NO , де
N – кількість вершин у дереві.
Доведення. Спочатку проаналізуємо обчислювальну складність алгоритму Дейкстри. На
першій ітерації цього алгоритму повинні бути проглянутими (N-1) непофарбовані вершини. Так як
перегляд вершин відбувається за допомогою рівняння )},()(),(min{)( xyaydxdxd += , то на
першій ітерації виконуються )1( −N операція додавання та )1( −N операція порівняння, а також
проводиться вибір найменшого з )1( −N чисел (тобто виконується ще )1( −N операцій
порівняння). Отже, перша ітерація включає )1(3 −⋅ N операцій. Аналогічно можна показати, що
друга ітерація включає )2(3 −⋅ N операцій, третя – )3(3 −⋅ N і т.д. Загальна кількість операцій в
алгоритмі Дейкстри визначається співвідношенням
2/)1(*3)(*3
1
−=−∑
=
NNiN
N
i
.
Окрім указаних операцій, на кожній ітерації алгоритму необхідно також виконувати операції
по знаходженню пофарбованих та непофарбованих вершин. Отже, час роботи алгоритму Дейкстри
в найгіршому випадку )5,1( 2NO . Тоді можна зробити висновок, що час роботи алгоритму
знаходження найдовшого шляху в найгіршому випадку )5,1( 3NO . Дійсно, в алгоритмі Дейкстри
кожна вершина фарбується лише один раз, а в алгоритмі знаходження найдовшого шляху вона
може фарбуватися до )1( −N разів.
3. Методи пошуку у дереві з нечітко заданими дугами
У випадку задання дуг графа нечітко, тобто за допомогою векторів чисел nkxdxd k ,1)),(()( == ,
застосовуються такі методи знаходження наймовірніших шляхів:
Метод згорток. Головна ідея цього методу полягає у заміні векторних оцінок числовими за
допомогою різних згорток [5]. Наприклад, це може бути звичайне середнє значення елементів
вектора чи згортка такого вигляду:
∑=
j
jiji uaa * , (*)
де ju – вага відповідного елемента вектора, або значення, обчислене за методом Ходжа –
Лемана,
∑−+=
j
jijiji paaa **)1(min* ββ ,
ISSN 1028-9763. Математичні машини і системи, 2004, № 1 125
де ija – елементи вектора; jp – їх ваги; )1;0(∈β – коефіцієнт “колективної
обережності”; ∑
=
=
n
j
i
sk
n 1
1β .
Після цього застосовується вищезгаданий метод пошуку найдовшого шляху. Треба зазначити, що
вказані згортки є адитивними. Це означає, що якщо один з векторів є більший за інший (тобто кожен
його елемент більший за відповідний елемент іншого вектора), то після згортки він отримує більшу
оцінку, що дозволяє уникнути ситуації, коли після застосування згортки та методу пошуку
найдовшого шляху буде знайдений шлях, який насправді (без застосування згортки) не є
наймовірнішим (тобто існує шлях ймовірніший за нього). Сформулюємо та доведемо це твердження
при застосуванні якої-небудь згортки (наприклад, Ходжа-Лемана та згортки (*)).
Твердження 2. Якщо ii ba ≥ , то ''
ii ba ≥ , де ),...,(),,...,( 11 njjnjj bbbaaa == , та
∑−+=
j
jijij paaa **)1(min*' ββ , ∑−+=
j
jijij pbbb **)1(min*' ββ ,
де ija – елементи вектора; jp – їх ваги; )1;0(∈β – коефіцієнт “колективної обережності”;
∑
=
=
n
j
i
sk
n 1
1β .
Доведення. Так як ii ba ≥ , то ijij baji ≥∀ :, . Звідси випливає, що при 10 << β
ijij ba min*min* ββ ≥ та ∑∑ −≥−
j
jij
j
jij pbpa **)1(**)1( ββ . Тоді очевидно, що '
i
i
i ba ≥ .
Також для згортки (*) сформулюємо і доведемо теорему.
Теорема. Не існує шляху ліпшого за шлях, який був знайдений у дереві за допомогою
методу згорток із застосуванням алгоритму знаходження найдовшого шляху.
Тобто, якщо був знайдений шлях ),...,( 1 kaaa = , довжина якого ),...,( '
1
' i
naaa = , де
∑
=
=
k
j
iji aa
1
' , то не існує шляху ),...,( 1 mbbb = з довжиною ),...,( ''
1
'
nbbb = , де ∑
=
=
m
j
iji bb
1
' , для якого
'' ab > , тобто '':,1 ii abni >=∀ і, відповідно, ∑∑
==
>=∀
k
j
ij
m
j
ij abni
11
:,1 .
Доведення. Нехай такий шлях знайдено. Отже,
),...,(: 1 mbbbb =∃ , ),...,( ''
1
'
nbbb = , ∑
=
=
m
j
iji bb
1
' та '' ab > . Тобто для якого
∑∑
==
>=∀
k
j
ij
m
j
ij abni
11
:,1 . (**)
Була застосована згортка ∑=
i
jiji uaa * . Це означає, що у шляху ),...,( 1 kaaa = кожна
дуга отримала оцінку ∑
=
=
n
j
jiji uaa
1
'' * і весь шлях в цілому має довжину ∑∑
= =
=
k
i
n
j
jij uaa
1 1
'' * .
ISSN 1028-9763. Математичні машини і системи, 2004, № 1
126
Відповідно і у шляху ),...,( 1 mbbb = кожна дуга отримала оцінку ∑
=
=
n
j
jiji ubb
1
'' * , і весь шлях має
довжину ∑∑
= =
=
k
i
n
j
jij ubb
1 1
'' * . Відомо, що після виконання згортки та застосування алгоритму
знаходження найдовшого шляху був знайдений шлях ),...,( 1 kaaa = , довшого за який не існує.
Тобто '''' ba ≥ . Це означає, що ∑∑ ∑∑
= = = =
≥
k
i
n
j
m
i
n
j
jijjij ubua
1 1 1 1
** або ∑ ∑ ∑∑
= = ==
≥
n
j
n
j
m
i
ijj
k
i
ijj buau
1 1 11
.
Перетворюємо цю нерівність таким чином: ∑ ∑ ∑
= = =
≥−
n
j
k
i
m
i
ijijj bau
1 1 1
0)( . Враховуючи нерівність (**),
отримуємо 0
11
<−∑∑
==
m
i
ij
k
i
ij ba . Враховуючи те, що 0:,1 ≥=∀ junj , отримуємо явну суперечність.
Отже, ∑∑
==
>=∀=¬∃
k
j
ij
m
j
ijm abnibbb
11
1 :,1:),...,( . Теорему доведено.
Якщо потрібно працювати безпосередньо з нечіткими оцінками дуг дерева, то доцільно
застосовувати такий метод:
Модифікований алгоритм пошуку найдовшого шляху. Треба знайти найдовший шлях з
вершини s у вершину t . Дуги графа задані нечітко за допомогою векторів.
Крок 1. )0,...,0()( =sd i та ),...,()( ∞∞=xd i для всіх sx ≠ , 0=i .
Крок 2. Для кожної непофарбованої вершини x наступним чином перерахувати величину
)(xd i :
)},()(),(max{)( xyaydxdxd iii += .
Очевидно, що ці вектори можуть бути незрівнянними. Тоді
)()( xdxd ii = та ),()()(1 xyaydxd ii +=+ , 2+= ii .
Тобто в цю вершину є два можливі шляхи. Якщо ж вектори є зрівнянними, то
)},()(),(max{)( xyaydxdxd iii += та 1+= ii .
Отже, маємо для вершин ix такі характеристики:
))(),...,(()( 1 ikii xdxdxd = ,
)( ii xd – довжина одного з можливих шляхів до вершини ix .
Після цього вибираємо домінуючі вершини ix , де Ai ∈ , A – деяка множина, для якої
виконується pxdxdkAjx ipjkj ∀≥¬∃∉¬∃ )()(:, , та фарбуємо їх. Якщо для пофарбованої
вершини )(xd збільшилось, то розфарбовуємо її та відповідну дугу.
ISSN 1028-9763. Математичні машини і системи, 2004, № 1 127
Крок 3. Якщо всі вершини, для яких −∞>)(xd пофарбовані, та після виконання кроку 2
жодне )(xd не збільшилось, завершити процедуру: найкоротші шляхи із s в t знайдено. Інакше
перейти до кроку 2.
В найкращому випадку, коли всі шляхи у дереві будуть зрівнянними, цей алгоритм працює зі
швидкістю алгоритму Дейкстри.
Твердження 3. Час роботи модифікованого алгоритму знаходження найдовшого шляху в
найгіршому випадку становить )5,1( 3 nNO ∗∗ , де N – кількість вершин у дереві, а n – кількість
елементів у векторах, якими задаються переходи у дереві.
Доведення. На кожному кроці цього алгоритму повинні бути проглянутими )1( −N вершини.
Так як перегляд вершин відбувається за допомогою рівня )},()(),(max{)( xyaydxdxd += , то на
кожній ітерації виконуються )1( −N операція додавання та )1( −N операція порівняння, а також
проводиться вибір найбільшого з )1( −N векторів (тобто виконується ще )1( −N операцій
порівняння). Отже, кожна ітерація містить )1(3 −⋅ N операцій. Оскільки дії виконуються над
векторами, то операції порівняння, додавання та ін. вимагатимуть ще n підоперацій, де n –
кількість елементів вектора. Кожна вершина може бути пофарбована не більше, ніж )1( −N раз.
Загальна кількість операцій в алгоритмі Дейкстри визначається співвідношенням
nNNN ∗−∗−∗− )1()1()1(3 . Тому час роботи модифікованого алгоритму знаходження
найдовшого шляху в найгіршому випадку становить )5,1( 3 nNO ∗∗ .
“Матричний” метод. Він використовується в тому випадку, коли дерево розбивається на
певні рівні. Причому кожна вершина дерева посилається тільки на вершину нижчого рівня. Кожен
рівень дерева задається матрицею km
ijij
k
ij
k aaaA },...,{}{ 1== , де ija – це імовірність, з якою
можливий перехід з i -ї вершини k -го рівня до j -ї вершини 1+k рівня. Причому, якщо у k -ї
матриці було i стовпчиків, то у 1+k матриці буде i рядків.
До кожної матриці дописуємо один рядок та стовпчик. Якщо перша матриця має лише один
рядок, то в останній стовпчик записується одиничний вектор. Якщо ж вона має декілька рядків, то в
останній стовпчик записується вектор ),...,( 1 pvv , де )
1
,....,
1
(
cc
vi = , c – кількість вершин на
першому рівні (тобто всі вершини першого рівня рівнозначні). Елемент останнього рядка
)*(
1
1
1
1
,1 ∑
=
++ =
n
j
jmijil aaa , де l та m –розмірність матриці.
Таким чином, у останньому стовпчику останньої матриці ми отримаємо ваги вершин
найнижчого рівня у дереві. Використовуючи отриману інформацію про ваги вершин у дереві, можна
визначити наймовірніші шляхи у дереві.
Доведення. Очевидно, що кількість кроків у алгоритмі дорівнює сумі кількості рядків у всіх
матрицях, тобто кількості вершин у дереві. На кожному кроці для знаходження ваг вершин нижчого
рівня проглядаються всі елементи поточного рядка, які є векторами довжиною n . Тобто на кожному
ISSN 1028-9763. Математичні машини і системи, 2004, № 1
128
кроці переглядаються всі дуги, які ведуть з поточної вершини до вершин нижчого рівня. Це означає,
що ми перебираємо всі дуги у дереві. Отже, час роботи “матричного” алгоритму становить nr ⋅ . В
найгіршому випадку, коли кількість дуг у дереві максимальна і становить 2N , час роботи цього
алгоритму буде nN ∗2 .
4. Наближені методи пошуку у дереві
Час роботи алгоритму пошуку найдовшого шляху досить великий. Наприклад, при розмірності
матриці інцедентності 100100× і заданні лише тих її елементів, які знаходяться над головною
діагоналлю (тобто нема зворотніх зв′язків у дереві), алгоритм виконуватиме приблизно 1600000
операцій (що обумовлено необхідністю знаходження не тільки довжини найдовшого шляху, але й
визначенням вершин, які входитимуть у цей шлях). Це означає, що при застосуванні комп′ютера з
процесором Pentium600 програма, яка втілюватиме даний алгоритм і розроблена за допомогою
C++Builder 5.0, буде працювати приблизно одну хвилину. Отже, необхідно запропонувати
наближені методи розв′язку задачі, які вимагатимуть меншого часу для виконання. Наприклад,
модифікацію відомого методу вектора спаду [6].
Треба знайти найдовший шлях з вершини sa у вершину ta . Відомий деякий початковий
шлях ),...,( ts aaa = , який з′єднує ці вершини. Визначаємо певний окіл r (глибину пошуку).
Крок 1. sy = .
Крок 2. За допомогою описаних методів знаходимо найдовший шлях з ya в rya + .
Замінюємо відповідний сегмент у шляху а: 1+= yy .
Крок 3. Якщо try ≤+ , то перейти до кроку 2. Якщо ж try >+ , то знаходимо найдовший
шлях з y в t . Замінюємо відповідний сегмент у шляху a . Закінчуємо роботу алгоритму.
Таким чином, покращуючи початковий шлях a , ми знаходимо оптимальний (локально
оптимальний) шлях. Він не обов′язково буде найдовшим (глобально оптимальним), але у випадку
великої кількості даних та обмеженого часу цей метод доцільно застосовувати.
Твердження 5. Час роботи модифікованого алгоритму вектора спаду в найгіршому випадку
становить ))(( 3 RKRO −∗ , де R – глибина пошуку; K – довжина початкового шляху.
Доведення. На кожному кроці алгоритму ми знаходимо за допомогою методу пошуку
найдовшого шляху найдовший шлях з вершини ja у вершину Rja + . Як вже було доведено, це
вимагатиме )( 3RO часу (в загальному випадку, час пошуку найдовшого шляху з 1a в na та з ja в
Rja + при nj ,1= , звичайно, однаковий. Але коли граф є деревом, то завжди існує можливість так
перенумерувати його вершини, що в матриці інцедентності ненульовими будуть лише елементи над
головною діагоналлю. Тоді легко змінити алгоритм так, що час пошуку найдовшого шляху з ja в
ISSN 1028-9763. Математичні машини і системи, 2004, № 1 129
Rja + буде )( 3RO в найгіршому випадку. Для цього потрібно переглядати не всі вершини, а тільки з
ja по Rja + , де nj ,1= ). Таких кроків буде RK − , бо для останніх R вершин початкового шляху
обчислень не проводиться. Отже, час роботи модифікованого алгоритму вектора спаду в
найгіршому випадку становить ))(( 3 RKRO −∗ .
Також у випадку великої кількості інформації можливе розбиття дерева на піддерева іншими
методами, в кожному з яких за допомогою вищезгаданих алгоритмів будуть знаходитися
наймовірніші шляхи. Після цього процедура “склейки” будує глобальний наймовірніший шлях.
Декомпозиційний метод. Застосовується, якщо можливе розбиття дерева на певні рівні.
Вершини кожного з цих рівнів посилаються лише одна на одну та на верхні вершини наступного
рівня.
Потрібно знайти найдовший шлях з вершини s у вершину t .
Крок 1. sy = . Визначаємо рівні, до яких належать вершини s та t . Знаходимо найдовші
шляхи з вершини s до всіх найнижчих вершин її рівня (тобто до вершин, які посилаються лише на
вершини наступного рівня) sy = .
Крок 2. 1+= yy . Знаходимо найдовші шляхи з верхніх вершин (вершин, на які
посилаються нижні вершини вищого рівня) поточного рівня до нижніх. Виділяємо пару вершин,
з′єднаних найдовшим шляхом.
Крок 3. Якщо поточний рівень містить вершину t і вона відноситься до верхніх вершин, то
перейти до кроку 4. Якщо поточний рівень містить вершину t і вона не відноситься до верхніх
вершин, то знайти найдовші шляхи з верхніх вершин поточного рівня у вершину t . Знайти ту з
верхніх вершин, шлях з якої до t найдовший. Перейти до кроку 4. Якщо поточний рівень не містить
вершину t , то перейти до кроку 2.
Крок 4. “Склеюємо” шляхи сусідніх рівнів таким чином: спочатку намагаємося знайти
найдовший шлях з останньої вершини шляху верхнього рівня до першої вершини шляху нижчого
рівня. Якщо ці вершини взагалі неможливо з′єднати, то відкидаємо останню вершину шляху з
вищого рівня і знаходимо найдовший шлях з останньої вершини вищого рівня до першої вершини
нижчого рівня. Якщо ж і ці вершини неможливо з′єднати, то відкидаємо першу вершину шляху
нижчого рівня, і т.д.
В найгіршому випадку доведеться шукати найдовший шлях між першою вершиною вищого
рівня та останньою вершиною нижчого рівня. Включаємо знайдені вершини у загальний шлях. Якщо
ж з′єднати таким чином вершини двох рівнів не вдалося, то в даному дереві неможливо з′єднати
вершини s та t .
Продовжуючи дану процедуру, ми з′єднаємо вершини s і t .
Очевидно, що знайдений шлях може не бути глобально оптимальним. Але такий підхід
дозволяє обробляти за короткий час великі об′єми даних.
ISSN 1028-9763. Математичні машини і системи, 2004, № 1
130
Нехай ii
j
i mjniaa ,1,,1),( === – i -ий рівень дерева, i
ja – вершини цього рівня. На
кожному рівні im вершин. ii
k
i qkbb ,1),( == – “верхні” вершини цього рівня, ii
t
i wtcc ,1),( == –
“нижні” вершини цього рівня. Тоді обробка декомпозиційним алгоритмом цього рівня вимагатиме
часу 3)( iii mwq ∗∗ (тут 3)( im – це час пошуку найдовшого шляху iu від верхньої вершини до
нижньої в найгіршому випадку). Процедура “склеювання” шляхів i -го та 1+i -го рівнів в найгіршому
випадку займає
3)()( 131 ∗+∗+ ++ iiii mmmm .
В цій формулі 31)( ++ ii mm – це час пошуку найдовшого шляху між будь-якими двома вершинами
рівнів i та 1+i .
Спочатку відкидається остання вершина шляху iu . Шукається найдовший шлях, який
з′єднує останню вершину шляху iu та першу вершину шляху 1+iu . Якщо ці вершини можливо
з′єднати, то знаходження відповідного шляху в найгіршому випадку займатиме 31)( ++ ii mm . Якщо
ж такого шляху не існує, то на з′ясування цього в найгіршому випадку піде час 31)( ++ ii mm .
Якщо шлях не був знайдений, вилучаємо першу вершину шляху 1+iu та знаходимо
найдовший шлях з останньої вершини шляху iu до першої вершини шляху 1+iu . Навіть якщо такого
шляху не існує, в найгіршому випадку на з′ясування цього піде 31)( ++ ii mm часу.
Аналогічна ситуація виникає і коли вилучається остання вершина шляху iu та перша
вершина шляху 1+iu . Отже, маємо три ситуації, при розгляді кожної в найгіршому випадку
вимагається 31)( ++ ii mm . Очевидно, що в найгіршому випадку доведеться таким чином перебрати
всі елементи двох шляхів і в результаті з′єднати першу вершину шляху iu та останню вершину
шляху 1+iu . Тому у формулі (*) другим додатком є 3)( 1 ∗+ +ii mm .
Отже, загалом можна сформулювати таке твердження:
Твердження 6. Час роботи декомпозиційного алгоритму в найгіршому випадку становить
∑∑
−
=
++
=
∗+∗++∗∗
1
1
131
1
3 3)()()(
n
i
iiii
n
i
iii mmmmmwq
або
3
1
1
1313 )()3)()()(( nnn
n
i
iiiiiii mwqmmmmmwq ∗∗+∗+∗++∗∗∑
−
=
++ .
Алгоритм послідовного аналізу варіантів. Необхідно знайти найдовший шлях з вершини s
у вершину t.
Крок 1. sy = . Визначаємо рівні, до яких належать вершини s та t .
Крок 2. Знаходимо найдовші шляхи із вершини s до всіх найнижчих вершин її рівня (тобто
до вершин, які посилаються лише на вершини наступного рівня). sy = .
ISSN 1028-9763. Математичні машини і системи, 2004, № 1 131
Крок 3. Якщо поточний рівень містить вершину t і вона відноситься до верхніх вершин, то
перейти до кроку 4. Якщо поточний рівень містить вершину t і вона не відноситься до верхніх
вершин, то знайти найдовші шляхи з верхніх вершин поточного рівня у вершину t . Знайти ту з
верхніх вершин, шлях з якої до t найдовший. Перейти до кроку 4. Якщо поточний рівень не містить
вершину t , то перейти до кроку 2.
Крок 4. “Склеюємо” шляхи сусідніх рівнів i и 1+i таким чином: задаються коефіцієнти iu та
ih . Для шляху g , яким буде проходити через вершини цих двох рівнів, повинно виконуватися
)( 1++≥ iii ffug , де 1, +ii ff – найдовші шляхи рівнів i та 1+i . Так само задається глибина
пошуку t . Знаходимо найдовший шлях з останньої вершини шляху верхнього рівня до першої
вершини шляху нижнього рівня. Якщо )( 1++≥ iii ffug , то процедуру склейки завершено. Інакше
відкидаємо вершини із шляхів поточних рівнів (дозволяється відкидати не більш, ніж ih вершин) та
повторюємо процедуру “склейки”. Якщо не вдалося з′єднати два рівні, то понижуємо значення iu і
повторюємо все з початку.
5. Висновки
Пропонується методика прогнозування розвитку нестабільних процесів на основі використання
експертної інформації відносно характеру розвитку окремих параметрів, що впливають на
результати прогнозу. Пошук наймовірніших шляхів у дереві рішень здійснюється за допомогою
оригінальних методів. Основна їх наукова новизна така:
– вперше розроблено метод, який дозволяє знаходити наймовірніші шляхи у дереві рішень
із чітко заданими дугами;
– вперше запропоновано метод, що дозволяє знаходити наймовірніші шляхи у дереві
рішень, побудованому на основі нечіткої експертної інформації;
– вперше розроблено методи пошуку оптимальних шляхів у дереві рішень, які дозволяють
знаходити локальні розв′язки та вирішують проблему великої розмірності, що виникає при значному
обсязі даних.
Подальші дослідження у цьому напрямку полягають у розробці більш досконалих методів збору
експертної інформації та наближених методів пошуку оптимальних шляхів у дереві рішень, які не
будуть вимагати задання початкового шляху або розбиття дерева на певні рівні (адже при
розв′язанні практичних задач це не завжди можливо здійснити) .
СПИСОК ЛІТЕРАТУРИ
1. Волошин О.Ф., Панченко М.В. Використання експертного оцінювання для якісного прогнозування на основі
багатопараметричних залежностей// Математичні машини і системи. – 2002. – № 2. – С. 83 – 90.
2. Згуровський М. Хто бачить майбутнє, той перемагає// Дзеркало тижня. – 2001. – № 25. – С. 14.
3. Тэрано Т., Асаи К., Сугэно М. Прикладные нечеткие системы. – М.: Мир, 1993. – 287 с.
4. Волошин А.Ф. Метод локализации области оптимума в задачах математического программирования // Доклады АН СССР.
Серия: кибернетика и теория регулирования. – Т. 293. – 1989. – № 3. – С. 549 – 553.
5. Макаров В. И. и др. Основы принятия решений и теории выбора. – М.: Наука, 1983. – 352 с.
ISSN 1028-9763. Математичні машини і системи, 2004, № 1
132
6. Волошин О.Ф., Гнатієнко Г.М. Побудова колективного ранжування за мірою рангів об’єктів // Вісник Київського
університету. Серія: кібернетика. –2001. – № 4. – С.140 – 147.
7. Волошин А.Ф., Гнатиенко Г.М. Построение компромиссной ранжировки в задачах группового выбора // Труды Всесоюзной
конференции “Проблемы теоретической кибернетики”. – Волгоград. – 1990. – С.15 –18.
8. Майника Э. Алгоритмы оптимизации на сетях и графах. – М.: Мир, 1981. – 476 с.
9. Сергиенко И.В. Математические модели и методы решения задач дискретной оптимизации. – Киев: Наукова думка, 1985.
– 384 с.
|