Машина Тюрінга
Дипломная работа - Компьютеры, программирование
Другие дипломы по предмету Компьютеры, программирование
змінюється, то номер j включається з приведенням подібних в М. Знову виконується п. 2.
- Якщо вага
, то робиться висновок, що шляхи з вершини X н до вершині X k не існує, інакше виконується процедура виділення дуг, рухаючись в зворотному порядку перевіряємо чи виконується умова Xi - X j = l ij, для входів вершини X i, якщо воно виконується, то вершина X j і дуга l ij виділяються.
4. Після виділення дуг будуються довгі шляхи, довжини яких рівні V k.
ЗАУВАЖЕННЯ
При побудові довгих шляхів розглядаються елементарні або прості довгі шляхи, довгі шляхи із заданим числом виконання циклів.
але. При кожній зміні ваги V i вершини це збільшення ваги необхідно передати вершинам результату X i, тобто потрібні спеціальні засоби, що відбивають факти отримання вершиною нової ваги і передачу його іншим вершинам. Як такий засіб використовується масив номерів вершин, що отримали нову вагу(при кожній зміні ваги номер вершини включається в цей масив, якщо його там не було, при передачі ваги виключається).
Структури даних
З самої структури алгоритму очевидно, що для його функціонування потрібні:
.Масив М - масив дуг-зв'язності в осередках з номерами i, j якого знаходитиметься вага відповідної дуги l ij.
. Xi - вершини графа.
. Vi - ваги відповідних вершин .
. G(Xi) - результат перерахованих вагів вершин Xi.
. tt - індекси верши при їхньому розрахунку.
Опис схеми алгоритму
Схема хвилевого алгоритму знаходження найдовшого шляху виконується
За допомогою 1. Розрахунку вагів вершин. Тобто для початку потрібно зробити розмітку усх вагів вершин. 2. Потім розмічаємо дуги по вагах, які були розраховані пунктом раніше.3 Накінець будуємо найдовші шляхи, якщо їх декілька. Тобто сума розміток дуг цих шляхів повинна співпасти із вагою останньої вершини.
Опис процедури CountTop2
Функція розраховує ваги усіх вершин шляхом надання їм нульового значення. Після чого вершина Хн заноситься у масив номерів вершин М. Масив перевіряється на пустоту, якщо умова відбувається, то процедура закінчується, інакше вершина, індекс якої був занесений у масив М, перевіряється на те, чи вага вершини буде меншо, ніж вага новообчисленої. Якщо умова правдива, то вершині надається більша вага, а її індекс заноситься до масиву М.Після цього перевіряється чи залишились не обраховані вершини у правдивому результаті повертаємось на етап перевірки порівняння вагів вершини даної, та ново обрахованої, якщо ж ні, то повертаємось на етап перевірки пустоти масиву індексів.
Опис процедури MarkArrow
Рухаємось у зворотному напрямку, тобто у масив М заносимо кількість входів G-1 . Потім робимо перевірку умови X i - X j = l ij. При правдивості умови переходимо до розмітки дуги lij. Потім перевіряєм маси в на порожність. При позитивному результаті закінчуємо процедуру. При негативному - повертаємось на етап перевірки умови X i - X j = l ij.
Опис процедури BuildWays
У масив М заносимо індекси усіх виділених вершин. Робимо перевірку на те чи сума усіх виділених дуг рівна вазі останньої вершини. Якщо так - будуємо шлях. Перевіряємо масив на порожність. Якщо умова правдива - закінчуємо процедуру, якщо ні переходимо на етап перевірки рівності суми шляхів дуг та віги останньої вершини.
Покроковий опис схеми алгоритмів
Мал. 2 Опис основної схеми Найдовший шлях
Блок №1
Функція розрахунку вагів вершин CountTop2
Блок №2
Функція розмітки дуг MarkArrow
Блок №3
Функція зібрання знайдених шляхів BuildWays
Мал 2.1Опис процедури CountTop2
Блок №1
Усім вершинам надається значення 0. В масив М записується індекс першої вершини.
Блок №2
Перевірка на порожність масиву М.
Блок №3
Вибір із масиву індекс вершини.
Блок №4
Перевірка на те чи вага вершини менша ніж нова вага вершини V(Gi)+1.
Блок №5
Запис у масив М індексу вершини що змінила свою вагу. Надання вазі вершини нове значення.
Блок №6
Перевірка на наявність вершин.
Мал. 2.2 опис процедури MarkArrow
Блок №1
Занесення у масив М кількість входів G-1
Блок №2
Перевырка умови X i - X j = l ij.
Блок №3
Виділяємо дугу lij
Блок №4
Перевірка на пустоту масиву М
Мал. 2.2 опис процедури BuildWays
Блок №1
Занесення у масив М кількість входів входів
Блок №2
Перевырка умови на те чи сума дуг дорівнює вазі останньої вершини.
Блок №3
Будуємо шлях Way
Блок №4
Перевірка на пустоту масиву М.
Контрольний приклад
Для детального опису дії хвилевого алгоритму пошуку довгого шляху скористаємося графом що задається таблиці зв'язності :
x1x2x3x4x5x6x7x8x13425x212x343x434x56x63x75x8
Таким чином, знаючи таблицю зв'язності можна побудувати граф для наочнішої ілюстрації прикладу :
Отже, на першому проході хвилевого алгоритму виконується пункт 1, тобто встановлюються значення вагів усіх вершин в нуль, і поміщає в масив М індекс початкової вершини, математично це можна записати так:
Крок № 1:
П. 1:
На другому проході, оскільки. М<>0, виконується пункт 2, з масиву М забирається перший елемент, цей індекс надається індексній змінній i
складається безліч результатів для вершини Х i, а потім обчислюються ваги суміжних вершин :
Крок № 2:
П. 2:
Як видно з приведених записів, в результаті цього проходу чотири вершини отримали нові ваги, і відповідно в масив М потрапили їх ?/p>