Tytuł artykułu
Autorzy
Identyfikatory
Warianty tytułu
Greddy algorithm in block world.
Konferencja
XI Krajowa Konferencja Automatyzacji Dyskretnych Procesów Przemysłowych, Zakopane 24-27.09.1998
Języki publikacji
Abstrakty
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.
Słowa kluczowe
Rocznik
Tom
Strony
261--267
Opis fizyczny
rys. Bibliogr. 5 poz.
Twórcy
autor
- Instytut Automatyki Politechniki Śląskiej 44-100 Gliwice ul. Akademicka 16, tel. 032/237-27-50, agaluszka@ia.polsl.gliwice.pl
Bibliografia
Typ dokumentu
Bibliografia
Identyfikator YADDA
bwmeta1.element.baztech-article-BSL2-0002-0027