Jestem dość zdezorientowany z pomysłem zastosowania problemu z 8-krotnym błędem przy użyciu programowania dynamicznego. Wydaje się, że nie jest to możliwe z jednego końca, ponieważ dla DP "jeśli problem został podzielony na serię podproblemów i znaleziono optymalne rozwiązanie dla każdego podproblemu, to uzyskane rozwiązanie byłoby zrealizowane poprzez rozwiązanie tych podproblemów. nie ma takiej struktury, której nie można rozwiązać za pomocą programowania dynamicznego "(Reference). Biorąc to pod uwagę, optymalne rozwiązanie dla płyty 7x7 może nie być optymalne (nawet niepoprawne) dla 8x8. Rezultat problemu może więc nie zostać zrealizowany poprzez optymalne rozwiązanie problemu podrzędnego.Problem z 8-krotnym użyciem programowania dynamicznego
Z drugiej strony, DP jest optymalizacją dla problemów z cofaniem ... jeżeli tak, to problem z 8-rosemetowym może zostać rozwiązany przez cofnięcie ... czy to znaczy, że przechowywanie tylko ślepych uliczek może przekształcić rozwiązanie do śledzenia wstecznego w DP? Jeśli tak, to może 2,1 nie jest możliwe dla rodzica 1,1, ale może być wykonalne dla 1,2.
Aktualizacja
ktoś ma pomysł, czy 8-królowa lub problemu n-królowa może być rozwiązany za pomocą programowania dynamicznego? Jeśli tak, to jakie będą komentarze na temat powyższych uwag?
Na czym polega pytanie? – Amy
@lnuyasha zaktualizował pytanie. – mqpasta
@mqpasta, wyszukiwanie w Internecie dla "8 dynamicznych programów queens" generuje sporą liczbę trafień. Czy przeczytałeś któreś z tych źródeł, aby zobaczyć, jak zdefiniowano DP _ dla tego problemu? I nie zgadzasz się? Masz rację, że 7-elementowe rozwiązanie nie jest składnikiem rozwiązania z 8-krotnym królem, więc twoje pytanie jest bardzo interesujące. –