主専攻実験(春) 巡回セールスマン問題

ओઐ߈࣮ݧ य़ ϝλώϡʔϦεςΟΫεͱ८ճηʔϧεϚϯ໰୊ ᜊ஍ਸେ

࣮ݧܭը w ݄ w ࣮ݧςΩετͷಡΈࠐΈɺ֤छख๏Λௐ΂ΔͳͲ w ݄ w ࣮ݧͰ༻͍ΔΞϧΰϦζϜͷܾఆͱϨϙʔτͷਐḿ w
ɾ݄ w தؒൃදͷ४උɺΞϧΰϦζϜͷ࣮૷ɺ࠷ऴൃද΁ͷܭଌ

ࢀߟ w ߨٛࢿྉ QEG w ૊߹ͤ࠷దԽୈ൛ ཧ࿦ͱΞϧΰϦζϜ
w l5IF5SBWFMJOHTBMFTNBOQSPCMFNBOENJOJNVNTQBNNJOHUSFFTz w .JDIBFM)FME 3JDIBSE.,BSQ

࣮૷ͨ͠ख๏ w ݫີղ๏ w ྻڍ๏ w ಈతܭը๏ w ෼ࢬݶఆ๏ ະ׬੒
ޙड़ w ώϡʔϦεςΟΫε w ࠷ۙྡ઀๏ɾ࠷ۙ௥Ճ๏ w ম͖ͳ·͠๏

ݫີղ๏ w ྻڍ๏ w ॱྻͷྻڍͱίετͷܭࢉ0 OO w ಈతܭը๏ w
ݱ࣌఺ͷ֗ͱ౸ୡ͍ͯ͠Δ֗ͷঢ়ଶͰܭࢉ0 O??O ͲͪΒ΋ݱ࣮తͰͳ͍

࠷ۙ௥Ճ๏ w ࠷ۙྡ઀๏ w ద౰ͳ఺͔Βग़ൃ͠ɺ·ͩ౸ୡ͍ͯ͠ͳ͍఺ͷݱࡏͷ఺͔Β͏ͪ ࠷΋͍ۙ΋ͷΛ௥Ճ͍ͯ͘͠ɻશͯͷ఺΁౸ୡޙ։࢝఺΁໭Δɻ  ߨٛࢿྉΑΓ w ܭࢉྔ͕૿͑ͯ΋͍͍ͷͰվྑͯ͠ΈΔ

ྫ վྑແ͠ ͕࠷୹ͩͱԾఆʢϢʔΫϦουڑ཭ʣ ࢝఺Λͱͯ͠ߟ͑Δ

ྫ վྑແ͠ ͕࠷୹ͩͱԾఆʢϢʔΫϦουڑ཭ʣ

࠷ۙྡ઀๏ͷվྑ w શ఺͔Β։࢝ ֤఺Ͱಉ༷ͷૢ࡞Λߦ͏ w ๚Ε͍ͯΔ఺ͷू߹ʹଐ͞ͳ͍఺ͷ͏ͪɺ  ๚Ε͍ͯΔ఺ͷ͍ͣΕ͔΁࠷΋͍ۙ఺ΛબͿ w ্ه఺Λ༻͍ͯͭͳ͗ม͑Λߦ͍८ճ࿏Λߋ৽
w ৗʹ८ճ࿏Λߏஙͯ͠࠷ॳͷ఺΁໭ΔίετΛ࡟ݮ͢Δ

ྫ վྑ༗Γ ͕࠷୹ͩͱԾఆʢϢʔΫϦουڑ཭ʣ ࢝఺͸೚ҙͷ఺ ࠓճ͸

ྫ վྑ༗Γ ͕࠷୹ͩͱԾఆʢϢʔΫϦουڑ཭ʣ ࠷ۙͷ఺ͱͰ८ճ࿏Λੜ੒

