• Najnowsze pytania
  • Bez odpowiedzi
  • Zadaj pytanie
  • Kategorie
  • Tagi
  • Zdobyte punkty
  • Ekipa ninja
  • IRC
  • FAQ
  • Regulamin
  • Książki warte uwagi

Błędne wyświetlenie wyniku programu - problem szachowy

Fiszki IT
Fiszki IT
0 głosów
113 wizyt
pytanie zadane 6 kwietnia 2019 w C i C++ przez Alan Kruszyński Obywatel (1,410 p.)

Naskrobałem program mający rozwiązywać problem "N-Hetmanów" na szachownicy NxN. Chcę sprawdzać ilość możliwych unikalnych rozwiązań oraz wyświetlać pierwsze znalezione - w tym celu w funkcji sprawdzającej czy pole jest atakowane próbuję przechwycić pierwsze N pozycji hetmanów zapisując wiersze i kolumny do wektorów i wyświetlić je na końcu programu. Program nie wyświetla prawidłowo wszystkich hetmanów - 5 dobrze, 6 zle i kolejnych już wcale. W czym tkwi problem? Próbowałem modyfikować warunek sprawdzający pole, sprawdzałem poprawność funkcji wyświetlania i nie mam pomysłu.

1 odpowiedź

0 głosów
odpowiedź 6 kwietnia 2019 przez mrspock1 Mądrala (6,400 p.)
edycja 7 kwietnia 2019 przez mrspock1
Czy na pewno zrobiłeś to przez BFS? Na wszelki wypadek sprawdź na przykład tutaj pisałem dużo o zagadkach przeszukujących graf i masz tam pseudoprogram. Do BFS potrzebujesz struktury danych typu "kolejka" i algorytm jest iteracyjny.

http://informatyka-delphi.blogspot.com/2018/05/problem-naczyn-odmierzajacych.html

a tu jest aplikacja internetowa która to zadanie liczy (zagadka odmierzanie objętości)

http://zagadki-informatyczne.pl/

Ogólnie algorytmy przeszukujące graf są szybsze bo są rzędu wielomianowego podczas gdy brute force są rzędu wykładniczego.

Zauważ jednak że rozwiązanie tego zadania przez BFS zamiast brute force, przez proste dostosowanie kodu, niczego nie przyspieszy bo brute force w tym przypadku działa na zasadzie przeszukiwania drzewa a nie zwykłego grafu (każda kolejna badana pozycja jest inna). Nie mamy tego korzystnego przypadku jaki jest w grafach, że napotykamy tą samą pozycję w związku z tym już jej ponownie nie przeszukujemy bo wcześniej ją zaznaczyliśmy.

Prawdopodobnie dałoby się problem przedstawić jako graf (eliminacja powtarzania pozycji) jeśliby sprawdzać dla każdej pozycji czy nie istnieje już wcześniej badana pozycja symetryczna, czyli plansza obrócona o 90 stopni. Wtedy pozornie mielibyśmy trochę przyspieszenie, w tym przypadku niewielkie. Faktycznie jednak algorytm brute force też może mieć to zaimplementowane w taki sam sposób bo z warunków zadania wynika że brute force jest w stanie określić czy pozycja symetryczna już była wcześniej przeszukiwana.

Typowe zadania na algorytmy grafowe opierają się na tym, że nie da się ich zamienić na brute force bo nie wiemy czy dojście do pozycji symetrycznej na pewno musiało być badane wcześniej. Wybrany został zły problem do tego zadania bo to nie jest typowy problem grafowy, gdyż można go z taką samą efektywnością rozwiązać przez brute force.

Podobne pytania

0 głosów
1 odpowiedź 324 wizyt
pytanie zadane 4 kwietnia 2019 w C i C++ przez Alan Kruszyński Obywatel (1,410 p.)
0 głosów
1 odpowiedź 391 wizyt
pytanie zadane 23 stycznia 2019 w C i C++ przez Alan Kruszyński Obywatel (1,410 p.)
0 głosów
1 odpowiedź 104 wizyt
pytanie zadane 3 marca 2018 w C i C++ przez pewien_programista Obywatel (1,070 p.)
Porady nie od parady
Zadając pytanie postaraj się o szczegółowe opisanie problemu oraz udostępnienie wszystkich istotnych informacji (kody źródłowe, zrzuty ekranu itp.).Opisanie problemu

84,758 zapytań

133,559 odpowiedzi

295,986 komentarzy

56,012 pasjonatów

Motyw:

Akcja Pajacyk

Pajacyk od wielu lat dożywia dzieci. Pomóż klikając w zielony brzuszek na stronie. Dziękujemy! ♡

Oto dwie polecane książki warte uwagi. Pełną listę znajdziesz tutaj.

...