Перегляд вихідного коду сторінки Комбінаторна оптимізація

'''Комбінаторна оптимізація''' ({{lang-en|Combinatorial optimization}})&nbsp;— розділ [[Теорія оптимізації|теорії оптимізації]]. Розглядає задачі оптимізації, у яких [[множина розв'язків]] є [[цілі числа|дискретною]] або може бути зведена до дискретної.

== Визначення ==

Задача [[Дискретна оптимізація|дискретної оптимізації]] визначається як четвірка <math>\mathcal P = (X, (S_x)_{x \in X}, c, goal)</math>, де:
* <math>X</math>&nbsp;— формальна мова над множиною <math>\{0, 1\}</math> розв'язна за [[Клас складності P|поліноміальний час]];
* <math>S_x</math>&nbsp;— підмножина <math>\{0, 1\}^*</math> для кожного <math>x\in X</math>; існує поліном <math>p</math> такий, що <math>size(y) \leq p(size(x))</math> для всіх <math>y \in S_x</math> та всіх <math>x \in X</math>, та мови <math>\{(x, y) : x \in X, y \in S_x\}</math> та <math>\{ x \in X : S_x = \emptyset \}</math> розв'язні за поліноміальний час;
* <math>c : \{(x, y) : x \in X, y \in S_x \} \to Q</math> є функцією, обчислюваною за поліноміальний час;
* <math>goal \in \{max, min\}</math>

Елементи <math>X</math> називають екземплярами <math>\mathcal P</math>. Для кожного екземпляру <math>x</math> елементи <math>S_x</math> називають ''припустимими розв'язками'' <math>x</math>.

== Приклади ==

=== Задача комівояжера ===
{{Main|Задача комівояжера}}

В задачі комівояжера задане ціле <math>n>0</math> та відстані між всіма парами <math>n</math> міст у вигляді <math>(n \times n)</math> матриці <math>[d_{ij}]</math>, де <math>d_{ij}\in Z^+</math>. [[Цикл (теорія графів)|Обхід]]&nbsp;— це замкнений [[Шлях (теорія графів)|маршрут]], що проходить через кожне місто один раз. Задача полягає у відшуканні обходу з найменшою довжиною.<ref>{{cite book|title=Комбинаторная оптимизация, алгоритмы и сложность|author=Х. Пападимитриу, К. Стайглиц|видавництво=Мир}}</ref>

Можна взяти ''F''={всі [[перестановка|перестановки]] <math>\pi</math> з <math>n</math> об'єктів}. Кожна перестановка <math>\pi</math> є обходом, якщо інтерпретувати <math>\pi(j)</math> як місто, відвідуване після міста <math>j</math>, <math>j = 1, \dots, n</math>. Тоді вартість <math>c</math> відображає <math>\pi</math> в <math>\sum_{j=1}^n d_{j\pi(j)}.</math>

== Див. також ==
* [[Дискретна оптимізація]]
* [[Задача про 1-центр]]

== Примітки ==
{{reflist}}

== Література ==

* {{iw2|Bernhard Korte}}, {{iw2|Jens Vygen||de}}: ''Combinatorial Optimization: Theory and Algorithms.'' In: ''Algorithms and Combinatorics'' Band 21, 4. Auflage, Springer-Verlag, Berlin 2008, ISBN 978-3-540-71843-7.
* [[Сергієнко Іван Васильович (академік)|Сергиенко И. В.]], {{comment|Гуляницкий Л. Ф.|Гуляницький Леонід Федорович}}, {{comment|Сиренко С. И.|Сіренко Сергій Ігоревич}} [http://dspace.nbuv.gov.ua/xmlui/bitstream/handle/123456789/44402/07-Sergienko.pdf Классификация прикладных методов комбинаторной оптимизации] {{Webarchive|url=https://web.archive.org/web/20160113045215/http://dspace.nbuv.gov.ua/xmlui/bitstream/handle/123456789/44402/07-Sergienko.pdf |date=13 Січня 2016 }} ([http://dspace.nbuv.gov.ua/handle/123456789/44402 info] {{Webarchive|url=https://web.archive.org/web/20160119045929/http://dspace.nbuv.gov.ua/handle/123456789/44402 |date=19 Січня 2016 }}) // [[Кібернетика та системний аналіз|Кибернетика и системный анализ]].&nbsp;— 2009.&nbsp;— №&nbsp;5.&nbsp;— С. 71-83.&nbsp;— Бібліогр.: 74 назв. {{ref-ru}}
* Л.&nbsp;Ф.&nbsp;Гуляницкий, С.&nbsp;И.&nbsp;Сиренко. [http://irbis-nbuv.gov.ua/cgi-bin/irbis_nbuv/cgiirbis_64.exe?C21COM=2&I21DBN=UJRN&P21DBN=UJRN&IMAGE_FILE_DOWNLOAD=1&Image_file_name=PDF/Koma_2009_1_17.pdf Гибридная метаэвристика, основанная на оптимизации муравьиными колониями и Н-методе] {{Webarchive|url=https://web.archive.org/web/20160122064654/http://irbis-nbuv.gov.ua/cgi-bin/irbis_nbuv/cgiirbis_64.exe?C21COM=2&I21DBN=UJRN&P21DBN=UJRN&IMAGE_FILE_DOWNLOAD=1&Image_file_name=PDF%2FKoma_2009_1_17.pdf |date=22 Січня 2016 }} ([http://www.irbis-nbuv.gov.ua/cgi-bin/irbis_nbuv/cgiirbis_64.exe?I21DBN=LINK&P21DBN=UJRN&Z21ID=&S21REF=10&S21CNR=20&S21STN=1&S21FMT=ASP_meta&C21COM=S&2_S21P03=FILA=&2_S21STR=Koma_2009_1_17 info] {{Webarchive|url=https://web.archive.org/web/20160123022550/http://www.irbis-nbuv.gov.ua/cgi-bin/irbis_nbuv/cgiirbis_64.exe?I21DBN=LINK&P21DBN=UJRN&Z21ID=&S21REF=10&S21CNR=20&S21STN=1&S21FMT=ASP_meta&C21COM=S&2_S21P03=FILA=&2_S21STR=Koma_2009_1_17 |date=23 Січня 2016 }}) // Компьютерная математика.&nbsp;— 2009.&nbsp;— Вып. 1.&nbsp;— С. 142—151. / '''Об авторах:''' стр. 151.

== Див. також ==
{{Портал|Математика}}
* [[Задача комівояжера]],
* [[Задача пакування рюкзака]],
* [[Задача прокату лиж]],
* [[Обчислювальна складність]].
* [[Цілочисельне програмування]]

{{Math-stub}}

[[Категорія:Комбінаторна оптимізація]]