Ȭა୰ȭ‫ږ‬ၚഎ̈́࢐೒વ‫ٺ‬อ୆̤̫ͥͅ
ζσΙ΀ȜΐͿϋΠ͈ࠐႹౝ॑਀༹Ք ౶ ఱ ‫ڠ‬ȁ‫ ܊‬ന ֥ ങՔ ౶ ࢥު ఱ ‫ڠ‬ȁչ ൥ ರ ࢼྴࡣ‫ުࢥؚ‬ఱ‫ڠ‬ȁ২ ུ ȁ ੈྴࡣ‫ުࢥؚ‬ఱ‫ڠ‬ȁஂ ȁ ణ ٚలĲડȁ͉̲͛ͅ
ȁ߃ාȄଲ‫ڎٮ‬౷́ఱܰ࿅̈́౷ૼब‫̦ٺ‬ອอ̱̞̀ͥȅඅͅȄ2011ා3࠮11඾ͅอ୆̱̹൐ཤ౷༷ఊ໹ဢ‫ؗ‬౷ૼ͉́Ȅ൐ཤ̥ͣ‫۾‬൐̥̫̀ͅଃఱ̈́๭‫ͬٺ‬̧̭̱̹̭͉ܱ֨ܳ͂‫ͅ؛‬૧̱̞ḙ͈̠̏̈́͢ఱܰ࿅̈́౷ૼब‫ͅٺ‬చ̳ͥζσΙ΀ȜΐͿϋΠഎͺίυȜΙ̱͂̀Ȅ࡛ह̯̰̈́৾ͤ͘͘ழ͙̦࣐̞̈́ͩͦ̀
ͥȅ̷͈৾ͤழ͙͈1̱̾͂̀ RoboCup Rescue Simulation ίυΐͿ·Π [1] ̦ಕ࿒̯̞ͦ̀ͥȅRoboCup Rescue Simulation ͉Ȅ౷ૼब‫࠺ฺ̠ͅٺ‬໤͈‫غ‬ब̤͍͢ുٟȄൽႹ͈໾ण̦อ୆̱̹‫ب‬ேഎ̈́๭बസঌ̤̞̀ͅȄब‫ݣٺ‬੩బ ) કཡబȆ‫ݢݣ‬బȆൽႹ߼‫ٳ‬బ * ̦ब‫ݣٺ‬੩‫ڰ‬൲࣐̠ͬ̈́ΏηντȜΏοΰ̜ͥȅ
RoboCup Rescue Simulation ͈ಎ́Ȅब‫ݣٺ‬੩బ͉΀ȜΐͿϋΠ̱͂̀κΟσ‫ا‬̯̤ͦ̀ͤȄζσΙ΀ȜΐͿϋΠͺίυȜΙͅ‫̞̀̿ܖ‬ब‫ݣٺ‬੩‫ڰ‬൲͈ΏηντȜΏοϋ࣐̠̭̦ͬ̈́͂‫خ‬ෝ̜́ͥȅRoboCup Rescue Simulation ͉̯̰͘ͅ
̈́͘ࡄ‫هݪ‬ఴ̦‫̤ͤ̀ͦ͘܄‬Ȅ̷͈ಎ͈1̾ͅ΀ȜΐͿϋΠͥ͢ͅࠐႹౝ॑࿚
ఴ̦̜ͥȅRoboCup Rescue Simulation ͉́Ȅब‫ݣٺ‬੩బ΀ȜΐͿϋΠ̦ब‫ݣٺ‬੩‫ڰ‬൲࣐̠̹ͬ̈́͛ͅȄब‫ݣٺ‬੩‫ڰ‬൲͈చય͂̈́ͥ‫װ‬ઘಎ͈࠺໤͞ൽႹ͈‫ۊ‬᠒Ȅ

ғ25ғ̹͉͘ঌྦྷོ͈཯̱̹࠺໤́͘֊൲࣐̠ͬ̈́ຈါ̦̜ͥȩ̭͈̏͂Ȅब‫ݣٺ‬੩‫ڰ‬൲ͬͤ͢ଇ௸࣐̠̹͉̈́͛ͅͅȄ΀ȜΐͿϋΠ͈࿒എ౷͈́͘ࠐႹͬͤ࢘͢
ၚഎͅౝ̳॑ͥຈါ̦̜ͥȅȁζσΙ΀ȜΐͿϋΠΏΑΞθ̤̫ͥͅࠐႹౝ॑࿚ఴ͈‫ܡ‬ంࡄ‫̱̀͂ݪ‬ȄA*ͺσΌςΒθ [2] ͞Θͼ·ΑΠρ༹ [3] ̦̈́̓౶̞ͣͦ̀ͥḙ͈̏ͦͣͺσΌςΒθ͉ΈρέΥΛΠχȜ·ષ͈2͈̾ΦȜΡ‫͈ۼ‬डౣࠐႹͬౝ̳॑ͥͺσΌςΒθ̜́ͥȅ̹͘ȄA* ͺσΌςΒθͬ‫ͅܖ‬٨ၻͬঔ̱̹ D* ͺσΌςΒθ [4]͞ Adaptive A* ͺσΌςΒθ [5] ̦̜̈́̓ͥḙ͈̏ͦͣࠐႹౝ॑ͺσΌςΒθ͉Ȅࠗॳশ‫ͅا௸͈ࣞۼ‬ਹതͬ౾̞̞̀ͥȅ̱̥̱Ȅब‫ݣٺ‬੩‫ڰ‬൲͞๰ඳ͈̹͈͛
ࠐႹౝ͉॑́ȄൽႹ̦஠̀ঀ̢ͥે‫̩̈́ઁ͉ޙ‬ȄൽႹͅવ‫̦ٺ‬อ୆̳ͥ‫خ‬ෝ଻̦̜ͥȅ̳̻̈́ͩȄ۪‫ޏ‬ȪൽႹૂ༭ȫͅ‫̳ͥ۾‬মஜ౶ে̦ୃ‫̞̩̀̽̈́̈́́ږ‬̭ͥ͂ͬே೰̱̫̞̈́ͦ͊̈́ͣ̈́ȅ༷֚́Ȅ໹ુশ͈́ਔ༏۪‫಺ޏ‬औ൝ͤ͢ͅ
ब‫ٺ‬শ̤̫۪ͥͅ‫ޏ‬་‫̜̞ͥ̀̾ͅا‬೾ഽ͈ထே̦‫خ‬ෝ̜́ͥ͂‫ب‬೰̳̭ͥ͂
͉ఏ൚̜́ͥ͂ࣉ̢ͣͦͥȅ̽̀͢Ȅब‫ٺ‬শ̤̫ͥͅ֊൲ْ̤̞͉ࠗ̀ͅḘ͈̏ͦͣະ‫ږ‬৘଻͂ထே‫خ‬ෝ଻ͬࣉၪ̱̀ࠐႹ஖఼̳̭̦ͬͥ͂བ̱̞͘ȅ̹͘Ȅࠗॳশ‫̷͈͈ͤ͜͢͜ۼ‬Ȅ࿒എ౷͒ൢో̳͈ͥ́͘শ‫ͬۼ‬ౣ̩̳̭̦ͥ͂ਹါ
͂̈́ͥȅ̷͈̹͛Ȅ֊൲শ‫ͅۼ‬๤႕̳ͥ௙֊൲΋ΑΠ͜ਹါ͂̈́ͥȅȁ̷ུ̭́ა໲͉́Ȅ‫ږ‬ၚഎવ‫̦ٺ‬อ୆̳̭ͥ͂ͬே೰̱Ȅͤ࢘͢ၚ̩͢࿒എ
౷́͘֊൲̳̹ͥ͛ͅȄൽႹ̩̞͈̓ͦͣͅ‫ږ‬ၚ́વ‫̦ٺ‬อ୆̳̥ͥͬা̳
ȶવ‫ٺ‬อ୆ၚȷ͂ȄडౣࠐႹͅવ‫̧͈̹̜̦͂̽ٺ‬యఢࠐႹ̜́ͥȶֶٝࠐႹȷͬ
၌ဥ̳̭ͥ͂ͬࣉ̢ͥȅߓఘഎ͉ͅȄવ‫ࠐͥ͢ͅٺ‬Ⴙ͈໑ङ‫ږ‬ၚȄֶ̤͍ٝ͢
ࠐႹ͈͒୨ͤఢ̢ယօ଻ͬࣉၪ̱̹ບ‫۾ث‬ତͅ‫̩̿ܖ‬૧̱̞ A* ͺσΌςΒθ
ͬ೹մ̱Ȅ̷͈଻ෝບ‫̠࣐ͬث‬ȅలĳડȁ੨೰݅
ȁུડ͉́ȄࠐႹౝ॑࿚ఴͅ‫ވ‬೒̱̀ဥ̞ͣͦͥΟȜΗࢹ௮̈́̓ͬ೰̳݅ͥȅғ26ғ‫ږ‬ၚഎ̈́࢐೒વ‫ٺ‬อ୆̤̫ͥͅζσΙ΀ȜΐͿϋΠ͈ࠐႹౝ॑਀༹

ࠐႹౝ̦̤̭॑̈́ͩͦͥਹ͙ັ̧Έρέ G ͬո‫̠͈͢ͅئ‬೰̳݅ͥȅ೰݅ 1 ȁΈρέȁȁȁȁG=)V, E, C*
̭̭́ V ͉ΦȜΡ )node* ͈ਬࣣȄE ͉ΦȜΡ͂ΦȜΡ̪ͬ̾̈́༏ )edge* ̜́ͥȅȁ̹͘ȄC ͉༏ͅ΋ΑΠͬဓ̢ͥ‫۾‬ତ̜́ͥȅ̷̸ͦͦȄո‫̠͈͢ͅئ‬೰̳݅ͥȅ೰݅ 2 ȁΦȜΡ͈ਬࣣȁȁȁȁV = {v1, v2,…, vn}

೰݅ 3 ȁ༏͈ਬࣣȁȁȁȁE = {ei, Ҕj vi, vj ɸ V, vi ͂ vj ͈͂‫ͅۼ‬༏̦ంह̳ͥ }೰݅ 4 ȁ༏͈΋ΑΠ‫۾‬ତȁȁȁȁȁC : E ɨ R+
̭̭́Ȅ༏ ei, j ͅဓ̢̹ͣͦ΋ΑΠ͉ ci, j ̳͂ͥȅȁΈρέ G ̤̫ͥͅΦȜΡ vs ̥ͣ vg ͈́͘ࠐႹͬո‫̠͈͢ͅئ‬೰̳݅ͥȅ೰݅ 5 ȁࠐႹȁȁȁȁࠐႹ͉ΦȜΡႥ )vs, vs+1, … , vg-1, vg * ́ນ̳ȅંȄ‫ ڎ‬vi ̥ͣ vi+1͉ͅȄ༏ ei, i+1 ̦ంह̱̫̞̈́ͦ͊̈́ͣ̈́ȅȁ̹͘ȄࠐႹ )vs, vs+1, … , vg-1, vg * ͈΋ΑΠͬո‫̠͈͢ͅئ‬೰̳݅ͥȅ೰݅ 6 ȁࠐႹ͈΋ΑΠȁȁȁȁcs, s+1+cs+1, s+2+…+cg-2, g-1+ cg-1, gȁΦȜΡ vs ̥ͣΦȜΡ vg ͈́͘डౣࠐႹ̷̧͈͈͂͂΋ΑΠ̜́ͥडౣ΋Αғ27ғ

Πͬո‫̠͈͢ͅئ‬೰̳݅ͥȅ೰݅ 7 ȁडౣࠐႹȁȁȁȁΦȜΡ vs ̥ͣΦȜΡ vg ͈́͘஠͈̀ࠐႹ͈ಎ́ȄࠐႹ͈΋ΑΠ̦ड઀͈͈͜ȅ

