WOJSKOWA AKADEMIA TECHNICZNA

im. Jarosława Dąbrowskiego

Laboratorium

z przedmiotu SYSTEMY EKSPERCKIE

"Algorytm heurystyczny (najpierw najlepszy)"

Prowadzący zajęcia:

dr inż. Roman Wantoch-Rekowski

Wykonał:

Rafał Łańcucki, grupa I9B2S1

1. Treść zadania

Zaprojektować i zaimplementować algorytm heurystyczny (najpierw najlepszy) ustawiający na szachownicy n x n polowej n hetmanów tak aby nie atakowały się wzajemnie. W rozwiązaniu należy zaproponować własną modyfikację heurystycznej funkcji oceny wierzchołków. hetmany należy ustawiać w kolejnych wierszach począwszy od pierwszego.

2. Realizacja zadania

Algorytm zaimplementowany został w języku Java. Wynikiem jest wyświetlana w konsoli wiadomość zawierająca wszystkie wprowadzone dane wraz z otrzymanymi wynikami.

Wykorzystany algorytm heurystyczny działa wg. prostej zasady. Przy określaniu kolejnego wierzchołka liczy się wartość funkcji oceny ustalonej względem oddalenia od lewego szachownicy, a także wartością funkcji w poprzedniej linii. Gdy wartość funkcji oceny dla danego pola jest największa następuje przesunięcie hetmana na dane pole. Gdy kolejny hetman nie posiada już możliwości ruchu następuje powrót do poprzedniej linii na szachownicy.

Wtedy wybierane jest pole z kolejną najlepszą oceną.

Postać analityczna funkcji oceny:

$$f\left( x \right) = f\left( x - 1 \right)*\sum_{n}^{i = 0}{}\sum_{n}^{j = 0}{w_{\text{ij}}*\left| (i - n) \right|}$$

fx – funkcja oceny

i – wartości dla pól poziomych

j – wartości dla pól pionowych

n – ilość pól

w – wartość określająca czy pole w tym rzędzie jest zajęte

3. Wynik działania programu dla n=18

Wielkość szachownicy to: 18x18

Proponowane rozstawienia na szachownicy

pole pionowe pozycja: 0 pole poziome pozycja: 17

pole pionowe pozycja: 1 pole poziome pozycja: 15

pole pionowe pozycja: 2 pole poziome pozycja: 13

pole pionowe pozycja: 3 pole poziome pozycja: 16

pole pionowe pozycja: 4 pole poziome pozycja: 10

pole pionowe pozycja: 5 pole poziome pozycja: 3

pole pionowe pozycja: 6 pole poziome pozycja: 6

pole pionowe pozycja: 7 pole poziome pozycja: 2

pole pionowe pozycja: 8 pole poziome pozycja: 5

pole pionowe pozycja: 9 pole poziome pozycja: 1

pole pionowe pozycja: 10 pole poziome pozycja: 12

pole pionowe pozycja: 11 pole poziome pozycja: 0

pole pionowe pozycja: 12 pole poziome pozycja: 11

pole pionowe pozycja: 13 pole poziome pozycja: 14

pole pionowe pozycja: 14 pole poziome pozycja: 7

pole pionowe pozycja: 15 pole poziome pozycja: 9

pole pionowe pozycja: 16 pole poziome pozycja: 4

pole pionowe pozycja: 17 pole poziome pozycja: 8

Ilość kroków wykonana dla zadanej wielkości szachownicy: 41281

Dla zobrazowanego wyniku widać, że hetmani poustawiani są w dobrej kolejności i rzeczywiście ścieżki ich dróg się nie przecinają.