Problem z 8-krotnym użyciem programowania dynamicznego

Question

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.

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?

Answer 1

optymalnym rozwiązaniem dla planszy 7x7 może nie optymalne, jak również (nawet niepoprawne) na 8x8.

Tak, masz rację. Ale nie jest to dobry sposób na rozdzielenie problemu. Zajrzyj do paper yi_H posted in his answer, twierdzenie 2.4, i spójrz na opis algorytmu. Dzielą rozwiązania na klasy równoważności zgodnie z zestawami zamkniętych linii (tj. Linii zagrożonych przez królowe). Twierdzenie 2.4 gwarantuje, że po rozwiązaniu problemu podrzędnego na konkretnym zbiorze zamkniętych linii, mogą rozwiązać resztę oddzielnie, a następnie połączyć wynik! Bardzo sprytny.

Answer 2

Wystarczy zaksięgowania oczywistą google obrażeń:

A dynamic programming solution to the n-queens problem

Uwaga: To jest nadal bardzo powolne dla dużych n'S, O (f (n) * 8^n), lepiej użyć innego algorytm:

A Polynomial Time Algorithm for the N-Queens Problem