Lankide:GarikoitzArtola/Proba orria

Wikipedia, Entziklopedia askea


Konplexutasun konputazionala[aldatu | aldatu iturburu kodea]

Saltzaile ibiltariaren problema NP-gogorra dela frogatu da (zehatzago esanda, NP-osoa da FPNP konplexutasun-klaserako; ikus funtzioaren problema), eta problemaren honako bertsioa NP-osoa da: distantzien matrize bat eta zenbaki bat emanik, erabaki distantzia baino txikiagoa den ibilbidea existitzen den. "Bidaiariaren Problema Botila-lepoduna" (ingelesez, Bottleneck TSP) ere NP-gogorra da. Problemak NP-gogor izaten jarraitzen du hirien arteko distantziak planoan distantzia euklidestarra erabiliz kalkulatzen badira ere. Problemaren planteamendutik hiri bakoitza "behin bakarrik" bisitatzeko eskakizuna kenduta ere problemak NP-gogor izaten jarraitzen du.

Hurbiltze-algoritmoen konplexutasuna[aldatu | aldatu iturburu kodea]

Problemaren planteamendu orokorra, hau da, hiri guztiak behin bakarrik bisitatu eta hasierako hirian amaitzen den ibilbiderik laburrena aurkitzea, NPO-osoa da (NP-Optimization problem, NPO).[1] Distantziaren neurria metrika bada (eta, beraz, simetrikoa), problema APX-oso bihurtzen da (ingelesez, APproXimable-complete), hau da, NP optimizazio problema da baina konstante batez mugatutako hurbilketa bat kalkulatzea posiblea da hurbilketa-algoritmo baten bidez denbora polinomialean.[2] Christofidesen algoritmoak gehienez ibilbide laburrena baino 1.5 aldiz luzeagoa den ibilaldia itzultzen du.[3][4][5]

Distantziak 1era eta 2ra mugatzen badira (metrika bat izanik), hurbilketa-ratioa 8/7-ekoa bihurtzen da, hau da gehienez 8/7 aldiz luzeagoa den ibilaldia aurkitzen da. [6] Desberdintza triangeluarra betetzen duten problema asimetrikoetan, duela gutxira arte emaitza denbora logaritmikoan itzultzen zuten algoritmoak besterik ez ziren ezagutzen. [7] 2018an, Svensson-ek, Tarnawski-k eta Végh-ek faktore konstante bateko hurbilketa metodoa garatu zuten.[8] Gaur egungo algoritmo onena Traub-ek eta Vygen-ek garatu zutena da, errendimendua lortzen du.[9] Ezagutzen den hurbiltasunerako bornerik onena 75/74-koa da.[10]

Bidaiariaren problemaren maximizatze-bertsiorako, hau da, hiri guztiak behin bakarrik bisitatu eta hasierako hirian amaitzen den ibilbiderik luzeena aurkitzearen problemarako, soluzioa 63/38-an hurbil daiteke.[11] Distantziaren funtzioa simetrikoa bada, algoritmo determinista bat erabiliz ibilbide luzeena 4/3-ean hurbil daiteke [12] eta ausazkotasuna erabiltzen duen algoritmo baten bidez -ean.[13]

Gizakien eta animalien errendimendua[aldatu | aldatu iturburu kodea]