೰݅ 8 ȁडౣ΋ΑΠȁȁȁȁडౣࠐႹ͈΋ΑΠͬडౣ΋ΑΠ͂ࡤ͐ȅȁౝ॑ͬ‫ٳ‬ই̳ͥΦȜΡ ) ‫ٳ‬ইΦȜΡ * ̥ͣ࿒എ౷͂̈́ͥΦȜΡ ) ࿒എ౷ΦȜΡ * ͒֊൲̳ͥచયͬ΀ȜΐͿϋΠ͂ࡤ͍Ȅ‫΀ڎ‬ȜΐͿϋΠ͈ෝႁ̤͍͢൲ै
ͬո‫̠͈͢ͅئ‬೰̳݅ͥȅ೰݅ 9 ȁ΀ȜΐͿϋΠ͈ෝႁ͂൲ै
ȁȁȁȁ●ȁ΀ȜΐͿϋΠ͉Ȅဓ̢̹ͣͦͺσΌςΒθ̱̹̦̽̀ͅȄ֊൲୶ΦȜΡͬࠨ೰̳ͥȄȁȁȁȁɜȁ΀ȜΐͿϋΠ̦൳۪֚‫ͅޏ‬ໝତఘంह̧̳ͥ͂Ȅ஠΀ȜΐͿϋΠ͉൳শͅ൲ै̳ͥȄȁȁȁȁɜȁ΀ȜΐͿϋΠ൳আ͉ুဇ̥̾൳শͅ೒૞‫خ‬ෝ̜́ͥȄȁȁȁȁɜȁ΀ȜΐͿϋΠ͉൳֚Έρέષͅໝତంह̳̭̦̜ͥ͂ͥȅȁ༏ȄΦȜΡ̤̫ͥͅવ‫̷͈͂ٺ‬વ‫ૂ̳ͥ۾ͅٺ‬༭ͬո‫̠͈͢ͅئ‬೰̳݅ͥȅ

೰݅10ȁવ‫ٺ‬ȁȁȁȁ༏Ȫ̱̩͉͜ΦȜΡȫͅ‫͈̥ͣة‬࿚ఴ̦อ୆̱Ȅ΀ȜΐͿϋΠ̦೒ً̧̩́̈́̈́ͥેఠͬȄ༏Ȫ̱̩͉͜ΦȜΡȫ͈વ‫̳ͥ͂ٺ‬ȅғ28ғ‫ږ‬ၚഎ̈́࢐೒વ‫ٺ‬อ୆̤̫ͥͅζσΙ΀ȜΐͿϋΠ͈ࠐႹౝ॑਀༹

೰݅11ȁવ‫ૂٺ‬༭ȁȁȁȁ‫ڎ‬༏Ȫ̱̩͉͜‫ڎ‬ΦȜΡȫ͈વ‫͈ٺ‬ခྫͅ‫ૂ̳ͥ۾‬༭ͬવ‫ૂٺ‬༭̳͂ͥȅȁવ‫ૂٺ‬༭ͬං̹΀ȜΐͿϋΠ͉࿒എ౷ͅൢోֶ̳̹̳ͥ͛ٝͥͅȅ̷ֶ͈ٝࠐႹͬո‫̠͈͢ͅئ‬೰̳݅ͥȅ
೰݅12ȁֶٝࠐႹ
ȁȁȁȁडౣࠐႹષ͈̜ͥ༏̦વ‫ͤ͢ͅٺ‬೒࣐ະ‫خ‬ෝ̜́ͥ͂‫ب‬೰̧̱̹͈͂
Ȫষ஝͈ȫडౣࠐႹֶͬٝࠐႹ̳͂ͥȅȁडࢃͅȄडౣࠐႹౝ॑࿚ఴ̞̾̀೰̳݅ͥȅ೰݅13ȁडౣࠐႹ࿚ఴ
ȁȁȁȁ΀ȜΐͿϋΠ̦ౝ॑ͬ‫ٳ‬ই̳ͥΦȜΡ ) ‫ٳ‬ইΦȜΡ * ̥ͣ࿒എ౷͂̈́
ͥΦȜΡ ) ࿒എ౷ΦȜΡ * ͈́͘डౣࠐႹͬౝ̳॑ͥ࿚ఴંȄ΀ȜΐͿϋΠ̦ໝତంह̳ͥાࣣ͉Ȅȶ஠΀ȜΐͿϋΠ̦‫ٳ‬ইΦȜΡ̥ͣ࿒എ౷ΦȜΡ́͘֊൲ۖၭ̳͈̥̥ͥͥͅশ‫ۼ‬ȷͬड઀̳ͥͅࠐႹͬౝ॑
̳ͥ࿚ఴ̳͂ͥȅలĴડȁडౣࠐႹౝ॑࿚ఴ͈‫ܡ‬ంࡄ‫ݪ‬ġĴįĲġłī ͺσΌςΒθġȁA* ͺσΌςΒθ [2] ͉Ȅ1968ාͅ Hart ͣ̽̀͢ͅ‫ٳ‬อ̯̹ͦͺσΌςΒθ̜́ͤȄ૽ࢥ౶ෝ̤̫ͥͅࠐႹౝ॑࿚ఴ͈యນഎ̈́ͺσΌςΒθ̞͂̈́̽̀ͥȅA* ͺσΌςΒθ͉́Ȅ‫ٳ‬ইΦȜΡ̥ͣ࿒എ౷ΦȜΡ͒ঢͥडౣ΋ΑΠ͈ଔ೰౵ͅ‫ࠐ̞̀̿ܖ‬Ⴙౝ॑ͬૺ͛ͥḙ̏ͦͤ͢ͅȄࠐႹ͈஠ౝ̵̴॑ͬͅౣ̞ࠗॳ
শ‫́ۼ‬࿒എ౷ΦȜΡ͈́͘डഐࠐႹͬౝ̧̳̭̦॑ͥ͂́ͥȅ

ғ29ғĴįĲįĲġłī ͺσΌςΒθ͈‫ٽ‬ါġȁA* ͺσΌςΒθ͉Ȅ̜ͥΦȜΡ̥ͣႋ୪̳ͥΦȜΡͬ஖఼̳ͥশͅȄ࢓༞͂̈́ͥႋ୪ΦȜΡ̥ͣ࿒എ౷ΦȜΡ͈́͘डౣ΋ΑΠ͈ଔ೰౵̦ड͜઀̯̩̈́
ͥΦȜΡͬ஖఼̱̀ࠐႹౝ॑ͬૺ༹̞̩༷̜͛̀́ͥḙ̭̏́Ȅडౣ΋ΑΠ͈ଔ೰౵̞̾̀ͅ୰ྶ̳ͥȅౝ॑ࠐႹષ̜ͥͅΦȜΡͬ p ̳͂ͥȅ‫ٳ‬ইΦȜΡ̥ͣΦȜΡ p ͬ೒ͤȄ࿒എ౷ΦȜΡ́͘ঢͥࠐႹ͈डౣ΋ΑΠ f)p* ͬȄո‫͈ئ‬̠͢ͅນ̳ȅ
f)p*= g)p*+ h)p*̭̭́Ȅg)p* ͂ h)p* ͉ո‫͈ئ‬փྙͬ঵̾ȅɜȁg)p*ȇ‫ٳ‬ইΦȜΡ̥ͣΦȜΡ p ͈́͘डౣ΋ΑΠɜȁh)p*ȇΦȜΡ p ̥ͣ࿒എ౷ΦȜΡ͈́͘डౣ΋ΑΠȁౝ̦॑ΦȜΡ p ́͘ૺ̺ͭાࣣͬࣉ̢ͥ͂Ȅ‫ٳ‬ইΦȜΡ̥ͣΦȜΡ p ͈́͘डౣ΋ΑΠ g)p* ͉‫̦̞ͥ̀ͦͣ͛ݥ‬Ȅh)p* ͉ౝ॑ͬૺ̞̥̫͛̀̈́ͦ͊‫͛ݥ‬̧̭̦̞ͥ͂́̈́ḙ̷̏́Ȅh)p* ͉ͅଔ೰౵̱͂̀ h* )p* ͬဥ̞̀Ȅ‫ٳ‬ইΦȜΡ̥ͣΦȜΡ p ͬ೒ͤ࿒എ౷ΦȜΡ͒ঢͥडౣ΋ΑΠ͈ଔ೰౵ͬո‫̠͈͢ͅئ‬ນ̳ȅf* )p*= g)p*+ h* )p*ȁ̧̭͈͂ h* )p* ͈̭͂ͬΪνȜςΑΞͻΛ·‫۾‬ତ͂͐͢ȅ̷̱̀Ḙ͈̏ͺσΌςΒθ͉ h* )p* ̦ૄ࠯ ʍp, 0 ≤ h* )p* ≤ h)p* ͬྖ̧̹̳͂Ȅ‫ࠐͥ͘ݥ‬Ⴙ̦‫ٳ‬ইΦȜΡ̥ͣ࿒എ౷ΦȜΡ͈́͘डౣࠐႹ̜̭̦́ͥ͂༗બ̯̞ͦ̀ͥḙ̏ͦͬ A* ͺσΌςΒθ͂ࡤ͐ȅ̱̹̦̽̀Ȅ࡛हࠐႹౝ̦॑ૺ̞ͭ́ͥΦȜΡғ30ғ‫ږ‬ၚഎ̈́࢐೒વ‫ٺ‬อ୆̤̫ͥͅζσΙ΀ȜΐͿϋΠ͈ࠐႹౝ॑਀༹

̥ͣষ͈ࠐႹ͂̈́ͥΦȜΡͬ஖఼̳ͥশͅȄ࢓༞͂̈́ͥΦȜΡ̞̾̀ͅ f*)p*͈౵ͬ‫͛ݥ‬Ȅf*)p* ͈౵̦ड઀̈́ͥͅΦȜΡͬࠐႹ̱͂̀஖఼̳̭ͥ͂́ࠐႹ
ౝ॑ͬૺ͛ͥȅయນഎ̈́ h*)p* ͈౵̱͉͂̀Ȅ࿒എ౷͈́͘ξȜ·ςΛΡ‫ݻ‬ၗ̦̜̈́̓ͥȅ

Ĵįĳġłī ͺσΌςΒθ͈෩୆ȁུ୯͉́Ȅ࡛ह́͘ͅࣉմ̧̯̹ͦ̀ A* ͺσΌςΒθ͈٨ၻ̞̾̀ͅ۰ౙ
ͅ୰ྶ̳ͥȅ

