Rozproszony przegląd zupełny z obcięciami w drzewie poszukiwań dla problemów NP-trudnych

Abstract

Artykuł przedstawia zagadnienie znajdowania optimum problemów NP-trudnych w środowiskach rozproszonych złożonych z dużej liczby maszyn, połączonych w luźno powiązane podsieci. Całość omawiana jest na podstawie optymalizacyjnego, dyskretnego problemu plecakowego rozwiązywanego za pomocą przeglądu zupełnego zmodyfikowanego o dokonywanie obcięć w drzewie poszukiwań. Do scharakteryzowania problemu oraz przedstawienia algorytmu użyto modelu środowiska rozproszonego zaproponowanego przez autora.

Optimum finding of NP-hard problems in wide distributed environments algorithm is presented. As an main example 0-1 Knapsack Problem is solved using distributed complete search with branch-and-bound technique. Distributed environment model proposed by the author is used to describe the algorithm and efficiency estimations.