Bidaiariaren problemaren ebazpenak psikologia kognitiboko ikertzaileen arreta erakarri du. Izan ere, gizakia problemaren soluziotik oso gertu dauden ibilbideak azkar (ia denbora linealean) aurkitzeko gai dela ikusi da. Hiri kopuruaren arabera errendimendua aldatzen da: 10-20 hiriko problemetan (10-20 erpin dituzten grafoetan) aurkitutako ibilbidea optimotik %1 aldendu daiteke eta problema handiagoetan (120 erpineko grafoetan) %11.[14][15] Gizakiek problema ebazteko eta optimotik gertu dauden soluzioak erraz (itxuraz behintzat) aurkitzeko erakutsi duten ahalmenak ikertzaileak hipotesiak egitera eraman ditu. Hipotesi horietako batek dio, gizakiek heuristikoak erabiltzen ditutela. Horren inguruko teoriarik ezagunenak ganbiltasunaren hipotesia (ingelesez, convex-hull hypothesis) eta gurutzatzea saihestearen heuristikoa (ingelesez, crossing-avoidance heuristic) dira.[16][17][18] Hala ere, giza errendimendua askotarikoa dela ikusi da, gizaki batzuek trebetasun handia erakusten duten arren beste batzuek traketsak dira soluzio onak aurkitzen. Gainera, grafoaren geometriak ere eragin handia sortzen du problemaren ebazpenaren errendimenduan.[19][20][21] Gizakiek erabiltzen dituzten estrategiak ulertu eta emulatuz gero, bidaiariaren problema ebazteko algoritmo hobeak aurkitu ahal izango direla ondorioztatu da egindako ikerketetatik.[22] Horrekin batera, giza pentsamenduaren mekanismoak hobeto ezagutzea lortu da.[23] "Journal of Problem Solving" aldizkari zientifikoaren lehen alea bidaiariaren problemaren ebazpenean gizakiek erakutsitako errendimenduari buruzkoa izan zen,[24] eta 2011ko argitalpen batean gaiari buruzko dozenaka artikulu zientifiko zerrendatzen dira.[25]

2011ean animalien kognizioari buruzko ikerketa bat egin zen. Ikerketaren izenburua "Let the Pigeon Drive the Bus" zen, euskaraz "Utzi usoari autobusa gidatzen". "Don't let the Pigeon Drive the Bus!" haurrentzako liburu ezagunaren izenburutik abiatuz jarri zitzaion izen hori ikerketa proiektuari. Helburua usoek espazioari buruz duten ezagutza aztertzea zen. Haien hegaldi-ereduak aztertu nahi zituzten, bidaiariaren problemaren ebazpenerako estrategia berriak bilatzeko asmoz. Horretarako, laborategi batean txorientzako hainbat elikagailu jarri zituzten ilarrekin. Hasierako esperimentuan, usoak laborategiko txoko batean kokatu eta aske utzi zituzten, elikagailuetako ilarrak jatera joan zitezen. Ikertzaileek ikusi zuten usoak hurbilen zegoen elikatzailera joaten zirela, gehienetan. Bigarren esperimentuan ez zuten ilar kopuru bera jarri elikagailu guztietan, gertuen zeudenetan oso gutxi jarri zuten eta urrutiago zeudenetan gehiago. Usoak askatzean, haiek egindako hegaldiak aztertuz konturatu ziren hurbilen zegoen elikagailura joateak elikagailu guztiak bisitatu behar izatea eragiten zuen kasuetan, usoek haien jokaera aldatzen zutela. Horrela, usoek nora joan erabaki behar zutenean hurbil egoteak garrantzia bazuela ikusi zuten arren, haien hegaldia hainbat urratsetan planifikatzeko gai zirela ondorioztatu zuten eta batzuetan urrunago dagoen elikagailura joatea erabakitzen zutela. Hori horrela egiten zuten, batez ere beti hurbilenera joatea eraginkorra ez zenean (ilar gutxi zegoenean hurbilenekoetan). [26] Emaitza horiek bat datoz primateak ez diren beste animalia batzuekin egindako esperimentuetako emaitzekin, eta frogatzen dute primateak ez diren animalia batzuek gai direla ibilbide konplexuak planifikatzeko. Hortaz, badirudi primate ez diren animaliek espazioa kudeatzeko trebetasun kognitibo sofistikatu samarra izan dezaketela.

Konputazio naturala[aldatu | aldatu iturburu kodea]

Badira naturan inspiratuta garatu izan diren ebazpen metodoak. Bidaiariaren problema euklidestarrerako hurbilpen soluzio bat aurkitzeko, adibidez, partikulen populazio bat difusio-sare batean zehar mugitzean materialaren portaera morfologikoa nola egokitzen den aztertu izan da. Ikerketa lan batean Physarum polycephalum motako ameba hainbat puntuz (elikadura-iturriz) osatutako sare batean kokatu zuten, eta ikusi zen ameba tamainaz txikitzen zela elikadura-puntuen konfiguraziora egokituz zioan neurrian. Eskuz amebaren perimetroa jarraituz gero, elikadura-puntuen arteko ibilbide bat aurkitu ahal izango litzateke. Ibilbide hori saltzaile ibiltariaren problemarako soluzio optimoaren hurbilpen moduan ikus daiteke.[27]