ĴįĳįĲġŅī ͺσΌςΒθġȁD* ͺσΌςΒθ [4] ͉Ȅ1994ාͅ Anthony Stentz ̽̀͢ͅ೹մ̯̹ͦࠐႹౝ॑ͺσΌςΒθ̜́ͥȅD* ͺσΌςΒθ͉́Ȅ࿒എ౷ΦȜΡ̥ͣ A* ͺσΌςΒθͬ৘࣐̱Ȅ‫ڎ‬ΦȜΡ́࿒എ౷༷͈࢜༏ܱͬ჏̱̤̩̭̀͂́Ȅ࡛ह౷̥ͣ࿒എ౷͒֊൲ಎ̥͈̈́ͭͣͅવ‫̧̹̦ܳٺ‬ાࣣͅȄA* ͺσΌςΒθͥ͢ͅౝ॑ͬ߫ͤ༐̳ͤ͢͜ౣ̞ࠗॳশ‫ֶ́ۼ‬ٝࠐႹͬ‫̧̦̭ͥ́͂ͥ͛ݥ‬ȅĴįĳįĳġłťŢűŵŪŷŦġłī ͺσΌςΒθġȁAdaptive A* ͺσΌςΒθ [5] ͉Ȅ2006ාͅ Sven ͣ̽̀͢ͅ೹մ̯̹ͦࠐႹౝ॑ͺσΌςΒθ̜́ͥȅAdaptive A* ͺσΌςΒθ͉́Ȅ೒࣐‫خ‬ෝ̈́༏͈ତ̦
ࡘઁ̳ͥાࣣͅȄA* ͺσΌςΒθͥ͢ͅౝ॑ͬ߫ͤ༐̳ͤ͢͜ౣ̞ࠗॳশ‫ۼ‬ֶ́ٝࠐႹͬ‫̧̦̭ͥ́͂ͥ͛ݥ‬ȅĴįĴġ‫ܡ‬ంͺσΌςΒθͅచ̳ͥ࠿൦
ȁུડ́੆͓̹̠͢ͅȄ࡛ह͈ A* ͺσΌςΒθ͈٨ၻ͉ࠗॳশ‫ͅۼ‬ਹ̧̤̞̞͈̦͕̜ͬ̀ͥ͂ͭ̓́ͥ͜ȅ̱̥̱Ȅࠗॳশ‫̜̀̽́͜௸̷̦͈͈ࣞ͜ۼ‬Ȅ೒࣐ະෝ̈́વ‫͒ٺ‬ൢో̱̱̠̀͂͘Ȅֶ̱̹ٝͤȄ࿗̹̳̽ͤͥ໦̺̫Ȅ࿒എ౷͈́͘௙֊൲΋ΑΠ̦ఱ̧̩̈́ͤȄ࿒എ౷͒ൢో̳͈̦ͥಁ̩̱̠̈́̽̀͘ȅғ31ғ̷̭́Ȅུა໲͉́ࠐႹવ‫ͅٺ‬ൢో̳̭ͥ͂ͬ‫ږ‬ၚഎͅ๰̫Ȅडਞഎͅ࿒എ౷
ͅൢో̳̥̥ͥ́ͥ͘ͅশ‫ͬۼ‬ౣੀ̳ͥͺσΌςΒθͬȄষડ́೹մ̳ͥȅలĵડȁ೹մ਀༹
ȁུડ͉́Ȅུა໲̦೹մ̳ͥࠐႹౝ॑਀༹̞̾̀ͅ୰ྶ̳ͥȅ̴ུ͉͘ა໲
̦చય̳͂ͥ࿚ఴ୭೰̞̾̀ͅ୰ྶ̱Ȅষུͅა໲͈೹մ਀༹̞̾̀ͅ୰ྶ̳
ͥȅĵįĲġ࿚ఴ୭೰
ȁུ୯͉́Ȅུა໲̦చય̳͂ͥ࿚ఴ͈۪‫΀͂ޏ‬ȜΐͿϋΠ̞̾̀ͅ୰ྶ̳ͥȅĵįĲįĲġ‫ܡ‬ంࡄ‫͈͂ݪ‬௖֑തȁ‫ܡ‬ంࡄ‫͉́ݪ‬ȄවႁΈρέͅ֊൲વ‫̦ٺ‬อ୆̳̭ͥ͂ͬࣉၪ̱̞̞̀̈́ાࣣ
̦ఉ̞ȅ̹͘ȄවႁΈρέͅ֊൲વ‫̦ٺ‬อ୆̳̭ͥ͂ͬࣉၪ̱̞̀ͥࡄ‫̜̽́ݪ‬̀͜Ȅવ‫ૂٺ‬༭̦۰ౙͅව਀̧́ͥ୭೰̞͂̈́̽̀ͥȅ̱̥̱Ȅ౷ૼब‫ٺ‬൝́ൽႹͅવ‫̦ٺ‬อ୆̱̹ાࣣȄવ‫ࣉͬٺ‬ၪ̱̞̞̀̈́ࠐႹౝ͉॑࢘ၚഎ̞̭́̈́
̦͂ఉ̩Ȅવ‫ૂٺ‬༭̦۰ౙͅව਀̧̞́̈́ાࣣ͜ఉ̞ḙ̷̏́Ȅུა໲͉́ȄවႁΈρέ͈༏ͅવ‫̦ٺ‬อ୆̱Ȅવ‫ૂٺ‬༭̦۰ౙͅව਀̧̞̠́̈́̈́͢࿚ఴ୭
೰̤̭̠ͬ̈́ȅ̹͘Ȅ΀ȜΐͿϋΠ͉࡛৘ଲ‫ͬۼ૽͈ٮ‬ே೰̱̤̀ͤȄ਱໦ͅࢩ̞ൽႹͬ֊൲̳̭ͥ͂ͬே೰̱̞͈̀ͥ́Ȅ΀ȜΐͿϋΠ൳আ͈઩ඏ͞ਸ਼త
͉ࣉၪ̱̞͈̳̈́͂ͥ͜ȅĵįĲįĳġ۪‫ޏ‬ȁུა໲͉́ȄࠐႹౝ̤̭̠॑ͬ̈́વ‫ٺ‬อ୆ၚͬ঵̾ਹ͙ັ̧Έρέ G' ͬո‫̠͈͢ͅئ‬೰̳݅ͥȅғ32ғ‫ږ‬ၚഎ̈́࢐೒વ‫ٺ‬อ୆̤̫ͥͅζσΙ΀ȜΐͿϋΠ͈ࠐႹౝ॑਀༹

೰݅14ȁવ‫ٺ‬อ୆ၚͬ঵̾ΈρέȁȁȁG'=)V, E, C, B*
ȁV, E , C ̷̸͉ͦͦ೰݅2, 3, 4 ͂൳̲͈̜́ͥ͜ȅ̹͘Ȅ༏ͅવ‫ٺ‬อ୆ၚͬဓ̢ͥ‫۾‬ତ B ͬո‫̠͈͢ͅئ‬೰̳݅ͥȅ

೰݅15ȁવ‫ٺ‬อ୆ၚȁȁȁȁB : E ɨ R+
̭̭́Ȅ༏ ei, j ဓ̢̹ͣͦવ‫ٺ‬อ୆ၚ͉ bi, j ̳͂ͥȅȁུა໲́ե̠ࠐႹવ‫͉ٺ‬ΏηντȜΏοϋ‫ٳ‬ইশͅȄȶવ‫ٺ‬อ୆ၚȷͅ‫̿ܖ‬̞̀‫ڎ‬༏ͅอ୆̳ͥḙ̏ͦոࣛȄࠐႹવ‫̦ٺ‬อ୆̱̹༏ͬવ‫ٺ‬༏͂ࡤ͐ȅ̹͘ȄࠐႹવ‫͉ٺ‬ΏηντȜΏοϋ‫ٳ‬ইশത́ࠨ೰̯ͦȄΏηντȜΏοϋಎͅ௩ࡘ̳̭͉̞ͥ͂̈́ȅĵįĲįĴġ΀ȜΐͿϋΠȁུა໲͉́Ȅ΀ȜΐͿϋΠ͈ෝႁ̤͍͢൲ैͬո‫̠͈͢ͅئ‬೰͛ͥȅɜȁဓ̢̹ͣͦͺσΌςΒθ̱̹̦̽̀ͅȄ֊൲୶ΦȜΡͬࠨ೰̳ͥȅɜȁ൳۪֚‫ͅޏ‬ໝତఘ΀ȜΐͿϋΠ̦ంह̧̳ͥ͂Ȅ஠΀ȜΐͿϋΠ͉൳শͅ൲ै̳ͥȅɜȁ΀ȜΐͿϋΠ൳আ͉൳শͅ೒૞‫خ‬ෝ̜́ͤȄ਋૞‫خ‬ෝιΛΓȜΐତ͞ιΛΓȜΐಿ͈ଷࡠ͉̞̈́ȅɜȁ੝‫ેܢ‬ఠ́વ‫ૂٺ‬༭ͬ‫̞̈́͘܄‬Έρέͅ‫ૂ̳ͥ۾‬༭ͬ৾ං̧́ͥȅɜȁવ‫ٺ‬༏ͅ୪௽̱̞̀ͥΦȜΡͅൢో̳ͥ́͘ȄࠐႹવ‫ͬٺ‬อࡉ̧̞́̈́ȅɜȁໝତ͈΀ȜΐͿϋΠ̦Ȅ൳শͅ൳̲ΦȜΡȪ̹͉͘༏ȫͅ֊൲̱̀͜઩ඏȆਸ਼త͉อ୆̱̞̈́ȅ

ғ33ғĵįĳġͺσΌςΒθ
ȁུა໲͉́ȄA* ͺσΌςΒθͬ‫ͅܖ‬ͺσΌςΒθͬ୭̳ࠗͥȅ3ડ́୰ྶ̱
̹̠͢ͅȄ࿒എ౷͈́͘ൢోশ‫ͬۼ‬ౣ̩̳̹͉ͥ͛ͅȄࠗॳশ‫͂ۼ‬࿒എ౷́͘
͈௙֊൲΋ΑΠͬ઀̯̩̳ͥຈါ̦̜ͥȅ̱̥̱Ȅ֊൲ಎͅࠐႹવ‫͒ٺ‬ൢో̱̱̠̀͂͘Ȅ࿒എ౷͈͒௙֊൲΋ΑΠ̦ఱ̧̩̱̠̈́̽̀͘ȅ̹͘ȄࠐႹવ‫͉ٺ‬Ȅવ‫ٺ‬༏ͅ୪௽̱̞̀ͥΦȜΡͅൢో̱̞̈́͂อࡉ̧̞́̈́ḙ̷̏́Ȅུა໲͉́વ‫ٺ‬อ୆ၚֶ͂ٝࠐႹͬ၌ဥ̳̭ͥ͂̽̀͢ͅȄA* ͺσΌςΒθͬ٨ၻ̱Ḙ͈̏࿚ఴ͈ٜࠨͬ࿒ঐ̳ȅĵįĳįĲġłī ͺσΌςΒθ͈٨ၻུა໲͉́ȄA* ͺσΌςΒθ́ဥ̞ͣͦͥ h*)p* ͈ࠗॳ༹༷ͬ೹մ̳ͥȅh*)p* ͈ࠗॳ༹༷ͬո‫ͅئ‬া̳ḙ̭͉̏́ȄΦȜΡ p ̥ͣ࿒എ౷͈́͘डౣࠐႹ
ͬ )v1, v2, v3, …* ̳͂ͥȅ1.ȁ ΦȜΡ p ̥ͣ࿒എ౷͈́͘डౣ΋ΑΠͬࠗॳ̳ͥȅ2.ȁ डౣ΋ΑΠ́࿒എ౷͒ൢో̧́ͥ‫ږ‬ၚͬࠗॳ̳ͥȅ3.ȁ 1͂ 2͈ୟͬࠗॳ̳ͥȅ4.ȁ ‫ڎ‬ΦȜΡ vi ̤̞̀ͅ vi ̥ͣ vi+1 ̦೒̞ͦ̈́͂‫ب‬೰̱̹ાࣣ͈डౣ΋ΑΠȪֶٝࠐႹ̤̫ͥͅ΋ΑΠȇֶٝࠐႹಿ̳͂ͥȫͬࠗॳ̳ͥȅ5.ȁ 3ͬ‫ͅܖ‬ষ͈ࠗॳ࣐̠ͬȅ

ȁȁȁ
ȁȁȁ
ȁȁȁ
6.ȁ 3͂ 5͈გͬ h*)p* ̳͂ͥȅғ34ғ‫ږ‬ၚഎ̈́࢐೒વ‫ٺ‬อ୆̤̫ͥͅζσΙ΀ȜΐͿϋΠ͈ࠐႹౝ॑਀༹

ĵįĳįĳġ൲ै႕ȁ଎4.1ͅা̳Έρέ̤̞̀ͅȄΦȜΡ 7̥ͣΦȜΡ8͈́͘डౣࠐႹͅ‫̱̀۾‬೹մ਀༹ͬဥ̞̀ౝ̳॑ͥ႕ͬࣉ̢ͥȅંȄ۰ౙ͈̹֚͛໐͈વ‫ٺ‬อ୆ၚ͈͙
া̳ȅ
ΌȜσ
˔

