Лекція.
Тема: Застосування графів при моделюванні.

Кількість годин: 2 години.





План
1.    Формування задачі ’лабіринт’.
2.    Математична модель.
3.    Розробка алгоритму.
4.    Програма на Pascal.
1.    Формулювання задачі.

Лабіринт ми можемо уявити собі як систему кімнат, деякі з них зв’язані коридором. Задача полягає в тому, щоб з початкової кімнати (від входу) знайти шлях в останню кімнату.
Лабіринт, складається з 12 кімнат, графічно він має такий вигляд:
Шуканий шлях може бути представлений послідовністю номерів кімнат, через які цей шлях проходить. В наведеному прикладі таким шляхом може служити послідовність: 1, 2, 6, 10, 12, 8.
При розв’язуванні задачі ми повинні користуватися тільки тими засобами, якими може користуватися мандрівник в лабіринті. Будемо вважати, що мандрівник знає номер тієї кімнати, в яку він ввійшов( нехай цей номер написаний на дверях кімнати чи на підлозі) та номер кімнати  в яку веде оглядовий коридор( нехай цей номер написаний над входом в коридор). Мандрівник може запам’ятати(відмітити) ті кімнати в яких він уже був, та в необхідності може пройти частину пройденого шляху в протилежному напрямку. При пошуку потрібного нам шляху потрібно дотримуватися таких правил:
    При русі вперед з тієї кімнати в якій находиться завжди потрібно йти в кімнату; в якій ще не був, якщо таких кімнат декілька то вибрати кімнату з найменшим номером;
    Зайшовши в потрібну кімнату, потрібно відмітити, що в ній побував;
    Якщо з даної кімнати, наприклад, 3 неможна пройти в кімнату, в якій ще не був, то потрібно вернутися, в попередню кімнату, наприклад, з кімнати 3 в кімнату 2.

Прослідкуємо, як буде вести себе мандрівник, керуючись цим правилом в наведеному лабіринті.
З кімнати 1 він перейде в кімнату 2. В кімнаті 2 з можливих варіантів 3, 4, 6 він вибере кімнату 3, так як у неї найменший номер. З кімнати 3 не можливо перейти в нову кімнату, так як це безвихідне положення. Тому мандрівник повернеться в кімнату 2. Тепер з можливих варіантів 4, 6 він вибере варіант з найменшим номером, тобто 4. З кімнати 4 він перейде в 5. Так як кімната 5 – це безвихідь, то він змушений буде повернутися в 4, а потім і в 2. Хід подальших дій мандрівника зрозумілий. Таким методом (спроб і помилок) він кінець кінцем відшукає шлях виходу з лабіринту: 1, 2, 6, 8, 10, 12.

2.    Математична модель.

Оскільки ми хочемо доручити розв’язок цієї задачі комп’ютеру, необхідно створити математичну модель розглядуваної ситуації і при розробці алгоритму розв’язку задачі організувати дію з елементами введеними нами структури даних.
Зразком лабіринту може бути графік вершини якого є кімнатами, а ребра – коридорами лабіринту. Зручним методом математичного представлення графа служить матриця суміжних його вершин. При заповненні матриці використовуються наступні правила:
    Вертикальні стовбці – номера кімнат: 1, 2, …, 12;
    Горизонтальні стрічки також позначають номера кімнат: 1, 2, …, 12;
    На перетині стовпчика і стрічки записується 1 , якщо між кімнатами є коридор, наприклад, на перетині стовпця 2 і стрічки 1 стоїть 1, так як кімнати1 і 2 з’єднані коридором.
    На перетині стрічки і стовпця ставиться 0, якщо
•    Між кімнатами немає з’єднуючого коридору, наприклад, на перетині стрічки 1 і стовпця 3 стоїть 0, так як кімнати 1, 3 не з’єднані коридором;
•    Перетин створений стрічкою і стовбцем з однаковим номером, наприклад, з кімнати 1 в кімнату 1 немає коридору, тому на перетині стрічки 1 і стовпця 1 ставимо 0.

З урахуванням приведених правил для графа, відповідного лабіринту нашого прикладу, матриця суміжності така:
1    2    3    4    5    6    7    8    9    10    11    12    Номер
1    0    1    0    0    0    0    0    0    0    0    0    0    кімнат
2    1    0    1    1    0    1    0    0    0    0    0    0   
3    0    1    0    0    0    0    0    0    0    0    0    0   
4    0    1    0    0    1    0    0    0    0    0    0    0   
5    0    0    0    1    0    0    0    0    0    0    0    0   
6    0    1    0    0    0    0    1    1    0    1    0    0   
7    0    0    0    0    0    1    0    0    0    0    0    0   
8    0    0    0    0    0    1    0    0    1    1    0    0   
9    0    0    0    0    0    0    0    1    0    0    0    0   
10    0    0    0    0    0    0    0    1    0    0    1    1   
11    0    0    0    0    0    0    0    0    0    1    0    0   
12    0    0    0    0    0    0    0    0    0    1    0    0   
Номер                                           
кімнат   

