Methods_AP_PZ

стіни лівою рукою> означає одне й тільки одне: з кожної черговий i-ї точки лабіринту необхідно намагатися пройти спочатку вліво, потім - прямо,

вправо або назад і обов'язково в зазначеному порядку, а для цього й потрібний прапор напрямку прибуття.

Наприклад, якщо ми прийшли в i-ю точку зверху, те евристика лівої руки припускає наступну схему спроб відшукання i+1 точки шляху через лабіринт

В результаті евристика може бути реалізована, наприклад, у такий спосіб:

(i) увести напрямок і координати точки входу input H, s і k;

(ii)запам'ятати першу точку шляху через лабіринт i = 1, X(i) = k, Y(i) = s;

(iii)цикл пошуку

do

case H

1: <прибувзверху>

2: <прибувсправа>

3: <прибувзнизу>

4: <прибувзліва>

fi; inc(i)

until s=1 or s=m or k=1 or k=n od;

(iv) вивід маршруту:

print <маршрут через лабіринт>; for j=1 to i do writeln (X(j), Y(j)) od;

61

Залежно від напрямку прибуття перемикач H викликає один з операторів: <прибув зверху>, <прибув справа>, <прибув знизу> або <прибув зліва>.

Усі ці оператори виконують те саме: перевіряють за годинниковою стрілкою сусідні клітинки й залежно від того, яка з них першою виявиться прохідною, викликає відповідний оператор <йти вправо>, <йти вниз>, <йти вліво> або <йти вгору>

do <прибув зверху>:

if L(s, k + 1) = 1 then <йти вправо>; break fi

od

62

Lengthoptimalway = m*n; for (int i = 0 ; i < n*m ; i++ )

Way[i] = Optimalway[i] = -1; int *Dist;

Dist = new int[n*m];

for (int i = 0 ; i < n ; i++ ) for (int j = 0 ; j < m ; j++ )

Dist[i * m + j] = ( Maze[i][j] == 0 ? 0 : -1 ); Way[Lengthway++] = Current = Begin; while ( Lengthway > 0 ){

if(Current == End){

if (Lengthway < Lengthoptimalway){ for (int i = 0 ; i < Lengthway ; i++ )

Optimalway[i] = Way[i];

Lengthoptimalway = Lengthway;

}

if (Lengthway > 0) Way[--Lengthway] = -1; Current = Way[Lengthway-1];

}

else{

int Neighbor = -1;

if ((Current/m - 1) >= 0 && !Insert(Way, Current - m) && (Dist[Current - m] == 0 || Dist[Current - m] > Lengthway) && Dist[Current] < Lengthoptimalway)

Neighbor = Current - m; else

if ((Current%m - 1) >= 0 && !Insert(Way,Current - 1)&& (Dist[Current - 1]== 0 || Dist[Current - 1] > Lengthway) && Dist[Current] < Lengthoptimalway )

Neighbor = Current - 1; else

if ((Current%m + 1) < m && !Insert(Way,Current + 1) && (Dist[Current + 1]== 0 || Dist[Current + 1] > Lengthway) && Dist[Current] < Lengthoptimalway )

Neighbor = Current + 1;

64

else

if ((Current/m + 1) < n && !Insert(Way,Current + m) && (Dist[Current + m]== 0 || Dist[Current + m] > Lengthway) && Dist[Current] < Lengthoptimalway )

Neighbor = Current + m; if ( Neighbor != -1 ){

Way[Lengthway++] = Neighbor;

Dist[Neighbor] = Dist[Current] + 1;

Current = Neighbor;

}

else {

if (Lengthway > 0) Way[--Lengthway] = -1; Current = Way[Lengthway-1];

}

}

}

if ( Lengthoptimalway < n*m )

cout << endl << "Yes. Length way=" << Lengthoptimalway<< endl; else cout << endl << "No" << endl;

}

8.2 Завдання на практичну роботу

Реалізувати програмно всі завдання на практичну роботу.

1.Напишіть програму, що реалізовує версію, коли Х містить різне число значущих цифр у цілої і дробової частинах.

2.Для завдання 1 також визначте вплив похибок округлення (обмеженої довжини розрядної сітки ЕОМ) на результати роботи.

3.Для завдання 1 передбачте в алгоритмі заглушки для обліку та/або корекції цих похибок.

4.Розробити алгоритм і написати програму для завдання Аладдіна:

скільки цінних речей (заданих масою і ціною) може поміститися в рюкзак