ı

ı

ˑ

ˎ

ıįıĳ

˒

˕
ȇΦȜΡ

ıįıĶ

ː

ˍ

Ĳı

ȇ༏ȁ֊൲΋ΑΠ͉஠̀Ĳ
ȁȁȁତল͉વ‫ٺ‬อ୆

ıįĲ
ıįıĳ

ˏ

ˌ

˓

ĲĲ

ΑΗȜΠ
଎ġĵįĲĻ වႁΈρέͺσΌςΒθ͉ո‫͈ئ‬ၠͦͅ‫࣐ͥͦͩ̀̽״‬ȅ
1.ȁ ࡛ह͈ΦȜΡͅႋ୪̱̞̀ͥΦȜΡ3̞̾̀ͅ h*)3* ͬࠗॳ̳ͥȅȁȁ)a* डౣ΋ΑΠ́࿒എ౷͒ൢో̧́ͥ‫ږ‬ၚ ȿ डౣ΋ΑΠȁȁȁȁ0.98 ȿ 0.98 ȿ 1 ȿ 3 = 2.8812ȁȁ)b*ȪֶٝࠐႹͬ஖఼̱̫̞̈́ͦ͊̈́ͣ̈́‫ږ‬ၚȿֶٝࠐႹ͈΋ΑΠȫ͈ࣣࠗ
ȁȁȁȁ0.02 ȿ 3 + 0.98 ȿ 0.02 ȿ 4 + 0.98 ȿ 0.98 ȿ 0 ȿ 7 = 0.1384
ȁȁ)c* h*)3* = 2.8812 + 0.1384 = 3.0196
2.

൳အͅȄΦȜΡ 0 ̞̾̀ͅ h*)0* ͬࠗॳ̳ͥḙ̭͉̏́ 3.19͂̈́ͥȅ

3.ȁ ‫ڎ‬ΦȜΡ͈ f *)p* ͬࠗॳ̳ͥȅȁȁ)a* f* )3*= g)3*+ h*)3* = 1 + 3.0196 = 4.0196

ғ35ғȁȁ)b* f *)0* = g )0* + h*)0* = 1 + 3.19 = 4.194
4.ȁ ࡛ह͈ΦȜΡͅႋ୪̱̞̀ͥΦȜΡ͈ಎ́Ȅf *)p* ͈౵̦֚๔઀̯̞ΦȜΡ͒֊൲̳ͥḙ̭͉̏́ΦȜΡ3͒֊൲̳ͥȅ5.ȁ ࡛ह͈ΦȜΡͅႋ୪̱̞̀ͥΦȜΡ6͂ΦȜΡ4͂ΦȜΡ7̞̾̀ͅ f*)p*ͬࠗॳ̳ͥȅ
6.ȁ ΦȜΡ6͈ f *)p* ͂ΦȜΡ4͈ f *)p* ͈౵̦൳̲̦̈́ͥͅḘ̭͉̏́ΦȜ
Ρ6͒֊൲̳ͥȅ7.ȁ ࡛ह͈ΦȜΡͅႋ୪̱̞̀ͥΦȜΡ5͂ΦȜΡ3̞̾̀ͅ f *)p* ͬࠗॳ̳ͥȅ8.ȁ ̭̭͉́ΦȜΡ5͒֊൲̳ͥȅ9.ȁ ࡛ह͈ΦȜΡͅႋ୪̱̞̀ͥΦȜΡ8͉࿒എ౷͈̈́́ȄΦȜΡ8͒֊൲̳ͥȅ10. ࿒എ౷͒ൢో̱̹͈́ȄͺσΌςΒθਞၭ͂̈́ͥȅĵįĴġłī ͺσΌςΒθ͂೹մ਀༹͈ໝࣣ̞̾̀ͅ
ȁུა໲͉́Ȅ΀ȜΐͿϋΠ̦ໝତ͈ાࣣ͜৘ࡑ̤̭̠ͬ̈́ȅ̷͈ાࣣȄA*ͺσΌςΒθ͂೹մ਀༹͈͕̥ͅȄA* ͺσΌςΒθ͂೹մ਀༹ͬழ̵͙ࣣͩ
̹਀༹̦࢘‫ض‬എ̈́‫خ‬ෝ଻̦ခͥḙ̷̏́Ȅུა໲͉́ A* ͺσΌςΒθ͂೹մ਀༹ͬழ̵͙ࣣ̹ͩ਀༹́͜৘ࡑ̤̭̠ͬ̈́ḙ͈̏ાࣣȄ΀ȜΐͿϋΠ͈฼ତ̦ A* ͺσΌςΒθ́൲ै̱Ȅॼ͈ͤ฼ତ̦೹մ਀༹́൲ै̳͈̳ͥ͂ͥ͜ȅ̹͘Ȅུა໲͉́ A* ͺσΌςΒθ͂೹մ਀༹ͬழ̵͙ࣣ̹ͩ਀༹ͬໝࣣ͂ࡤ
͐ȅĵįĵġၑა౵
ȁུა໲͉́Ȅ೹մ਀༹̦͈̓೾ഽȄ௙֊൲΋ΑΠ͈ड઀౵ͅ߃̫̹̥̿ͬ฻
౯̳̹ͥ͛Ȅड੝̥ͣ஠͈̀વ‫ૂٺ‬༭ͬ঵̞̽̀ͥેఠ́ࠗॳ̱̹डౣࠐႹಿ
ࠗ͜ॳ̳ͥȅ̹͘Ȅड੝̥ͣ஠͈̀વ‫ૂٺ‬༭ͬ঵̞̽̀ͥેఠ́ࠗॳ̱̹डౣ
ࠐႹಿͬၑა౵͂ࡤ͐ȅғ36ғ‫ږ‬ၚഎ̈́࢐೒વ‫ٺ‬อ୆̤̫ͥͅζσΙ΀ȜΐͿϋΠ͈ࠐႹౝ॑਀༹

లĶડȁ೹մ਀༹͈ບ‫ث‬ġĶįĲġ৘ࡑ࿒എ
ȁུა໲́೹մ̱̹ࠐႹౝ॑਀༹̦Ȅ‫ܡ‬ం਀༹͈ A* ͺσΌςΒθ͞ၑა౵͂
๤͓̀Ȅ͈̓೾ഽ͈௙֊൲΋ΑΠ̥̈́ͥͅȄ̹͘Ȅ͈̓೾ഽ͈ࠗॳশ‫ͥ̈́ͅۼ‬̥ͬ‫̹̳͛ͥͅ෇ږ‬৘ࡑ̤̭̠ͬ̈́ȅĶįĳġུ৘ࡑ̜̥̠́̾ łī ͺσΌςΒθ̞̾̀ͅȁུ৘ࡑ̜̥̠́̾ A* ͺσΌςΒθ͈ଔ೰౵ h*)p* ͉ͅȄ৘ष͈ΦȜΡ p ̥ͣΌȜσ͈́͘֊൲΋ΑΠͬဥ̞̹ȅ̾ͤ͘ȄΘͼ·ΑΠρ༹͂൳༹̲༷́ࠗ
ॳ̳͈̳ͥ͂ͥ͜ȅĶįĴġ৘ࡑ۪‫ޏ‬৘ࡑ͉ͅ1ర͈ࠗॳ‫ঀͬܥ‬ဥ̱̹ȅ̷͈ࠗॳ‫͈ܥ‬ΑβΛ·͉ນ5.1͈೒̜ͤ́ͥȅ̹͘ȄίυΈρθ࡞ࢊ͉ͅ C++ ͬঀဥ̱Ȅ΋ϋΩͼσ۪‫ ͉ͅޏ‬Visual Studio2010ͬঀဥ̱̹ȅນĶįĲĻ ৘ࡑͅဥ̞̹ࠗॳ‫͈ܥ‬ΑβΛ·OS
CPUMemoryWindows 7
AMD Athlon X2 Dual Core Processor 5200+
3GBĶįĵġခփओ͈࠿೰
௙֊൲΋ΑΠ͈໹޳Ȇດ੔༊ओ̺̫͉́Ȅ೹մ਀༹̦࿹̞̥̠̥ͦ̀ͥ̓฻
౯̱̞̿ͣḙ̷̏́Ȅུა໲͉́Ȅ৘ࡑࠫ‫͈ض‬ٜଢ଼͈̹͛ͅȄခփओ͈࠿೰ͬ
̤̭̹̈́̽ḙ̭͉̏́Ȅ৘ࡑࠫ‫͈ض‬ΪΑΠΈρθͤ͢Ȅ৘ࡑࠫ‫ୃ̥ͣͅྶ͉ض‬ܰ໦ື̴̱̹̦̤̽̀ͣͅȄ3ດུոષ͈࠿೰͈͂̈́ͥ́ȄΦϋΩριΠςΛ
·࠿೰͈ΑΞͻȜσȆΡͽχΑ༹ [8] ͬဥ̞̹ȅ̹͘Ȅ‫بྫܦ‬୰ͬȶ໹޳౵ͅओ̦̞̈́ȷ̱͂Ȅ‫ݕܤ‬ၚ͉1% ̱̹͂ȅ

ғ37ғĶįĶġ‫෇ږ‬৘ࡑġĶįĶįĲġ‫෇ږ‬৘ࡑඤယȁ̴͘Ȅ೹մ਀༹̦ A* ͺσΌςΒθͅ๤͓̀Ȅ௙֊൲΋ΑΠ̦઀̯̩̥̈́ͥ
̠̥̓ͬ۰ౙ̈́වႁΈρέ́‫̳ͥ෇ږ‬ȅ‫෇ږ‬৘ࡑͅঀဥ̱̹වႁΈρέͬ଎
5.1Ȅ଎5.2ͅা̳ȅ̹͘Ȅ‫෇ږڎ‬৘ࡑ͈મळͬນ5.2ͅা̳ȅ̯ͣͅȄ΀ȜΐͿϋΠ̦ໝତ͈ાࣣȄ஠΀ȜΐͿϋΠ́‫ٳ‬ইΦȜΡ͂࿒എ౷ΦȜΡ͉൳̺̦֚ȄΑΗȜΠ̳ͥΗͼηϋΈ̦֑̠͈̳͂ͥ͜ȅ଎ġĶįĲġΈρέĲ

ғ38ғ‫ږ‬ၚഎ̈́࢐೒વ‫ٺ‬อ୆̤̫ͥͅζσΙ΀ȜΐͿϋΠ͈ࠐႹౝ॑਀༹

଎ġĶįĳġΈρέĳນĶįĳĻ ‫෇ږڎ‬৘ࡑ͈୭೰
৘ࡑ๔࣢

Έρέ

‫ٳ‬ইΦȜΡ࿒എ౷ΦȜΡ

΀ȜΐͿϋΠତ

৘ࡑٝତ

1-1

Έρέ1

ΦȜΡ20

1-2

Έρέ2

ΦȜΡ20

ΦȜΡ4

1

1000

ΦȜΡ4

10

1000

2-1

Έρέ1

ΦȜΡ20

2-2

Έρέ2

ΦȜΡ20

ΦȜΡ4

1

1000

ΦȜΡ4

10

1000

ĶįĶįĳġ‫෇ږ‬৘ࡑࠫ‫ض‬ĶįĶįĳįĲġ৘ࡑġĲĮĲȁ΀ȜΐͿϋΠ͈௙֊൲΋ΑΠ͈໹޳Ȇດ੔༊ओ͂Ȅ৘ࡑͅါ̱̹໹޳ࠗॳশ
‫ͬۼ‬ນ5.3ͅা̳ .

ғ39ғນĶįĴĻ ৘ࡑĲĮĲ̤̫ͥͅ΋ΑΠ͈໹޳Ȇດ੔༊ओ͂໹޳ࠗॳশ‫ۼ‬ͺσΌςΒθ
A*
೹մ਀༹
ၑა౵

