Problem n-hetmanów



Interesującym przykładem
problemu kombinatorycznego jest zagadnienie N - hetmanów polegające na
ustawieniu na szachownicy N x N, N hetmanów
w taki sposób, żeby się wzajemnie nie atakowały.

Wydaje się, że problem
jest stosunkowo prosty, ale ... w istocie tak nie jest. Kto nie wierzy -
niech spróbuje rozwiązać go np. dla N=20 !

Sieci neuronowe można bardzo efektywnie wykorzystać do rozwiązania tego
problemu i problemów podobnych. Odpowiednio zdefiniowana sieć (w omawianym
wypadku jest to sieć dyskretna Hopfielda) w kolejnych etapach
proponuje przybliżone rozwiązania problemu, by po pewnym czasie osiągnąć
rozwiązanie końcowe.



Sieć poszukując rozwiązania często próbuje ustawić inną liczbę
hetmanów - np. N-1, ale jest za to karana, co w konsekwencji zmusza ją do
przekonfigurowania bieżącego
ustawienia w kierunku rozwiązania z N niekolidującymi hetmanami.
















W przypadku N=8 sieć w 1000 prób znajduje
rozwiązanie problemu średnio 998 razy !.











Oto przykład funkcjonowania sieci w przypadku standardowej szachownicy
8x8 czyli o 64-ech polach:







Etap
Zaproponowane rozwiązanie
Liczba kolizji
Liczba hetmanów

1

4
8

2

2
7

3

3
8

4

1
7





Wreszcie sieć uzyskuje rozwiązanie, spełniające wszystkie założenia, a więc 8
hetmanów ustawionych bez żadnej kolizji:













Jak sprawdzić poprawność rozwiązania ?





Po prostu: w każdym wierszu i w każdej kolumnie musi znajdować
się dokładnie jeden hetman, przy czym na żadnej przekątnej nie może być
ustawiony więcej niż jeden z nich.








Na koniec zapraszamy do obejrzenia w akcji sieci rozwiązującej
problem N-hetmanów w postaci miniprogramu
napisanego w języku Java.



[ Początek strony ]
[ MiNIWyklady ]



Wszystkie prawa zastrzeżone © 2000 Wydział Matematyki i Nauk Informacyjnych Politechniki Warszawskiej