ЛАБОРАТОРНА РОБОТА №1
з дисципліни:
“Комп'ютерні системи штучного інтелекту”
Тема : А-алгоритм, як евристичний метод пошукуВаріант №16
Мета роботи: Вивчити А-алгоритм та приклад його реалізації для гри у вісімки.
Відповіді на контрольні запитання:
Методологія пошуку в ширину - пошук в ширину обирає того кандидата, глибина якого найменша.
Принцип роботи А-алгоритму - Методологія пошуку полягає у послідовному спусканні по дереву від початкового стану до тих пір, поки не буде досягнутий деякий кінцевий стан. Якщо провести порівняння з пошуком в ширину, то можна помітити, що пошук вглибину обирає того кандидата, глибина якого найменша, а пошук за допомогою А-алгоритму для кожного кандидата визначає оцінку, і обирається кандидат з найкращою оцінкою. Граф, що відповідає заданому етапу пошуку, називається графом пошуку. Коли не вдається досягнути кінцевого стану у графі пошуку, виникає задача вибору деякого стану, до якого буде застосовуватись оператор з метою породження нових станів (“розкриття” станів).
Відмінності у методологія А-алгоритму та пошуку в ширину – Якщо провести порівняння з пошуком в ширину, то можна помітити, що пошук вглибину обирає того кандидата, глибина якого найменша, а пошук за допомогою А-алгоритму для кожного кандидата визначає оцінку, і обирається кандидат з найкращою оцінкою.
Принцип роботи А*-алгоритму – Алгоритм пошуку назвемо допустимим, якщо він завжди знаходить оптимальний розв’язок. Якщо граф пошуку скінчений, а евристичний член h(n) є нижньою оцінкою мінімальної вартості шляху між станом n і якимсь із кінцевих станів (h*(n)), то має місце застосування алгоритму пошуку типу А* і тоді забезпечується виконання наступних умов:
1. Виконується зупинка програми, що реалізує цей алгоритм;
2. Така зупинка дозволяє або знайти деякий шлях до кінцевого стану (якщо
такий шлях існує), або підтвердити факти відсутності шляху;
3. Коли шлях до кінцевого стану знайдений, то він має мінімальну вартість. У загальному випадку якщо не забезпечується наявність такої нижньої оцінки h(n), алгоритм має тип А ( а не А*) і виконуються тільки умови 1 та 2.
Інші приклади використання А*-алгоритму - Алгоритм пошуку А* знаходить оптимальний шлях між двома вершинами в графі. В залежності від функції вартості, яка задає кожному ребру його «вагу», оптимальність може означати найкоротший, найшвидший або навіть найпростіший шлях. Теоретично, алгоритм може розв'язувати всі задачі, які можна представити у вигляді задачі пошуку оптимального шляху на графі. Алгоритм A* використовується як для планування шляхів, так і в комп'ютерних іграх. Для планування шляхів, як евристична функція використовується лінійна відстань до цілі, оскільки згідно з нерівністю трикутника вона дає оптимальні оцінки. Також алгоритм А* використовується в іграх, в яких необхідно досягти наперед заданий стан, наприклад, в задачі про вісім ферзів, або в п'ятнашках. Евристикою може слугувати, наприклад, кількість невірно пересунутих камінців.
Текст програми:
Board.ts
import { cloneDeep } from 'lodash';
type historyItem = { heuristic: number, move: string };
export class Board {
public static readonly EMPTY_VALUE = -1;
private previousMoves: string[] = [];
private history: historyItem[] = [];
constructor(private state: Array
}
get depth(): number {
return this.history.length;
}
evaluate(): number {
let sum = 0;
let sort = 0;
for (let x = 0; x < this.state.length; x++) {
for (let y = 0; y < this.state[x].length; y++) {
const element = this.state[x][y];
sum += this.calculateDistance(x, y, element);
// sort += this.calculateSort(x, y, element);
}
}
if (isNaN(sum) || isNaN(sort))
throw new Error('kek');
return sum + 3 * sort;
}
equals(otherBoard: Board): boolean {
for (let x = 0; x < this.state.length; x++) {
for (let y = 0; y < this.state[x].length; y++) {
if (this.state[x][y] !== otherBoard.state[x][y]) {
return false;
}
}
}
return true;
}
printHistory(): void {
console.log(this.history.map(i => i.move).join(‘, ‘));
}
printMe(): void {
console.log(this.state);
}
getNextBoards(): Board[] {
const nextBoards: Board[] = [];
const [x, y] = this.getEmptyCoordinates();
if (y !== 0) {
const newBoard = new Board(cloneDeep(this.state));
newBoard.move('u');
nextBoards.push(newBoard);
}
if (y !== 2) {
const newBoard = new Board(cloneDeep(this.state));
newBoard.move('d');
nextBoards.push(newBoard);
}
if (x !== 0) {
const newBoard = new Board(cloneDeep(this.state));
newBoard.move('l');
nextBoards.push(newBoard);
}
if (x !== 2) {
const newBoard = new Board(cloneDeep(this.state));
newBoard.move('r');
nextBoards.push(newBoard);
}
return nextBoards;
}
move(direction: ('u' | 'r' | 'd' | 'l')): void {
this.history.push({
heuristic: this.evaluate(),
move: direction
});
const [x, y] = this.getEmptyCoordinates();
let newX: number;
let newY: number;
switch(direction) {
case 'u':
newX = x;
newY = y - 1;
break;
case 'r':
newX = x + 1;
newY = y;
break;
case 'd':
newX = x;
newY = y + 1;
break;
case 'l':
newX = x - 1;
newY = y;
break;
}
this.state[x][y] = this.state[newX][newY];
this.state[newX][newY] = Board.EMPTY_VALUE;
}
private getEmptyCoordinates(): number[] {
for (let x = 0; x < this.state.length; x++) {
for (let y = 0; y < this.state[x].length; y++) {
if (this.state[x][y] === Board.EMPTY_VALUE) {
return [x, y];
}
}
}
}
private calculateDistance(x: number, y: number, val: number) {
const goalX = val == Board.EMPTY_VALUE ? 2 : val % 3;
const goalY = val == Board.EMPTY_VALUE ? 2 : Math.ceil(val / 3);
return Math.abs(x - goalX) + Math.abs(y - goalY);
}
private calculateSort(x: number, y: number, value: number) {
if (value !== Board.EMPTY_VALUE) {
if (x === 1 && y === 1) {
return 1;
} else {
let xMove = 0;
if (y === 0 && x < 2) xMove = 1;
else if (y === 2 && x > 0) xMove = -1;
let yMove = 0;
if (x === 2 && y < 2) yMove = 1;
if (x === 0 && y > 0) yMove = -1;
const newX = x + xMove;
const newY = y + yMove;
const nextValue = this.state[newX][newY];
if (nextValue === value + 1 || (nextValue === Board.EMPTY_VALUE && value === 7)) {
return 0;
} else {
return 2;
}
}
} else {
return 0;
}
}
}
Main.ts
import { Board } from "./board";
const startState =
[
[2, 4, 3],
[7, Board.EMPTY_VALUE, 1],
[5, 8, 6]
];
const board = new Board(startState);
const queue = [board];
const passedBoards: Board[] = [board];
while (queue.length > 0) {
const currentBoard = queue.reverse().pop();
console.log('---------------------------------------');
console.log(current state ', currentBoard.toString());
console.log('score: ', currentBoard.evaluate());
if (currentBoard.evaluate() === 0) {
currentBoard.printHistory();
console.log('exit');
process.exit(1);
} else {
currentBoard.getNextBoards().forEach(board => {
if (!passedBoards.some(passedBoard => passedBoard.equals(board))) {
passedBoards.push(board);
board.printMe();
queue.push(board);
}
});
queue.sort((a, b) => a.evaluate() - b.evaluate());
queue[0].printHistory();
console.log(queue.length);
console.log(passedBoards.length);
}
}
Демонстрація роботи:
heuristic:5
depth:21
total:26
---
---
current state
1 8 3
2 6 0
7 5 4
current scores
heuristic:6
depth:20
total:26
---
---
current state
1 8 3
2 4 5
7 0 6
current scores
heuristic:6
depth:20
total:26
---
---
current state
0 5 2
1 6 4
7 8 3
current scores
heuristic:7
depth:19
total:26
---
---
current state
0 5 2
1 6 4
7 8 3
current scores
heuristic:7
depth:19
total:26
---
---
current state
6 7 3
4 5 8
1 0 2
current scores
heuristic:6
depth:20
total:26
---
---
current state
1 2 8
6 3 0
7 4 5
current scores
heuristic:6
depth:20
total:26
---
---
current state
6 2 4
7 5 3
0 1 8
current scores
heuristic:7
depth:19
total:26
---
---
current state
8 5 3
4 1 2
7 0 6
current scores
heuristic:6
depth:20
total:26
---
---
…
------------------
current state
2 7 1
4 5 6
0 8 3
current scores
heuristic:5
depth:21
total:26
---
---
current state
2 7 1
4 5 6
8 3 0
current scores
heuristic:5
depth:21
total:26
---
---
current state
1 2 3
4 5 0
8 6 7
current scores
heuristic:4
depth:22
total:26
---
---
current state
4 2 1
8 5 3
7 6 0
current scores
heuristic:5
depth:21
total:26
---
---
current state
1 2 3
4 5 0
7 8 6
current scores
heuristic:2
depth:24
total:26
---
---
current state
1 2 3
4 5 6
7 8 0
current scores
heuristic:0
depth:25
total:25
[[1, 2, 3], [4, 5, 6], [7, 8, 0]]
['l', 'u', 'r', 'r', 'd', 'l', 'l', 'u', 'r', 'r', 'u', 'l', 'd', 'r', 'd', 'l', 'l', 'u', 'r', 'r', 'u', 'l', 'd', 'r', 'd']
25
Висновок. На даній лабораторній роботі я вивчив А-алгоритм та реалізував його для гри у вісімки.