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

• Autorzy: Gałuszka A.

Warianty tytułu

EN

Greddy algorithm in block world.

• Konferencja: XI Krajowa Konferencja Automatyzacji Dyskretnych Procesów Przemysłowych, Zakopane 24-27.09.1998
• Języki publikacji: PL

Abstrakty

PL

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.

EN

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

PL

świat klocków; problemy NP-złożone; algorytmy zachłanne; system STRIPS

• Wydawca: Wydawnictwo Politechniki Śląskiej
• Czasopismo: Zeszyty Naukowe. Automatyka / Politechnika Śląska
• Rocznik: 1998
• Tom: z. 125
• Strony: 261--267
• Opis fizyczny: rys. Bibliogr. 5 poz.

Twórcy

autor

Gałuszka A.

• Instytut Automatyki Politechniki Śląskiej 44-100 Gliwice ul. Akademicka 16, tel. [phone],