ম͖ಷ͠๏ w Թ౓5ͱPQUͷࢬுସ͑ૢ࡞ΛऔΓೖΕͯԹ౓͕ऩଋ͢Δ·Ͱ  Ұఆͷ֬཰ͱลͷ૯࿨ͷൺֱͰுସ͑ૢ࡞Λߦ͏ w ࠓճͷύϥϝʔλ͸5@45"35 5@&/% 5@'"$503 w ลͷுସ͑ૢ࡞ʹؔͯ͠͸ߨٛࢿྉதͷख๏Λࢀর
w ղۭؒͷੑ࣭͕໰୊ʹґଘ͢ΔͨΊ໰୊͝ͱʹύϥϝʔλΛ༻ҙ

ܭଌʹ͋ͨͬͯ w MBOHVBHF$ w NBDIJOF.BD#PPL1SP 3FUJOB JODIɺ&BSMZ w
DPNQJMFSHDDWFSTJPO Y@BQQMFEBSXJO w DQV$PSFJ6 ()[ w DPNQJMFPQUJPOH 0TUED

541-*#Λ༻͍ͯܭଌ ॲཧ࣌ؒ NT ճ໨ ճ໨ ճ໨ TUUTQ ౎ࢢ
QSUTQ ౎ࢢ UTQUTQ  ౎ࢢ MJOUTQ  ౎ࢢ ࠷ۙ௥Ճ๏ ݁Ռ ࠷దղ ࣮ߦղ TUUTQ ౎ࢢ QSUTQ ౎ࢢ UTQUTQ  ౎ࢢ MJOUTQ  ౎ࢢ ֓ͶഒҎ಺ ౎ࢢఔ౓·ͰͰ͋Ε͹TFD΄Ͳ

࠷ۙ௥Ճ๏ͷܭଌ w ۤखͳέʔεɾ഑ஔ͕͋Δ w શ఺͔Β։࢝ͯ͠΋ղͷ্ݶ͸ܾ·ͬͯ͠·͏ w ΞϧΰϦζϜࣗମͷվྑͰ͔͠޲্͠ͳ͍ w վળͷݟࠐΈ͕ബ͍ w
ͨͩ ᩦཉʹ௥Ճ͍ͯ͘͠΋ͷͰಘΒΕΔղۭؒΛ  શ୳ࡧͯ͠΋͋Δఔ౓ͷ࣌ؒͰऴྃ͢ΔͨΊ ͦ͏͍͏఺Ͱ༏ल

541-*#Λ༻͍ͯܭଌ ম͖ಷ͠๏ ൓෮ճ਺ 5@45"35 5@&/% 5@'"$503 ॲཧ࣌ؒ NT ճ໨ ճ໨
ճ໨ TUUTQ ౎ࢢ QSUTQ ౎ࢢ UTQUTQ  ౎ࢢ MJOUTQ  ౎ࢢ ࣌ؒͷ૬ؔ͸΄΅ແ͠ ॳظϧʔτੜ੒ͳͲͷ࣌ؒ

541-*#Λ༻͍ͯܭଌ ম͖ಷ͠๏ ൓෮ճ਺ 5@45"35 5@&/% 5@'"$503 ݁Ռ ࠷దղ ճฏۉ TUUTQ
౎ࢢ QSUTQ ౎ࢢ UTQUTQ  ౎ࢢ MJOUTQ  ౎ࢢ TU͸΄΅࠷ద ൓෮ճ਺͕গͳͯ͘΋ྑ͍ղ ౎ࢢ਺͕ଟ͍ͱղ͸ ζϨΔେ͖͘

541-*#Λ༻͍ͯܭଌ ম͖ಷ͠๏ ൓෮ճ਺ 5@45"35 5@&/% 5@'"$503 ॲཧ࣌ؒ NT ճ໨ ճ໨
ճ໨ TUUTQ ౎ࢢ QSUTQ ౎ࢢ UTQUTQ  ౎ࢢ MJOUTQ  ౎ࢢ ઌͱൺ΂ͯ࿐ࠎʹ஗͘ͳΔ

541-*#Λ༻͍ͯܭଌ ম͖ಷ͠๏ ݁Ռ ࠷దղ ύϥϝʔλ มߋલ ճฏۉ TUUTQ ౎ࢢ
QSUTQ ౎ࢢ UTQUTQ  ౎ࢢ MJOUTQ  ౎ࢢ ൓෮ճ਺ 5@45"35 5@&/% 5@'"$503 ౎ࢢ਺͕ଟ͍ํ͕Ըܙ͕ଟ͍ গͳ͍ํͰ͸ٯʹਫ਼౓͕ѱԽ

ম͖ಷ͠๏ͷܭଌ w ൓෮ճ਺ w ໰୊ͷ౎ࢢ਺΍ঢ়ଶʹΑͬͯมԽͤ͞Δͱ޲্ͷ༨஍͕͋Δ w ͨͩ͠ہॴղʹམͪͯ͠·͏৔߹΋͋Δ w ہॴղʹରͯ͠ w
্هͷہॴղʹରͯ͠ཚ਺΍Թ౓Λ্ख͘ௐ੔͢Δ w ࠷ۙ௥Ճ๏ͷΑ͏ʹہॴղʹམͪͯऴྃ͢Δ͜ͱ͸ݮΔ w ద੾ͳղۭؒΛݟ͚ͭ Կ౓͔ௐ੔͢Δͱঘྑ

ݫີղͷߴ଎Խ w ݫີղΛߨٛࢿྉͷଞͷ࣮૷Λߟ͑Δ w Ҋ w ෼ࢬݶఆ๏ w ෼ࢬΧοτ๏ w
4"5΍ผ໰୊ʹม׵ w ͳͲͳͲ ߨٛࢿྉʹهࡌ͞Ε͍ͯͨͨΊ௅ઓ

෼ࢬݶఆ๏ w ໦ͷ୳ࡧΛϕʔεʹߟ͑Δ w ݶఆૢ࡞ w ͋Δ৚݅Λݩʹ෦෼໦͕୳ࡧՄೳ͔ͷ৚݅෼ذ w ࢬמΓ͕Ͱ͖ΔͷͰຊདྷͷΦʔμʔΑΓগͳ͘ݟੵ΋ΕΔ w
෼ࢬૢ࡞ w ໰୊Λ͍͔ͭ͘ͷ෦෼໰୊ʹ෼͚ͯߟ͑Δ w ֤εςοϓʹ͍ͭͯݶఆૢ࡞ͰՄೳͱ൑அ͞ΕΕ͹୳ࡧΛߦ͏

541ʹؔ͢ΔΞΠσΞ ྫ ८ճ࿏ ८ճ࿏ ८ճ࿏ ८ճ࿏ ८ճ࿏ ८ճ࿏

541ʹؔ͢ΔΞΠσΞ w .JOVNVN4QBOOJOH5SFF .45 Λ༻͍ͯԼքΛࢉग़ w 1SJN΍,SVTLBMʹͯ0 O? ఔ౓Ͱࢉग़Ͱ͖Δ w
શମͱͯ͠0 ?OO? w ݶఆૢ࡞ͰࢬמΓ͕ՄೳʹͳΔ w ࢀߟl5IF5SBWFMJOHTBMFTNBOQSPCMFNBOENJOJNVNTQBNNJOHUSFFTz

541ʹؔ͢ΔΞΠσΞ w USFFͷఆٛ w ௖఺ͷ࣍਺͕Ͱ͋Δ w ௖఺͔ΒลΛҰͭ࡟আ͢Δͱ࠷খશҬ໦ʹͳΔ w ಋग़͸0 O?

541ʹؔ͢ΔΞΠσΞ w USFFͷಛ௃ w ࠷খશҬ໦͕ߏ੒͢Δล͸ શͯͷ఺͕ܨ͕͍ͬͯΔάϥϑͷ࠷খ w NJO8 w USFF͸NJO8ΑΓάϥϑΛߏ੒͢Δίετ͸ߴ͍
w POF58 w POF58NJO8͕੒Γཱͭ

541ʹؔ͢ΔΞΠσΞ w USFFͷಛ௃ w ·ͨ ͋Δάϥϑ͕USFFΛߏ੒͢Δͱ͖ ͦͷάϥϑ͔Βಋ͚  Δ८ճ࿏ͷղPOF5BOT w POF5BOTPOF58Ͱ͋Δ͜ͱ͕ݴ͑Δ
w ͜ͷ͜ͱ͸USFF͕८ճ࿏ʹͳΔ৔߹Λߟྀ͢Δͱ໌Β͔ w ΑͬͯPOF5BOTPOF58NJO8͕ݴ͑Δ

541ʹؔ͢ΔΞΠσΞ w ͋Δ෦෼໦͔Βಋ͔ΕΔ࢑ఆղΛ9ͱ͢Δͱ w 9ΑΓେ͖ͳPOF58ͷ஋ΛอͭUSFF͸  9ΑΓখ͞ͳ࢑ఆղΛ࣋ͨͳ͍ w POF5BOTPOF58NJO8ΑΓ w
Αͬͯɺ෦෼໰୊தͰUSFFΛߏங͢Δͱ࢑ఆղΛݩʹ  ݶఆૢ࡞͕ߦ͑ΔΑ͏ʹͳΔ

࣮૷ w ෼ࢬૢ࡞ʹ͓͍ͯ͸ lઈରʹ࢖༻͠ͳ͍ลzͱzઈରʹ࢖༻͢ΔลzΛ ༻͍ͯ෦෼໰୊Λੜ੒ w ࣍਺͕Ҏ্ͷ௖఺͸෼ࢬૢ࡞͕Ͱ͖Δ આ໌ུ w
લॲཧؚΊͯߦఔ౓ͷ࣮૷ w ͜ͷൃද·Ͱʹਖ਼͘͠ಈ͖·ͤΜͰͨ͠ɻ w খ͍͞έʔε O ఔ౓͸ಈ࡞͢Δ

·ͱΊ w ۙࣅࢉ๏Λߏங͢Δʹ͋ͨͬͯ͸໰୊ͷ܏޲ͱର৅ͷղۭؒΛٻΊ ͦΕʹԠͯ͡ύϥϝʔλΛௐઅ͢ΔඞཁͳͲ͕͋Δ w ໰୊͕ෳࡶʹͳΕ͹ύϥϝʔλ਺΋૿͑ΔͨΊௐ੔΋೉͘ͳΔ w ݫີղΛٻΊΔͨΊʹ͸άϥϑߏ଄ -1ͷ෦෼໰୊ͳͲΛߟ͑Δඞ ཁ͕͋Δ
w ෦෼໰୊ʹؔͯۙ͠ࣅࢉ๏ͳͲΛద༻͠ Լք͕ܾΊΒΕΕ͹ͨͱ ͑࠷ۙ௥Ճ๏ͷΑ͏ʹ޲্͕๬Ίͳͯ͘΋׆͔ͤΔ͔΋͠Εͳ͍

࣮ݧͷײ૝ w ݫີղ๏ʹؔͯ͠ଟ࣌ؒ͘Λׂͭ͘΋Γ͕ͩͬͨ෼ࢬݶఆ๏ʹؔ͠ ͯΞΠσΞΛ࣮૷͢ΔͷͰ΄ͱΜͲ͕࣌ؒͳ͘ͳͬͯ͠·ͬͨ w ͨͩ ෼ࢬݶఆ๏ʹݶͬͯ΋Լքͷಋग़ํ๏ʹؔͯ͠จݙ͕େྔʹ͋ Δ΄͔ɺ෦෼໰୊΁ฒྻԽ͢ΔͳͲͷख๏΋ݟ౰ͨͬͨ w ࠷ऴൃදʹ޲͚ͯͷ੍࣌ؒ໿ͰจݙΛࢀߟఔ౓ʹ͔͠Ͱ͖ͳ͔ͬ
ͨͷͰޙʑಡΜͰΈ͍ͨ

͜ΕͰൃද͸ऴΘΓͰ͢

主専攻実験(春) 巡回セールスマン問題

主専攻実験(春) 巡回セールスマン問題

More Decks by TAKAMASA Saichi

Other Decks in Technology

Featured

Transcript