໹޳
66.49935.95834.927

ດ੔༊ओ
12.23
2.192
-

໹޳ࠗॳশ‫) ۼ‬s*
0.000210.00030-ȁ৘ࡑ1-1̤̫ͥͅ΀ȜΐͿϋΠ͈௙֊൲΋ΑΠ͈ΪΑΠΈρθͬ଎5.3ͅা̳ .
A*

ᥦ᱌ᡭἲ

⌮ㄽ್

900
800
700

ᗘᩘ

600
500
400
300
200
100
0
34 36 38 40 42 44 46 48 50 52 54 56 58 60 62 64 66 68 70⥲⛣ືࢥࢫࢺ

଎ġĶįĴĻ ৘ࡑġĲĮĲ͈௙֊൲΋ΑΠ͈ΪΑΠΈρθ

ȁA* ͺσΌςΒθ͂೹մ਀༹ͅ‫̱̀۾‬΋ΑΠ͈໹޳౵ͅచ̱͈̀࠿೰͈ࠫ‫ض‬Ȅ
t = 34.106, P = 0.000͂̈́ͤ‫بྫܦ‬୰͉‫̹̯ͦݕܤ‬ȅ̽̀͢ȄA* ͺσΌςΒθ͂೹մ਀༹̤̫ͥͅ΋ΑΠ͈໹޳౵͉ͅခփओ̦ခͥȅĶįĶįĳįĳġ৘ࡑġĲĮĳȁ΀ȜΐͿϋΠ͈௙֊൲΋ΑΠ͈໹޳Ȇດ੔༊ओ͂Ȅ৘ࡑͅါ̱̹໹޳ࠗॳশ
‫ͬۼ‬ນ5.4ͅা̳ȅғ40ғ‫ږ‬ၚഎ̈́࢐೒વ‫ٺ‬อ୆̤̫ͥͅζσΙ΀ȜΐͿϋΠ͈ࠐႹౝ॑਀༹

ນĶįĵĻ ৘ࡑĲĮĳ̤̫ͥͅ΋ΑΠ͈໹޳Ȇດ੔༊ओ͂໹޳ࠗॳশ‫ۼ‬ͺσΌςΒθ
A*
೹մ਀༹
ໝࣣ
ၑა౵

໹޳
42.32735.39340.51634.934

ດ੔༊ओ
3.716
1.050
2.790
-

໹޳ࠗॳশ‫) ۼ‬s*
0.001120.001860.00156-ȁ৘ࡑ1-2̤̫ͥͅ΀ȜΐͿϋΠ͈௙֊൲΋ΑΠ͈ΪΑΠΈρθͬ଎5.5ͅা
̳ȅ
A*

⌮ㄽ್

」ྜ

ᥦ᱌ᡭἲ

900
800
700

ᗘᩘ

600
500
400
300
200
100
0
34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

⥲⛣ືࢥࢫࢺ

଎ġĶįĵĻ ৘ࡑġĲĮĳ͈௙֊൲΋ΑΠ͈ΪΑΠΈρθ

ȁ̹͘Ȅ3͈̾਀༹ͅ‫̱̀۾‬΋ΑΠ͈໹޳౵ͅచ̳ͥခփओ࠿೰͈ࠫ‫ͬض‬ນ5.5
ͅা̳ȅນĶįĶĻ ৘ࡑĲĮĳ̤̫ͥͅ΋ΑΠ͈໹޳͈ခփओ࠿೰ࠫ‫ض‬๤‫ڛ‬చય
A*ȇ೹մ਀༹
A*ȇໝࣣ೹մ਀༹ȇໝࣣ

t
3.195411.50531.635

ғ41ғ

P
0.000
0.000
0.000

ခփओ
ခ
ခ
ခ

ĶįĶįĳįĴġ৘ࡑġĳĮĲȁ΀ȜΐͿϋΠ͈௙֊൲΋ΑΠ͈໹޳Ȇດ੔༊ओ͂Ȅ৘ࡑͅါ̱̹໹޳ࠗॳশ
‫ͬۼ‬ນ5.6ͅা̳ȅນĶįķĻ ৘ࡑĳĮĲ̤̫ͥͅ΋ΑΠ͈໹޳Ȇດ੔༊ओ͂໹޳ࠗॳশ‫ۼ‬ͺσΌςΒθ
A*
೹մ਀༹
ၑა౵

໹޳
42.37035.94534.090ດ੔༊ओ
14.671
5.399

໹޳ࠗॳশ‫) ۼ‬s*
0.000310.00017--ȁ৘ࡑ2-1̤̫ͥͅ΀ȜΐͿϋΠ͈௙֊൲΋ΑΠ͈ΪΑΠΈρθͬ଎5.5ͅা
̳ȅ
A*

⌮ㄽ್

ᥦ᱌ᡭἲ

1000
900
800

ᗘᩘ

700
600
500
400
300
200
100
0
34

37

40

43

46

49

52

55

58

61

64

67

70

⥲⛣ືࢥࢫࢺ

଎ġĶįĶĻ ৘ࡑġĳĮĲ͈௙֊൲΋ΑΠ͈ΪΑΠΈρθ

ȁA* ͺσΌςΒθ͂೹մ਀༹ͅ‫̱̀۾‬΋ΑΠ͈໹޳౵ͅచ̱͈̀࠿೰͈ࠫ‫ض‬Ȅ
t = 18.175, P = 0.000͂̈́ͤ‫بྫܦ‬୰͉‫̹̯ͦݕܤ‬ȅ̽̀͢ȄA* ͺσΌςΒθ͂೹մ਀༹̤̫ͥͅ΋ΑΠ͈໹޳౵͉ͅခփओ̦ခͥȅғ42ғ‫ږ‬ၚഎ̈́࢐೒વ‫ٺ‬อ୆̤̫ͥͅζσΙ΀ȜΐͿϋΠ͈ࠐႹౝ॑਀༹

ĶįĶįĳįĵġ৘ࡑġĳĮĳȁ΀ȜΐͿϋΠ͈௙֊൲΋ΑΠ͈໹޳Ȇດ੔༊ओ͂Ȅ৘ࡑͅါ̱̹໹޳ࠗॳশ
‫ͬۼ‬ນ5.7ͅা̳ȅນĶįĸĻ ৘ࡑĳĮĳ̤̫ͥͅ΋ΑΠ͈໹޳Ȇດ੔༊ओ͂໹޳ࠗॳশ‫ۼ‬ͺσΌςΒθ
A*
೹մ਀༹
ໝࣣ
ၑა౵

໹޳
35.43235.23735.17834.071

ດ੔༊ओ
2.736
1.024
2.018
-

໹޳ࠗॳশ‫) ۼ‬s*
0.000960.001630.00154-ȁ৘ࡑ2-2̤̫ͥͅ΀ȜΐͿϋΠ͈௙֊൲΋ΑΠ͈ΪΑΠΈρθͬ଎5.6ͅা
̳ȅ
A*

ᥦ᱌ᡭἲ

⌮ㄽ್

」ྜ

1000
900
800

ᗘᩘ

700
600
500
400
300
200
100
0
34

35

36

37

38

39

40

41

42

43

44

45

46

⥲⛣ືࢥࢫࢺ

଎ġĶįķĻ ৘ࡑĳĮĳ͈௙֊൲΋ΑΠ͈ΪΑΠΈρθ

ȁȁ̹͘Ȅ3͈̾਀༹ͅ‫̱̀۾‬΋ΑΠ͈໹޳౵ͅచ̳ͥခփओ࠿೰͈ࠫ‫ͬض‬ນ5.8
ͅা̳ȅ

ғ43ғ

ນĶįĹĻ ৘ࡑĳĮĳ̤̫ͥͅ΋ΑΠ͈໹޳͈ခփओ࠿೰ࠫ‫ض‬๤‫ڛ‬చય
A*ȇ೹մ਀༹
A*ȇໝࣣ೹մ਀༹ȇໝࣣ

t
19.0049.977
16.974

P
0.000
0.000
0.000

ခփओ
ခ
ခ
ခ

ĶįĶįĴġࣉख़ȁ‫෇ږ‬৘ࡑ͈ࠫ‫ͤ͢ض‬Ȅ೹մ਀༹͉‫ܡ‬ం਀༹ͤ͢͜໹޳֊൲΋ΑΠ͉઀̯̩̈́
̭ͥ͂ͬা̱̞̀ͥȅ̹̺̱Ȅ̷͈ࠐႹ͈ࠗॳ͉ͅ೹մ਀༹͈༷̦শ‫ͬۼ‬ါ̳ͥȅ̱̥̱Ȅ̷͈ओ͉֊൲΋ΑΠͅ๤͓̀઀̯̞̹͛‫ྫ͉ޣג‬ণ̧́ͥȅ̾ͤ͘Ḙ͈̠۪̏̈́͢‫̞̤̀ͅޏ‬Ȅ೹մ਀༹̦࢘‫ض‬എ̜́ͥḙ̷̏́Ȅষ୯̥ͣ৘
ष͈౷଎ΟȜΗ̥ͣ୆଼̱̹Έρέ́͜Ȅ࢘‫̹̳͛ͥ෇ږ̥̠̥̜̦ͬ̓ͥض‬ͅ৘ࡑ̤̭̠ͬ̈́ȅĶįķġ؊ဥ৘ࡑġĶįķįĲġ؊ဥ৘ࡑඤယ
ȁ؊ဥ႕̱͂̀Ȅ৘ष͈౷଎ΟȜΗ̥ͣ୆଼̱̹Έρέ́͜೹մ਀༹͈࢘‫̦ض‬̜̭ͥ͂ͬ‫̳ͥ෇ږ‬ȅȁུა໲͉́Ȅ࣭ാ౷ၑ͈֭อ࣐̱̞̀ͥ2003ාഽๅ౷଎ΟȜΗ [6] ̥ͣවႁΈρέ G' = )V, E, C, B* ͬ୆଼̱̹ḙ̭͉̏́ȄV ͉࢐ओത͈ਬࣣȄE ͉࢐ओതͬࠒ̪ൽႹ͈ਬࣣȄC ͉࢐ओത͂࢐ओത͈‫ݻ‬ၗ͈ਬࣣȄB ͉ൽႹ͈વ‫ٺ‬อ୆ၚ̳͂ͥȅ̹͘ȄൽႹ͈વ‫ٺ‬อ୆ၚ B ͉ྴࡣ‫ؚ‬ঌ̦อ࣐̱̞̀ͥȶ̜̹͈̈́‫͈ځ‬౷ૼζΛίȷ[7] ͈‫ࡏܓاેס‬ഽͬ‫ͅܖ‬୭೰̱̹ȅ‫ڎ‬؊ဥ৘ࡑ͈મळͬນ5.9ͅা̳ȅ̹͘Ȅ΀ȜΐͿϋΠ̦ໝତ͈ાࣣȄ஠΀ȜΐͿϋΠ́‫ٳ‬ইΦȜΡ͂࿒എ౷ΦȜΡ͉൳̺̦֚ȄΑΗȜΠ̳ͥΗͼηϋΈ̦֑̠͈̳͂ͥ͜ȅғ44ғ‫ږ‬ၚഎ̈́࢐೒વ‫ٺ‬อ୆̤̫ͥͅζσΙ΀ȜΐͿϋΠ͈ࠐႹౝ॑਀༹

ນĶįĺĻ ‫ڎ‬؊ဥ৘ࡑ͈୭೰
৘ࡑ๔࣢
3
4
5-1
5-2
5-3
5-4
5-5
6-1
6-2
6-3

౷ߊ
઎გߊ
ಎఆߊ
ಎఆߊ
ಎఆߊ
ಎఆߊ
ಎఆߊ
ಎఆߊ
ୌߊ
ୌߊ
ୌߊ

