WsdSI/LJK/za1
From WikiZMSI
Spis treści |
[edytuj]
Problem
Rozwiązywany problem to n-hetmanów, gdzie n jest parametrem programu. Określa on wielkość szachownicy jak i liczbę hetmanów.
[edytuj]
Algorytm
Należy zrealizować przeszukiwanie rozwiązania w grafie stosując algorytm przeszukiwania wszerz (BFS Breadth First Search) i/lub w głąb (DFS Depth First Search).
- Stan początkowy: pusta szachownica;
- Stan końcowy: takie ustawienie hetmanów na szachownicy, by nie występowały bicia;
- Funkcja generowania potomka:
- ustawienie hetmana w kolumnie i-tym i j-tym wierszu, przy czym nie należy wstawiać hetmana jeżeli wiersz lub kolumna jest już zajęta przez wcześniej wstawionego hetmana;
- uwzględniać fakt, że wstawianie może nastąpić tylko w pole, gdzie nie występują bicia na przekątnej z już wstawionymi hetmanami.
[edytuj]
Wynik
- Pierwsze znalezione rozwiązanie.
- Liczba wszystkich rozwiniętych (sprawdzonych) węzłów aż do rozwiązania.
[edytuj]
Punktacja
Program należy oddać na zajęciach laboratoryjnych/wymagana prezentacja działania programu. Za program można zdobyć max 1 pkt.
- [ 0 , 0.75 ) za BFS
- [ 0 , 1 ) za BFS i DFS
[edytuj]
Termin oddania programu
- Grupa 20A ---6 kwietnia 2019
- Grupa 20B --- 31 marca 2019
- Grupa powt. --- 31 marca 2019