Матриця А

3.    Розробка алгоритму.

Тепер можна розпочати пошук на графік шляху, який з’єднує початкову вершину з номером 1, з кінцевою вершиною, що має номер <n>. При цьому ми будемо додержуватися наступних правил:
    Вершину, в якій ми побували (кімнату з якої ми вийшли) в своєму русі по графіку будемо рахувати відмічено;
    Для зберігання інформації про те які вершини відміченні, ведемо  в розгляд одновимірний масив М={mi} довжиною <n>;
    Вважаємо, що всі початкові  mi=0;
    Після відвідування і-тої вершини підкладемо mi=1;
    Номер наступної розглядуваної вершини(вершини, в якій ми знаходимося) позначимо через <k>;
    Для зберігання умови задачі вважаємо в той час, коли ми знаходимося в вершині з номером   <k>, доступні для використання являються тільки елементи <k> -ої стрічки матриці А (хоча вся вона знаходиться в пам’яті комп’ютера).
    Номера вершин, складаючи шуканий шлях будемо послідовно вносити в одновимірний масив P={Pi}довжиною <n>, всі елементи якого першочергово рівні 0.
    Кількість номерів, які уже внесені в масив P позначимо через <t>.
Застосувавши потрібним методом сформульовані правила по лабіринту можна дати таке першочерговий опис пошуку шляху в графі:
Зайти в початкову вершину відмітити її і занести в масив пройдених вершин.
Доки не досягнута остання вершина
Виконувати
Відшукати наступну вершину в яку можна перейти;
Якщо наступна вершина знайшлась
то перейти в наступну вершину відмітити її і внести в масив пройдених вершин
інакше повернутися до попередньої вершини.
Користуючись введеними позначеннями, не важко помітити, що словесний запис набору дій  з даними. При цьому будемо використовувати наступні заміни:
•    При пошуку наступну вершину будемо позначати через <j> номер розглядуваної вершини;
•    S означає:
S=0  – наступна вершина ще не знайдена;
S=1– наступна вершина вже знайдена.
•    В якості номера наступної вершини може бути взяте j, для якого Ак j=1 і m j=0.
Тепер запис алгоритму може виглядати так:
k:=1;  m k=1; t:=1; p t=1;
Доки k<n виконувати
j:=1; Si=0;
доки (S=0) i (j≤n) виконувати
Якщо (ак j=1) i (m j=0)
то S:=1
інакше j:=j+1

Якщо S=1
то k:=j;  m k=1; t:=t+1; p t=k;
інакше k:= p t ; t:=t-1; p t=0.
При записі цього алгоритму в вигляді програми на мові Паскаль добавити до нього ввід матриці суміжності і вивід на екран знайденого шляху – послідовність з t елементів масиву P.

4.    Програма на Паскаль

program labirint ;
type
Bin=-..1;
Dec=1..2;
Var
N, k, t, j, y, I, room: dec;
L: bin;
P: array[dec] of dec;
m: array[dec] of bin;
a: array[dec, dec] of bin;
begin
writeln (‘ введіть кількість вершин не більше 20:’);
readln(n);
for  i:=1 to n do
begin
m[i]:= ;    { m  - масив знайдених вершин}
p[i]:= ;    { p – масив вершин, які ведуть до виходу}
writeln(‘ введіть ’, i:2,’ стрічку матриці’);
for  i:=1 to n do real (a[i,j]);
end;
k:=1; t:=1; p[t]:=1; m[k]:=1;
while k<>n do
begin
i:=1;{j-ий номер наступної вибраної вершини}
l:= ;{ номер наступної розглядуваної вершини}
while (l=0) and (j<=n) do
begin { пошук наступних вершин}
if (a[k,j]=1) and (m[j]= )    then l:=1
else j:=j+1;
end;
if l=1 then
begin
k:=j; t:=t+1;
m[k]:=1;
p[t]:=k;
end
else
begin
k:=p[t];
t:=t-1;
p[t]:=;
end
end;
for  i:=1 to t do write(p[i]:5);{вивід вершин, яку потрібно пройти}
end.