‫ٳ‬ইպ౾
࿒എ౷΀ȜΐͿϋΠତ઎გߊ࿨ਫ਼೧ໍ࢖‫׬‬1ಎఆߊ࿨ਫ਼ ಎఆ࢖‫׬‬1
ઐࡔ಴3ಢ࿒ ಎఆ࢖‫׬‬1
ઐࡔ಴3ಢ࿒ ಎఆ࢖‫׬‬10
ઐࡔ಴3ಢ࿒ ಎఆ࢖‫׬‬100
ઐࡔ಴3ಢ࿒ ಎఆ࢖‫׬‬20
ઐࡔ಴3ಢ࿒ ಎఆ࢖‫׬‬30ධཱ‫ק‬1ಢ࿒ ๸෧ോ࢖‫׬‬1ධཱ‫ק‬1ಢ࿒ ๸෧ോ࢖‫׬‬10ධཱ‫ק‬1ಢ࿒ ๸෧ോ࢖‫׬‬
20

৘ࡑٝତ
1000
1000
1000
1000
1000
1000
1000
1000
1000
1000

Ķįķįĳġ؊ဥ৘ࡑࠫ‫ض‬ġĶįķįĳįĲġ৘ࡑĴȁ΀ȜΐͿϋΠ͈֊൲΋ΑΠ )m* ͈໹޳Ȇດ੔༊ओ͂Ȅ৘ࡑͅါ̱̹໹޳ࠗ
ॳশ‫ͬۼ‬ນ5.10ͅা̳ȅນĶįĲıĻ ৘ࡑĴ̤̫ͥͅ΋ΑΠ͈໹޳Ȇດ੔༊ओ͂໹޳ࠗॳশ‫ۼ‬ͺσΌςΒθA*೹մ਀༹ၑა౵໹޳ )m*
998.50998.35932.38ດ੔༊ओ )m*
122.8
122.6
-

໹޳ࠗॳশ‫) ۼ‬s*
0.001850.00789-ȁ΀ȜΐͿϋΠ͈௙֊൲΋ΑΠ )m* ͈ΪΑΠΈρθͬ଎5.7ͅা̳ȅ

ғ45ғ

A*

ᥦ᱌ᡭἲ

⌮ㄽ್

500
450
400

ᗘᩘ

350
300
250
200
150
100
50
0

⥲⛣ືࢥࢫࢺ(m)଎ĶįĸĻ ৘ࡑĴ͈௙֊൲΋ΑΠ͈ΪΑΠΈρθ

ȁA* ͺσΌςΒθ͂೹մ਀༹ͅ‫̱̀۾‬΋ΑΠ͈໹޳౵ͅచ̱͈̀࠿೰͈ࠫ‫ض‬Ȅ
t = 0.054, P = 0.998͂̈́ͤ‫بྫܦ‬୰͉‫̹̥̯̽̈́ͦݕܤ‬ȅ̽̀͢ȄA* ͺσΌςΒθ͂೹մ਀༹̤̫ͥͅ΋ΑΠ͈໹޳౵͉ͅခփओ̦ခ͉ͥ͂࡞̢̞̈́ȅĶįķįĳįĳġ৘ࡑĵȁ΀ȜΐͿϋΠ͈௙֊൲΋ΑΠ )m* ͈໹޳Ȇດ੔༊ओ͂Ȅ৘ࡑͅါ̱̹໹޳
ࠗॳশ‫ͬۼ‬ນ5.11ͅা̳ȅນĶįĲĲĻ ৘ࡑĵ̤̫ͥͅ΋ΑΠ͈໹޳Ȇດ੔༊ओ͂໹޳ࠗॳশ‫ۼ‬ͺσΌςΒθA*೹մ਀༹ၑა౵໹޳ )m*
2390.452355.78
1980.52ດ੔༊ओ )m*
363.9
325.6
-

໹޳ࠗॳশ‫) ۼ‬s*
0.00626
0.78707-ȁ΀ȜΐͿϋΠ͈֊൲΋ΑΠ )m* ͈ΪΑΠΈρθͬ଎5.8ͅা̳ȅғ46ғ‫ږ‬ၚഎ̈́࢐೒વ‫ٺ‬อ୆̤̫ͥͅζσΙ΀ȜΐͿϋΠ͈ࠐႹౝ॑਀༹

A*

ᥦ᱌ᡭἲ

⌮ㄽ್

300
250

ᗘᩘ

200
150
100
50
0

⥲⛣ືࢥࢫࢺ(m)଎ġĶįĹĻ ৘ࡑĵ͈௙֊൲΋ΑΠ͈ΪΑΠΈρθ

ȁA* ͺσΌςΒθ͂೹մ਀༹ͅ‫̱̀۾‬΋ΑΠ͈໹޳౵ͅచ̱͈̀࠿೰͈ࠫ‫ض‬Ȅ
t = 1.807, P = 0.167͂̈́ͤ‫بྫܦ‬୰͉‫̹̥̯̽̈́ͦݕܤ‬ȅ̽̀͢ȄA* ͺσΌςΒθ͂೹մ਀༹̤̫ͥͅ΋ΑΠ͈໹޳౵͉ͅခփओ̦ခ͉ͥ͂࡞̢̞̈́ȅĶįķįĳįĴġ৘ࡑĶĮĲȁ΀ȜΐͿϋΠ͈֊൲΋ΑΠ )m* ͈໹޳Ȇດ੔༊ओ͂Ȅ৘ࡑͅါ̱̹໹޳ࠗ
ॳশ‫ͬۼ‬ນ5.12ͅা̳ȅນĶįĲĳĻ ৘ࡑĶĮĲ̤̫ͥͅ΋ΑΠ͈໹޳Ȇດ੔༊ओ͂໹޳ࠗॳশ‫ۼ‬ͺσΌςΒθA*೹մ਀༹ၑა౵໹޳ )m*
2209.74
1631.941518.90ດ੔༊ओ )m*
411.41
237.29-໹޳ࠗॳশ‫) ۼ‬s*
0.00553
0.05872-ȁ΀ȜΐͿϋΠ͈௙֊൲΋ΑΠ )m* ͈ΪΑΠΈρθͬ଎5.9ͅা̳ȅ

ғ47ғ

⌮ㄽ್

A*

ᥦ᱌ᡭἲ

400
350
300

ᗘᩘ

250
200
150
100
50
0
1400 1550 1700 1850 2000 2150 2300 2450 2600 2750 2900 3050 3200 3350 3500⥲⛣ືࢥࢫࢺ(m)଎ĶįĺĻ ৘ࡑĶĮĲ͈௙֊൲΋ΑΠ͈ΪΑΠΈρθ

ȁA* ͺσΌςΒθ͂೹մ਀༹ͅ‫̱̀۾‬΋ΑΠ͈໹޳౵ͅచ̱͈̀࠿೰͈ࠫ‫ض‬Ȅ
t = 33.116, P = 0.000͂̈́ͤ‫بྫܦ‬୰͉‫̹̯ͦݕܤ‬ȅ̽̀͢ȄA* ͺσΌςΒθ͂೹մ਀༹̤̫ͥͅ΋ΑΠ͈໹޳౵͉ͅခփओ̦ခͥȅĶįķįĳįĵġ৘ࡑġĶĮĳȁ΀ȜΐͿϋΠ͈֊൲΋ΑΠ )m* ͈໹޳Ȇດ੔༊ओ͂Ȅ৘ࡑͅါ̱̹໹޳ࠗ
ॳশ‫ͬۼ‬ນ5.13ͅা̳ȅນĶįĲĴĻ ৘ࡑĶĮĳ̤̫ͥͅ΋ΑΠ͈໹޳Ȇດ੔༊ओ͂໹޳ࠗॳশ‫ۼ‬ͺσΌςΒθ
A*
೹մ਀༹
ໝࣣ
ၑა౵

໹޳ )m*
1697.091621.50
1633.021517.91ດ੔༊ओ )m*123.61
178.6099.90-໹޳ࠗॳশ‫) ۼ‬s*
0.02049
0.31606
0.10512-ȁ΀ȜΐͿϋΠ͈௙֊൲΋ΑΠ )m* ͈ΪΑΠΈρθͬ଎5.10ͅা̳ȅғ48ғ‫ږ‬ၚഎ̈́࢐೒વ‫ٺ‬อ୆̤̫ͥͅζσΙ΀ȜΐͿϋΠ͈ࠐႹౝ॑਀༹

A*

ᥦ᱌ᡭἲ

」ྜ

⌮ㄽ್

450
400
350

ᅇᩘ

300
250
200
150
100
50
0
1400 1500 1600 1700 1800 1900 2000 2100 2200 2300 2400 2500⥲⛣ືࢥࢫࢺ(m)଎ĶįĲıĻ ৘ࡑĶĮĳ͈௙֊൲΋ΑΠ͈ΪΑΠΈρθ

ȁ̹͘Ȅ3͈̾਀༹ͅ‫̱̀۾‬΋ΑΠ͈໹޳౵ͅచ̳ͥခփओ࠿೰͈ࠫ‫ͬض‬ນ5.14
ͅা̳ȅນĶįĲĵĻ ৘ࡑĶĮĳ̤̫ͥͅ΋ΑΠ͈໹޳͈ခփओ࠿೰ࠫ‫ض‬๤‫ڛ‬చય
A*ȇ೹մ਀༹
A*ȇໝࣣ೹մ਀༹ȇໝࣣ

t
17.23913.34610.340

P
0.000
0.000
0.000

ခփओ
ခ
ခ
ခ

ĶįķįĳįĶġ৘ࡑĶĮĴȁ΀ȜΐͿϋΠ͈֊൲΋ΑΠ )m* ͈໹޳Ȇດ੔༊ओ͂Ȅ৘ࡑͅါ̱̹໹޳ࠗ
ॳশ‫ͬۼ‬ນ5.15ͅা̳ȅғ49ғ

ນĶįĲĶĻ ৘ࡑĶĮĴ̤̫ͥͅ΋ΑΠ͈໹޳Ȇດ੔༊ओ͂໹޳ࠗॳশ‫ۼ‬ͺσΌςΒθ
A*
೹մ਀༹
ໝࣣ
ၑა౵

໹޳ )m*
1537.18
1632.04
1529.911519.17ດ੔༊ओ )m*
56.28
255.3
55.07
-

໹޳ࠗॳশ‫) ۼ‬s*
0.17054
3.149190.67886-ȁ΀ȜΐͿϋΠ͈௙֊൲΋ΑΠ )m* ͈ΪΑΠΈρθͬ଎5.11ͅা̳ȅ
A*

ᥦ᱌ᡭἲ

」ྜ

⌮ㄽ್

600
500

ᗘᩘ

400
300
200

0

1400
1450
1500
1550
1600
1650
1700
1750
1800
1850
1900
1950
2000
2050
2100
2150
2200
2250
2300
2350
2400
2450
2500
2550
2600
2650
2700
2750
2800
2850
2900
2950

100

⥲⛣ືࢥࢫࢺ(m)଎ĶįĲĲĻ ৘ࡑĶĮĴ͈௙֊൲΋ΑΠ͈ΪΑΠΈρθ

ȁ̹͘Ȅ3̾਀༹ͅ‫̱̀۾‬΋ΑΠ͈໹޳౵ͅచ̳ͥခփओ࠿೰͈ࠫ‫ͬض‬ນ5.16
ͅা̳ȅນĶįĲķĻ ৘ࡑĶĮĴ̤̫ͥͅ΋ΑΠ͈໹޳͈ခփओ࠿೰ࠫ‫ض‬๤‫ڛ‬చય
A*ȇ೹մ਀༹
A*ȇໝࣣ೹մ਀༹ȇໝࣣ

t
2.296
5.086
5.592

P
0.000
0.000
0.000

ғ50ғ

ခփओ
ခ͉͂࡞̢̞̈́ခခ‫ږ‬ၚഎ̈́࢐೒વ‫ٺ‬อ୆̤̫ͥͅζσΙ΀ȜΐͿϋΠ͈ࠐႹౝ॑਀༹

