www.wikidata.uk-ua.nina.az

Комбінаторна оптимізація англ Combinatorial optimization розділ теорії оптимізації Розглядає задачі оптимізації множина

Комбінаторна оптимізація

Комбінаторна оптимізація (англ. Combinatorial optimization) — розділ теорії оптимізації. Розглядає задачі оптимізації множина розв'язків яких дискретна або може бути зведена до дискретної.

Визначення Редагувати

Задача дискретної оптимізації визначається як четвірка , де:

  •  — формальна мова над множиною розв'язна за поліноміальний час;
  •  — підмножина для кожного ; існує поліном такий, що для всіх та всіх , та мови та розв'язні за поліноміальний час;
  • є функцією, обчислюваною за поліноміальний час;

Елементи називають екземплярами . Для кожного екземпляру елементи називають припустимими розв'язками .

Приклади Редагувати

Задача комівояжера Редагувати

В задачі комівояжера задане ціле та відстані між всіма парами міст у вигляді матриці , де . Обхід — це замкнений маршрут, що проходить через кожне місто один раз. Задача полягає у відшуканні обходу з найменшою довжиною.

Можна взяти F={всі перестановки з об'єктів}. Кожна перестановка є обходом, якщо інтерпретувати як місто, відвідуване після міста , . Тоді вартість відображає в

Див. також Редагувати

Примітки Редагувати

  1. Х. Пападимитриу, К. Стайглиц. Комбинаторная оптимизация, алгоритмы и сложность. Мир. 

Література Редагувати

Див. також Редагувати


Це незавершена стаття з математики.
Ви можете допомогти проєкту, виправивши або дописавши її.
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри
Дата публікації:
Kombinatorna optimizaciya angl Combinatorial optimization rozdil teoriyi optimizaciyi Rozglyadaye zadachi optimizaciyi mnozhina rozv yazkiv yakih diskretna abo mozhe buti zvedena do diskretnoyi Zmist 1 Viznachennya 2 Prikladi 2 1 Zadacha komivoyazhera 3 Div takozh 4 Primitki 5 Literatura 6 Div takozhViznachennya RedaguvatiZadacha diskretnoyi optimizaciyi viznachayetsya yak chetvirka P X S x x X c g o a l displaystyle mathcal P X S x x in X c goal nbsp de X displaystyle X nbsp formalna mova nad mnozhinoyu 0 1 displaystyle 0 1 nbsp rozv yazna za polinomialnij chas S x displaystyle S x nbsp pidmnozhina 0 1 displaystyle 0 1 nbsp dlya kozhnogo x X displaystyle x in X nbsp isnuye polinom p displaystyle p nbsp takij sho s i z e y p s i z e x displaystyle size y leq p size x nbsp dlya vsih y S x displaystyle y in S x nbsp ta vsih x X displaystyle x in X nbsp ta movi x y x X y S x displaystyle x y x in X y in S x nbsp ta x X S x displaystyle x in X S x emptyset nbsp rozv yazni za polinomialnij chas c x y x X y S x Q displaystyle c x y x in X y in S x to Q nbsp ye funkciyeyu obchislyuvanoyu za polinomialnij chas g o a l m a x m i n displaystyle goal in max min nbsp Elementi X displaystyle X nbsp nazivayut ekzemplyarami P displaystyle mathcal P nbsp Dlya kozhnogo ekzemplyaru x displaystyle x nbsp elementi S x displaystyle S x nbsp nazivayut pripustimimi rozv yazkami x displaystyle x nbsp Prikladi RedaguvatiZadacha komivoyazhera Redaguvati Dokladnishe Zadacha komivoyazheraV zadachi komivoyazhera zadane cile n gt 0 displaystyle n gt 0 nbsp ta vidstani mizh vsima parami n displaystyle n nbsp mist u viglyadi n n displaystyle n times n nbsp matrici d i j displaystyle d ij nbsp de d i j Z displaystyle d ij in Z nbsp Obhid ce zamknenij marshrut sho prohodit cherez kozhne misto odin raz Zadacha polyagaye u vidshukanni obhodu z najmenshoyu dovzhinoyu 1 Mozhna vzyati F vsi perestanovki p displaystyle pi nbsp z n displaystyle n nbsp ob yektiv Kozhna perestanovka p displaystyle pi nbsp ye obhodom yaksho interpretuvati p j displaystyle pi j nbsp yak misto vidviduvane pislya mista j displaystyle j nbsp j 1 n displaystyle j 1 dots n nbsp Todi vartist c displaystyle c nbsp vidobrazhaye p displaystyle pi nbsp v j 1 n d j p j displaystyle sum j 1 n d j pi j nbsp Div takozh RedaguvatiZadacha pro 1 centrPrimitki Redaguvati H Papadimitriu K Stajglic Kombinatornaya optimizaciya algoritmy i slozhnost Mir Literatura RedaguvatiBernhard Korte en 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 Sergienko I V Gulyanickij L F Sirenko S I Klassifikaciya prikladnyh metodov kombinatornoj optimizacii Arhivovano 13 Sichnya 2016 u Wayback Machine info Arhivovano 19 Sichnya 2016 u Wayback Machine Kibernetika i sistemnyj analiz 2009 5 S 71 83 Bibliogr 74 nazv ros L F Gulyanickij S I Sirenko Gibridnaya metaevristika osnovannaya na optimizacii muravinymi koloniyami i N metode Arhivovano 22 Sichnya 2016 u Wayback Machine info Arhivovano 23 Sichnya 2016 u Wayback Machine Kompyuternaya matematika 2009 Vyp 1 S 142 151 Ob avtorah str 151 Div takozh Redaguvati nbsp Portal Matematika Zadacha komivoyazhera Zadacha pakuvannya ryukzaka Zadacha prokatu lizh Obchislyuvalna skladnist Cilochiselne programuvannya nbsp Ce nezavershena stattya z matematiki Vi mozhete dopomogti proyektu vipravivshi abo dopisavshi yiyi Otrimano z https uk wikipedia org w index php title Kombinatorna optimizaciya amp oldid 35053664