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

• Autorzy: Tusiewicz M.

Warianty tytułu

EN

Distributed complete search with branch--and-bound for NP-hard problems

• Języki publikacji: PL

Abstrakty

PL

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.

EN

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.

Słowa kluczowe

PL

przegląd zupełny; problemy NP-trudne; obliczenia rozproszone; obcięcia w drzewie poszukiwań

EN

complete search; NP-hard problems; distributed branch-and-bound

• Wydawca: Wydawnictwa AGH
• Czasopismo: Automatyka / Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie
• Rocznik: 2005
• Tom: T. 9, z. 1-2
• Strony: 245--253
• Opis fizyczny: Bibliogr. 13 poz., rys.

Twórcy

autor

Tusiewicz M.

• EAIiE, Katedra Informatyki, Akademia Górniczo-Hutnicza w Krakowie

Bibliografia

• [1] Lawler E.L., Wood D.E.: Branch and bound methods: A survey. Operations Research, (14), 1966, 670-719
• [2] Boyd S., Ghosh A., Magnani A.: Branch and Bound Methods. Notes for EE392o, Stanford University, 2003
• [3] Cormen, Leiserson, Rivest: Wprowadzenie do algorytmów. WNT, 2000
• [4] Gendron B., Crainic T.G.: Parallel branch-and-bound algorithms: Survey and synthesis. Technical Report 913, Centre de recherche sur les transports, Montreal (Canada), May 1993
• [5] Tusiewicz M.: Grafowy model środowiska systemu wieloagentowego. VI Międzynarodowe Warsztaty Doktoranckie OWD 2004, vol. 4
• [6] Drummond, Filho, Uchoa, Castro: Towards a Grid Enabled Branch-and-Bound Algorithm. International Symposium on Mathematical Programming (ISMP 2003), Copenhagen, Denmark
• [7] Clausen J.: Parallel Branch-and-Bound, Principles and Personal Experiments. Kluwer Academic Publishers, 1997, 239-267
• [8] Cung V. D., Dowaji S., Le Cun B., Mautor T., Roucairol C.: Parallel and Distributed Branch-and-Bound/A * Algorithms. (94/31). Laboratoire PRISM, Université de Versailles, 1994
• [9] Dowaji, Roucairol: Load balancing strategy and priority of tasks in distributed environments. Fourteenth Annual IEEE Conference, Intemational Phoenix Conference on Computers and Communications, p.15-22, Seottsdale, Arizona, USA, March 28-31, 1994
• [10] Tusiewicz M.: System wieloagentowy: teoria, projekt, implementacja oraz przykłady zastosowań. Kraków, Instytut Infomiatyki, Uniwersytet Jagielloński, 2003
• [11] Bruin, Kindervater, Trienekens: Asynchronous Parallel Branch-and-Bound and Anomalies. Erasmus University, Department of Computer Science, EUR-CS-95-05, Roterdam, Netherlands, 1995
• [12] Yahfoufi, Dowaji: A Self-Stabilizing Distributed Branch-and-Bound Algorithm. Proceedings of the 1996 IEEE 15th Annual International Phoenix Conference on Computers and Communications
• [13] www.grid.org