Ķįķįĳįķġ৘ࡑĶĮĵȁ΀ȜΐͿϋΠ͈֊൲΋ΑΠ )m* ͈໹޳Ȇດ੔༊ओ͂Ȅ৘ࡑͅါ̱̹໹޳ࠗ
ॳশ‫ͬۼ‬ນ5.17ͅা̳ȅນĶįĲĸĻ ৘ࡑĶĮĵ̤̫ͥͅ΋ΑΠ͈໹޳Ȇດ੔༊ओ͂໹޳ࠗॳশ‫ۼ‬ᐔဋ )m*
1062.391032.761049.27
963.05ͺσΌςΒθ
A*
೹մ਀༹
ໝࣣ
ၑა౵

ᮡḰ஍Ꮕ )m*
91.04
88.14
86.83
-

ᐔဋ⸘▚ᤨ㑆 )s*
0.03772
0.438290.16579-ȁ΀ȜΐͿϋΠ͈௙֊൲΋ΑΠ )m* ͈ΪΑΠΈρθͬ଎5.12ͅা̳ȅ

」ྜ

ᥦ᱌ᡭἲ

A*

⌮ㄽ್

500
450
400

ᗘᩘ

350
300
250
200
150
100

1750

1700

1650

1600

1550

1500

1450

1400

1350

1300

1250

1200

1150

1100

1050

950

1000

900

850

800

0

750

50

⥲⛣ືࢥࢫࢺ(m)଎ĶįĲĲĻ ৘ࡑĶĮĵ͈௙֊൲΋ΑΠ͈ΪΑΠΈρθ

ȁ̹͘Ȅ3͈̾਀༹ͅ‫̱̀۾‬΋ΑΠ͈໹޳౵ͅచ̳ͥခփओ࠿೰͈ࠫ‫ͬض‬ນ5.18
ͅা̳ȅ

ғ51ғ

ນĶįĲĹĻ ৘ࡑĶĮĵ̤̫ͥͅ΋ΑΠ͈໹޳͈ခփओ࠿೰ࠫ‫ض‬๤‫ڛ‬చય
A*㧦ឭ᩺ᚻᴺA*㧦ⶄว೹մ਀༹ȇໝࣣ

t
9.277
3.744
5.705

P
0.000
0.000
0.000

ခփओ
ခ
ခ
ခ

Ķįķįĳįĸġ৘ࡑĶĮĶȁ΀ȜΐͿϋΠ͈௙֊൲΋ΑΠ )m* ͈໹޳Ȇດ੔༊ओ͂Ȅ৘ࡑͅါ̱̹໹޳
ࠗॳশ‫ͬۼ‬ນ5.19ͅা̳ȅນĶįĲĺĻ ৘ࡑĶĮĶ̤̫ͥͅ΋ΑΠ͈໹޳Ȇດ੔༊ओ͂໹޳ࠗॳশ‫ۼ‬ᐔဋ )m*
1007.80
993.70990.04930.66ͺσΌςΒθ
A*
೹մ਀༹
ໝࣣ
ၑა౵

ᮡḰ஍Ꮕ )m*
85.58
82.23
74.28
-

ᐔဋ⸘▚ᤨ㑆 )s*
0.05782
0.43575
0.17549-ȁ΀ȜΐͿϋΠ͈௙֊൲΋ΑΠ )m* ͈ΪΑΠΈρθͬ଎5.13ͅা̳ȅ
A*

ᥦ᱌ᡭἲ

」ྜ

⌮ㄽ್

500
450
400

ᗘᩘ

350
300
250
200
150
100
50
0

⥲⛣ືࢥࢫࢺ(m)଎ĶįĲĴĻ ৘ࡑĶĮĶ͈௙֊൲΋ΑΠ͈ΪΑΠΈρθ

ғ52ғ‫ږ‬ၚഎ̈́࢐೒વ‫ٺ‬อ୆̤̫ͥͅζσΙ΀ȜΐͿϋΠ͈ࠐႹౝ॑਀༹

ȁ̹͘Ȅ3͈̾਀༹ͅ‫̱̀۾‬΋ΑΠ͈໹޳౵ͅచ̳ͥခփओ࠿೰͈ࠫ‫ͬض‬ນ5.20
ͅা̳ȅນĶįĳıĻ ৘ࡑĶĮĶ̤̫ͥͅ΋ΑΠ͈໹޳͈ခփओ࠿೰ࠫ‫ض‬๤‫ڛ‬చય
A*㧦ឭ᩺ᚻᴺA*㧦ⶄว೹մ਀༹ȇໝࣣ

t
4.677
5.290
0.599

P
0.000
0.000
0.932

ခփओ
ခ
ခ
ခ͉͂࡞̢̞̈́

ĶįķįĳįĹġ৘ࡑġķĮĲȁ΀ȜΐͿϋΠ͈֊൲΋ΑΠ )m* ͈໹޳Ȇດ੔༊ओ͂Ȅ৘ࡑͅါ̱̹໹޳ࠗ
ॳশ‫ͬۼ‬ນ5.21ͅা̳ȅນĶįĳĲ৘ࡑķĮĲ̤̫ͥͅ΋ΑΠ͈໹޳Ȇດ੔༊ओ͂໹޳ࠗॳশ‫ۼ‬ࠕ࡞ࠧ࡝࠭ࡓA*ឭ᩺ᚻᴺℂ⺰୯ᐔဋ )m*
2210.89
1916.49
1706.52ᮡḰ஍Ꮕ )m*
485.2
397.5
-

ᐔဋ⸘▚ᤨ㑆 )s*
0.00586
0.10926-ȁ΀ȜΐͿϋΠ͈௙֊൲΋ΑΠ )m* ͈ΪΑΠΈρθͬ଎5.14ͅা̳ȅ
A*

ᥦ᱌ᡭἲ

⌮ㄽ್

700
600

ᗘᩘ

500
400
300
200
100
0
1650 1800 1950 2100 2250 2400 2550 2700 2850 3000 3150 3300 3450 3600⥲⛣ືࢥࢫࢺ(m)଎ĶįĲĵĻ ৘ࡑķĮĲ͈௙֊൲΋ΑΠ͈ΪΑΠΈρθ

ғ53ғȁA* ͺσΌςΒθ͂೹մ਀༹ͅ‫̱̀۾‬΋ΑΠ͈໹޳౵ͅచ̱͈̀࠿೰͈ࠫ‫ض‬Ȅ
t = 18.731, P = 0.000͂̈́ͤ‫بྫܦ‬୰͉‫̹̯ͦݕܤ‬ȅ̽̀͢ȄA* ͺσΌςΒθ͂೹մ਀༹̤̫ͥͅ΋ΑΠ͈໹޳౵͉ͅခփओ̦ခͥȅĶįķįĳįĺġ৘ࡑķĮĳȁ΀ȜΐͿϋΠ͈֊൲΋ΑΠ )m* ͈໹޳Ȇດ੔༊ओ͂Ȅ৘ࡑͅါ̱̹໹޳ࠗ
ॳশ‫ͬۼ‬ນ5.22ͅা̳ȅນĶįĳĳĻ ৘ࡑķĮĳ̤̫ͥͅ΋ΑΠ͈໹޳Ȇດ੔༊ओ͂໹޳ࠗॳশ‫ۼ‬ᐔဋ )m*
1848.07
1824.26
1798.80
1704.31ͺσΌςΒθ
A*
೹մ਀༹
ໝࣣ
ၑა౵

ᮡḰ஍Ꮕ )m*
148.1
227.9
126.0
-

ᐔဋ⸘▚ᤨ㑆 )s*
0.026390.414190.15669-ȁ΀ȜΐͿϋΠ͈௙֊൲΋ΑΠ )m* ͈ΪΑΠΈρθͬ଎ 5.15ͅা̳ȅ
A*

ᥦ᱌ᡭἲ

1800

1900

」ྜ

⌮ㄽ್

700
600

ᅇᩘ

500
400
300
200
100
0
1600

1700

2000

2100

2200

2300

2400

2500

⥲⛣ືࢥࢫࢺ(m)଎ĶįĲĶĻ ৘ࡑķĮĳ͈௙֊൲΋ΑΠ͈ΪΑΠΈρθ

ȁ̹͘ȄA* ͺσΌςΒθ͂೹մ਀༹ͅ‫̱̀۾‬΋ΑΠ͈໹޳౵ͅచ̳ͥခփओ
࠿೰͈ࠫ‫ͬض‬ນ5.23ͅা̳ȅғ54ғ‫ږ‬ၚഎ̈́࢐೒વ‫ٺ‬อ୆̤̫ͥͅζσΙ΀ȜΐͿϋΠ͈ࠐႹౝ॑਀༹

ນĶįĳĴĻ ৘ࡑķĮĳ̤̫ͥͅ΋ΑΠ͈໹޳͈ခփओ࠿೰ࠫ‫ض‬๤‫ڛ‬చયtPခփओA*㧦ឭ᩺ᚻᴺ

9.671

0.000

ခ

A*㧦ⶄว

8.168

0.000

ခ

೹մ਀༹ȇໝࣣ

4.535

0.000

ခ

ĶįķįĳįĲıġ৘ࡑķĮĴȁ΀ȜΐͿϋΠ͈֊൲΋ΑΠ )m* ͈໹޳Ȇດ੔༊ओ͂Ȅ৘ࡑͅါ̱̹໹޳ࠗ
ॳশ‫ͬۼ‬ນ5.24ͅা̳ȅນĶįĳĵĻ ৘ࡑķĮĴ̤̫ͥͅ΋ΑΠ͈໹޳Ȇດ੔༊ओ͂໹޳ࠗॳশ‫ۼ‬ᐔဋ )m*
1773.49
1768.35
1749.46
1704.07ͺσΌςΒθ
A*
೹մ਀༹
ໝࣣ
ၑა౵

ᮡḰ஍Ꮕ )m*
95.77
146.7
87.65
-

ᐔဋ⸘▚ᤨ㑆 )s*
0.04951
0.63650
0.21919-ȁ΀ȜΐͿϋΠ͈௙֊൲΋ΑΠ )m* ͈ΪΑΠΈρθͬ଎5.16ͅা̳ȅ
A*

ᥦ᱌ᡭἲ

」ྜ

⌮ㄽ್

700
600

ᗘᩘ

500
400
300
200
100
0
1650 17001750 1800 18501900 19502000 2050 21002150 22002250 23002350⥲⛣ືࢥࢫࢺ(m)଎ĶįĲķĻ ৘ࡑķĮĴ͈௙֊൲΋ΑΠ͈ΪΑΠΈρθ

ғ55ғȁ̹͘Ȅ3͈̾਀༹ͅ‫̱̀۾‬΋ΑΠ͈໹޳౵ͅచ̳ͥခփओ࠿೰͈ࠫ‫ͬض‬ນ5.25
ͅা̳ȅນĶįĳĶĻ ৘ࡑķĮĴ̤̫ͥͅ΋ΑΠ͈໹޳͈ခփओ࠿೰ࠫ‫ض‬๤‫ڛ‬చય
A*㧦ឭ᩺ᚻᴺA*㧦ⶄว೹մ਀༹ȇໝࣣ

t
8.260
6.691
3.426

P
0.000
0.000
0.000

ခփओ
ခ
ခ
ခ

