Р. Г. Стронгина. Ниж- ний Новгород: Изд-во Нижегородского университета, 2002, 217 с


Решение задачи о рюкзаке с использованием параллельных



Pdf көрінісі
бет17/151
Дата26.01.2022
өлшемі1,64 Mb.
#24342
түріСеминар
1   ...   13   14   15   16   17   18   19   20   ...   151
Байланысты:
Seminar 1

Решение задачи о рюкзаке с использованием параллельных 
вычислений 
Задача разбивается на подзадачи, каждая из которых заключается в 
построении 
ω-совместимого  множества,  содержащего  выделенное 
подмножество  элементов  множества  A.  Каждая  из  подзадач  может 
быть решена с помощью обхода поддерева в дереве поиска, такого, что 


18 
элементы,  сопоставленные  ребрам  пути,  ведущего  от  корня  дерева  к 
корню  поддерева,  составляют  выделенное  подмножество  элементов 
множества  А.  Таким  образом,  обход  всего  дерева  поиска  может  быть 
заменен обходами поддеревьев, каждый из которых может выполнять-
ся независимо от других. Это означает, возможность повышения ско-
рости  решения  задачи,  за  счет  того,  что  одновременно  (параллельно) 
может  выполняться  несколько  обходов.  С  помощью  параллельных 
вычислений обход дерева может выполняться одновременно несколь-
кими процессами, каждый из которых будет выполнять обход не всего 
дерева  целиком,  а  лишь  выделенного  ему  поддерева.  Таким  образом, 
для  обхода  дерева  поиска  можно  одновременно  запустить  несколько 
параллельных процессов. При этом число обменов сообщениями меж-
ду процессами будет невелико. Параллельные алгоритмы такого типа 
могут  быть  реализованы  на  системах  кластерного  типа,  дешевизна  и 
простота которых очень привлекательны, а эффективность такого под-
хода достаточно высока.  


Достарыңызбен бөлісу:
1   ...   13   14   15   16   17   18   19   20   ...   151




©emirsaba.org 2024
әкімшілігінің қараңыз

    Басты бет