(заданий об'єм) Аладдіна.

5. Розробити алгоритм та написати програму для розв’язання задачі

комівояжера з використанням евристики.

65

6. Реалізувати програмно пошук у лабіринті за допомогою евристики

лівої руки.

66

Практична робота №9

Алгоритми пошуку в структурованих множинах

9.1 Теоретичні відомості

Розглянемо два алгоритма пошуку в структурованих множинах (дерева пошуку), тобто пошук шляху до шуканих даних:

- пошук в глибину (швидкий, але не гарантує глобально оптимальне рішення);

- пошук в ширину (повільний, але гарантує глобально оптимальное рішення).

Повний перебір, або пошук у ширину

Алгоритм повного перебору на дереві (пошук у ширину на дереві)

1.Занести початкову вершину у список, який називається «відкритий».

2.Якщо список «відкритий» пустий, то видати сигнал про невдачу пошуку, інакше перейти до наступного кроку.

3.Узяти першу вершину (позначимо її n) зі списку «відкритий» та перенести її у список «закритий».

4.Розкрити вершину n. Якщо дочірніх вершин немає, перейти до кроку

2, інакше занести дочірні вершини у кінець списку «відкритий» та побудувати вказівники на вершину n.

5. Якщо яка-небудь з дочірніх вершин вершини n є цільовою, то видати розв’язок, інакше перейти до кроку 2.

Можна показати, що у методі повного перебору буде знайдено найкоротший шлях до цільової вершини, якщо шлях до цілі взагалі існує.

Вершини та вказівники, що побудовані в процесі перебору, утворюють піддерево усього неявно визначеного дерева простору станів. Таке піддерево називається деревом перебору.

67

Пошук у глибину

При пошуку у глибину у першу чергу розкриваються вершини, що були побудовані останніми. Глибина вершини n (позначається d(n)) визначається таким чином:

глибина кореневої вершини дорівнює 0,

d(nj) = d(ni)+1, де nj – вершина, що є дочірньою вершини ni.

Щоб уникнути розгортання вершин уздовж нескінченного шляху,

застосовується механізм повернення. Указується деяка гранична глибина,

нижче якої вершини не розкриваються. Розкриваються лише вершини, що мають глибину, яка не перевищує граничної.

Алгоритм перебору углиб на дереві

1.Занести початкову вершину у список, який називається «відкритий».

2.Якщо список «відкритий» пустий, то видати сигнал про невдачу пошуку, інакше перейти до наступного кроку.

3.Узяти першу вершину (позначимо її n) зі списку «відкритий» та перенести її у список «закритий».

4.Якщо глибина вершини n дорівнює граничній глибині, перейти до кроку 2, інакше – до наступного кроку.

5.Розкрити вершину n, побудувавши усі її дочірні вершини. Розмістити їх (у довільному порядку) на початку списку «відкритий» та побудувати вказівники від них до вершини n.

6.Якщо яка-небудь з дочірніх вершин вершини n є цільовою, то видати розв’язок, інакше перейти до кроку 2.

Приклад 9.1

Вивести послідовність вершин графа при пошуку в глубину.

Вхід. Перший рядок містить кількість вершин n в неорієнтованому зв'язному графі. Кожен з наступних рядків містить пару вершин, з'єднаних ребром графа. Вершини графа нумеруються з 1 до n.

Вихід. Послідовність вершин, відвідуваних при пошуку в глибину.

68

Першою відвідується вершина з номером 1, як показано в прикладі.

Нехай m – матрица суміжності графа (m[i][j] = 1, якщо існує ребро між вершинами i та j, і m[i][j] = 0 інакше), used – булевий масив, в якому used[i] = 1, якщо вершина i помічена (пройдена) і used[i] = 0 інакше.

#include <stdio.h> #include <memory.h> #define MAX 100

int m[MAX][MAX], used[MAX]; int i, n, a, b, ptr;

void dfs(int v)

{

int i; used[v] = 1;

printf("Vertex %d is visited\n",v); for (i = 1; i <= n; i++)

69

if (m[v][i] && !used[i]) dfs(i);

}

void main(void)

{

memset(m, 0, sizeof(m)); memset(used, 0, sizeof(used)); scanf("%d", &n);

while (scanf("%d %d", &a, &b) == 2) m[a][b] = m[b][a] = 1;

dfs(1);

}

9.2 Завдання на практичну роботу

Виконати завдання згідно вказівок викладача.

1. Знайти всі правильні послідовності з дужок заданої довжини.

Послідовність дужок є правильною тоді і тільки тоді, коли вона або порожня,

або складається з двох правильних послідовностей, або має вигляд

(правильна послідовність) методом пошуку вглиб.

2. На шахівниці n*n знайти всі способи розмістити n тур так, щоб жодна тура не погрожувала іншій. Тура погрожує всім фігурам, що стоять з нею на одній горизонталі чи вертикалі методом пошуку вглиб.

3. Та ж задача для ферзів. На відміну від тури, ферзь погрожує ще й по діагоналі методом пошуку вглиб.

4. Число 1 можна записати як суму n чисел вигляду 1/і, де і - натуральне число. Наприклад, для n=3 маємо 1=1/2+1/4+1/4. Знайти всі способи запису числа 1 для заданого n методом пошуку вглиб.

5.Виконати пошук в глибину за допомогою вікна у задачі пошуку виходу з лабіринту.

6.Виконати пошук в ширину за допомогою вікна та кільцевого стека у задачі пошуку виходу з лабіринту.

70