ĶįķįĴġࣉख़ġĶįķįĴįĲġ΀ȜΐͿϋΠĲఘ͈́৘ࡑࠫ‫ࣉض‬ख़ȁ؊ဥ৘ࡑ͈ࠫ‫ͤ͢ض‬Ȅ೹մ਀༹͈௙֊൲΋ΑΠ̦ A* ͺσΌςΒθ͈௙֊൲΋ΑΠͤ͢઀̯̩̭̦̥̹̈́ͥ͂ͩ̽ȅඅͅȄA* ͺσΌςΒθ͈௙֊൲΋ΑΠ̦ၑა౵͈௙֊൲΋ΑΠͤ͢ఱ໙ͅఱ̧̩̈́ͥાࣣͅȄ೹մ਀༹̦࢘‫ض‬എ̜̭̦́ͥ͂ఉ̞̞̠͂ࠫ‫̦ض‬ං̹ͣͦḙ͉̏ͦȄA* ͺσΌςΒθ̦વ‫ٺ‬อ୆ၚͬࣉၪ̵̱̞̞̞̀̈́́ȄA* ͺσΌςΒθ́ࠗॳ̯̹ͦࠐႹ͉ͅȄવ‫ٺ‬อ୆ၚ͈̞ࣞ༏̦ంह̱̱̠̭̦̀͂͘ఉ̞͈ͅచ̱Ȅ೹մ਀༹̦વ‫ٺ‬อ୆ၚ͈̞ࣞ༏ͬ๰̫̀ࠐႹͬࠗॳ̱̤̀ͤȄ೹մ਀༹́ࠗॳ̯̹ͦࠐႹષͅȄવ‫ٺ‬อ୆ၚ͈̞ࣞ༏̦ంह̱̞̭̦̿ͣ͂ၑဇ̺͂ࣉ̢ͣͦͥȅȁ̹͘ȄA* ͺσΌςΒθ͂೹մ਀༹͈௙֊൲΋ΑΠ͈ओ̦͕̞͂ͭ̓́̈́ા
ࣣ̦̜͈͉ͥȄΈρέ͈વ‫ٺ‬อ୆ၚ̦஠ఘഎͅ೩̥̹̽ͤȄֶٝࠐႹ̦डౣࠐ
Ⴙͅ๤͓̀๱ુͅಿ̥̹̱̽ͤ̀ȄA* ͺσΌςΒθ́ࠗॳ̱̹ࠐႹ͂೹մ਀
༹́ࠗॳ̱̹ࠐႹ̦൳̲̱̞̈́̽̀͘ͅȄA* ͺσΌςΒθ͂೹մ਀༹͈ओ̦
̩̱̠̭̦̈́̈́̽̀͂͘ၑဇ̺͂ࣉ̢ͣͦͥȅĶįķįĴįĳġ΀ȜΐͿϋΠໝତఘ͈́৘ࡑࠫ‫ࣉض‬ख़ȁ؊ဥ৘ࡑ͈ࠫ‫ͤ͢ض‬Ȅ΀ȜΐͿϋΠͬໝତఘ̱̹ͅાࣣ͉ȄA* ͺσΌςΒθ͂೹մ਀༹͈ओ̦઀̯̩̭̦̥̹̈́ͥ͂ͩ̽ḙ͉̏ͦȄ΀ȜΐͿϋΠ̦ໝତғ56ғ‫ږ‬ၚഎ̈́࢐೒વ‫ٺ‬อ୆̤̫ͥͅζσΙ΀ȜΐͿϋΠ͈ࠐႹౝ॑਀༹

ఘ̞ͥાࣣͅȄA* ͺσΌςΒθ͉́Ȅ࿒എ౷ͅ߃̞΀ȜΐͿϋΠ̦डౣࠐႹ
͈વ‫͈ٺ‬ခྫͬ‫͈̳́ͥ෇ږ‬Ȅ࿒എ౷̥ͣ‫΀̞׿‬ȜΐͿϋΠ͉ၑა౵͕͖͂൳
̲ࠐႹ́֊൲̧́ȄA* ͺσΌςΒθ͈௙֊൲΋ΑΠ̦ၑა౵͈௙֊൲΋ΑΠͅ߃̩̦̈́ͥȄ೹մ਀༹͉́डౣࠐႹͬडࢃ́͘೒̞ͣ̈́ȪडౣࠐႹ͈વ‫͈ٺ‬ခྫͬ‫̞̱̈́෇ږ‬ȫ̭̦̜͂ͤȄ΀ȜΐͿϋΠͬໝତ̱̀͜ͅȄၑა౵͈௙֊
൲΋ΑΠͅ߃̩̭̦̈́ͥ͂ઁ̞̭̦̈́͂ၑဇ̺͂ࣉ̢ͣͦͥȅȁ̹͘Ȅໝࣣ̦ A* ͺσΌςΒθ͞೹մ਀༹ͤ͢͜௙֊൲΋ΑΠ̦઀̯̩̈́ͥ
̭̦̜͈͉͂ͥȄ೹մ਀༹͈ౣਫ਼̜́ͥȶडౣࠐႹ͈વ‫͈ٺ‬ခྫͬ‫̱̈́෇ږ‬̞ȷ̞̠͂අ଻ͬȄA* ͺσΌςΒθ̦ક̱̞̥̺̀ͥͣ͂ࣉ̢ͣͦͥȅ̷̱̀Ȅໝࣣ̦೹մ਀༹ͤ͢͜௙֊൲΋ΑΠ̦ఱ̧̩̭̦̜͈͉̈́ͥ͂ͥȄ೹մ਀༹͈
ౣਫ਼̜́ͥȶडౣࠐႹ͈વ‫͈ٺ‬ခྫͬ‫̞̱̈́෇ږ‬ȷ̞̠͂අ଻ͬ A* ͺσΌςΒθ̦ક̳၌തͤ͢͜ȄA* ͺσΌςΒθ͈ౣਫ਼̜́ͥȶવ‫ͅٺ‬઩ඏ̱̳̞͞ȷ
̞̠͂අ଻̦ఱ̧̩̥̺̈́ͥͣ͂ࣉ̢ͣͦͥȅĶįķįĴįĴġ࠿೰ࠫ‫ࣉض‬ख़ȁ࠿೰͈ࠫ‫ض‬Ȅఉ̩͈ાࣣ́ခփओ̦ခͤȄ೹մ਀༹̦࿹̞̭̦̥ͦ̀ͥ͂ͩ̽
̹ȅ̹͘ȄA* ͺσΌςΒθ͈௙֊൲΋ΑΠ̦೹մ਀༹͈௙֊൲΋ΑΠͤ͢઀̯̩̈́ͥાࣣ͉́Ȅခփओ͉ྫ̥̹̽ȅ̾ͤ͘Ȅ৘ष͈౷଎ΟȜῌ೹մ਀༹
ͬഐဥ̱̹ાࣣ́࢘͜‫̹̥̦̭̜̦̽ͩ͂ͥض‬ȅల˒ડȁ͂͛͂ࣽ͘ࢃ͈‫ه‬ఴġķįĲġ͂͛͘
ȁུა໲ֶ͉́ٝࠐႹͬ၌ဥ̳ͥ਀༹ͬ೹մ̱Ȅ͕͖஠͈̀ાࣣ̤̞̀ͅȄ‫ܡ‬ం਀༹͈௙֊൲΋ΑΠͤ͢Ȅ೹մ਀༹͈௙֊൲΋ΑΠ̦઀̯̩̞̠̈́ͥ͂ࠫ‫ض‬ͬං̧̭̦̹ͥ͂́ȅ̹͘Ȅ೹մ਀༹͈௙֊൲΋ΑΠͤ͢Ȅ‫ܡ‬ం਀༹͈௙֊൲
΋ΑΠ̦઀̯̩̈́ͥાࣣ́͜Ȅခփओ͉ྫ̥̹̽ḙ͈̭̥̏͂ͣȄུა໲́೹

ғ57ғ

մ̱̹਀༹͉Ȅ̜̥̲ͣ͛વ‫ૂٺ‬༭ͬဓ̢̞̞ͣͦ̀̈́ે‫̞̤̀ͅޙ‬ခ̜̭̦࢘́ͥ͂໦̥̹̽ȅུ̱̹̦̽̀਀༹͉Ȅ౷ૼब‫ͬٺ‬ே೰̱̹ൽႹΥΛΠχȜ·̤̞̀ͅခ࢘̈́਀༹̜́ͥ͂ࣉ̢ͣͦͥȅķįĳġࣽࢃ͈‫ه‬ఴࣽࢃ͈‫ه‬ఴ̱͂̀Ȅո‫͈ئ‬2̦̾‫̬ͥͦͣݷ‬ɜȁ઩ඏଷࢄ
ȁȁུა໲͉́Ȅໝତఘ͈΀ȜΐͿϋΠ́৘ࡑ̳ͥषͅȄ΀ȜΐͿϋΠ൳আ͈઩ඏͬࣉၪ̱̞̞̀̈́ȅ̱̥̱Ȅ΀ȜΐͿϋΠ࡛ͬ৘ଲ‫͈ٮ‬৬ၰ൝͂ே೰
̱̹ાࣣ͞Ȅ਱໦ͅࢩ̩̞̈́ൽႹͬ֊൲̳ͥ͂ே೰̱̹ાࣣ͉ͅȄ઩ඏଷࢄ̦ຈါ̈́ͥ͂ͅࣉ̢ͣͦͥȅɜȁਸ਼తଷࢄ
ȁȁུა໲͉́Ȅໝତఘ͈΀ȜΐͿϋΠ́৘ࡑ̳ͥषͅȄ΀ȜΐͿϋΠ൳আ͈́ൽႹਸ਼తͬࣉၪ̱̞̞̀̈́ȅ̱̥̱Ȅ΀ȜΐͿϋΠ࡛ͬ৘ଲ‫͈ٮ‬৬ၰ൝͂ே೰̱̹ાࣣȄਸ਼తଷࢄ̦ຈါ̈́ͥ͂ͅࣉ̢ͣͦͥȅ৫ৃȁུࣂ͈֚໐͉Ք౶ఱ‫ݪࡄڠ‬੩଼ȪC-168ȫȶब‫ݣٺ‬੩΀ȜΐͿϋΠΏηντȜΏοϋ̤̫ͥͅ౷଎͈೰ၾ‫ا‬Ȇ໦႒͂‫ݣ‬੩୽ၞ͈‫۾‬Ⴒ଻ȷ
Ȫ2012ාഽȫ଼͈‫ض‬
̜́ͥȅ

४ࣉ໲ࡃ
Ȯ1ȯRobocup rescue simulation, http://roborescue.sourceforge.net/.
Ȯ2ȯP.E. Hart, N.J. Nilsson, and B. Raphael,ȨA formal basis for the heuristic determination ofғ58ғ‫ږ‬ၚഎ̈́࢐೒વ‫ٺ‬อ୆̤̫ͥͅζσΙ΀ȜΐͿϋΠ͈ࠐႹౝ॑਀༹
minimum cost paths , Systems Science and Cybernetics, IEEE Transactions on, 4)2*: pp. 100-107,1968.
Ȯ3ȯE.W.Dijkstra,ȨA note on two problems in connexion with graphs , Numerische mathematic,
1)1*: pp. 269-271, 1959.
Ȯ4ȯA. Stentz,ȨOptimal and efﬁcient path planning for partially-known environments , In Robotics
and Automation, 1994. Proceedings, 1994 IEEE International Conference on, pp. 3310-3317. IEEE,1994.
Ȯ5ȯS. Koenig and M. Likhachev,ȨA new principle for incremental heuristic search: Theoretical results , In
Proceedings of the International Conference on Automated Planning and Scheduling, pp. 410-413,
2006.
Ȯ6ȯ࣭ാ౷ၑ֭Ȅତ౵౷଎ 25000.
Ȯ7ȯ̜̹͈̈́‫͈ځ‬౷ૼζΛίȄ
http://www.city.nagoya.jp/kurashi/category/20-2-5-6-0-0-0-0-0-0.html.
Ȯ8ȯ‫ז‬ന࿭Ȅ‫݌‬നൽࢬȄȨൡࠗഎఉਹ๤‫ܖ༹͈ڛ‬யȩȄ΍ͼ΀ϋΞͻΑΠ২Ȅ1997

ғ59ғ