Algoritmoen ebaluazioa[aldatu | aldatu iturburu kodea]

Bidaiariaren problema ebazteko algoritmoak ebaluatzeko, badira liburutegi estandarrak. TSPLIB liburutegian hainbat adibideren instantziak eta erlazionatutako problemak aurki daitezke (ikus TSPLIB kanpo erreferentzien atalean)[28] Instantzia horietako asko egungo hirien zerrendak eta gaur egungo zirkuitu inprimatuen diseinuak dira.

Kulturan eta zineman[aldatu | aldatu iturburu kodea]

  • "Travelling Salesman" Timothy Lanzone-k 2012an zuzendutako filma da. Ameriketako Estatu Batuetako gobernuak kontratatutako lau matematikariren istorioa kontatzen da. Informatikaren historiako problemarik zailena ebazteko kontratatuak izan dira: P vs NP problema ebazteko[29]
  • Bob Bosch matematikariak eta Tom Wexler informatikariak bidaiariaren problemaren soluzioak erabiltzen dituzte artelanak puntuen eta haietatik pasatzen diren ibilbideen bidez adierazteko. "Optimization art" edo "opt-art" deitzen zaio teknika horri. [30]


Ikus, gainera[aldatu | aldatu iturburu kodea]


  1. ↑ Orponen, P.; Mannila, H. (1987). On approximation preserving reductions: Complete problems and robust measures' (Report). Department of Computer Science, University of Helsinki. Technical Report C-1987–28.
  2. ↑ Papadimitriou & Yannakakis (1993).
  3. ↑ Christofides (1976).
  4. ↑ Serdyukov, Anatoliy I. (1978), "О некоторых экстремальных обходах в графах" [On some extremal walks in graphs] (PDF), Upravlyaemye Sistemy (in Russian), 17: 76–79
  5. ↑ van Bevern, René; Slugina, Viktoriia A. (2020). "A historical note on the 3/2-approximation algorithm for the metric traveling salesman problem". Historia Mathematica. 53: 118–127. arXiv:2004.02437. doi:10.1016/j.hm.2020.04.003. S2CID 214803097.
  6. ↑ Berman & Karpinski (2006).
  7. ↑ Kaplan et al. (2004).
  8. ↑ Svensson, Ola; Tarnawski, Jakub; Végh, László A. (2018). "A constant-factor approximation algorithm for the asymmetric traveling salesman problem". Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing - STOC 2018. Stoc 2018. Los Angeles, CA, USA: ACM Press: 204–213. doi:10.1145/3188745.3188824. ISBN 978-1-4503-5559-9. S2CID 12391033.
  9. ↑ Traub, Vera; Vygen, Jens (8 June 2020). "An improved approximation algorithm for ATSP". Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing. Stoc 2020. Chicago, IL: ACM: 1–13. arXiv:1912.00670. doi:10.1145/3357713.3384233. ISBN 978-1-4503-6979-4. S2CID 208527125.
  10. ↑ Karpinski, Lampis & Schmied (2015).
  11. ↑ Kosaraju, Park & Stein (1994).
  12. ↑ Serdyukov (1984).
  13. ↑ Hassin & Rubinstein (2000).
  14. ↑ Macgregor, J. N.; Ormerod, T. (June 1996), "Human performance on the traveling salesman problem", Perception & Psychophysics, 58 (4): 527–539, doi:10.3758/BF03213088, PMID 8934685.
  15. ↑ Dry, Matthew; Lee, Michael D.; Vickers, Douglas; Hughes, Peter (2006). "Human Performance on Visually Presented Traveling Salesperson Problems with Varying Numbers of Nodes". The Journal of Problem Solving. 1 (1). CiteSeerX 10.1.1.360.9763. doi:10.7771/1932-6246.1004. ISSN 1932-6246.
  16. ↑ Rooij, Iris Van; Stege, Ulrike; Schactman, Alissa (1 March 2003). "Convex hull and tour crossings in the Euclidean traveling salesperson problem: Implications for human performance studies". Memory & Cognition. 31 (2): 215–220. CiteSeerX 10.1.1.12.6117. doi:10.3758/bf03194380. ISSN 0090-502X. PMID 12749463. S2CID 18989303.
  17. ↑ MacGregor, James N.; Chu, Yun (2011). "Human Performance on the Traveling Salesman and Related Problems: A Review". The Journal of Problem Solving. 3 (2). doi:10.7771/1932-6246.1090. ISSN 1932-6246.
  18. ↑ MacGregor, James N.; Chronicle, Edward P.; Ormerod, Thomas C. (1 March 2004). "Convex hull or crossing avoidance? Solution heuristics in the traveling salesperson problem". Memory & Cognition. 32 (2): 260–270. doi:10.3758/bf03196857. ISSN 0090-502X. PMID 15190718.
  19. ↑ Vickers, Douglas; Mayo, Therese; Heitmann, Megan; Lee, Michael D; Hughes, Peter (2004). "Intelligence and individual differences in performance on three types of visually presented optimisation problems". Personality and Individual Differences. 36 (5): 1059–1071. doi:10.1016/s0191-8869(03)00200-9.
  20. ↑ Kyritsis, Markos; Gulliver, Stephen R.; Feredoes, Eva (12 June 2017). "Acknowledging crossing-avoidance heuristic violations when solving the Euclidean travelling salesperson problem". Psychological Research. 82 (5): 997–1009. doi:10.1007/s00426-017-0881-7. ISSN 0340-0727. PMID 28608230. S2CID 3959429.
  21. ↑ Kyritsis, Markos; Blathras, George; Gulliver, Stephen; Varela, Vasiliki-Alexia (11 January 2017). "Sense of direction and conscientiousness as predictors of performance in the Euclidean travelling salesman problem". Heliyon. 3 (11): e00461. doi:10.1016/j.heliyon.2017.e00461. PMC 5727545. PMID 29264418.
  22. ↑ Kyritsis, Markos; Gulliver, Stephen R.; Feredoes, Eva; Din, Shahab Ud (December 2018). "Human behaviour in the Euclidean Travelling Salesperson Problem: Computational modelling of heuristics and figural effects". Cognitive Systems Research. 52: 387–399. doi:10.1016/j.cogsys.2018.07.027. S2CID 53761995.
  23. ↑ MacGregor, James N.; Chu, Yun (2011), "Human performance on the traveling salesman and related problems: A review", Journal of Problem Solving, 3 (2), doi:10.7771/1932-6246.1090.
  24. ↑ Journal of Problem Solving 1(1), 2006, retrieved 2014-06-06.
  25. ↑ MacGregor, James N.; Chu, Yun (2011), "Human performance on the traveling salesman and related problems: A review", Journal of Problem Solving, 3 (2), doi:10.7771/1932-6246.1090.
  26. ↑ Gibson, Brett; Wilkinson, Matthew; Kelly, Debbie (1 May 2012). "Let the pigeon drive the bus: pigeons can plan future routes in a room". Animal Cognition. 15 (3): 379–391. doi:10.1007/s10071-011-0463-9. ISSN 1435-9456. PMID 21965161. S2CID 14994429.
  27. ↑ Jones, Jeff; Adamatzky, Andrew (2014), "Computation of the travelling salesman problem by a shrinking blob" (PDF), Natural Computing: 2, 13, arXiv:1303.4969, Bibcode:2013arXiv1303.4969J
  28. ↑ "TSPLIB". comopt.ifi.uni-heidelberg.de. Retrieved 10 October 2020.
  29. ↑ Geere, Duncan (26 April 2012). "'Travelling Salesman' movie considers the repercussions if P equals NP". Wired UK. Retrieved 26 April 2012.
  30. ↑ When the Mona Lisa is NP-HardBy Evelyn Lamb, Scientific American, 31 April 2015
"https://eu.wikipedia.org/w/index.php?title=Lankide:GarikoitzArtola/Proba_orria&oldid=9334357"(e)tik eskuratuta