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