Розв’язання задачі знаходження гіпотетично зв’язаних об’єктів
Застосування методу знаходження лінійного логічного перетворення для розв’язання задачі знаходження гіпотетично зв’язаних об’єктів, що дозволяє підвищити швидкість пошуку розв’язку системи предикатних рівнянь. Аналіз ефективності застосування методу.
| Рубрика | Программирование, компьютеры и кибернетика |
| Вид | статья |
| Язык | украинский |
| Дата добавления | 19.06.2018 |
| Размер файла | 26,8 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
Розв'язання задачі знаходження гіпотетично зв'язаних об'єктів
Вечірська І.Д.,
Дудар З.В.,
Токарєв В.В.,
Четвериков Г.Г.
Анотація
Пропонується застосування методу знаходження n-го лінійного логічного перетворення для розв'язання задачі знаходження гіпотетично зв'язаних об'єктів, який дозволяє підвищити швидкість і точність пошуку розв'язку системи предикатних рівнянь. Проведено аналіз ефективності застосування вищевказаного методу до задачі знаходження гіпотетично зв'язаних об'єктів. логічний гіпотетичний предикатний
Вступ і постановка задачі
На сьогодні процес обробки даних в інтелектуальних системах базується на певних знаннях про предметну область. Проте самі системи подання знань, які моделюють діяльність людини, недостатньо формалізовані. Розроблено досить багато способів подання знань. При цьому, зазвичай, кожна система подання знань має свої переваги і недоліки, наділена певною структурою та ефективна на конкретних предметних областях [1]. Природно, що чим більш узагальнений характер мови подання знань, тим на більшому просторі предметних областей вона може бути реалізована. Такою універсальною мовою подання знань можна вважати мову алгебри скінченних предикатів, яка дозволяє формалізувати довільні відношення [2, 3]. Мова алгебри предикатів і предикатних операцій ефективна та зручна для опису різної інформації, формування запитів в базах даних та моделювання діяльності людини.
Наразі розробляється структура, умови застосування, взаємозв'язків з іншими системами та комплексів задач між собою, режими роботи та принципи функціонування автоматизованої системи комплексних розрахунків (АСКР) інтегрованої інформаційно-обчислювальної системи підприємства електрозв'язку. Однією з задач, що розв'язує АСКР, є задача знаходження гіпотетично зв'язаних абонентів. Вхідні дані представлені множиною всіх абонентів міста Харкова, множиною абонентів, гіпотетичний зв'язок з якими необхідно встановити, а також номерами телефонів, по яким здійснювались дзвінки за визначений проміжок часу. Необхідно знайти всіх абонентів Харкова, які можуть бути гіпотетично зв'язані між собою. Тут і надалі в якості "гіпотетично зв'язаних" слід розуміти не безпосередній зв'язок між об'єктами (абонентами), а весь ланцюг телефонних дзвінків, через який могла передаватись інформація.
Метод знаходження -ого лінійного логічного перетворення. Метод знаходження -ого лінійного логічного перетворення було викладено та обґрунтовано в [4, 5]. Формула для його знаходження має вигляд:
,
де
та
, де
.
Метод знаходження -ого лінійного логічного перетворення можна розбити на наступні етапи. Спочатку необхідно знайти матрицю , яка є суперпозицією ядер лінійних логічних перетворень з в і, відповідно, з в : . На наступному етапі необхідно знайти кон'юнкцію всіх суперпозицій ядра лінійного логічного перетворення та вхідного вектора.
Таким чином, можно зробити висновок, що n-е лінійне логічне перетворення () залежить від виду матриці . Важливо, що матриця залежить тільки від області визначення змінної x. Тобто крок, на якому степінь лінійного логічного перетворення при подальших діях не змінюється, безпосередньо залежить від розмірності області визначення змінної x.
Було доведено твердження про те, що якщо для знаходження -ого лінійного логічного перетворення на двох послідовних кроках значення перетворення повторюється, то це значення буде повторюватись також і на наступних кроках [4]. Це твердження використовувалось для розв'язання задачі знаходження гіпотетично зв'язаних абонентів.
Аналіз застосованого методу. Проведемо далі порівняння методу, за допомогою якого раніше розв'язувалась задача знаходження гіпотетично зв'язаних абонентів, а також методу знаходження -го лінійного логічного перетворення. Раніше під час пошуку розв'язків на заданому просторі станів задавалася глибина пошуку. Таким чином, перед початком пошуку встановлювався параметр MAXSTEP, який задавав кількість ітерацій. На практиці обмежувались 5-ма кроками. Розв'язуючи за допомогою методу знаходження -го лінійного логічного перетворення, параметр MAXSTEP теж враховує час пошуку розв'язків, і він також обмежує кількість ітерацій. Але відмінність полягає в тому, що якщо розв'язок задовольняє критерію закінчення роботи метода раніше ніж параметр досягне встановленого значення, то програма закінчує пошук.
Тести розіб'ємо на декілька випадків, якщо розв'язок знаходиться за 1, 2 та кроків:
1. Припустимо, що є якась множина номерів телефонів, з яких дзвонили нечасто і не на різні номери телефонів. Тоді розв'язок знаходиться вже на 2-му кроці, але через те, що не відомо наперед за скільки кроків, міг забрати більше часу на розв'язання. За статистикою таких абонентів біля 35 процентів. Застосовуючи метод знаходження -го лінійного логічного перетворення в будь-якому випадку знаходимо розв'язок за 2 ітерації. Згідно з методом, який застосовували раніше, кількість кроків залежала від встановленого параметру MAXSTEP.
2. Припустимо, що є множина номерів телефонів, де розв'язок знаходиться за 3 кроки. За статистикою таких абонентів біля 40 процентів. Застосовуючи метод знаходження -ого лінійного логічного перетворення в будь-якому випадку знаходимо розв'язок на 3-му кроці. Згідно з методом, який застосовували раніше, - в залежності від установленого параметра MAXSTEP. І якщо ми встановимо MAXSTEP=1, то кінцевий розв'язок взагалі не буде знайденим. В інших випадках, збільшуючи значення MAXSTEP, витрачається час на зайві кроки алгоритму.
3. Припустимо, що є множина номерів телефонів, де розв'язок знаходиться за кроків.
Застосовуючи метод знаходження -го лінійного логічного перетворення в будь-якому випадку знаходимо розв'язок за кроків. Згідно з методом, який застосовували раніше, - в залежності від установленого параметра MAXSTEP. В цьому випадку, якщо параметр задати занадто маленьким, то кінцевий розв'язок не буде знайдено, тільки проміжний, а якщо задати занадто великим, то пошук розв'язку забере багато часу.
Висновки. Отже, метод знаходження -го лінійного логічного перетворення дає змогу завжди знаходити кінцевий розв'язок. Використовуючи параметр MAXSTEP, обмежується кількість кроків і розв'язок буде знайдено швидше в більшості випадків (якщо розв'язок знаходиться за 2-6 кроків). Застосовуючи метод, який використовувався раніше, не можна задавати параметр MAXSTEP маленьким (2 або 3), оскільки близько 30 процентів номерів телефонів не вкладаються в цей інтервал, якщо ж задати більше 3, то приблизно для 75 процентів номерів будуть виконані зайві ітерації. Застосування методу знаходження -го лінійного логічного перетворення позбавляє цих недоліків.
Застосування методу знаходження -го лінійного логічного перетворення для розв'язання задачі знаходження гіпотетично зв'язаних абонентів дозволило підвищити швидкість та точність пошуку розв'язків задачі за рахунок зменшення кількості кроків під час обробки інформації, внаслідок формулювання чіткого критерію закінчення роботи.
Список літератури
1. Люггер, Дж. Искусственный интеллект: стратегии и методы решения сложных проблем: пер. с англ. [Текст] / Дж. Люгер - М. : Издательский дом "Вильямс", 2003. - 864 с.
2. Бондаренко, М.Ф. Теория интеллекта: учеб. [Текст] / М.Ф. Бондаренко Ю.П. Шабанов-Кушнаренко - Харьков: Изд-во СМИТ, 2006. - 571 с.
3. Вечірська, І. Д. Про дослідження властивостей лінійних логічних перетворень [Текст] / І. Д. Вечірська, Ю.П. Шабанов-Кушнаренко // Системи обробки інформації: Зб. наук. праць. - Харків: ХУПС, 2007. - № 6. - С. 86 - 90.
4. Вечирская, И.Д. О методе нахождения n-го линейного логического преобразования [Текст] / И.Д. Вечирская, Ю.П. Шабанов-Кушнаренко // Искусственный интеллект - 2007. - № 3. - С. 382-389.
5. Вечирская, И.Д. Действия над линейными логическими преобразованиями [Текст] / І. Д. Вечірська // Новые технологии. - 2005. - № 1-2 (7-8) - С. 162-168.
Размещено на Allbest.ru
...Подобные документы
Розв’язання нелінійних алгебраїчних рівнянь методом дихотомії. Вирішення задачі знаходження коренів рівняння. Розробка алгоритму розв’язання задачі і тестового прикладу. Блок-схеми алгоритмів основних функцій. Інструкція користувача програмою мовою С++.
курсовая работа [2,0 M], добавлен 24.09.2010Застосування симплекс-методу для розв’язання оптимізаційних задач лінійного програмування, що містять три змінні. Функції ітераційної обчислювальної процедури, що виконують приведення до зручного для розв’язання оптимального вигляду ЗЛП за кілька кроків.
курсовая работа [359,5 K], добавлен 18.09.2013Технологія візуального проектування. Аналітичне розв’язання задачі в загальному вигляді. Програмування в консольному режимі. Сценарій розв’язання задачі в Delphi та блок-схема алгоритму. Програмний код додатку та опис інтерфейсу з екранними копіями.
курсовая работа [2,4 M], добавлен 22.06.2009Метод розв’язків рівнянь більш високих порядків. Вибір методу розв'язання задачі Коші. Методи розв'язання крайових задач розглядаються на прикладі звичайного диференціального рівняння другого порядку. Вибір методу інструментальних засобів вирішення задач.
курсовая работа [132,0 K], добавлен 03.12.2009Задача лінійного програмування. Розв’язання задачі геометричним методом. Приведення системи рівнянь до канонічного вигляду. Розв’язання симплекс-методом. Розв’язок двоїстої задачі. Задача цілочислового програмування і дробово-лінійного програм.
контрольная работа [385,2 K], добавлен 04.06.2009Розв’язання нелінійних алгебраїчних рівнянь методом хорд. Опис структури програмного проекту та алгоритмів розв’язання задачі. Розробка та виконання тестового прикладу. Інші математичні способи знаходження коренів рівнянь, та опис виконаної програми.
курсовая работа [4,1 M], добавлен 28.09.2010Розв’язання системи рівняння методом Гауса за схемою з частковим вибором головного елементу. Рішення задачі Коші методом Рунге-Кутта. Знаходження моментів кубічних сплайнів методом прогонки. Розв’язування системи нелінійних рівнянь методом Ньютона.
контрольная работа [252,3 K], добавлен 04.06.2010Стандартний спосіб розв’язання задачі Коші для звичайного диференціального рівняння першого порядку чисельними однокроковими методами. Геометричний зміст методу Ейлера. Побудова графіку інтегральної кривої. Особливість оцінки похибки за методом Рунге.
курсовая работа [112,9 K], добавлен 30.11.2009Огляд та аналіз методів розв’язання системи диференціальних рівнянь та вибір методів рішення. Алгоритми методів Ейлера. Вибір методу рішення задачі Коші. Рішення диференціальних рівнянь. Отримання практичних навиків програмування на мові Паскаль.
курсовая работа [174,3 K], добавлен 06.03.2010Постановка та описання алгоритму розв’язання задачі про оптимальне призначення, формулювання вимог. Обґрунтування вибору засобів програмування. Розробка структури програми та системи її візуалізації, тестування та верифікація, оцінка ефективності.
курсовая работа [1,1 M], добавлен 12.05.2013Початковий опорний план, перехід від одного до іншого. Оптимальний розв’язок, його головні критерії. Знаходження опорного плану задачі, складання симплексної таблиці. Приклад оформлення першої та другої таблиці для розв’язку задач лінійного програмування.
лекция [479,7 K], добавлен 10.10.2013Дослідження застосування різницевого методу для розв’язання крайової задачі. Дослідження проводиться на прикладі заданого диференційного рівняння. Дається опис методу та задачі в цілому. Застосування при обчисленні формули Чебишева і формули Гаусса.
курсовая работа [157,2 K], добавлен 03.12.2009Визначення і розв’язання задачі Коші для звичайних диференціальних рівнянь першого порядку методом Ейлера, алгоритм розв’язання, похибка при вирішенні. Складання блок-схеми. Реалізація алгоритму у середовищі Borland Pascal. Результат роботи програми.
курсовая работа [264,0 K], добавлен 20.08.2010Приклади застосування цілочисельних задач лінійного програмування у плануванні та управлінні виробництвом, геометрична інтерпретація їх розв’язків на площині. Завдання складання розкладу занять на математичному факультеті. Математична модель розкладу.
дипломная работа [933,1 K], добавлен 23.09.2012Використання мови програмуванння Java при виконанні "задачі лінійного програмування": її лексична структура і типи даних. Методи розв’язання задачі. Особливості логічної структури програми, побудова її зручного інтерфейсу за допомогою симплекс методу.
курсовая работа [437,9 K], добавлен 24.01.2011В роботі розглянуто наближені методи розв’язку нелінійних рівнянь. Для вказаних методів складено блок-схеми та написано програму, за якою розв’язується задане рівняння. Аналіз як самого рівняння і методів його розв’язання так і результатів обрахунку.
курсовая работа [302,8 K], добавлен 03.12.2009Загальні відомості та геометричний зміст розв'язання задачі Коші. Використання методу Ейлера для розв'язання звичайних диференціальних рівнянь першого порядку. Розробка блок-схеми та реалізація алгоритму в середовищі програмування Borland Delphi 7.0.
курсовая работа [398,1 K], добавлен 14.10.2012Розгляд та аналіз основних способів розв’язання звичайних диференціальних рівнянь за методом Рунге-Кутта з автоматичним вибором кроку. Способи оцінки погрішності і збіжності методу Рунге-кутти четвертого порядку з автоматичним вибором довжини кроку.
контрольная работа [31,0 K], добавлен 18.01.2013Види рівнянь та методи їх розв’язань. Чисельні методи уточнення коренів, постановка задачі. Рішення нелінійного рівняння методом простих та дотичних ітерацій. Використання програмних засобів. Алгоритми розв’язку задач. Програми мовою С++, їх тестування.
курсовая работа [232,2 K], добавлен 12.02.2013Створення нескладних програмних продуктів. Швидка побудова програм з використанням візуальних компонентів. Сценарій розв’язання задачі в Delphi. Програмування та програмний код в консольному режимі. Компоненти, їх властивості та структура взаємозв’язку.
курсовая работа [2,7 M], добавлен 10.06.2009
