Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Використання евристичної функції для створення гри.
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
Не вказано
Кафедра:
Електронні обчислювальні машини
Інформація про роботу
Рік:
2007
Тип роботи:
Лабораторна робота
Предмет:
Системи штучного інтелекту
Група:
КСМ-5
Частина тексту файла (без зображень, графіків і формул):
Міністерство освіти та науки України
Національний університет „Львівська політехніка”
Кафедра ЕОМ
Звіт
з лабораторної роботи № 2
З дисципліни: „Системи штучного інтелекту”
На тему: „ Використання евристичної функції для створення гри ”
Виконав:
ст. гр. КСМ-5
Львів 2007
Мета роботи: Cтворення зразку евристичної функції, яка описує стан укладанки, що полягає у складанні в зростаючому порядку цифр від 1 до 8. Створений алгоритм має за мету розв’язання гри при мінімально можливій кількості кроків, а також розпізнавання станів, у яких гра не має розв’язку. Початковий стан гри встановлюється випадковим чином. Головними елементами евристичної функції є складові підрахунку відстаней вибраних елементів від їх попереднього місця.
Теоретичні відомості
Алгоритм гри є простим і базується на 3 засадах:
Підраховане значення евристичної функції відбиває єдиний можливий крок, що залежить від розташування нульового елементу і для якого значення функції є мінімальним (нескінченне від біжучого значення функції)
Не варто повторювати попередній крок, якщо він призводить до заплутування алгоритму, і відповідно, не скорочує кількість кроків
Нульове значення евристичної функції означає, що даний стан гри є кінцевим станом (елементи є укладеними або їх укладання є неможливим)
Стан гри описаний N*N-елементною таблицею Tab[*] цілих цифр в полях пронумерованих від 0 до N*N
Приймемо наступну послідовність алгоритму:
Етап 1
Початковою метою гри є уставляння одиниці на першому місці (в таблиці це поле з номером 0). Відповідно, цей порядок повинен мати найбільший приоритет, тобто йому має відповідати складова, що має найбільшу вагу в моделі функції. Ось ця складова:
wartosc+=1000000*abs(miejsce[1]%3-szukana%3);
//розглядання нормованої метрики по горизонталі
wartosc+=1000000*abs(miejsce[1]/3-szukana/3);
//розглядання нормованої метрики по вертикалі
Де значення змінної szukana в цей момент дорівнює 0.
Найбільша вага цієї складової у зразку евристичної функції доводить, що цей елемент ніколи не буде пересунуто зі свого місця.
На цьому етапі гри нульове поле прагне до нульового місця таблиці елементів
Етап 2
Наступний крок полягає у встановленні 2 і 3 на свої місця. Очевидно евристична функція намагається встановити їх відповідно стану:
1
_
2
х
x
3
х
x
х
Де х означає поле замін перед випадковим укладанням залишкових цифр 4,5,6,7,8
Цей етап описує наступний фрагмент коду:
Елемент 2 має більшу вагу ніж 3, і його варто поставити на власну позицію першим. На цьому етапі нульове поле прагне до першого елементу таблиці.
тобто значення змінної szukana буде зараз 1.
Зауважимо, що у момент гри представлений вище, не має можливості виконання іншого кроку, як відправлення 2 і 3 на свої місця. Це виникає з початкових умов (не можна повернутись) і окрім цього алгоритм забезпечує, що одиниця лишається на свому місці.
Очевидно, що потрібно забезпечити перед досягненням нуля евристичною функцією (що призвело би до закінчення алгоритму на цьому етапі) привласнити їй числове значення
if (Tab[0]==1 && Tab[2]==2 && Tab[5]==3) wartosc+=30;
Після встановлення 2 і 3 на власні місця мусимо скорегувати значення евристичної функції у 110000, що реалізує наступний код:
if (Tab[0]==1 && Tab[1]==2 && Tab[2]==3)
//після встановлення 2 i 3 на місця
{
szukana=3;
wartosc-=110000;
}
Алгоритм забезпечує пересування нульового елементу в таблиці до поля з номером 3, що є необхідним при переході до наступного етапу гри.
Етап 3
На цьому етапі, що є подібним до етапу 2, займемося 4 і 7. Хочемо прийти до наступного стану гри:
1
2
3
_
x
x
4
7
x
Де х означає поле, що можна заміняти перед випадковим укладанням залишених цифр 5, 6, 8.
Елемент 4 має вищу вагу ніж 7, тому його слід поставити на власну позицію першим. На цьому етапі нульове поле прагне до третього елементу таблиці (встановлений в кінці етапу 2).
Тобто значення змінної зараз буде 3.
Подібно, як у етапі 2 зауважимо, що у момент гри, представлений вище, алгоритм не має можливості виконання іншого кроку, як встановлення 4 і 7 на власні місця (pomimo że zwiększa to wartość funkcji heurystycznej w stosunku do wartości bieżącej). Це виникає з початкових умов (не можна повернутись) разом з алгоритмом, що забезпечує, що елементи 1,2,3 лишаються на своїх місцях.
Очевидно, що потрібно забезпечити перед досягненням нуля евристичною функцією (що призвело би до закінчення алгоритму на цьому етапі) впровадити числове значення
Нульовий елемент на потребу етапу 4 буде зараз розташований у 8 полі таблиці.
Етап 4
Є кінцевим етапом. Він однозначно прагне до встановлення нульового елементу в поле 8, за умови, що принаймі 5 або 6 або 8 знаходяться на свому місці ( якщо це не так, тоді функція приймає числове значення 10, що означає бажаний стан):
Якщо це відбулося, можна вважати, що гра укладена чи не вдається до укладання. Очевидно, в обох випадках, значення функції буде дорівнювати 0. Poprawne Правильне укладання описується перед визначенням послідовності елементів в таблиці Tab, в іншому випадку гра не вдається до укладання.
Також існують стани, в яких значення функції потрібно змодифікувати, щоб алгоритм почав робити виправлення, у відповідності до етапу 1.
Фрагмент коду програми:
void FindMinWay(int level)
{
int other,prevP;
for(int i=0;i<size;i++)
{
int j=0; other=1;
while ((j<level)&& other)
{
if(matTmp[j]==i) other=0;
j++;
};
if (other)
{
matTmp[level]=i;
if (level==0){LengthTmp=0;}
else
{
prevP=matTmp[level-1];
LengthTmp=LengthTmp+mat[prevP][i];
};
level++;
if(level<size)FindMinWay(level);
if ((level==size)&&(LengthTmp<=LengthMin))
{
if(LengthTmp==LengthMin) {amount++;}
else {LengthMin= LengthTmp;amount=1;};
for(int k=0;k<size;k++)matMin[amount][k]=matTmp[k];
};
if (level==size)
{
printf( "Pointers:");
for (int z = 0; z < size; z++) printf( "%d ",matTmp[z]);
printf("TmpLength is %d\n",LengthTmp);
} ;
level--;
if (level!=0)LengthTmp=LengthTmp-mat[prevP][i];
};
};
}
Висновок:
в ході даної лабораторної роботи я дослідив використання евристичних алгоритмів для створення ігор.
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора