Зависимость целевой функции от нескольких переменных в задаче размещения объектов и ее решение методом структурно-алфавитного поиска
Проведено аналіз задачі розміщення різногабаритних об'єктів. Показано, що цільова функція в ній залежить від кількох змінних, якими є комбінаторні конфігурації різних типів. За цією ознакою вона поділяється на кілька підзадач, тому для її розв язання розроблено самоналагоджувальний алгоритм. Ме...
Збережено в:
| Опубліковано в: : | Кибернетика и системный анализ |
|---|---|
| Дата: | 2013 |
| Автор: | |
| Формат: | Стаття |
| Мова: | Російська |
| Опубліковано: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2013
|
| Теми: | |
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/86219 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Зависимость целевой функции от нескольких переменных в задаче размещения объектов и ее решение методом структурно-алфавитного поиска / Н.К. Тимофеева // Кибернетика и системный анализ. — 2013. — Т. 49, № 2. — С. 106-114. — Бібліогр.: 44 назв. — рос. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1860078707968835584 |
|---|---|
| author | Тимофеева, Н.К. |
| author_facet | Тимофеева, Н.К. |
| citation_txt | Зависимость целевой функции от нескольких переменных в задаче размещения объектов и ее решение методом структурно-алфавитного поиска / Н.К. Тимофеева // Кибернетика и системный анализ. — 2013. — Т. 49, № 2. — С. 106-114. — Бібліогр.: 44 назв. — рос. |
| collection | DSpace DC |
| container_title | Кибернетика и системный анализ |
| description | Проведено аналіз задачі розміщення різногабаритних об'єктів. Показано, що цільова функція в ній залежить від кількох змінних, якими є комбінаторні конфігурації різних типів. За цією ознакою вона поділяється на кілька підзадач, тому для її розв язання розроблено самоналагоджувальний алгоритм. Методом структурно-алфавітного пошуку, який грунтується на відомому розв язному випадку, розв'язується задача розміщення одногабаритних об'єктів
The problem of location of various-sized objects is analyzed. The objective function is shown to depend on several variables, which are various combinatorial configurations. On this principle, it is divided into several subproblems; therefore, a self-adjusting algorithm is developed to solve it. A location problem for objects of the same size is solved by the structurally-alphabetical search, which is based on the known solvable case.
|
| first_indexed | 2025-12-07T17:15:06Z |
| format | Article |
| fulltext |
ÓÄÊ 519.816
Í.Ê. ÒÈÌÎÔÅÅÂÀ
ÇÀÂÈÑÈÌÎÑÒÜ ÖÅËÅÂÎÉ ÔÓÍÊÖÈÈ ÎÒ ÍÅÑÊÎËÜÊÈÕ
ÏÅÐÅÌÅÍÍÛÕ Â ÇÀÄÀ×Å ÐÀÇÌÅÙÅÍÈß ÎÁÚÅÊÒÎÂ
È ÅÅ ÐÅØÅÍÈÅ ÌÅÒÎÄÎÌ ÑÒÐÓÊÒÓÐÍÎ-ÀËÔÀÂÈÒÍÎÃÎ ÏÎÈÑÊÀ
Êëþ÷åâûå ñëîâà: êîìáèíàòîðíàÿ îïòèìèçàöèÿ, ðàçìåùåíèå ðàçíîãàáàðèò-
íûõ îáúåêòîâ, êîìáèíàòîðíàÿ êîíôèãóðàöèÿ, öåëåâàÿ ôóíêöèÿ, ìåòîä ñòðóê-
òóðíî-àëôàâèòíîãî ïîèñêà, ïåðåñòàíîâêà, ðàçáèåíèå ìíîæåñòâà.
ÂÂÅÄÅÍÈÅ
Çàäà÷è ðàçìåùåíèÿ îáúåêòîâ âîçíèêàþò â ðàçëè÷íûõ îòðàñëÿõ: êîíñòðóêòîð-
ñêîì ïðîåêòèðîâàíèè âû÷èñëèòåëüíîé àïïàðàòóðû, îïòèìàëüíîì ðàñêðîå, ìî-
äåëèðîâàíèè íåêîòîðûõ õèìè÷åñêèõ è ôèçè÷åñêèõ ïðîöåññîâ è ò. ä. [1–37].
Ýòè çàäà÷è ðàçäåëÿþòñÿ ïî ãàáàðèòàì îáúåêòîâ, ñïîñîáó çàäàíèÿ êîîðäèíàò íà
ïîâåðõíîñòè äëÿ èõ ðàçìåùåíèÿ, à òàêæå ïî ñòðóêòóðå âõîäíûõ äàííûõ.
Êàæäàÿ òàêàÿ çàäà÷à òðåáóåò ñïåöèàëüíûõ ïîäõîäîâ äëÿ ñâîåãî ðåøåíèÿ,
â ÷àñòíîñòè, ïðèìåíÿþòñÿ ìåòîäû ëèíåéíîãî ïðîãðàììèðîâàíèÿ [1, 32], îïòè-
ìàëüíîãî ðàñêðîÿ ìàòåðèàëîâ è ïëîòíîãî ðàçìåùåíèÿ [6–10], ìåòîäû, îñíîâàí-
íûå íà äèñêðåòíûõ ìîäåëÿõ ðàçìåùåíèÿ [2–5, 11–17, 19–28, 30, 31], à òàêæå
àëãîðèòìû, èñïîëüçóþùèå ñèëîâûå ôóíêöèè [12, 18]. Â ðàáîòàõ [2, 3, 12] çà-
äà÷à ðàçìåùåíèÿ ñâåäåíà ê êëàññè÷åñêîé çàäà÷å î íàçíà÷åíèÿõ.
Îïèñàííûå ïîäõîäû ðàçðàáàòûâàëèñü â çàâèñèìîñòè îò ïîäêëàññà ðåøàåìûõ
çàäà÷: äëÿ îäíèõ ýôôåêòèâíû ìåòîäû ïëîòíîãî ðàçìåùåíèÿ, äëÿ äðóãèõ —
äèñêðåòíûå ìîäåëè. Çíà÷èòåëüíàÿ ÷àñòü àëãîðèòìîâ ðàçìåùåíèÿ ðàçíîãàáàðèòíûõ
ìîäóëåé, êîòîðûå îðèåíòèðîâàíû íà êîíñòðóêòîðñêîå ïðîåêòèðîâàíèå óçëîâ ÝÂÌ,
ðàáîòàåò ïðèìåðíî ïî îäíîé ñõåìå: ñíà÷àëà ìîíòàæíîå ïîëå ðàçáèâàþò íà
ïðÿìîóãîëüíûå ïîçèöèè ðàçíîé øèðèíû è ôèêñèðîâàííîé âûñîòû, ïîòîì ìîäóëè
óïàêîâûâàþò â çàäàííûå ïîçèöèè øèðèíîé a, è âûñîòîé, êðàòíîé a [13–17, 20, 21,
26]. Â íåêîòîðûõ àëãîðèòìàõ ìîíòàæíîå ïîëå ðàçáèâàþò íà ïðÿìîóãîëüíûå
ïîçèöèè, â êîòîðûõ ìîæåò ðàçìåñòèòüñÿ ìîäóëü íàèáîëüøåãî ðàçìåðà
ñ ïîñëåäóþùåé óïàêîâêîé â íèõ ìîäóëåé ìåíüøèõ ðàçìåðîâ [24].
 [23] ðàçìåùåíèå ðàçíîãàáàðèòíûõ ìîäóëåé ñâåäåíî ê ðàçìåùåíèþ îäíîãàáàðèòíûõ.
Äëÿ ýòîãî íà k-é èòåðàöèè ýëåìåíòû êîìïîíóþòñÿ â îäíîãàáàðèòíûå ìîäóëè ñ ïîñëåäó-
þùèì èõ ðàçìåùåíèåì èòåðàöèîííûì àëãîðèòìîì â äèíàìè÷åñêè ïåðåñòðîåííûå
ïîçèöèè íà ïîâåðõíîñòè ïëàòû äî òåõ ïîð, ïîêà íå áóäåò ðàçìåùåí ìîäóëü ñ íàèìåíüøèìè
ãàáàðèòàìè. Â [28–31] ïî îïðåäåëåííûì ïðàâèëàì îáúåêòû îáúåäèíÿþòñÿ â êëàñòåðû
(ôðàãìåíòû) èëè èõ ìíîæåñòâî ðàçáèâàåòñÿ íà áëîêè (ãðóïïû). Ñ èñïîëüçîâàíèåì ìåòîäîâ
ïëîòíîãî ðàçìåùåíèÿ èëè äðóãèõ èçâåñòíûõ ìåòîäîâ íà ïîâåðõíîñòè ïîñëåäîâàòåëüíî
ðàçìåùàþòñÿ êàê ôðàãìåíòû, òàê è âîøåäøèå â íèõ ýëåìåíòû.
 [37] îïèñàíà çàäà÷à ñîçäàíèÿ îïòèìàëüíîé êëàâèàòóðû, â êîòîðîé áóêâû ïî
îïðåäåëåííûì ïðèçíàêàì îáúåäèíåíû â êëàñòåðû ñ ïîñëåäóþùèì èõ ðàçìåùåíèåì
íà íåé. Îäíàêî íè â îäíîé èç óïîìÿíóòûõ ðàáîò íå ïðîàíàëèçèðîâàíû çàäà÷è
ðàçìåùåíèÿ îáúåêòîâ ñ âûÿâëåíèåì ïðèçíàêîâ, ïî êîòîðûì äëÿ èõ ðåøåíèÿ
âûáèðàåòñÿ òîò èëè èíîé ïîäõîä. Íåêîòîðûå àâòîðû çàäà÷ó ðàçìåùåíèÿ íàçûâàþò
ïîêðûòèåì èëè ðàçáèåíèåì, ÷àñòî ïîëàãàÿ, ÷òî àðãóìåíòîì öåëåâîé ôóíêöèè â ýòèõ
çàäà÷àõ ÿâëÿåòñÿ ïåðåñòàíîâêà.
 íàñòîÿùåé ñòàòüå ñäåëàíà ïîïûòêà âûÿâèòü îáùèå ïðèçíàêè, ïðèñóùèå
îïèñàííûì çàäà÷àì. Ïîêàçàíî, ÷òî öåëåâàÿ ôóíêöèÿ â çàäà÷å ðàçìåùåíèÿ îáúåê-
106 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2013, ¹ 2
� Í.Ê. Òèìîôååâà, 2013
òîâ ïðîèçâîëüíîé ôîðìû çàâèñèò îò íåñêîëüêèõ ïåðåìåííûõ (êîìáèíàòîðíûõ êîí-
ôèãóðàöèé ðàçëè÷íûõ òèïîâ), âñëåäñòâèå ÷åãî îíà åñòåñòâåííî ðàçäåëÿåòñÿ íà ïîä-
çàäà÷è, êîòîðûå ðåøàþòñÿ íåçàâèñèìûìè àëãîðèòìàìè â èòåðàöèîííîì ðåæèìå.
ÌÀÒÅÌÀÒÈ×ÅÑÊÀß ÏÎÑÒÀÍÎÂÊÀ ÇÀÄÀ×È ÐÀÇÌÅÙÅÍÈß ÎÁÚÅÊÒÎÂ
 ÐÀÌÊÀÕ ÒÅÎÐÈÈ ÊÎÌÁÈÍÀÒÎÐÍÎÉ ÎÏÒÈÌÈÇÀÖÈÈ
Çàäà÷à ðàçìåùåíèÿ îáúåêòîâ ôîðìóëèðóåòñÿ ñëåäóþùèì îáðàçîì: ìíîæåñòâî
îäíîãàáàðèòíûõ èëè ïðîèçâîëüíîé ôîðìû îáúåêòîâ íåîáõîäèìî ðàçìåñòèòü
â îáëàñòè ðàçìåùåíèÿ òàê, ÷òîáû ñìîäåëèðîâàííàÿ ïî çàäàííûì êðèòåðèÿì
öåëåâàÿ ôóíêöèÿ ïðèíèìàëà îïòèìàëüíîå çíà÷åíèå, à ðàññòîÿíèå ìåæäó îáú-
åêòàìè ðàâíÿëîñü îïðåäåëåííîé âåëè÷èíå.
Ïî ãàáàðèòàì îáúåêòîâ, ñòðóêòóðå ïîñàäî÷íûõ ìåñò, ãäå îíè ðàçìåùàþòñÿ,
à òàêæå ïî ñòðóêòóðå âõîäíûõ äàííûõ çàäà÷ó ðàçìåùåíèÿ ðàçäåëÿþò íà ïîäêëàñ-
ñû, äëÿ êîòîðûõ çàäàíû:
— óñòàíîâî÷íûå ïîçèöèè, â êîòîðûõ ðàçìåùàþòñÿ îäíîãàáàðèòíûå îáúåêòû;
— óñòàíîâî÷íûå ïîçèöèè, â êîòîðûõ ðàçìåùàþòñÿ êàê îäíîãàáàðèòíûå, òàê
è ðàçíîãàáàðèòíûå îáúåêòû;
— îáëàñòü, â êîòîðîé ðàçìåùàþòñÿ îáúåêòû ïðîèçâîëüíîé ôîðìû áåç óñòà-
íîâî÷íûõ ïîçèöèé;
— ñâÿçè ìåæäó îáúåêòàìè, åñëè îíè ñóùåñòâóþò.
Ñàìàÿ ïðîñòàÿ èç ýòèõ çàäà÷ — ðàçìåùåíèå îäíîãàáàðèòíûõ îáúåêòîâ â çà-
äàííûå óñòàíîâî÷íûå ïîçèöèè, àðãóìåíòîì öåëåâîé ôóíêöèè â êîòîðîé ÿâëÿåòñÿ
ïåðåñòàíîâêà.
Äàëåå ðàññìîòðèì çàäà÷ó ðàçìåùåíèÿ, â êîòîðîé ìîæíî àïïðîêñèìèðîâàòü
ïðÿìîóãîëüíèêàìè îáúåêòû ñ ñóùåñòâóþùèìè ìåæäó íèìè ñâÿçÿìè. Äëÿ óïðî-
ùåíèÿ åå ðåøåíèÿ ïðåäñòàâèì îáúåêòû ãåîìåòðè÷åñêèìè òî÷êàìè.
Çàäà÷à ðàçìåùåíèÿ çàäàåòñÿ äâóìÿ ìíîæåñòâàìè: A è B. Ýëåìåíòàì a Al � ,
l n�{ }1, ,� , ñîîòâåòñòâóþò îáúåêòû, êîòîðûå íåîáõîäèìî ðàçìåñòèòü â çàäàííîé
îáëàñòè. Ýëåìåíòàì b Bt � , t n�{ }1, , ~
� , ñîîòâåòñòâóþò óñòàíîâî÷íûå ïîçèöèè
äëÿ ðàçìåùåíèÿ îáúåêòîâ èëè ìíîæåñòâî òî÷åê ãåîìåòðè÷åñêîé îáëàñòè ðàçìå-
ùåíèÿ, ãäå n — êîëè÷åñòâî ýëåìåíòîâ ìíîæåñòâà A, ~n — êîëè÷åñòâî ýëåìåíòîâ
ìíîæåñòâà B. Ïîëîæèì, ÷òî n n� ~.
Ñóùåñòâóþò äâà òèïà òàêèõ çàäà÷. Ê òèïó I îòíîñÿòñÿ çàäà÷è ðàçìåùåíèÿ
ìîäóëåé íà ïå÷àòíûõ ïëàòàõ, ïðîåêòèðîâàíèÿ ñâåðõáîëüøèõ èíòåãðàëüíûõ ìèê-
ðîñõåì è îïòèìàëüíîãî ðàñêðîÿ, ê òèïó II — çàäà÷à ðàçìåùåíèÿ áóêâ àëôàâèòà
íà êëàâèàòóðå [37].  çàäà÷àõ òèïà I êàæäîå ìíîæåñòâî ïðåäñòàâèì â âèäå ãðàôà,
âåðøèíàìè êîòîðîãî ÿâëÿþòñÿ åãî ýëåìåíòû, à êàæäîìó ðåáðó ïîñòàâëåíî â ñî-
îòâåòñòâèå ÷èñëî c Rlt � (R — ìíîæåñòâî âåùåñòâåííûõ ÷èñåë), ò.å. ìåæäó ýëå-
ìåíòàìè ìíîæåñòâ A è B ñóùåñòâóþò ñâÿçè, ÷èñëîâîå çíà÷åíèå êîòîðûõ íàçîâåì
âåñàìè. Âåëè÷èíû clt íàçîâåì âõîäíûìè äàííûìè è çàäàäèì èõ ìàòðèöàìè.  çà-
äà÷àõ òèïà II ìåæäó ýëåìåíòàìè çàäàííûõ ìíîæåñòâ ñâÿçåé íå ñóùåñòâóåò, à âå-
ñàìè ÿâëÿþòñÿ ÷èñëà v Rj � , êîòîðûì â ñîîòâåòñòâèå ïîñòàâëåíû íåêîòîðûå
ñâîéñòâà ýòèõ ýëåìåíòîâ. Èõ ÷èñëîâûå çíà÷åíèÿ çàäàþòñÿ êîíå÷íûìè ïîñëåäîâà-
òåëüíîñòÿìè, êîòîðûå òàêæå ÿâëÿþòñÿ âõîäíûìè äàííûìè. Ýòè âåëè÷èíû îïðå-
äåëÿþò çíà÷åíèå öåëåâîé ôóíêöèè.
Äëÿ îáîèõ òèïîâ çàäà÷ èç ýëåìåíòîâ îäíîãî èç çàäàííûõ ìíîæåñòâ, íàïðè-
ìåð a Al � , îáðàçóåòñÿ êîìáèíàòîðíîå ìíîæåñòâî W — ñîâîêóïíîñòü êîìáèíà-
òîðíûõ êîíôèãóðàöèé îïðåäåëåííîãî òèïà (ïåðåñòàíîâêè, ðàçáèåíèÿ è ò.ä.). Íà
ýëåìåíòàõ w êîìáèíàòîðíîãî ìíîæåñòâà W ââîäèòñÿ öåëåâàÿ ôóíêöèÿ F w( ). Íå-
îáõîäèìî íàéòè ýëåìåíò w* ìíîæåñòâà W, äëÿ êîòîðîãî îïðåäåëåííûé ôóíêöèî-
íàë ïðèíèìàåò ýêñòðåìàëüíîå çíà÷åíèå ïðè âûïîëíåíèè çàäàííûõ îãðàíè÷åíèé,
ò.å. F w F w
w W W
( ) ( )*
�
� �
glob extr
0
, ãäå extr { }� min, max , W 0 — ïîäìíîæåñòâî, îïðå-
äåëÿåìîå îãðàíè÷åíèÿìè çàäà÷è.
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2013, ¹ 2 107
ÇÀÂÈÑÈÌÎÑÒÜ ÖÅËÅÂÎÉ ÔÓÍÊÖÈÈ Â ÇÀÄÀ×Å ÐÀÇÌÅÙÅÍÈß ÎÁÚÅÊÒÎÂ
ÎÒ ÍÅÑÊÎËÜÊÈÕ ÏÅÐÅÌÅÍÍÛÕ
Ðàññìîòðèì çàäà÷ó òèïà I, â êîòîðîé çàäàíà îáëàñòü äëÿ ðàçìåùåíèÿ îáúåêòîâ
ïðîèçâîëüíîé ôîðìû, íî íå çàäàíû óñòàíîâî÷íûå ïîçèöèè. Ìåæäó îáúåêòàìè
ñóùåñòâóþò ñâÿçè. Ïîëàãàåì, ÷òî îáúåêòû àïïðîêñèìèðîâàíû ïðÿìîóãîëüíè-
êàìè, êîòîðûå â ïðîöåññå ðåøåíèÿ çàäà÷è ïðåäñòàâëÿþòñÿ êàê ãåîìåòðè÷åñêèå
òî÷êè. Äëÿ ýòîé çàäà÷è îïðåäåëèì àðãóìåíò öåëåâîé ôóíêöèè (êîìáèíàòîð-
íóþ êîíôèãóðàöèþ).
Ïóñòü çàäàíî ìíîæåñòâî A a an� { }1, ,� , êàæäîìó ýëåìåíòó a As � êîòîðîãî ñî-
îòâåòñòâóåò îïðåäåëåííûé îáúåêò, ðàçìåùàåìûé íà ïðÿìîóãîëüíîé ïîâåðõíîñòè ñ íàíå-
ñåííîé íà íåé îðòîãîíàëüíîé êîîðäèíàòíîé ñåòêîé. Ïåðåíóìåðóåì ÿ÷åéêè ýòîé ñåò-
êè è èõ ïîñëåäîâàòåëüíóþ íóìåðàöèþ ïðåäñòàâèì ìíîæåñòâîì B b bn� { }1, , ~� .
Ñôîðìóëèðóåì òåîðåìó.
Òåîðåìà. Öåëåâàÿ ôóíêöèÿ â çàäà÷å ðàçìåùåíèÿ îáúåêòîâ ïðîèçâîëüíîé
ôîðìû çàâèñèò îò íåñêîëüêèõ ïåðåìåííûõ, êîòîðûìè ÿâëÿþòñÿ êîìáèíàòîðíûå
êîíôèãóðàöèè ðàçëè÷íûõ òèïîâ. Ïî àðãóìåíòó öåëåâîé ôóíêöèè îíà åñòåñòâåííî
ðàçäåëÿåòñÿ íà íåñêîëüêî ïîäçàäà÷.
Äîêàçàòåëüñòâî. Çàäà÷ó ðàçìåùåíèÿ îáúåêòîâ ïðîèçâîëüíîé ôîðìû ñâåäåì
ê çàäà÷å ðàçìåùåíèÿ îäíîãàáàðèòíûõ îáúåêòîâ ñ ïîñëåäóþùèì èõ ðàçìåùåíèåì
íà ñôîðìèðîâàííîì èç ýëåìåíòîâ ìíîæåñòâà B b bn� { }1, , ~� ðåãóëÿðíîì ïîëå ïî-
çèöèé ñëåäóþùèì îáðàçîì. Ýëåìåíòû ìíîæåñòâà A a an� { }1, ,� îáúåäèíèì
â îäíîãàáàðèòíûå áëîêè, ò.å. ðåøèì çàäà÷ó êîìïîíîâêè, àðãóìåíòîì öåëåâîé
ôóíêöèè â êîòîðîé ÿâëÿåòñÿ ðàçáèåíèå n-ýëåìåíòíîãî ìíîæåñòâà íà ïîäìíîæåñòâà.
Ñîîòâåòñòâåííî ýëåìåíòû ìíîæåñòâà B îáúåäèíèì â ïîñàäî÷íûå ìåñòà òàêèì îá-
ðàçîì, ÷òîáû íà êàæäîì èç íèõ ðàçìåñòèëèñü îáðàçîâàííûå áëîêè.  ýòîì ñëó÷àå
òàêæå ðåøàåòñÿ çàäà÷à ðàçáèåíèÿ.
Èç ýëåìåíòîâ as áàçîâîãî ìíîæåñòâà A, s n�{ }1, ,� , îáðàçóåòñÿ êîìáèíàòîð-
íîå ìíîæåñòâî � — ñîâîêóïíîñòü ðàçáèåíèé n-ýëåìåíòíîãî ìíîæåñòâà íà ïîä-
ìíîæåñòâà � ��, à èç ýëåìåíòîâ bl áàçîâîãî ìíîæåñòâà B îáðàçóåòñÿ êîìáèíà-
òîðíîå ìíîæåñòâî
~
� — ðàçáèåíèå ýëåìåíòîâ ìíîæåñòâà B íà ïîäìíîæåñòâà
~ ~
� ��. Èç óïîðÿäî÷åíèÿ ýëåìåíòîâ bl â ~ ~
� �� îáðàçóåòñÿ ìíîæåñòâî ðàçìåùåíèé
áåç ïîâòîðåíèé M. Ïîñêîëüêó îáðàçîâàííûå ïîäìíîæåñòâà � �� îáúåäèíÿþò çà-
äàííûå ìîäóëè èç ìíîæåñòâà A â îäíîãàáàðèòíûå îáúåêòû, ïîñëåäíèå íåñëîæíî
ðàçìåñòèòü íà îäíîðîäíîì ïîëå ïîçèöèé èç ~ ~
� ��, â êàæäîé èç êîòîðûõ ðàçìåùà-
åòñÿ áëîê (ïîäìíîæåñòâî) � �j � ��, j �{ }1, ,� � , ãäå � — êîëè÷åñòâî ïîäìíî-
æåñòâ � j â �. Àðãóìåíòîì öåëåâîé ôóíêöèè â çàäà÷å ðàçìåùåíèÿ îäíîãàáàðèò-
íûõ îáúåêòîâ ÿâëÿåòñÿ ïåðåñòàíîâêà. Ñîîòâåòñòâåííî èç ïîäìíîæåñòâ � j
ðàçáèåíèÿ � �� îáðàçóåì ìíîæåñòâî ïåðåñòàíîâîê �.
Ââåäåì öåëåâóþ ôóíêöèþ íà ýëåìåíòàõ �, ~�, � è � ìíîæåñòâ �,
~
�, � è .
 ðåçóëüòàòå çàäà÷à ðàçìåùåíèÿ ðàçíîãàáàðèòíûõ îáúåêòîâ íà ïîâåðõíîñòè çà-
êëþ÷àåòñÿ â íàõîæäåíèè òàêèõ � *
� �, � *
� �, ~ ~*� � �, �*
� M, äëÿ êîòîðûõ
ñìîäåëèðîâàííûé ôóíêöèîíàë ïðèíèìàåò îïòèìàëüíîå çíà÷åíèå ïðè âûïîëíåíèè
çàäàííûõ óñëîâèé, ò.å. F F( , , ~ , ) ( , , ~, )* * * *
~ ~
� � � � � � � �
�
�
�
�
�
�
�
�
�
extr
M
�
�
�
, ãäå extr { }� min, max .
Èç ýòîãî cëåäóåò, ÷òî çàäà÷à ðàçìåùåíèÿ îáúåêòîâ ïðîèçâîëüíîé ôîðìû ðàç-
äåëÿåòñÿ íà íåñêîëüêî ïîäçàäà÷, à öåëåâàÿ ôóíêöèÿ â íåé çàâèñèò îò íåñêîëüêèõ
ïåðåìåííûõ, êîòîðûìè ÿâëÿþòñÿ êîìáèíàòîðíûå êîíôèãóðàöèè ðàçëè÷íûõ òèïîâ,
÷òî è äîêàçûâàåò òåîðåìó.
108 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2013, ¹ 2
Ñëåäîâàòåëüíî, çàäà÷à ðàçìåùåíèÿ ðàçíîãàáàðèòíûõ îáúåêòîâ ïî àðãóìåíòó
öåëåâîé ôóíêöèè åñòåñòâåííî ðàçäåëÿåòñÿ íà òàêèå ïîäçàäà÷è:
— êîìïîíîâêà áàçîâûõ ýëåìåíòîâ â îäíîãàáàðèòíûå îáúåêòû;
— îáúåäèíåíèå ýëåìåíòîâ êîîðäèíàòíîé ñåòêè â ðåãóëÿðíîå ïîëå ïîçèöèé,
â êàæäîé èç êîòîðûõ ìîæíî ðàçìåñòèòü ïîëó÷åííûå îáúåêòû;
— ðàçìåùåíèå îäíîãàáàðèòíûõ îáúåêòîâ íà ðåãóëÿðíîì ïîëå ïîçèöèé.
Äëÿ ðåøåíèÿ êàæäîé ïîäçàäà÷è ðàçðàáàòûâàþòñÿ íåçàâèñèìûå àëãîðèòìû,
êîòîðûå ðàáîòàþò êàê âñòðîåííûå ïðîöåäóðû â èòåðàöèîííîì ðåæèìå, ÷òî õà-
ðàêòåðíî äëÿ ãèáðèäíûõ àëãîðèòìîâ [23, 38]. Îïòèìàëüíîå ðåøåíèå íàõîäèòñÿ
íà íåñêîëüêèõ êîìáèíàòîðíûõ ìíîæåñòâàõ.
Ñ èñïîëüçîâàíèåì òåîðèè êîìáèíàòîðíîé îïòèìèçàöèè ñôîðìóëèðóåì ìàòå-
ìàòè÷åñêóþ ïîñòàíîâêó äëÿ çàäà÷è ðàçìåùåíèÿ òèïà II íà ïðèìåðå ðàçìåùåíèÿ
áóêâ àëôàâèòà íà êëàâèàòóðå [37].
Ýòà çàäà÷à òàêæå çàäàåòñÿ äâóìÿ ìíîæåñòâàìè: A è B. Êàæäîìó ýëåìåíòó
a Al � , l n�{ }1, ,� , cîîòâåòñòâóåò îïðåäåëåííàÿ êëàâèøà, à ýëåìåíòó b Bt � ,
t n�{ }1, , ~
� , — áóêâà àëôàâèòà, êîòîðóþ íåîáõîäèìî ðàçìåñòèòü â çàäàííîé îá-
ëàñòè, ãäå n — êîëè÷åñòâî ýëåìåíòîâ ìíîæåñòâà A, ~n — êîëè÷åñòâî ýëåìåíòîâ
ìíîæåñòâà B. Ïîëîæèì, ÷òî n n� ~. Òàêèì îáðàçîì, èìååì äâà ìíîæåñòâà, ìåæäó
ýëåìåíòàìè êîòîðûõ îòñóòñòâóþò ñâÿçè. Âìåñòî íèõ ýëåìåíòó a Al � ïîñòàâëåíî
â ñîîòâåòñòâèå âðåìÿ, çàòðà÷èâàåìîå íà íàæàòèå ýòîé êëàâèøè. Ââåäåì êîíå÷-
íóþ ïîñëåäîâàòåëüíîñòü (ôóíêöèþ íàòóðàëüíîãî àðãóìåíòà) �( )|j n
1
, ãäå �( )j —
çíà÷åíèå âðåìåíè, çàòðà÷èâàåìîãî íà íàæàòèå j-é êëàâèøè. Êàæäîìó ýëåìåíòó
b Bt � ïðèñâîåíî çíà÷åíèå, ñîîòâåòñòâóþùåå ÷àñòîòå âñòðå÷àåìîñòè áóêâû â ñëî-
âàõ îïðåäåëåííîãî ÿçûêà. Ââåäåì êîìáèíàòîðíóþ ôóíêöèþ �( ( ), ) |f j wk n
1
�
� ( ( ( ), ) , , ( ( ), ))� �1 1f w f n wk
n
k
� , ãäå � j
kf j w( ( ), ) — ÷àñòîòà âñòðå÷àåìîñòè
j-é áóêâû â ñëîâàõ îïðåäåëåííîãî ÿçûêà â k-ì âàðèàíòå ðåøåíèÿ çàäà÷è, w Wk
� —
àðãóìåíò öåëåâîé ôóíêöèè (êîìáèíàòîðíàÿ êîíôèãóðàöèÿ), k — ïîðÿäêîâûé íî-
ìåð wk âî ìíîæåñòâå W. Çàäà÷à çàêëþ÷àåòñÿ â íàõîæäåíèè òàêîé ïåðåñòàíîâêè
w Wk
� , äëÿ êîòîðîé öåëåâàÿ ôóíêöèÿ F w f j w jk
j
j
n
k( ) ( ( ), ) ( )�
�
� �
1
ïðè âû-
ïîëíåíèè çàäàííûõ îãðàíè÷åíèé ïðèíèìàåò îïòèìàëüíîå çíà÷åíèå.  [37] äëÿ
ýôôåêòèâíîãî ðåøåíèÿ ýòîé çàäà÷è áóêâû ïî îïðåäåëåííûì ïðèçíàêàì îáúåäè-
íåíû â êëàñòåðû ñ ïîñëåäóþùèì èõ ðàçìåùåíèåì íà êëàâèàòóðå. Öåëåâàÿ ôóíê-
öèÿ â ýòîé çàäà÷å çàâèñèò îò äâóõ ïåðåìåííûõ: ïåðåñòàíîâêè è ðàçáèåíèÿ n-ýëå-
ìåíòíîãî ìíîæåñòâà íà ïîäìíîæåñòâà, à ïîèñê åå çíà÷åíèÿ ïðîâîäèòñÿ íà äâóõ
êîìáèíàòîðíûõ ìíîæåñòâàõ.
ÐÅØÅÍÈÅ ÇÀÄÀ×È ÐÀÇÌÅÙÅÍÈß ÎÄÍÎÃÀÁÀÐÈÒÍÛÕ ÎÁÚÅÊÒÎÂ
ÌÅÒÎÄÎÌ ÑÒÐÓÊÒÓÐÍÎ-ÀËÔÀÂÈÒÍÎÃÎ ÏÎÈÑÊÀ
Äëÿ ðåøåíèÿ çàäà÷ êîìáèíàòîðíîé îïòèìèçàöèè ðàçðàáîòàíî ìíîãî ìåòîäîâ è
àëãîðèòìîâ, ñðåäè êîòîðûõ âûäåëèì îñíîâàííûå íà ðàñïîçíàâàíèè ñòðóêòóðû
âõîäíîé èíôîðìàöèè è õàðàêòåðèçóþùèåñÿ áîëüøèì áûñòðîäåéñòâèåì, íàïðè-
ìåð ìåòîä áëèæàéøåãî ñîñåäà, «æàäíûé» àëãîðèòì è ò. ä. Ìåòîä ñòðóêòóð-
íî-àëôàâèòíîãî ïîèñêà, ïðèìåíåííûé ïðè ðåøåíèè çàäà÷è ðàçìåùåíèÿ
îäíîãàáàðèòíûõ îáúåêòîâ, îñíîâàí íà ðàñïîçíàâàíèè ñòðóêòóðû âõîäíîé
èíôîðìàöèè [39, 40].  íåì èñïîëüçîâàí èçâåñòíûé ðàçðåøèìûé ñëó÷àé,
ñôîðìóëèðîâàííûé ñëåäóþùèì îáðàçîì [41]. Èìååì äâà ìíîæåñòâà ïåðåñòà-
íîâîê, çàäàííûõ ñèñòåìàìè ( )d è ( )e , íà êîòîðûõ ââåäåíà öåëåâàÿ ôóíêöèÿ
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2013, ¹ 2 109
de
. Äëÿ ýòèõ ñèñòåì îïðåäåëåíû ïåðåñòàíîâêè, ãäå de
ïðèíèìàåò íàè-
áîëüøåå èëè íàèìåíüøåå çíà÷åíèå. Åñëè ýëåìåíòû ïåðåñòàíîâêè ñèñòåìû ( )d
óïîðÿäî÷åíû ïî óáûâàíèþ èõ âåëè÷èí, à ýëåìåíòû ïåðåñòàíîâêè ñèñòåìû ( )e
óïîðÿäî÷åíû ïî âîçðàñòàíèþ, òî çíà÷åíèå de
ÿâëÿåòñÿ ãëîáàëüíûì ìèíèìó-
ìîì. Åñëè ýëåìåíòû îáåèõ ïåðåñòàíîâîê óïîðÿäî÷åíû ïî âîçðàñòàíèþ èõ âå-
ëè÷èí, òî çíà÷åíèå de
ÿâëÿåòñÿ ãëîáàëüíûì ìàêñèìóìîì. Ýòîò ðàçðåøèìûé
ñëó÷àé íå ïðèíàëåæèò íè îäíîìó èç êëàññîâ çàäà÷ êîìáèíàòîðíîé îïòèìèçàöèè.
Îí ýôôåêòèâåí äëÿ çàäà÷, ðåøàåìûõ íà ïåðåñòàíîâêàõ è íà ïîäìíîæåñòâå èçî-
ìîðôíûõ êîìáèíàòîðíûõ êîíôèãóðàöèé. Äëÿ èñïîëüçîâàíèÿ îïèñàííîãî ðàçðåøè-
ìîãî ñëó÷àÿ äëÿ ðåøåíèÿ çàäà÷ êîìáèíàòîðíîé îïòèìèçàöèè ìåòîäîì ñòðóêòóð-
íî-àëôàâèòíîãî ïîèñêà âõîäíûå äàííûå ñìîäåëèðóåì ôóíêöèÿìè íàòóðàëüíîãî
àðãóìåíòà. Íàõîæäåíèå îïòèìàëüíîãî ðåøåíèÿ îñóùåñòâëÿåòñÿ ïî ýòèì ôóíêöè-
ÿì, êîòîðûå óïîðÿäî÷åíû ïî âîçðàñòàíèþ èëè óáûâàíèþ èõ çíà÷åíèé. Ñîãëàñíî
ðàçðàáîòàííûì ïðàâèëàì îïðåäåëÿåòñÿ ïîñëåäîâàòåëüíîñòü ëîêàëüíûõ îïòèìóìîâ
òàêèõ, ÷òî îíà ñîäåðæèò ãëîáàëüíîå èëè ïðèáëèæåííîå ê ãëîáàëüíîìó ðåøåíèå.
Äëÿ çàäà÷è ðàçìåùåíèÿ çíà÷åíèÿ âåñîâ ìåæäó ýëåìåíòàìè ìíîæåñòâà A çà-
äàäèì ñèììåòðè÷åñêîé êîìáèíàòîðíîé ìàòðèöåé Q wk( ), à ìíîæåñòâà B — ñèì-
ìåòðè÷åñêîé ìàòðèöåé C. Ýëåìåíòû h íàääèàãîíàëåé ñèììåòðè÷åñêîé êîìáèíà-
òîðíîé ìàòðèöû Q wk( ) ïðåäñòàâèì êîìáèíàòîðíîé ôóíêöèåé �( ( ), )|f j wk m
1
�
� ( ( ( ), ), , ( ( ), )� �1 1f w f m wk
m
k
� , à ýëåìåíòû h íàääèàãîíàëåé ñèììåòðè÷åñêîé
ìàòðèöû C — ôóíêöèåé íàòóðàëüíîãî àðãóìåíòà �( )j m
1
, ãäå m
n n
�
�( )1
2
— êîëè-
÷åñòâî ýëåìåíòîâ h íàääèàãîíàëåé ìàòðèö C è Q wk( ), h n� �1 1, . Öåëåâàÿ ôóíê-
öèÿ ïðèìåò âèä F w f j w jk
j
j
m
k( ) ( ) ( ( ), ) ( )1
1
�
�
� � .  íåêîòîðûõ çàäà÷àõ âàæíî
îïòèìèçèðîâàòü ïëîùàäü, êîòîðóþ çàíèìàþò ðàçìåùàåìûå îáúåêòû, ïîýòîìó
ââåäåì òàêîé êðèòåðèé F w S wk
l
k
l
n
( ) ( ) ( )2
1
�
�
, ãäå S wl
k( ) — ïëîùàäü, çàíèìàå-
ìàÿ l-ì îáúåêòîì ñ ó÷åòîì ðàññòîÿíèÿ ìåæäó ñîñåäíèìè îáúåêòàìè äëÿ k-ãî âà-
ðèàíòà ðàçìåùåíèÿ.
Ââåäåì ñèñòåìû êîìáèíàòîðíûõ ôóíêöèé H è �H , ãäå �( ( ), )|f j w Hk m
1
� —
êîìáèíàòîðíàÿ ôóíêöèÿ, àðãóìåíòîì êîòîðîé ÿâëÿåòñÿ ïåðåñòàíîâêà w Wk
� ,
îáðàçîâàííàÿ èç ýëåìåíòîâ áàçîâîãî ìíîæåñòâà A a an n� { }1 , ,� , à �( ( ), )|
'
f j w i m
1
�
� �H — êîìáèíàòîðíàÿ ôóíêöèÿ, àðãóìåíòîì êîòîðîé ÿâëÿåòñÿ ïåðåñòàíîâêà w Wi'
� �,
îáðàçîâàííàÿ èç ýëåìåíòîâ áàçîâîãî ìíîæåñòâà
~ ~ , , ~A a am m� { }1 � . Åñëè
� �( ( ), )| ( ( ), )|'f j w f j wm m1
1
1
1
� , ãäå w w1 1, ' — ïåðâûå ïåðåñòàíîâêè ñîîòâåòñòâåííî
â W, �W è �( ( ), )|f j w Hm1
1
� , à �( ( ), )|'f j w Hm1
1
� �, òî H H� �. Çàäà÷ó ðàçìåùåíèÿ
îáúåêòîâ, âõîäíûå äàííûå â êîòîðîé çàäàíû ôóíêöèÿìè �( ( ), )|f j wk m
1
è �( )|j m
1
,
íàçîâåì áàçîâîé èëè çàäà÷åé ñèñòåìû H. Çàäà÷ó, âõîäíûå äàííûå â êîòîðîé çàäàíû
ôóíêöèÿìè
�
�( ( ), ) |'f j w i m
1
èëè
�
�( ( ), )|'f j w t m
1
, ãäå
�
�( ( ), )'f j w i
�
�( ( ), )'f j w i
� 1 èëè
� �
� �( ( ), ) ( ( ), )' 'f j w f j wt t
� � 1 , è
�
�( )|j m
1
èëè
�
�( )|j m
1
, à
�
�( )j �
�
�( )j � 1 èëè
�
�( )j
�
�
�( )j 1 , îáðàçîâàííûå èç �( ( ), )|f j wk m
1
è �( )|j m
1
, íàçîâåì óïîðÿäî÷åííîé èëè
çàäà÷åé ñèñòåìû �H . Çíà÷åíèå öåëåâîé ôóíêöèè äëÿ çàäà÷è ðàçìåùåíèÿ
110 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2013, ¹ 2
îäíîãàáàðèòíèõ îáúåêòîâ íàõîäèòñÿ â ïðåäåëàõ max ( )
' *
' *
w W
t
t
F w
� �
F wk( )
� �
min ( )
' *
' *
w W
i
i
F w , ãäå max ( )
' *
' *
w W
t
t
F w
� �
, min ( )
' *
' *
w W
i
i
F w
� �
— ñîîòâåòñòâåííî ãëîáàëüíûå
ìàêñèìóì è ìèíèìóì ñèñòåìû �H , êîòîðàÿ ñîâïàäàåò ñ ðàçðåøèìûì ñëó÷àåì,
îïèñàííûì â [41].
Ïðèâåäåì âû÷èñëèòåëüíóþ ñõåìó íàõîæäåíèÿ ìèíèìàëüíîãî çíà÷åíèÿ öåëå-
âîé ôóíêöèè äëÿ çàäà÷è ðàçìåùåíèÿ îäíîãàáàðèòíûõ îáúåêòîâ ìåòîäîì ñòðóêòóð-
íî-àëôàâèòíîãî ïîèñêà (ìàêñèìàëüíîå çíà÷åíèå îïðåäåëÿåòñÿ àíàëîãè÷íî).
Øàã 1. Áàçîâóþ çàäà÷ó ðàçìåùåíèÿ ñâåäåì ê óïîðÿäî÷åííîé, ïðåäñòàâèâ
âõîäíûå äàííûå ôóíêöèÿìè
�
�( ( ), )|'f j w t m
1
è
�
�( )|j m
1
. Ïåðåéäåì ê øàãó 2.
Øàã 2. Ïî ôóíêöèè
�
�( ( ), ) |'f j w t m
1
, èñïîëüçóÿ ïðàâèëà, èçëîæåííûå â [42],
íàõîäèì ïåðåñòàíîâêó w Wk
� . Åñëè
�
� �( ( ), ) | ( ( ), ) |'f j w f j wt m k m
1 1
� , òî â êà÷åñòâå
ãëîáàëüíîãî ðåøåíèÿ ïðèíèìàåì ïåðåñòàíîâêó w Wk
� , êîòîðàÿ ñîâïàäàåò ñ ãëî-
áàëüíûì w Wt'
� � äëÿ óïîðÿäî÷åííîé çàäà÷è. Ïåðåõîäèì ê øàãó 10. Èíà÷å ïîëà-
ãàåì F F w t* '( )� è ïåðåõîäèì ê øàãó 3.
Øàã 3. Íàõîäèì òåêóùèé ëîêàëüíûé ìèíèìóì, íà÷èíàÿ ñ íîìåðà j �1 çíà÷åíèÿ
êîìáèíàòîðíîé ôóíêöèè
�
�( ( ), ) |'f j w t m
1
. Äëÿ
�
�( ( ), )'f j w t ñòðîèì ïåðåñòàíîâêó ïî
÷èñëîâîé ôóíêöèè
�
�( )|j m
1
, íà÷èíàÿ ñ íîìåðà l �1. Ïîëàãàåì
~
l l� . Ïåðåõîäèì ê øàãó 4.
Øàã 4. Ôîðìèðóåì ïåðåñòàíîâêó ñëåäóþùèì îáðàçîì. Íîìåðà ñòðîêè è
ñòîëáöà, ãäå íàõîäèòñÿ j-å çíà÷åíèå êîìáèíàòîðíîé ôóíêöèè, ÿâëÿþòñÿ ýëåìåí-
òàìè ñòðîÿùåéñÿ ïåðåñòàíîâêè. Íîìåðà ñòðîêè è ñòîëáöà, ãäå íàõîäèòñÿ l-å çíà-
÷åíèå ÷èñëîâîé ôóíêöèè, çàäàþò ìåñòà â ïåðåñòàíîâêå, êóäà ðàçìåùàþòñÿ íàé-
äåííûå ýëåìåíòû. Ïåðåõîäèì ê øàãó 5.
Øàã 5. Åñëè òåêóùàÿ ïåðåñòàíîâêà ïîñòðîåíà, ïåðåõîäèì ê øàãó 6. Èíà÷å
ïîëàãàåì l l� �1. Åñëè l m� , òî ïåðåõîäèì ê øàãó 4, èíà÷å — ê øàãó 7.
Øàã 6. Äëÿ ïîëó÷åííîé ïåðåñòàíîâêè wk âû÷èñëÿåì çíà÷åíèå öåëåâîé
ôóíêöèè F wk( ). Åñëè F w Fk( ) *
� , òî ïåðåõîäèì ê øàãó 7. Èíà÷å ëîêàëüíûì ðå-
øåíèåì áóäåò ïðåäûäóùåå çíà÷åíèå F wk( )�1 . Ïåðåõîäèì ê øàãó 7.
Øàã 7. Åñëè äëÿ çíà÷åíèÿ êîìáèíàòîðíîé ôóíêöèè j íàéäåí ëîêàëüíûé ìè-
íèìóì, ïåðåõîäèì ê øàãó 8. Èíà÷å ïîëàãàåì l l� �
~
1,
~
l l� . Åñëè l m� , òî ïåðåõî-
äèì ê øàãó 4, èíà÷å — ê øàãó 8.
Øàã 8. Åñëè ïî âñåì ëîêàëüíûì ìèíèìóìàì çíà÷åíèå öåëåâîé ôóíêöèè óâåëè-
÷èâàåòñÿ, ïåðåõîäèì ê øàãó 9.  èíîì ñëó÷àå çàïîìèíàåì çíà÷åíèå öåëåâîé ôóíê-
öèè è ïåðåñòàíîâêó î÷åðåäíîãî ëîêàëüíîãî ìèíèìóìà F wk( )�1 . Ïîëàãàåì j j� �1,
l �1,
~
l l� , F F wk* ( )�
�1 . Åñëè j m� , òî ïåðåõîäèì ê øàãó 4, èíà÷å — ê øàãó 9.
Øàã 9.  êà÷åñòâå ðåøåíèÿ çàäà÷è ïðèíèìàåì ïåðåñòàíîâêó, äëÿ êîòîðîé èç
âñåõ ëîêàëüíûõ ìèíèìóìîâ çíà÷åíèå öåëåâîé ôóíêöèè ÿâëÿåòñÿ íàèìåíüøèì.
Îíî ìîæåò ñîâïàäàòü ñ ãëîáàëüíûì ìèíèìóìîì. Ïåðåõîäèì ê øàãó 10.
Øàã 10. Êîíåö ðàáîòû àëãîðèòìà.
Èñïîëüçóÿ ïîäêëàññû ðàçðåøèìûõ çàäà÷, ìîæíî äîêàçàòü, ÷òî ìåòîäîì ñòðóêòóð-
íî-àëôàâèòíîãî ïîèñêà ïîëèíîìèàëüíî íàõîäèòñÿ ãëîáàëüíüíîå îïòèìàëüíîå ðåøåíèå.
Îïèøåì âû÷èñëèòåëüíóþ ñõåìó ãèáðèäíîãî àëãîðèòìà, â êîòîðîì ðåøåíèå
íåêîòîðûõ ïîäçàäà÷ îñóùåñòâëÿåòñÿ ñàìîíàñòðàèâàþùèìèñÿ àëãîðèòìàìè ðàç-
ìåùåíèÿ ðàçíîãàáàðèòíûõ ìîäóëåé íà ïëàòå [23].
Øàã 1. Ïîëàãàåì A *
� �,
~
\ *A A A� , ãäå A * — ïîäìíîæåñòâî, ýëåìåíòû
êîòîðîãî ñîîòâåòñòóþò óæå ðàçìåùåííûì ìîäóëÿì.
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2013, ¹ 2 111
Øàã 2. Îïðåäåëÿåì óñòàíîâî÷íûå ïîçèöèè ñ ïîìîùüþ ñàìîíàñòðàèâàþùå-
ãîñÿ àëãîðèòìà, â ïðîöåññå ðàáîòû êîòîðîãî íà î÷åðåäíîé èòåðàöèè îñóùåñòâëÿ-
åòñÿ äèíàìè÷åñêàÿ ïåðåñòðîéêà îáëàñòè ðàçìåùåíèÿ: èç çàäàííûõ ýëåìåíòîâ
ìíîæåñòâà B b bn� { }1, , ~� îáðàçóåì ðåãóëÿðíóþ ñèñòåìó óñòàíîâî÷íûõ ïîçèöèé
D d d� { }1, ,� � òàêèõ, ÷òî â d Dj � ðàçìåùàåòñÿ íàèáîëüøèé ïî ãàáàðèòàì ìî-
äóëü èç
~
A.
Øàã 3. Ðåøàåì çàäà÷ó êîìïîíîâêè ýëåìåíòîâ a Al �
~
ñàìîíàñòðàèâàþùèìñÿ
àëãîðèòìîì [43, 44], â êîòîðîì ðåàëèçîâàí ïîäõîä, îñíîâàííûé íà ðàñïîçíàâà-
íèè âõîäíîé èíôîðìàöèè. Ïîñêîëüêó èç-çà ñòðóêòóðû àðãóìåíòà öåëåâîé ôóíê-
öèè â ïðîöåññå ðåøåíèÿ ýòîé çàäà÷è ïîÿâëÿåòñÿ ñèòóàöèÿ íåîïðåäåëåííîñòè,
îïòèìèçàöèÿ îñóùåñòâëÿåòñÿ ñ èñïîëüçîâàíèåì íåñêîëüêèõ êðèòåðèåâ (ïîñòîÿí-
íûõ è ïåðåìåííûõ). Ïîëó÷àåì ìíîæåñòâî V v vk k k
� { }
1
, , ~�
.
Øàã 4. Ðàçìåùàåì îäíîãàáàðèòíûå ìîäóëè v Vj
k k
� ìåòîäîì ñòðóêòóðíî-àë-
ôàâèòíîãî ïîèñêà íà ðåãóëÿðíîì ïîëå ïîçèöèé D d d� { }1, ,� � .
Øàã 5. Âêëþ÷àåì ìîäóëè v Vj
k k
� , êîòîðûå ñîäåðæàò îäèí ýëåìåíò, â ìíî-
æåñòâî A * . Ôèêñèðóåì ýòè ýëåìåíòû â íàéäåííûõ ïîçèöèÿõ. Ïîëàãàåì
~
\ *A A A� .
Øàã 6.. Åñëè A A*
� , ïåðåõîäèì ê øàãó 7, èíà÷å — ê øàãó 2.
Øàã 7. Êîíåö ðàáîòû àëãîðèòìà.
Ðàññìîòðèì ðåøåíèå òåñòîâûõ ïðèìåðîâ ðàçðåøèìûõ çàäà÷ ìåòîäîì ñòðóê-
òóðíî-àëôàâèòíîãî ïîèñêà.
Ïðèìåð 1. Çàäàíî: n � 5 ; �( ( ), )| ( , , , , , , , , , )f j w m1
1
1 2 3 4 5 6 7 8 9 10� ; �( )|j m
1
�
� ( , , , , , , , , , )1 2 3 4 5 6 7 8 9 10 . Óïîðÿäî÷èì èõ ñëåäóþùèì îáðàçîì:
�
�( )|j m
1
�
� ( , , , , , , , , , )1 2 3 4 5 6 7 8 9 10 ;
�
�( ( ), ) | ( , , , , , , , , , )'f j w t m
1
10 9 8 7 6 5 4 3 2 1� . Ïî ýòèì ôóíê-
öèÿì îïðåäåëèì ëîêàëüíûå ìèíèìóìû: w1 5 4 3 2 1� ( , , , , ), äëÿ êîòîðîé F w( )1 230� ,
è w2 5 4 3 1 2� ( , , , , ), äëÿ êîòîðîé F w( )2 239� . Ïåðåñòàíîâêà w1 5 4 3 2 1� ( , , , , ) ñîâïà-
äàåò ñ ãëîáàëüíûì ìèíèìóìîì, ïîëó÷åííûì ïîëíûì ïåðåáîðîì è ÿâëÿåòñÿ ðå-
øåíèåì äàííîãî ïðèìåðà.
Ïðèìåð 2. Çàäàíî: n � 5; �( ( ), )| ( , , , , , , , , , )f j w m1
1
5 6 4 7 3 8 2 9 1 10� ; �( )|j m
1
�
� ( , , , , , , , , , )5 6 4 7 3 8 2 9 1 10 . Óïîðÿäî÷èì èõ ñëåäóþùèì îáðàçîì:
�
�( )|j m
1
�
� ( , , , , , , , , , )1 2 3 4 5 6 7 8 9 10 ;
�
�( ( ), ) | ( , , , , , , , , , )'f j w t m
1
10 9 8 7 6 5 4 3 2 1� . Ïî ýòèì ôóíê-
öèÿì îïðåäåëèì ëîêàëüíûå ìèíèìóìû: w1 1 2 5 3 4� ( , , , , ), äëÿ êîòîðîé F w( )1 274� ,
è w2 3 4 1 2 5� ( , , , , ), äëÿ êîòîðîé F w( )2 268� . Ïåðåñòàíîâêà w2 3 4 1 2 5� ( , , , , ) ñîâ-
ïàäàåò ñ ãëîáàëüíûì ìèíèìóìîì, ïîëó÷åííûì ïîëíûì ïåðåáîðîì è ÿâëÿåòñÿ ðå-
øåíèåì ýòîãî ïðèìåðà.
ÇÀÊËÞ×ÅÍÈÅ
Öåëåâàÿ ôóíêöèÿ â çàäà÷å ðàçìåùåíèÿ çàâèñèò îò íåñêîëüêèõ ïåðåìåííûõ: ïå-
ðåñòàíîâêè, ðàçáèåíèÿ n-ýëåìåíòíîãî ìíîæåñòâà íà ïîäìíîæåñòâà è ðàçìåùå-
íèÿ áåç ïîâòîðåíèé, âñëåäñòâèå ÷åãî îíà ðàçäåëÿåòñÿ íà íåñêîëüêî ïîäçàäà÷.
Äëÿ ðåøåíèÿ çàäà÷ ðàçìåùåíèÿ òèïà I è II êàê îäíîãàáàðèòíûõ, òàê è îáúåê-
òîâ ïðîèçâîëüíîé ôîðìû ìîæíî èñïîëüçîâàòü îäèí è òîò æå ïîäõîä, â êîòî-
ðîì çàäà÷à ðàçìåùåíèÿ îáúåêòîâ ïðîèçâîëüíîé ôîðìû ñâîäèòñÿ ê çàäà÷å ðàç-
ìåùåíèÿ îäíîãàáàðèòíûõ îáúåêòîâ ïóòåì äèíàìè÷åñêîé ïåðåñòðîéêè óñòàíî-
âî÷íûõ ïîçèöèé îáëàñòè ðàçìåùåíèÿ è ðàçìåðîâ ýòèõ îáúåêòîâ, ò.å. äëÿ èõ
ðåøåíèÿ íåîáõîäèìî ðàçðàáàòûâàòü ãèáðèäíûå àëãîðèòìû.
112 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2013, ¹ 2
Íàõîæäåíèå îïòèìàëüíîãî ðåøåíèÿ çàäà÷è ðàçìåùåíèÿ îäíîãàáàðèòíûõ
îáúåêòîâ ìåòîäîì ñòðóêòóðíî-àëôàâèòíîãî ïîèñêà äîñòèãàåòñÿ óïîðÿäî÷åíèåì
ïî âîçðàñòàíèþ (èëè óáûâàíèþ) çíà÷åíèé äâóõ êîíå÷íûõ ïîñëåäîâàòåëüíîñòåé
(ôóíêöèé íàòóðàëüíîãî àðãóìåíòà), êîòîðûìè çàäàþòñÿ âõîäíûå äàííûå. Ñõîäè-
ìîñòü îïèñàííîãî ìåòîäà äîêàçàíà ñ èñïîëüçîâàíèåì ïîäêëàññîâ ðàçðåøèìûõ çà-
äà÷, äëÿ êîòîðûõ èçâåñòíî ãëîáàëüíîå ðåøåíèå.
ÑÏÈÑÎÊ ËÈÒÅÐÀÒÓÐÛ
1. Ê à í ò î ð î â è ÷ Ë . Â . , Ç à ë ã à ë ë å ð Â . À . Ðàöèîíàëüíûé ðàñêðîé ïðîìûøëåííûõ ìàòåðè-
àëîâ. — Íîâîñèáèðñê: Íàóêà, ÑÎ ÀÍ ÑÑÑÐ, 1971. — 299 ñ.
2. Ï ð î å ê ò è ð î â à í è å öèôðîâûõ âû÷èñëèòåëüíûõ ìàøèí / Ñ.À. Ìàéîðîâ, Ã.È. Íîâèêîâ,
Î.Ô. Íåìîëî÷íîâ è äð. / Ïîä ðåä. Ñ.À. Ìàéîðîâà. — Ì.: Âûñø. øê., 1972. — 344 ñ.
3. Ñ å ë þ ò è í Â . À . Ìàøèííîå êîíñòðóèðîâàíèå ýëåêòðîííûõ óñòðîéñòâ. — Ì.: Ñîâ. ðàäèî,
1977. — 384 ñ.
4. Ñ å ð ã è å í ê î È . Â . , Ê à ñ ï ø è ö ê à ÿ Ì . Ô . Ìîäåëè è ìåòîäû ðåøåíèÿ íà ÝÂÌ êîìáèíà-
òîðíûõ çàäà÷ îïòèìèçàöèè. — Ê.: Íàóê. äóìêà, 1981. — 281 ñ.
5. Ã ó ë ÿ í è ö ê è é Ë . Ô . , Ñ å ð ã è å í ê î È . Â . , Õ î ä ç è í ñ ê è é À . Í . Äèàëîãîâûé ïàêåò
ïðîãðàìì ÂÅÊÒÎÐ-2. — Êèåâ, 1981. — 55 ñ. — (ÀÍ ÓÑÑÐ. Èí-ò êèáåðíåòèêè èì. Â.Ì. Ãëóø-
êîâà;. Ïðåïð. 1981. — 63).
6. Ð â à ÷ å â Â . Ë . Òåîðèÿ R-ôóíêöèé è íåêîòîðûå åå ïðèëîæåíèÿ. — Ê.: Íàóê. äóìêà, 1982. —
552 c.
7. Ñ ò î ÿ í Þ . à . Ðàçìåùåíèå ãåîìåòðè÷åñêèõ îáúåêòîâ. — Ê.: Íàóê. äóìêà, 1975. — 240 ñ.
8. Ñ ò î ÿ í Þ . à . , à è ë ü Í . È . Ìåòîäû è àëãîðèòìû ðàçìåùåíèÿ ïëîñêèõ ãåîìåòðè÷åñêèõ îá-
úåêòîâ. — Ê.: Íàóê. äóìêà, 1976. — 247 c.
9. Ñ ò î ÿ í Þ . à . , Ï ó ò ÿ ò è í  . Ï . Ðàçìåùåíèå èñòî÷íèêîâ ôèçè÷åñêèõ ïîëåé. — Ê.: Íàóê.
äóìêà, 1981. — 184 ñ.
10. Ñ ò î ÿ í Þ . à . , ß ê î â ë å â Ñ .  . Ìàòåìàòè÷åñêèå ìîäåëè è îïòèìèçàöèîííûå ìåòîäû ãåî-
ìåòðè÷åñêîãî ïðîåêòèðîâàíèÿ. — Ê.: Íàóê. äóìêà, 1986. — 267 ñ.
11. Ñ ò î ÿ í Þ . à . , Ñ î ê î ë î â ñ ê è é  . Ç . Î ðåøåíèè îäíîé çàäà÷è ðàçìåùåíèÿ ìåòîäîì ñó-
æàþùèõñÿ îêðåñòíîñòåé // ÓÑèÌ. — 1978. — ¹ 5. — Ñ. 114–116.
12. Ñ ï ð à â î ÷ í è ê . Ñèñòåìû àâòîìàòèçèðîâàííîãî ïðîåêòèðîâàíèÿ â ðàäèîýëåêòðîíèêå /
Å.Â. Àâäååâ, Ò.À. Åðåìèí, È.Ï. Íîðåíêîâ, Ì.È. Ëåñêîâ / Ïîä ðåä. ïðîô. È.Ï. Íîðåíêîâà. —
Ì.: Ðàäèî è ñâÿçü, 1986. — 368 ñ.
13. À á ð à é ò è ñ Ë . Á . , Ø å é í à ó ñ ê à ñ Ð . È . , Æ è ë ÿ â è ÷ þ ñ Â . À . Àâòîìàòèçàöèÿ ïðîåê-
òèðîâàíèÿ ÝÂÌ. — Ì.: Ñîâ. ðàäèî, 1978. — 272 ñ.
14. À â ò î ì à ò è ç à ö è ÿ ïðîåêòèðîâàíèÿ ïå÷àòíûõ áëîêîâ ñ ìîäóëÿìè ïðîèçâîëüíîé ôîðìû /
Å.Ï. Ãåðàñèìåíêî, Â.È. Êîò, È.ß. Ëàíäàó, Â.Ì. Ñîìêèí. — Ì.: Ìàøèíîñòðîåíèå, 1979. — 167 ñ.
15. Ð ó á ë ÿ ó ñ ê à ñ Ä . À . Àëãîðèòì ðàçìåùåíèÿ ðàçíîãàáàðèòíûõ ýëåìåíòîâ íà ïå÷àòíîé
ïëàòå // Âû÷èñë. òåõí. — Êàóíàñ, Ïîëèòåõí. èí-ò. 1981. — 14. — Ñ. 100–101.
16. Ì à ò è ö ê à ñ È . - Ê . Ë . , Ð è ø ê ó ñ A . B . , × è ð è ö à Â . Þ . Ðàçìåùåíèå ðàçíîãàáàðèòíûõ ìî-
äóëåé â öåëî÷èñëåííî êðàòíûõ ïîçèöèÿõ // Òàì æå. — Êàóíàñ, Ïîëèòåõí. èí-ò. 1978. — 10. — Ñ. 71–73.
17. Ê ó ð å é ÷ è ê Â . Ì . , Ç î ë î ò ü ê î À . Þ . Àëãîðèòì ðàçìåùåíèÿ ðàçíîãàáàðèòíûõ ýëåìåíòîâ
íà êîîðäèíàòíîé ñåòêå ñ ôèêñèðîâàííûìè ðàçìåðàìè // Òàì æå. — Êàóíàñ, Ïîëèòåõí. èí-ò.
1981. — 14. — Ñ. 107–108.
18. Ï å ò ð å í ê î À . È . , Ò å ò å ë ü á à ó ì À . ß . Ôîðìàëüíîå êîíñòðóèðîâàíèå ýëåêòðîííî-âû÷èñ-
ëèòåëüíîé àïïàðàòóðû. — Ì.: Ñîâ. ðàäèî, 1979. — 256 ñ.
19. Ð ó ñ ò à ì î â È . À . , Ò þ ò è í A . A . Î ðåøåíèè çàäà÷è ðàçìåùåíèÿ êîíñòðóêòèâíûõ êîìïî-
íåíòîâ ñ ó÷åòîì òðåáîâàíèé òðàññèðîâêè // ÓÑèÌ. — 1975. — ¹ 6. — Ñ. 107–115.
20. À ð á ó ç î â Â . À . , À í ò î í î â à Í . Â . Ðåëàêñàöèîííûé àëãîðèòì ðàçìåùåíèÿ ìåòîäîì
ãðóïïîâûõ ïåðåñòàíîâîê // Àâòîìàòèçàöèÿ êîíñòðóêòîðñêîãî ïðîåêòèðîâàíèÿ ÐÝÀ è ÇÂÀ:
Òåç. äîêë. — Ïåíçà: Ïîëèòåõí. èí-ò, 1982. — Ñ. 49–50.
21. Ì à ò è ö ê à ñ È . - Ê . Ë . Àëãîðèòì ðàçìåùåíèÿ ðàçíîãàáàðèòíûõ ýëåìåíòîâ â êðàòíûå ïîçè-
öèè // ÓÑèÌ. — 1979. — ¹ 4. — Ñ. 120–123.
22. Ï à ï à ä è ì è ò ð è ó Õ . , Ñ ò à é ã ë è ö Ê . Êîìáèíàòîðíàÿ îïòèìèçàöèÿ. Àëãîðèòìû è ñëîæ-
íîñòü / Ïåð. ñ àíãë. — Ì.: Ìèð, 1985. — 510 ñ.
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2013, ¹ 2 113
23. Ã ó ë ÿ í è ö ê è é Ë . Ô . , Ò è ì î ô å å â à Í . Ê . Î ðàçìåùåíèè ðàçíîãàáàðèòíûõ ýëåìåíòîâ íà
ïå÷àòíûõ ïëàòàõ // ÓÑèÌ. — 1982. — ¹ 3. — Ñ. 50–53.
24. Ê î á ç å â à Ò .  . Ê çàäà÷å ðàçìåùåíèÿ ðàçíîãàáàðèòíûõ ýëåìåíòîâ // Òàì æå. — 1982. —
¹ 1. — Ñ. 87–89.
25. Ã ó ë ÿ í è ö ê è é Ë . Ô . , Ì à ë û ø ê î Ñ . À . , Ñ å ð ã è å í ê î È . Â . Îäèí ïîäõîä ê ôîðìàëè-
çàöèè è ðåøåíèþ çàäà÷ ðàçìåùåíèÿ ðàçíîãàáàðèòíûõ ýëåìåíòîâ ÐÝÀ // Òàì æå. — 1990. —
¹ 4. — Ñ. 63–70.
26. À ð ò å ì î â Â . Á . , Ð ÿ á î â Ë . Ï . Àëãîðèòì ðàçìåùåíèÿ ìîäóëåé ðàçíûõ ãàáàðèòîâ íà ïå-
÷àòíîé ïëàòå // Îáìåí îïûòîì â ðàäèîïðîìûøëåííîñòè. — 1977. — ¹ 2. — Ñ. 23–31.
27. Ï ó ò ÿ ò è í  . Ï . , Ý ë ü ê è í À . Á . Ìàòåìàòè÷åñêàÿ ìîäåëü çàäà÷è îïòèìèçàöèè ðàçáèåíèé â
ÀÏÊ // Âåñò. ÍÒÓ «ÕÏÈ»: Ñá. íàó÷. òð. Òåìàòè÷. âûï. «Ñèñòåìíûé àíàëèç, óïðàâëåíèå è èíôîðìà-
öèîííûå òåõíîëîãè». — Õ.: Íàö. òåõí. óí-ò «Õàðüê. ïîëèòåõí. èí-ò», 2007. — ¹ 18. — Ñ. 98–105.
28. ß ð å ì ÷ ó ê Ñ . ² . , Ì î ð ã à ë þ ê Î . Ì . Âèêîðèñòàííÿ ìåòîäó øòðàôíèõ ôóíêö³é ïðè ðîç-
â’ÿçàíí³ ì³í³ìàêñíî¿ çàäà÷³ ðîçì³ùåííÿ äæåðåë // Ñèñòåìíèé àíàë³ç. ²íôîðìàòèêà, óïðàâë³ííÿ,
ÑÀ²Ó-2010: Ìàòåð³àëè âñåóêð. íàóê.-ïðàêò. êîíô., 4–5 áåð. 2010 ð. — Çàïîð³ææÿ: Êëàñè÷.
ïðèâàò. óí-ò., 2010 — Ñ. 208–210.
29. Ê î ç ³ í ² .  . Ìàòåìàòè÷í³ ìîäåë³ ðîçì³ùåííÿ, óïàêîâêè, ðîçïîä³ëó ç óìîâîþ ³íâàð³àíòíîñò³
ùîäî ãðóï ïåðåòâîðåíü: Àâòîðåô. äèñ. ... äîêò. ô³ç.-ìàò. íàóê / ²Ê ÍÀÍÓ. — Êè¿â, 2010. — 31 ñ.
30. Á à ç è ë å â è ÷ Ð . Ï . , Ù å ð á ’ þ ê ² . Ô . Øòó÷íà ³ºðàðõ³÷íà êëàñòåðèçàö³ÿ â çàäà÷àõ
ðîçì³ùåííÿ ð³çíîãàáàðèòíèõ ýëåìåíò³â // Èñêóññòâ. èíòåëëåêò. — 2002. — ¹ 3. — Ñ. 484–489.
31. Ã è í ç á ó ð ã Á . Ä . Àëãîðèòì ðàçìåùåíèÿ ìîäóëåé íà ïëàòå // Îáìåí îïûòîì â ðàäèîïðî-
ìûøëåííîñòè. — 1972. — Âûï 4. — Ñ. 31–33.
32. × ó á È . À . , Í î â î æ è ë î â à Ì .  . Ìåòîä ðåøåíèÿ ëèíåàðèçîâàííîé çàäà÷è ðàçìåùåíèÿ
íåîðèåíòèðîâàííûõ ãåîìåòðè÷åñêèõ îáúåêòîâ // ÓÑèÌ. — 2011. — ¹ 5. — Ñ. 47–52.
33. A p p l i c a t i o n of data analysis metods and of simulated anuealing for the automatic layout of
circuits / J.R. Barra, M. Becker, E.F, Kouka, M. Tricot // Comput.Syst.Sci. end Eng. — 1987. — 2,
N 1. — Ð. 3–15.
34. S h e r l e k a r D e e p a k , J a j a J . / Imput sensitive VLSI layouts for graphs of arbitrary degree //
Lect. Notes Comput. Sci. 1988. — 319. — P. 268–277.
35. C h u n g F . R . K . , G r a h a m R . L . , S a k s M . E . A dynamic location problem for graphs //
Combinatorica. — 1989. — 9, N 2. — P. 111–131.
36. S o n g L . , V a n n e l l i A . A VLSI placement method usined tabu slarch // Microelectron J. —
1992. — 23, N 3. — P. 167–172.
37. à à ä æ è å â À . à . , Ý ô å í ä è å â à . Ä . Î òåîðåòè÷åñêîì è âåðîÿòíîñòíî-ñòàòèñòè÷åñêîì
ïîäõîäàõ îïðåäåëåíèÿ îïòèìàëüíîé ðàñêëàäêè êîìïüþòåðíîé êëàâèàòóðû // Ïðîáëåìû óïðàâ-
ëåíèÿ è èíôîðìàòèêè. — 2009. — ¹ 5. — Ñ. 100–105.
38. Ò è ì î ô ³ º â à Í . Ê . Çàëåæí³ñòü ö³ëüîâî¿ ôóíêö³¿ â çàäà÷àõ êîìá³íàòîðíî¿ îïòèì³çàö³¿ â³ä áà-
ãàòüîõ çì³ííèõ òà ã³áðèäí³ àëãîðèòìè // ³ñí. ³ííèö. ïîë³òåõí. ³í-òó. 2009. — ¹ 2. — Ñ. 130–136.
39. Ò è ì î ô ³ º â à Í . Ê . Òåîðåòèêî-÷èñëîâ³ ìåòîäè ðîçâ’ÿçàííÿ çàäà÷ êîìá³íàòîðíî¿ îïòèì³çàö³¿:
Àâòîðåô. äèñ... äîêò. òåõí. íàóê / ²Ê ÍÀÍÓ. — Êè¿â, 2007. — 32 ñ.
40. Ò è ì î ô ³ º â à Í . Ê . Çàëåæí³ñòü ö³ëüîâî¿ ôóíêö³¿ â³ä ñòðóêòóðè âõ³äíèõ äàíèõ â çàäà÷àõ
êîìá³íàòîðíî¿ îïòèì³çàö³¿ // Âåñò. ÍÒÓ «ÕÏÈ». Òåìàò. âûï. «Ñèñòåìíûé àíàëèç, óïðàâëåíèå
è èíôîðìàöèîííûå òåõíîëîãèè»: Ñá. íàó÷. òð. — Õàðüêîâ. — 2005. — ¹ 55. — C. 81–86.
41. Õ à ð ä è Ã . Ã . , Ë è ò ò ë ü â ó ä Ä æ . Å . , Ï î ë è à Ã . Íåðàâåíñòâà. — Ì.: Ãîñ. èçä-âî èíîñòð.
ëèò., 1948. — 456 ñ.
42. Ò è ì î ô å å â à Í . Ê . Ìàòðèöû â çàäà÷àõ êîìáèíàòîðíîé îïòèìèçàöèè // Ïðîáëåìû óïðàâëå-
íèÿ è èíôîðìàòèêè. — 1996. — ¹ 3. — Ñ. 104–113.
43. Ò è ì î ô å å â à Í . Ê . Îäèí àëãîðèòì îïòèìàëüíîé êîìïîíîâêè áàçîâûõ ýëåìåíòîâ â êîðïóñà
èíòåãðàëüíûõ ìèêðîñõåì // Àëãîðèòìû è ïðîãðàììû ðåøåíèÿ çàäà÷ äèñêðåòíîé îïòèìèçàöèè.
— Ê.: Èí-ò êèáåðíåòèêè ÀÍ ÓÑÑÐ. — 1980. — Ñ. 3–20.
44. Ò è ì î ô å å â à Í . Ê . Î ïðèðîäå íåîïðåäåëåííîñòè è ïåðåìåííûõ êðèòåðèÿõ â çàäà÷àõ ðàçáè-
åíèÿ // Ïðîáëåìû óïðàâëåíèÿ è èíôîðìàòèêè. — 2009. — ¹ 5. — Ñ. 88–99.
Ïîñòóïèëà 16.01.2012
114 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2013, ¹ 2
|
| id | nasplib_isofts_kiev_ua-123456789-86219 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 0023-1274 |
| language | Russian |
| last_indexed | 2025-12-07T17:15:06Z |
| publishDate | 2013 |
| publisher | Інститут кібернетики ім. В.М. Глушкова НАН України |
| record_format | dspace |
| spelling | Тимофеева, Н.К. 2015-09-09T18:04:14Z 2015-09-09T18:04:14Z 2013 Зависимость целевой функции от нескольких переменных в задаче размещения объектов и ее решение методом структурно-алфавитного поиска / Н.К. Тимофеева // Кибернетика и системный анализ. — 2013. — Т. 49, № 2. — С. 106-114. — Бібліогр.: 44 назв. — рос. 0023-1274 https://nasplib.isofts.kiev.ua/handle/123456789/86219 519.816 Проведено аналіз задачі розміщення різногабаритних об'єктів. Показано, що цільова функція в ній залежить від кількох змінних, якими є комбінаторні конфігурації різних типів. За цією ознакою вона поділяється на кілька підзадач, тому для її розв язання розроблено самоналагоджувальний алгоритм. Методом структурно-алфавітного пошуку, який грунтується на відомому розв язному випадку, розв'язується задача розміщення одногабаритних об'єктів The problem of location of various-sized objects is analyzed. The objective function is shown to depend on several variables, which are various combinatorial configurations. On this principle, it is divided into several subproblems; therefore, a self-adjusting algorithm is developed to solve it. A location problem for objects of the same size is solved by the structurally-alphabetical search, which is based on the known solvable case. ru Інститут кібернетики ім. В.М. Глушкова НАН України Кибернетика и системный анализ Системный анализ Зависимость целевой функции от нескольких переменных в задаче размещения объектов и ее решение методом структурно-алфавитного поиска Залежність цільової функції від кількох змінних в задачі розміщення об'єктів та її розв'язання методом структурно-алфавітного пошуку Dependence of objective function on several variables in location problem and its solution by the method of structurally-alphabetical search Article published earlier |
| spellingShingle | Зависимость целевой функции от нескольких переменных в задаче размещения объектов и ее решение методом структурно-алфавитного поиска Тимофеева, Н.К. Системный анализ |
| title | Зависимость целевой функции от нескольких переменных в задаче размещения объектов и ее решение методом структурно-алфавитного поиска |
| title_alt | Залежність цільової функції від кількох змінних в задачі розміщення об'єктів та її розв'язання методом структурно-алфавітного пошуку Dependence of objective function on several variables in location problem and its solution by the method of structurally-alphabetical search |
| title_full | Зависимость целевой функции от нескольких переменных в задаче размещения объектов и ее решение методом структурно-алфавитного поиска |
| title_fullStr | Зависимость целевой функции от нескольких переменных в задаче размещения объектов и ее решение методом структурно-алфавитного поиска |
| title_full_unstemmed | Зависимость целевой функции от нескольких переменных в задаче размещения объектов и ее решение методом структурно-алфавитного поиска |
| title_short | Зависимость целевой функции от нескольких переменных в задаче размещения объектов и ее решение методом структурно-алфавитного поиска |
| title_sort | зависимость целевой функции от нескольких переменных в задаче размещения объектов и ее решение методом структурно-алфавитного поиска |
| topic | Системный анализ |
| topic_facet | Системный анализ |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/86219 |
| work_keys_str_mv | AT timofeevank zavisimostʹcelevoifunkciiotneskolʹkihperemennyhvzadačerazmeŝeniâobʺektovieerešeniemetodomstrukturnoalfavitnogopoiska AT timofeevank zaležnístʹcílʹovoífunkcíívídkílʹkohzmínnihvzadačírozmíŝennâobêktívtaíírozvâzannâmetodomstrukturnoalfavítnogopošuku AT timofeevank dependenceofobjectivefunctiononseveralvariablesinlocationproblemanditssolutionbythemethodofstructurallyalphabeticalsearch |