Wyniki wyszukiwania - BazTech

Ograniczanie wyników

Znaleziono wyników: 1

Liczba wyników na stronie

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: problemy NP-złożone

Sortuj według:

Ogranicz wyniki do:

Zachłanny algorytm planowania w 'świecie klocków'.

Gałuszka A.

Zeszyty Naukowe. Automatyka / Politechnika Śląska

1998

z. 125

261-267

Niniejszy artykuł analizuje zadania ze 'świata klocków', w których sytuację docelową stanowi opis wielu wież klocków. W ogólnym przypadku generacja optymalnego planu rozwiązującego takie zadanie jest problemem NP złożonym. Graf ograniczeń kolejnościowych redukuje przestrzeń stanów zadania. Artykuł pokazuje jak taki graf można zbudowć. Graf ten umożliwia zaimplementowanie algorytmu zachłannego, który generuje rozwiązanie. Algorytm ten jest wielmianowo złożony w czasie. Omówione zostały także warunki konieczne i wystarczające optymalności algorytmu zachłannego.

In this paper block world instance where the goal state is a complete description of a set of stacks is presented. In general to generate an optimal plan for such problem is NP-hard. Precedence constraints graph reduces block world states space. It is shown how this graph this graph can be built. Now it is possible to implement greedy algorithm which generates solution. This algorithms is polynomial-time complete. Necessary and sufficient of greedy algorithm optimality are also discussed.