{"id":170,"date":"2024-11-10T22:05:09","date_gmt":"2024-11-10T22:05:09","guid":{"rendered":"https:\/\/akosgombkoto.info\/?page_id=170"},"modified":"2025-01-15T09:21:59","modified_gmt":"2025-01-15T09:21:59","slug":"az-utazo-ugynok-problema","status":"publish","type":"page","link":"https:\/\/akosgombkoto.info\/en\/az-utazo-ugynok-problema\/","title":{"rendered":"The Traveling Salesman Problem"},"content":{"rendered":"

[et_pb_section fb_built=”1″ admin_label=”Header” _builder_version=”4.27.3″ _module_preset=”default” custom_padding=”0px||0px||false|false” global_colors_info=”{}”][et_pb_row column_structure=”1_2,1_2″ _builder_version=”4.27.3″ _module_preset=”default” custom_padding=”0px|||||” global_colors_info=”{}”][et_pb_column type=”1_2″ _builder_version=”4.16″ _module_preset=”default” global_colors_info=”{}”][et_pb_image src=”https:\/\/akosgombkoto.info\/wp-content\/uploads\/2025\/01\/data-science-070-2.png” title_text=”data-science-070-2″ _builder_version=”4.27.4″ _module_preset=”default” max_width_tablet=”500px” max_width_phone=”220px” max_width_last_edited=”off|tablet” max_height_tablet=”200px” max_height_phone=”100px” max_height_last_edited=”on|phone” custom_margin=”|||-8vw|false|false” custom_margin_tablet=”|||0vw|false|false” custom_margin_phone=”” custom_margin_last_edited=”on|tablet” hover_enabled=”0″ global_colors_info=”{}” sticky_enabled=”0″][\/et_pb_image][\/et_pb_column][et_pb_column type=”1_2″ _builder_version=”4.27.3″ _module_preset=”default” custom_padding=”||||false|false” custom_padding_tablet=”0px||||false|false” custom_padding_last_edited=”off|desktop” global_colors_info=”{}”][et_pb_text _builder_version=”4.27.3″ _module_preset=”d72c0383-6487-4f2c-ac5c-7d48a6376757″ header_font=”Roboto Slab||||||||” header_text_color=”#000000″ header_font_size=”52px” header_line_height=”1.2em” custom_margin=”||10px||false|false” header_font_size_tablet=”40px” header_font_size_phone=”20px” header_font_size_last_edited=”on|phone” locked=”off” global_colors_info=”{}”]<\/p>\n

Az utaz\u00f3 \u00fcgyn\u00f6k probl\u00e9ma<\/h1>\n

[\/et_pb_text][et_pb_text _builder_version=”4.27.4″ _module_preset=”default” text_font=”Roboto Mono||||||||” text_text_color=”#fcb03a” text_font_size=”18px” text_line_height=”1.8em” background_color=”#042f4f” custom_padding=”15px||15px|20px|true|false” global_module=”471″ saved_tabs=”all” global_colors_info=”{}”]<\/p>\n

Az ipari \u00e9s p\u00e9ld\u00e1ul HR-es alkalmaz\u00e1si p\u00e9ld\u00e1\u00e9rt g\u00f6rgess lejjebb az els\u0151 bekezd\u00e9sre.<\/strong><\/p>\n

[\/et_pb_text][et_pb_image src=”https:\/\/akosgombkoto.info\/wp-content\/uploads\/2024\/11\/04_Utazo_ugynok_problema_optimalizacio_brute_force_Kepernyokep-2024-11-09-224041.png” title_text=”04_Utazo_ugynok_problema_optimalizacio_brute_force_K\u00e9perny\u0151k\u00e9p 2024-11-09 224041″ show_in_lightbox=”on” _builder_version=”4.27.3″ _module_preset=”default” global_colors_info=”{}”][\/et_pb_image][\/et_pb_column][\/et_pb_row][\/et_pb_section][et_pb_section fb_built=”1″ admin_label=”Blog” _builder_version=”4.16″ _module_preset=”default” global_colors_info=”{}”][et_pb_row _builder_version=”4.16″ _module_preset=”default” global_colors_info=”{}”][et_pb_column type=”4_4″ _builder_version=”4.16″ _module_preset=”default” global_colors_info=”{}”][et_pb_text _builder_version=”4.27.3″ _module_preset=”default” text_font=”Roboto Mono||||||||” text_text_color=”#fcb03a” text_font_size=”18px” text_line_height=”1.8em” custom_padding=”15px||15px|20px|true|false” global_colors_info=”{}” background_color=”#042f4f”]<\/p>\n

Ipari \u00e9s p\u00e9ld\u00e1ul HR-es alkalmaz\u00e1si p\u00e9ld\u00e1k (nem ipari p\u00e9ld\u00e1k mint p\u00e9ld\u00e1ul a HR-es az ipari p\u00e9lda blokk alatt tal\u00e1lhat\u00f3):<\/span><\/p>\n

[\/et_pb_text][et_pb_text _builder_version=”4.27.4″ _module_preset=”default” text_font=”Roboto Mono||||||||” text_text_color=”#FFFFFF” text_font_size=”16px” text_line_height=”1.8em” background_color=”#042f4f” custom_padding=”20px|20px|20px|20px|true|true” hover_enabled=”0″ global_colors_info=”{}” sticky_enabled=”0″]<\/p>\n

Ipari alkalmaz\u00e1si p\u00e9lda:<\/strong><\/p>\n

<\/strong>Az utaz\u00f3 \u00fcgyn\u00f6k probl\u00e9m\u00e1ja (Traveling Salesman Problem, TSP) a gy\u00e1rt\u00f3iparban gyakran el\u0151fordul, f\u0151leg olyan ter\u00fcleteken, ahol a logisztikai hat\u00e9konys\u00e1g kiemelten fontos. A feladat l\u00e9nyege, hogy megtal\u00e1ljuk a legr\u00f6videbb utat, amely az \u00f6sszes sz\u00fcks\u00e9ges pontot (helysz\u00ednt, g\u00e9pet, rakt\u00e1rat stb.) \u00fagy \u00e9rinti, hogy az \u00fat a kiindul\u00e1si ponthoz t\u00e9rjen vissza.<\/p>\n

Gy\u00e1rt\u00f3ipari P\u00e9lda: Alkatr\u00e9szgy\u0171jt\u00e9s rakt\u00e1rakban:
Tegy\u00fck fel, hogy egy nagy gy\u00e1rt\u00f3\u00fczemben k\u00fcl\u00f6nb\u00f6z\u0151 alkatr\u00e9szeket kell begy\u0171jteni a gy\u00e1rt\u00e1si folyamat r\u00e9szek\u00e9nt, \u00e9s ezek az alkatr\u00e9szek k\u00fcl\u00f6nb\u00f6z\u0151 rakt\u00e1rakban, esetleg k\u00fcl\u00f6n\u00e1ll\u00f3 \u00e9p\u00fcletekben vannak. A c\u00e9l az, hogy egy targonc\u00e1s vagy gy\u0171jt\u0151robot bej\u00e1rja az \u00f6sszes rakt\u00e1rt a legr\u00f6videbb \u00faton, \u00edgy minimaliz\u00e1lva az utaz\u00e1si id\u0151t \u00e9s a k\u00f6lts\u00e9geket.<\/p>\n

Az utaz\u00f3 \u00fcgyn\u00f6k probl\u00e9ma alkalmaz\u00e1sa a p\u00e9ld\u00e1ban<\/p>\n

C\u00e9lok meghat\u00e1roz\u00e1sa:<\/p>\n

A feladat az, hogy az alkatr\u00e9szgy\u0171jt\u0151 targonca vagy robot a lehet\u0151 legr\u00f6videbb \u00faton l\u00e1togasson el minden sz\u00fcks\u00e9ges rakt\u00e1rba, \u00f6sszegy\u0171jtse az alkatr\u00e9szeket, \u00e9s t\u00e9rjen vissza a kiindul\u00e1si helyre.
Ezzel id\u0151t \u00e9s \u00fczemanyagot lehet megtakar\u00edtani, \u00e9s cs\u00f6kkenteni az alkatr\u00e9szgy\u0171jt\u00e9si ciklusid\u0151t, ami gyors\u00edtja a termel\u00e9st.<\/p>\n

Pontok \u00e9s t\u00e1vols\u00e1gok defini\u00e1l\u00e1sa:<\/p>\n

A rakt\u00e1rak helysz\u00edneit pontokk\u00e9nt defini\u00e1ljuk, \u00e9s minden egyes pont k\u00f6z\u00f6tti t\u00e1vols\u00e1got meghat\u00e1rozunk, p\u00e9ld\u00e1ul az \u00fatvonal hossz\u00e1t vagy a vezet\u00e9si id\u0151t.
Az algoritmus sz\u00e1m\u00e1ra megadjuk az \u00f6sszes rakt\u00e1r (pont) k\u00f6z\u00f6tti t\u00e1vols\u00e1gokat, \u00e9s azt, hogy az indul\u00f3 helysz\u00edn melyik ponton van.<\/p>\n

Algoritmus alkalmaz\u00e1sa:<\/p>\n

A TSP megold\u00e1s\u00e1hoz k\u00fcl\u00f6nf\u00e9le algoritmusok haszn\u00e1lhat\u00f3k (pl. brute force, dinamikus programoz\u00e1s, genetikus algoritmusok vagy heurisztikus megk\u00f6zel\u00edt\u00e9sek).
Az algoritmus kisz\u00e1m\u00edtja a legr\u00f6videbb utat, amely az \u00f6sszes rakt\u00e1rat \u00e9rinti, majd visszat\u00e9r a kiindul\u00e1si ponthoz. \u00cdgy az algoritmus optimaliz\u00e1lja a teljes utat a lehet\u0151 legr\u00f6videbb t\u00e1vols\u00e1g el\u00e9r\u00e9se \u00e9rdek\u00e9ben.<\/p>\n

Optim\u00e1lis \u00fatvonal alkalmaz\u00e1sa:<\/p>\n

Miut\u00e1n meghat\u00e1roztuk a legr\u00f6videbb utat, az alkatr\u00e9szgy\u0171jt\u0151 eszk\u00f6z (pl. targonca vagy robot) ezt az \u00fatvonalat k\u00f6veti, \u00edgy minimaliz\u00e1lva az utaz\u00e1si id\u0151t.
Az optimaliz\u00e1lt \u00fatvonal haszn\u00e1lat\u00e1val az \u00fczem jelent\u0151s id\u0151- \u00e9s k\u00f6lts\u00e9gmegtakar\u00edt\u00e1st \u00e9rhet el, ami jav\u00edtja a gy\u00e1rt\u00e1si folyamat eredm\u00e9nyess\u00e9g\u00e9t.<\/p>\n

Sk\u00e1l\u00e1zhat\u00f3s\u00e1g \u00e9s hat\u00e9konys\u00e1g jav\u00edt\u00e1sa:<\/p>\n

Ha a gy\u00e1rt\u00e1si ig\u00e9nyek vagy az \u00fatvonalak v\u00e1ltoznak, a TSP-t ism\u00e9t lefuttatva \u00faj \u00fatvonalat lehet gener\u00e1lni. Ez k\u00fcl\u00f6n\u00f6sen hasznos lehet, ha szezon\u00e1lis ingadoz\u00e1sok vannak a keresletben, \u00e9s rugalmas \u00fatvonaltervez\u00e9sre van sz\u00fcks\u00e9g.<\/p>\n

[\/et_pb_text][et_pb_text _builder_version=”4.27.4″ _module_preset=”default” text_font=”Roboto Mono||||||||” text_text_color=”#FFFFFF” text_font_size=”16px” text_line_height=”1.8em” background_color=”#042f4f” custom_padding=”20px|20px|20px|20px|true|true” hover_enabled=”0″ global_colors_info=”{}” sticky_enabled=”0″]<\/p>\n

HR-es p\u00e9lda:<\/p>\n

1. Toborz\u00f3k t\u00f6bb helysz\u00ednes interj\u00fak\u00f6r\u00fatja<\/p>\n

Toborz\u00e1s sor\u00e1n el\u0151fordulhat, hogy egy toborz\u00f3nak k\u00fcl\u00f6nb\u00f6z\u0151 helysz\u00edneken, p\u00e9ld\u00e1ul t\u00f6bb egyetemen vagy rendezv\u00e9nyhelysz\u00ednen kell megjelennie egy nap alatt. Az utaz\u00f3 \u00fcgyn\u00f6k probl\u00e9ma seg\u00edt abban, hogy a toborz\u00f3 a leghat\u00e9konyabb \u00fatvonalon haladjon, minimaliz\u00e1lva az utaz\u00e1si id\u0151t a helysz\u00ednek k\u00f6z\u00f6tt, \u00edgy t\u00f6bb id\u0151t t\u00f6lthet az interj\u00faztat\u00e1ssal vagy kapcsolat\u00e9p\u00edt\u00e9ssel.<\/p>\n

2. Munkav\u00e1llal\u00f3i j\u00f3l\u00e9ti programok szervez\u00e9se t\u00f6bb telephelyen<\/p>\n

Ha egy HR csapat j\u00f3l\u00e9ti programokat (p\u00e9ld\u00e1ul eg\u00e9szs\u00e9g\u00fcgyi sz\u0171r\u00e9seket vagy motiv\u00e1ci\u00f3s esem\u00e9nyeket) szervez k\u00fcl\u00f6nb\u00f6z\u0151 helysz\u00edneken, akkor az utaz\u00f3 \u00fcgyn\u00f6k probl\u00e9ma seg\u00edthet meghat\u00e1rozni az optim\u00e1lis \u00fatvonalat a szervez\u0151k sz\u00e1m\u00e1ra. Ez lehet\u0151v\u00e9 teszi, hogy a HR csapat tagjai gyorsabban eljussanak az egyes helysz\u00ednekre, \u00e9s az esem\u00e9nyeket id\u0151ben meg tudj\u00e1k tartani.<\/p>\n

[\/et_pb_text][et_pb_toggle title=”Az Utaz\u00f3 \u00dcgyn\u00f6k Probl\u00e9ma: (leny\u00edl\u00f3 tartalom – kattints a jobb sz\u00e9ls\u0151 + ikonra)” open_toggle_text_color=”#fcb03a” open_toggle_background_color=”#042f4f” closed_toggle_text_color=”#fcb03a” closed_toggle_background_color=”#042f4f” icon_color=”#fcb03a” open_icon_color=”#fcb03a” _builder_version=”4.27.4″ _module_preset=”default” title_font_size=”18px” closed_title_font_size=”18px” body_text_color=”#FFFFFF” body_font_size=”16px” body_line_height=”1.8em” hover_enabled=”0″ global_colors_info=”{}” sticky_enabled=”0″]<\/p>\n

Az Utaz\u00f3 \u00dcgyn\u00f6k Probl\u00e9m\u00e1t (X v\u00e1rost \u00fagy bej\u00e1rni, hogy a megtett \u00fat a legr\u00f6videbb legyen) jelen esetben egy „Brute Force” k\u00f3ddal oldottam meg. Ez egy tipikusan optimaliz\u00e1ci\u00f3s feladat.
Ez a megold\u00e1s kis X eset\u00e9n megfelel, azonban a v\u00e1rosok, helysz\u00ednek sz\u00e1m\u00e1val exponenci\u00e1lisan n\u0151 a sz\u00e1m\u00edt\u00e1si id\u0151.
A „Brute Force” k\u00f3dban, l\u00e1sd al\u00e1bb a k\u00f3dmagban, 5 helysz\u00ednt adtam meg \u00e9s m\u00e9g a permut\u00e1ci\u00f3k sz\u00e1m\u00e1t is ki\u00edrattam, mint az a Visual Studio k\u00f3dszerkeszt\u0151 parancssor\u00e1ban l\u00e1tszik a fenti k\u00e9pen, mint eredm\u00e9ny (teljes k\u00e9perny\u0151s n\u00e9z\u00e9s az aj\u00e1nlott).<\/p>\n

[\/et_pb_toggle][et_pb_toggle title=”Az Utaz\u00f3 \u00dcgyn\u00f6k Probl\u00e9ma kifejt\u00e9se: (leny\u00edl\u00f3 tartalom – kattints a jobb sz\u00e9ls\u0151 + ikonra)” open_toggle_text_color=”#fcb03a” open_toggle_background_color=”#042f4f” closed_toggle_text_color=”#fcb03a” closed_toggle_background_color=”#042f4f” icon_color=”#fcb03a” open_icon_color=”#fcb03a” _builder_version=”4.27.3″ _module_preset=”default” title_font_size=”18px” closed_title_font_size=”18px” body_text_color=”#FFFFFF” body_font_size=”16px” body_line_height=”1.8em” global_colors_info=”{}”]<\/p>\n

Az Utaz\u00f3 \u00dcgyn\u00f6k Probl\u00e9m\u00e1ja (TSP, Traveling Salesman Problem) egy klasszikus kombinatorikai optimaliz\u00e1l\u00e1si probl\u00e9ma, amelynek c\u00e9lja egy olyan leghat\u00e9konyabb \u00fatvonal megtal\u00e1l\u00e1sa, amelyben egy \u00fcgyn\u00f6k (vagy elad\u00f3) k\u00fcl\u00f6nb\u00f6z\u0151 v\u00e1rosokat l\u00e1togat meg, minden v\u00e1rost pontosan egyszer, \u00e9s v\u00e9g\u00fcl visszat\u00e9r a kiindul\u00f3 v\u00e1rosba. Az \u00fatvonal c\u00e9lja, hogy a megtett t\u00e1vols\u00e1g minim\u00e1lis legyen.<\/p>\n

A probl\u00e9ma l\u00e9nyeges elemei:
V\u00e1rosok halmaza: Van egy adott sz\u00e1m\u00fa v\u00e1ros, amelyeket az \u00fcgyn\u00f6knek meg kell l\u00e1togatnia.
T\u00e1vols\u00e1gok: Az adott v\u00e1rosok k\u00f6z\u00f6tti t\u00e1vols\u00e1gok ismertek (ez lehet fizikai t\u00e1vols\u00e1g, id\u0151, k\u00f6lts\u00e9g stb.).
C\u00e9l: Az \u00fcgyn\u00f6knek az \u00f6sszes v\u00e1rost \u00fagy kell megl\u00e1togatnia, hogy:
Minden v\u00e1rost pontosan egyszer l\u00e1togat meg.
V\u00e9g\u00fcl visszat\u00e9r a kiindul\u00f3 v\u00e1rosba.
A teljes \u00fatvonal hossza, ideje vagy k\u00f6lts\u00e9ge minim\u00e1lis legyen.
Mi\u00e9rt neh\u00e9z a TSP?
A TSP egy NP-neh\u00e9z (Non-polynomial) probl\u00e9ma, ami azt jelenti, hogy nem l\u00e9tezik olyan ismert algoritmus, amely minden esetben gyorsan (polinomi\u00e1lis id\u0151 alatt) oldja meg a probl\u00e9m\u00e1t, ha a v\u00e1rosok sz\u00e1ma n\u0151. A probl\u00e9m\u00e1t az optim\u00e1lis megold\u00e1s keres\u00e9se jellemzi. Az \u00f6sszes lehets\u00e9ges \u00fatvonal megvizsg\u00e1l\u00e1sa exponenci\u00e1lisan n\u0151 a v\u00e1rosok sz\u00e1m\u00e1nak n\u00f6veked\u00e9s\u00e9vel, ami miatt a probl\u00e9ma nagyon gyorsan sz\u00e1m\u00edt\u00e1sig\u00e9nyess\u00e9 v\u00e1lik.<\/p>\n

P\u00e9lda:
Tegy\u00fck fel, hogy egy \u00fcgyn\u00f6knek 4 v\u00e1rost kell megl\u00e1togatnia, \u00e9s az al\u00e1bbi t\u00e1vols\u00e1gokat ismerj\u00fck:<\/p>\n

V\u00e1rosok\u00a0 \u00a0 \u00a0 \u00a0A\u00a0 \u00a0B\u00a0 \u00a0C\u00a0 \u00a0D
\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0A\u00a0 0\u00a0 \u00a012\u00a0 18\u00a0 25
\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0B\u00a0 12\u00a0 0\u00a0 \u00a020\u00a0 30
\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0C\u00a0 18\u00a0 20\u00a0 0\u00a0 \u00a015
\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0D\u00a0 25\u00a0 30\u00a0 15\u00a0 0<\/p>\n

A k\u00e9rd\u00e9s az, hogy milyen sorrendben kell megl\u00e1togatni a v\u00e1rosokat, hogy a teljes t\u00e1vols\u00e1g a lehet\u0151 legr\u00f6videbb legyen. Az \u00f6sszes lehets\u00e9ges \u00fatvonal ebben az esetben 3! (3 faktori\u00e1lis – mivel a kiindu\u00e1si v\u00e1ros r\u00f6gz\u00edtett) = 6 lehets\u00e9ges kombin\u00e1ci\u00f3t jelent, teh\u00e1t az optim\u00e1lis megold\u00e1s megtal\u00e1l\u00e1s\u00e1hoz ezek mindegyik\u00e9t ki kell pr\u00f3b\u00e1lni. A probl\u00e9ma bonyolults\u00e1ga exponenci\u00e1lisan n\u0151, ahogy a v\u00e1rosok sz\u00e1ma n\u0151.<\/p>\n

Megold\u00e1sok:<\/p>\n

Brute-force („tiszta er\u0151b\u0151l” val\u00f3 keres\u00e9s): Minden lehets\u00e9ges \u00fatvonal kipr\u00f3b\u00e1l\u00e1sa (de gyors nem lesz sok v\u00e1ros eset\u00e9n).<\/p>\n

Heurisztikus algoritmusok: Mivel az optim\u00e1lis megold\u00e1s megtal\u00e1l\u00e1sa t\u00fal k\u00f6lts\u00e9ges lehet, heurisztikus algoritmusok (p\u00e9ld\u00e1ul a legk\u00f6zelebbi szomsz\u00e9d algoritmus) pr\u00f3b\u00e1lnak egy j\u00f3, de nem garant\u00e1ltan optim\u00e1lis megold\u00e1st tal\u00e1lni.<\/p>\n

Dinamikus programoz\u00e1s: Vannak dinamikus programoz\u00e1si algoritmusok, amelyek k\u00e9pesek hat\u00e9konyabban megoldani a probl\u00e9m\u00e1t kisebb v\u00e1rossz\u00e1mn\u00e1l, de ezek m\u00e9g mindig nem oldj\u00e1k meg a probl\u00e9m\u00e1t nagy v\u00e1rossz\u00e1m eset\u00e9n polinomi\u00e1lis id\u0151ben.<\/p>\n

Genetikai algoritmusok \u00e9s m\u00e1s evol\u00faci\u00f3s algoritmusok: Ezek a term\u00e9szetes szelekci\u00f3 elv\u00e9t alkalmazz\u00e1k a probl\u00e9m\u00e1k megold\u00e1s\u00e1ra.<\/p>\n

\u00d6sszegz\u00e9s:<\/p>\n

Az Utaz\u00f3 \u00dcgyn\u00f6k Probl\u00e9m\u00e1ja a gyakorlatban gyakran el\u0151fordul\u00f3, de sz\u00e1m\u00edt\u00e1silag neh\u00e9z probl\u00e9ma, amely az optim\u00e1lis \u00fatvonal keres\u00e9s\u00e9re \u00f6sszpontos\u00edt adott v\u00e1rosok halmaz\u00e1n. B\u00e1r a probl\u00e9m\u00e1ra nem ismert gyors algoritmus, sokf\u00e9le megk\u00f6zel\u00edt\u00e9st alkalmaznak a hat\u00e9kony megold\u00e1sok keres\u00e9s\u00e9re, k\u00fcl\u00f6n\u00f6sen olyan esetekben, amikor a pontos megold\u00e1s nem el\u00e9rhet\u0151 vagy nem sz\u00fcks\u00e9ges.<\/p>\n

[\/et_pb_toggle][et_pb_toggle title=”K\u00f3dmag: (leny\u00edl\u00f3 tartalom – kattints a jobb sz\u00e9ls\u0151 + ikonra)” open_toggle_text_color=”#fcb03a” open_toggle_background_color=”#042f4f” closed_toggle_text_color=”#fcb03a” closed_toggle_background_color=”#042f4f” icon_color=”#fcb03a” open_icon_color=”#fcb03a” _builder_version=”4.27.3″ _module_preset=”default” title_font_size=”18px” closed_title_font_size=”18px” body_text_color=”#FFFFFF” body_font_size=”16px” body_line_height=”1.8em” global_colors_info=”{}”]<\/p>\n

import itertools\n\n# T\u00e1vols\u00e1gm\u00e1trix: t\u00e1vols\u00e1gok (b\u00e1rmilyen egys\u00e9gben) a v\u00e1rosok, t\u00e1rgyak, berendez\u00e9sek k\u00f6z\u00f6tt (5 v\u00e1rosra, t\u00e1rgyra, berendez\u00e9sre \u00e9rt\u00e9kekkel)\ndistance_matrix = [\n    [0, 12, 18, 22, 28],\n    [12, 0, 26, 24, 32],\n    [18, 26, 0, 34, 16],\n    [22, 24, 34, 0, 20],\n    [28, 32, 16, 20, 0]\n]\n\n# A v\u00e1rosok, t\u00e1rgyak, berendez\u00e9sek sz\u00e1ma\nnum_things = len(distance_matrix)\n\n# Az \u00f6sszes v\u00e1ros, t\u00e1rgy, berendez\u00e9s felsorol\u00e1sa (0, 1, 2, ..., num_things-1)\nthings = list(range(num_things))\n\n# Legr\u00f6videbb t\u00e1vols\u00e1g \u00e9s legjobb \u00fatvonal\nshortest_distance = float('inf')\nbest_route = None\nperm_num = 0\n\n# Minden lehets\u00e9ges permut\u00e1ci\u00f3 (\u00fatvonal) kisz\u00e1m\u00edt\u00e1sa\nfor perm in itertools.permutations(things[1:]):  # Az els\u0151 helysz\u00edn mindig ugyanaz, \u00edgy azt fix\u00e1ljuk\n    route = [0] + list(perm) + [0]  # K\u00f6r\u00fatvonal l\u00e9trehoz\u00e1sa\n    current_distance = 0\n    perm_num = perm_num+1\n\n    # Az \u00fatvonal \u00f6sszes t\u00e1vols\u00e1g\u00e1nak kisz\u00e1m\u00edt\u00e1sa\n    \n    for i in range(len(route) - 1):\n        current_distance += distance_matrix[route[i]][route[i + 1]]\n        \n    \n    print(\"Permut\u00e1ci\u00f3 sorsz\u00e1ma :\", perm_num, \"   \", \"T\u00e1vols\u00e1g:\", current_distance, \"t\u00e1vols\u00e1gegys\u00e9g\")  \n\n    # Ha tal\u00e1ltunk r\u00f6videbb \u00fatvonalat, friss\u00edtj\u00fck a legjobb \u00fatvonalat\n    if current_distance < shortest_distance:\n        shortest_distance = current_distance\n        best_route = route\n\nprint()\nprint(f\"Legr\u00f6videbb \u00fatvonal: {best_route}\")\nprint(f\"Legr\u00f6videbb t\u00e1vols\u00e1g: {shortest_distance}\")<\/pre>\n
<\/code><\/p>\n
[\/et_pb_toggle][\/et_pb_column][\/et_pb_row][\/et_pb_section]<\/p>\n","protected":false},"excerpt":{"rendered":"
Az utaz\u00f3 \u00fcgyn\u00f6k probl\u00e9maAz ipari \u00e9s p\u00e9ld\u00e1ul HR-es alkalmaz\u00e1si p\u00e9ld\u00e1\u00e9rt g\u00f6rgess lejjebb az els\u0151 bekezd\u00e9sre. Ipari \u00e9s p\u00e9ld\u00e1ul HR-es alkalmaz\u00e1si p\u00e9ld\u00e1k (nem ipari p\u00e9ld\u00e1k mint p\u00e9ld\u00e1ul a HR-es az ipari p\u00e9lda blokk alatt tal\u00e1lhat\u00f3):Ipari alkalmaz\u00e1si p\u00e9lda: Az utaz\u00f3 \u00fcgyn\u00f6k probl\u00e9m\u00e1ja (Traveling Salesman Problem, TSP) a gy\u00e1rt\u00f3iparban gyakran el\u0151fordul, f\u0151leg olyan ter\u00fcleteken, ahol a logisztikai hat\u00e9konys\u00e1g […]<\/p>\n","protected":false},"author":1,"featured_media":0,"parent":0,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"_et_pb_use_builder":"on","_et_pb_old_content":"","_et_gb_content_width":"","footnotes":""},"class_list":["post-170","page","type-page","status-publish","hentry"],"_links":{"self":[{"href":"https:\/\/akosgombkoto.info\/en\/wp-json\/wp\/v2\/pages\/170","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/akosgombkoto.info\/en\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/akosgombkoto.info\/en\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/akosgombkoto.info\/en\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/akosgombkoto.info\/en\/wp-json\/wp\/v2\/comments?post=170"}],"version-history":[{"count":37,"href":"https:\/\/akosgombkoto.info\/en\/wp-json\/wp\/v2\/pages\/170\/revisions"}],"predecessor-version":[{"id":689,"href":"https:\/\/akosgombkoto.info\/en\/wp-json\/wp\/v2\/pages\/170\/revisions\/689"}],"wp:attachment":[{"href":"https:\/\/akosgombkoto.info\/en\/wp-json\/wp\/v2\/media?parent=170"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}