�ݺ�ߣ

‫ﺟﺴﺘﺠﻮ‬ ‫ﺗﻮﺳﻂ‬ ‫ﻣﺴﺎﺋﻞ‬ ‫ﺣﻞ‬‫ﺟﺴﺘﺠﻮ‬ ‫ﺗﻮﺳﻂ‬ ‫ﻣﺴﺎﺋﻞ‬ ‫ﺣﻞ‬‫ﺠﻮ‬ ‫ﺟ‬ ‫ﻮ‬ ‫ﻞ‬ ‫ﻞ‬‫ﺠﻮ‬ ‫ﺟ‬ ‫ﻮ‬ ‫ﻞ‬ ‫ﻞ‬
‫ﺳﻮم‬ ‫ﻓﺼﻞ‬
‫رﺿﻮي‬ ‫ﻧﺎﺻ‬ ‫ﺪ‬ ‫ﺳ‬‫رﺿﻮي‬ ‫ﻧﺎﺻﺮ‬ ‫ﺳﻴﺪ‬
Email: razavi@Comp.iust.ac.ir
1384
‫ﻣﻘﺪﻣﻪ‬‫ﻣﻘﺪﻣﻪ‬‫ﻣﻘﺪﻣﻪ‬‫ﻣﻘﺪﻣﻪ‬
‫ﺄﻟ‬ •‫ﻣﺴﺄﻟﻪ‬ ‫ﺣﻞ‬ ‫ﻫﺎي‬ ‫ﻋﺎﻣﻞ‬
•‫ﻣﺴﺄﻟﻪ‬ ‫اﻧﻮاع‬‫ﻣﺴﺄﻟﻪ‬ ‫اﻧﻮاع‬
•‫ﻣﺴﺄﻟﻪ‬ ‫ﺳﺎزي‬ ‫ﻓﺮﻣﻮﻟﻪ‬
•‫ﻧﻤﻮﻧﻪ‬ ‫ﻣﺴﺎﺋﻞ‬
•‫ﺟﺴﺘﺠﻮ‬ ‫اﺑﺘﺪاﻳﻲ‬ ‫ﻫﺎي‬ ‫اﻟﮕﻮرﻳﺘﻢ‬
N.Razavi- AI course-2005 2
‫ﻣﺴﺄﻟﻪ‬ ‫ﺣﻞ‬ ‫ﻫﺎي‬ ‫ﻋﺎﻣﻞ‬‫ﻣﺴﺄﻟﻪ‬ ‫ﺣﻞ‬ ‫ﻫﺎي‬ ‫ﻋﺎﻣﻞ‬‫ﻞ‬ ‫ي‬ ‫ﻞ‬‫ﻞ‬ ‫ي‬ ‫ﻞ‬
‫ﻣﺤﻴﻂ‬ ‫ﻣﻮرد‬ ‫در‬ ‫ﻓﺮﺿﻴﺎت‬:‫ﻗﻄﻌﻲ‬ ‫و‬ ‫ﮔﺴﺴﺘﻪ‬ ،‫ﻣﺸﺎﻫﺪه‬ ‫ﻗﺎﺑﻞ‬ ،‫اﻳﺴﺘﺎ‬
‫ﻣﺜﺎل‬‫روﻣﺎﻧ‬ ‫ﻣﺜﺎل‬‫روﻣﺎﻧ‬ ‫ﻣﺜﺎل‬:‫روﻣﺎﻧﻲ‬ ‫ﻣﺜﺎل‬:‫روﻣﺎﻧﻲ‬
•‫ﻚ‬‫ز‬‫ﻞ‬ ‫ﻄ‬ ‫ﺗ‬‫د‬‫؛‬ ‫ﺎﻧ‬‫ﻜﺎن‬‫ﻠ‬ ‫ﻓ‬‫اد‬ ‫آ‬ ‫ﺷ‬ •‫ﻳﻚ‬‫روز‬‫ﺗﻌﻄﻴﻞ‬‫در‬‫روﻣﺎﻧﻲ؛‬‫ﻣﻜﺎن‬‫ﻓﻌﻠﻲ‬‫ﺷﻬﺮآراد‬
•‫ﭘﺮواز‬،‫ﻓﺮدا‬‫ﺑﺨﺎرﺳﺖ‬‫را‬‫ﺗﺮك‬‫ﻣﻲ‬‫ﻛﻨﺪ‬.
•‫ﻓﺮﻣﻮﻟﻪ‬‫ﺳﺎزي‬‫ﻫﺪف‬:
–‫ﺑﻮدن‬‫در‬‫ﺑﺨﺎرﺳﺖ‬ ‫ن‬ ‫ﺑﻮ‬‫ر‬‫ﺖ‬ ‫ر‬ ‫ﺑ‬
•‫ﻓﺮﻣﻮﻟﻪ‬‫ﺳﺎزي‬‫ﻣﺴﺄﻟﻪ‬: ‫ﻮ‬ ‫ﺮ‬‫زي‬
–‫ﺣﺎﻟﺖ‬‫ﻫﺎ‬:‫ﺷﻬﺮﻫﺎي‬‫ﻣﺨﺘﻠﻒ‬
–‫ﻋﻤﻠﻴﺎت‬:‫رﻓﺘﻦ‬‫از‬‫ﺷﻬﺮي‬‫ﺑﻪ‬‫ﺷﻬﺮ‬‫دﻳﮕﺮ‬
•‫ﻳﺎﻓﺘﻦ‬‫ﭘﺎﺳﺦ‬:
–‫دﻧﺒﺎﻟﻪ‬‫اي‬‫از‬،‫ﺷﻬﺮﻫﺎ‬‫ﻣﺎﻧﻨﺪ‬: ‫دﻧﺒﺎﻟﻪ‬‫اي‬‫از‬،‫ﺷﻬﺮﻫﺎ‬‫ﻣﺎﻧﻨﺪ‬:
Arad Sibiu Fagaras Bucharest

‫ﻣﺜﺎل‬‫روﻣﺎﻧ‬ ‫ﻣﺜﺎل‬‫روﻣﺎﻧ‬ ‫ﻣﺜﺎل‬:‫روﻣﺎﻧﻲ‬ ‫ﻣﺜﺎل‬:‫روﻣﺎﻧﻲ‬
‫ﻣﺴﺄﻟﻪ‬ ‫اﻧﻮاع‬‫ﻣﺴﺄﻟﻪ‬ ‫اﻧﻮاع‬‫ع‬‫ع‬
•،‫ﻗﻄﻌﻲ‬‫ﻛﺎﻣﻼ‬‫ﻣﺸﺎﻫﺪه‬‫ﭘﺬﻳﺮ‬‫ﻣﺴﺎﺋﻞ‬‫ﺗﻚ‬–‫ﺣﺎﻟﺘﻪ‬
–‫ﻋﺎﻣﻞ‬‫دﻗﻴﻘﺎ‬‫ﻣﻲ‬‫داﻧﺪ‬‫در‬‫ﭼﻪ‬‫ﺣﺎﻟﺘﻲ‬‫ﺧﻮاﻫﺪ‬‫ﺑﻮد؛‬‫راه‬‫ﺣﻞ‬‫ﻳﻚ‬‫دﻧﺒﺎﻟﻪ‬‫ﻣﻲ‬‫ﺑﺎﺷﺪ‬.
•،‫ﻗﻄﻌﻲ‬‫ﻣﺸﺎﻫﺪه‬‫ﭘﺬﻳﺮ‬‫ﺟﺰﺋﻲ‬‫ﻣﺴﺎﺋﻞ‬‫ﭼﻨﺪ‬-‫ﺣﺎﻟﺘﻪ‬
–‫ﻣﻤﻜﻦ‬‫اﺳﺖ‬‫ﻋﺎﻣﻞ‬‫اﻳﺪه‬‫اي‬‫درﺑﺎره‬‫اﻳﻨﻜﻪ‬‫ﻛﺠﺎﺳﺖ‬‫ﻧﺪاﺷﺘﻪ‬‫ﺑﺎﺷﺪ؛‬‫راه‬‫ﺣﻞ‬‫ﻳﻚ‬‫دﻧﺒﺎﻟﻪ‬
‫ا‬‫اﺳﺖ‬.
‫ﻗﻄ‬‫ﺎ‬‫ﺎ‬‫ﺬ‬‫ﻞ‬ ‫ﺎ‬‫ﺎﻟ‬ ‫ا‬ •‫ﻏﻴﺮ‬‫ﻗﻄﻌﻲ‬‫و‬/‫ﻳﺎ‬‫ﻣﺸﺎﻫﺪه‬‫ﭘﺬﻳﺮ‬‫ﺟﺰﺋﻲ‬‫ﻣﺴﺎﺋﻞ‬‫اﺣﺘﻤﺎﻟﻲ‬
–‫ادراك‬‫اﻃﻼﻋﺎت‬‫ﺟﺪﻳﺪي‬‫درﺑﺎره‬‫ﺣﺎﻟﺖ‬‫ﻓﻌﻠﻲ‬‫ﻓﺮاﻫﻢ‬‫ﻣﻲ‬‫ﻛﻨﺪ‬.
‫ا‬ ‫ا‬‫ﺎ‬‫ا‬‫ﺎ‬ ‫ﮕ‬‫ﻔﺎ‬ ‫ا‬‫ﻛ‬ –‫در‬‫ﺣﻴﻦ‬‫اﺟﺮا‬‫ﺑﺎﻳﺪ‬‫از‬‫ﺣﺴﮕﺮﻫﺎ‬‫اﺳﺘﻔﺎده‬‫ﻛﻨﺪ‬.
–‫راه‬‫ﺣﻞ‬‫ﺑﻪ‬‫ﺻﻮرت‬‫ﻳﻚ‬‫درﺧﺖ‬
‫اﻏﻠ‬‫ا‬ ‫ا‬‫ﻚ‬‫ﺎ‬)(i t l –‫اﻏﻠﺐ‬‫ﺟﺴﺘﺠﻮ‬‫و‬‫اﺟﺮا‬‫ﺑﻪ‬‫ﺻﻮرت‬‫ﻳﻚ‬‫در‬‫ﻣﻴﺎن‬)(interleave
•‫ﻓﻀﺎي‬‫ﺣﺎﻟﺖ‬‫ﻧﺎﺷﻨﺎﺧﺘﻪ‬‫ﻣﺴﺎﺋﻞ‬‫اﻛﺘﺸﺎﻓﻲ‬(online)
‫ﻣﺜﺎل‬‫ﻣﻜﺶ‬ ‫دﻧﻴﺎي‬ ‫ﻣﺜﺎل‬‫ﻣﻜﺶ‬ ‫دﻧﻴﺎي‬ ‫ﻣﺜﺎل‬:‫ﻣﻜﺶ‬ ‫دﻧﻴﺎي‬ ‫ﻣﺜﺎل‬:‫ﻣﻜﺶ‬ ‫دﻧﻴﺎي‬
•‫ﺗﻚ‬-‫ﺣﺎﻟﺘﻪ‬،‫ﺷﺮوع‬‫در‬#5.
‫ا‬‫ﺣﻞ‬‫؟‬ ‫راه‬‫ﺣﻞ‬‫؟‬
•‫ﺗﻚ‬-‫ﺣﺎﻟﺘﻪ‬،‫ﺷﺮوع‬‫در‬#5.
‫ا‬‫ﻞ؟‬[Right Suck] ‫راه‬‫ﺣﻞ؟‬[Right, Suck]
•‫ﭼﻨﺪ‬-،‫ﺣﺎﻟﺘﻪ‬‫ﺷﺮوع‬‫در‬
{1 2 3 4 5 6 7 8}‫ﺜﺎل‬‫ﻞ‬Right {1, 2, 3, 4, 5, 6, 7, 8}‫ﻣﺜﺎل‬‫ﻋﻤﻞ‬Right
‫ﺑﻪ‬{2, 4, 6, 8}.
‫راه‬‫ﺣﻞ؟‬

•‫ﭼﻨﺪ‬-،‫ﺣﺎﻟﺘﻪ‬‫ﺷﺮوع‬‫در‬
{1, 2, 3, 4, 5, 6, 7, 8}‫ﻣﺜﺎل‬‫ﻋﻤﻞ‬Right
‫ﺑﻪ‬{2, 4, 6, 8}.
‫راه‬‫ﺣﻞ؟‬
[Right, Suck, Left, Suck]
•‫اﺣﺘﻤﺎﻟﻲ‬
-‫ﻏﻴﺮ‬‫ﻗﻄﻌﻲ‬:‫ﻣﻜﺶ‬‫ﻣﻲ‬‫ﺗﻮاﻧﺪ‬‫ﻳﻚ‬‫ﻓﺮش‬‫ﺗﻤﻴﺰ‬‫را‬‫ﻛﺜﻴﻒ‬‫ﻛﻨﺪ‬.
‫ك‬ ‫د‬‫ﻠ‬:‫د‬ ‫ﮔ‬‫ﺧﺎك‬‫د‬‫ﻞ‬‫ﻠ‬ ‫ﻓ‬ -‫درك‬‫ﻣﺤﻠﻲ‬:‫ﮔﺮد‬‫و‬‫ﺧﺎك‬‫در‬‫ﻣﺤﻞ‬‫ﻓﻌﻠﻲ‬
-‫ادراك‬:[L, Clean]‫ﻳﻌﻨﻲ‬‫ﺷﺮوع‬‫در‬#5‫ﻳﺎ‬#7
‫راه‬‫ﺣﻞ؟‬‫ﻞ‬
[Right, if dirt then Suck]
‫ﺗﻚ‬ ‫ﻣﺴﺎﺋﻞ‬ ‫ﺳﺎزي‬ ‫ﻓﺮﻣﻮﻟﻪ‬-‫ﺣﺎﻟﺘﻪ‬ ‫ﺗﻚ‬ ‫ﻣﺴﺎﺋﻞ‬ ‫ﺳﺎزي‬ ‫ﻓﺮﻣﻮﻟﻪ‬-‫ﺣﺎﻟﺘﻪ‬ ‫ﺗﻚ‬ ‫ﻣﺴﺎﺋﻞ‬ ‫ﺳﺎزي‬ ‫ﻓﺮﻣﻮﻟﻪ‬‫ﺣﺎﻟﺘﻪ‬ ‫ﺗﻚ‬ ‫ﻣﺴﺎﺋﻞ‬ ‫ﺳﺎزي‬ ‫ﻓﺮﻣﻮﻟﻪ‬‫ﺣﺎﻟﺘﻪ‬
‫ﻳﻚ‬‫ﻣﺴﺄﻟﻪ‬‫ﺑﻮﺳﻴﻠﻪ‬‫ﭼﻬﺎر‬‫ﻣﻮرد‬‫ﺗﻌﺮﻳﻒ‬‫ﻣﻲ‬‫ﺷﻮد‬:
‫ﻟ‬‫ﻟ‬ًA d 11..‫ﺣﺎﻟﺖ‬‫اوﻟﻴﻪ‬‫ﻣﺜﻼ‬‫ﺑﻮدن‬‫در‬‫ﺷﻬﺮ‬Arad
22..‫ﻋﻤﻞ‬‫ﻫﺎ‬‫ﻳﺎ‬‫ﺗﺎﺑﻊ‬‫ﺣﺎﻟﺖ‬‫ﺑﻌﺪي‬
S( x)=‫ﻣﺠﻤﻮﻋﻪ‬‫اي‬‫از‬‫زوج‬‫ﻫﺎي‬‫ﻋﻤﻞ‬-‫ﺣﺎﻟﺖ‬
• S(Arad) = {<Arad Zerind, Zerind>, …}
33..‫ﺗﺎﺑﻊ‬‫ﺗﺴﺖ‬‫ﻫﺪف‬
–‫ﺻﺮﻳﺢ‬:x = “at Bucharest”
N Di t( ) –‫ﺿﻤﻨﻲ‬:NoDirt( x)
44..‫ﺗﺎﺑﻊ‬‫ﻫﺰﻳﻨﻪ‬‫ﻣﺴﻴﺮ‬:
‫ﺜﺎل‬:‫ﻞ‬ ‫ا‬ ‫ﻓ‬‫ﺪا‬ ‫ﺗ‬‫ﻞ‬‫ﺎ‬‫ﺎ‬ ‫اﻧ‬‫ﺷﺪ‬ –‫ﻣﺜﺎل‬:‫ﻣﺠﻤﻮع‬،‫ﻓﻮاﺻﻞ‬‫ﺗﻌﺪاد‬‫ﻋﻤﻞ‬‫ﻫﺎي‬‫اﻧﺠﺎم‬‫ﺷﺪه‬‫و‬...
–‫ﻫﺰﻳﻨﻪ‬‫ﮔﺎم‬(Step cost):c( x, a, y) ≥ 0
•‫راه‬‫ﺣﻞ‬::‫دﻧﺒﺎﻟﻪ‬‫اي‬‫از‬‫ﻋﻤﻠﻴﺎت‬‫ﻛﻪ‬‫از‬‫ﺣﺎﻟﺖ‬‫اوﻟﻴﻪ‬‫ﺷﺮوع‬‫و‬‫ﺑﻪ‬‫ﺣﺎﻟﺖ‬‫ﻫﺪف‬‫ﺧﺘﻢ‬‫ﻣﻲ‬‫ﺷﻮد‬.
‫ﺣﺎﻟﺖ‬ ‫ﻓﻀﺎي‬ ‫ﻳﻚ‬ ‫اﻧﺘﺨﺎب‬‫ﺣﺎﻟﺖ‬ ‫ﻓﻀﺎي‬ ‫ﻳﻚ‬ ‫اﻧﺘﺨﺎب‬‫ﺣﺎﻟﺖ‬ ‫ﻓﻀﺎي‬ ‫ﻳﻚ‬ ‫اﻧﺘﺨﺎب‬‫ﺣﺎﻟﺖ‬ ‫ﻓﻀﺎي‬ ‫ﻳﻚ‬ ‫اﻧﺘﺨﺎب‬
•‫دﻧﻴﺎي‬‫واﻗﻌﻲ‬‫ﺑﻪ‬‫ﺷﺪت‬‫ﭘﻴﭽﻴﺪه‬‫ﻣﻲ‬‫ﺑﺎﺷﺪ‬
‫ا‬ ‫ﺎ‬‫ا‬‫ﻞ‬‫ﺄﻟ‬‫ﺎ‬‫ﻓﻀﺎ‬‫ﺎﻟ‬‫ا‬ ‫اﻧ‬‫ﺎﺷ‬ ،‫ﺑﻨﺎﺑﺮاﻳﻦ‬‫ﺑﺮاي‬‫ﺣﻞ‬‫ﻣﺴﺄﻟﻪ‬‫ﺑﺎﻳﺪ‬‫ﻓﻀﺎي‬‫ﺣﺎﻟﺖ‬‫اﻧﺘﺰاﻋﻲ‬‫ﺑﺎﺷﺪ‬.
•‫ﺣﺎﻟﺖ‬)‫اﻧﺘﺰاﻋﻲ‬(=‫ﻣﺠﻤﻮﻋﻪ‬‫اي‬‫از‬‫ﺣﺎﻟﺖ‬‫ﻫﺎي‬‫واﻗﻌﻲ‬
•‫ﻋﻤﻞ‬)‫اﻧﺘﺰاﻋﻲ‬(=‫ﺗﺮﻛﻴﺒﻲ‬‫ﭘﻴﭽﻴﺪه‬‫از‬‫ﻋﻤﻞ‬‫ﻫﺎي‬‫واﻗﻌﻲ‬
‫ﺜﻼ‬‫ﻞ‬Arad Zerind‫اﻧﺪ‬ ‫ﺗ‬‫ﻪ‬‫ا‬‫ﺪ‬‫از‬‫ﺎل‬ ‫ا‬‫ﺎﺷﺪ‬ –‫ﻣﺜﻼ‬‫ﻋﻤﻞ‬Arad Zerind‫ﻣﻲ‬‫ﺗﻮاﻧﺪ‬‫ﻣﺠﻤﻮﻋﻪ‬‫اي‬‫ﭘﻴﭽﻴﺪه‬‫از‬‫اﻋﻤﺎل‬‫ﺑﺎﺷﺪ‬.
•‫راه‬‫ﺣﻞ‬)‫اﻧﺘﺰاﻋﻲ‬(=
–‫ﻣﺠﻤﻮﻋﻪ‬‫اي‬‫از‬‫ﻣﺴﻴﺮﻫﺎي‬‫واﻗﻌﻲ‬‫ﻛﻪ‬‫در‬‫دﻧﻴﺎي‬‫واﻗﻌﻲ‬‫راه‬‫ﺣﻞ‬‫ﻣﻲ‬‫ﺑﺎﺷﻨﺪ‬.
•‫ﻫﺮ‬‫ﻋﻤﻞ‬‫اﻧﺘﺰاﻋ‬‫ﺑﺎﻳﺪ‬‫از‬‫ﻣﺴﺄﻟﻪ‬‫اﺻﻠ‬‫ﺳﺎده‬‫ﺗﺮ‬‫ﺑﺎﺷﺪ‬! ‫ﻫﺮ‬‫ﻋﻤﻞ‬‫اﻧﺘﺰاﻋﻲ‬‫ﺑﺎﻳﺪ‬‫از‬‫ﻣﺴﺄﻟﻪ‬‫اﺻﻠﻲ‬‫ﺳﺎده‬‫ﺗﺮ‬‫ﺑﺎﺷﺪ‬!
‫ﻣﺜﺎل‬‫ﻣﻜﺶ‬ ‫دﻧﻴﺎي‬ ‫ﺣﺎﻟﺖ‬ ‫ﻓﻀﺎي‬ ‫ﮔﺮاف‬ ‫ﻣﺜﺎل‬‫ﻣﻜﺶ‬ ‫دﻧﻴﺎي‬ ‫ﺣﺎﻟﺖ‬ ‫ﻓﻀﺎي‬ ‫ﮔﺮاف‬ ‫ﻣﺜﺎل‬:‫ﻣﻜﺶ‬ ‫دﻧﻴﺎي‬ ‫ﺣﺎﻟﺖ‬ ‫ﻓﻀﺎي‬ ‫ﮔﺮاف‬ ‫ﻣﺜﺎل‬:‫ﻣﻜﺶ‬ ‫دﻧﻴﺎي‬ ‫ﺣﺎﻟﺖ‬ ‫ﻓﻀﺎي‬ ‫ﮔﺮاف‬
•‫ﺣﺎﻻت؟‬
•‫اﻋﻤﺎل؟‬‫اﻋﻤﺎل؟‬
•‫ﻫﺪف؟‬ ‫ﺗﺴﺖ‬
•‫ﻣﺴﻴﺮ؟‬ ‫ﻫﺰﻳﻨﻪ‬
‫ﻣﺴﻴﺮ؟‬ ‫ﻫﺰﻳﻨﻪ‬

‫ﻣﺜﺎل‬‫ﻣﻜﺶ‬ ‫دﻧﻴﺎي‬ ‫ﺣﺎﻟﺖ‬ ‫ﻓﻀﺎي‬ ‫ﮔﺮاف‬ ‫ﻣﺜﺎل‬‫ﻣﻜﺶ‬ ‫دﻧﻴﺎي‬ ‫ﺣﺎﻟﺖ‬ ‫ﻓﻀﺎي‬ ‫ﮔﺮاف‬ ‫ﻣﺜﺎل‬:‫ﻣﻜﺶ‬ ‫دﻧﻴﺎي‬ ‫ﺣﺎﻟﺖ‬ ‫ﻓﻀﺎي‬ ‫ﮔﺮاف‬ ‫ﻣﺜﺎل‬:‫ﻣﻜﺶ‬ ‫دﻧﻴﺎي‬ ‫ﺣﺎﻟﺖ‬ ‫ﻓﻀﺎي‬ ‫ﮔﺮاف‬
•‫ﺣﺎﻻت؟‬‫ﻋﺎﻣﻞ‬ ‫ﻫﺎي‬ ‫ﻣﻜﺎن‬ ‫و‬ ‫ﺧﺎك‬ ‫و‬ ‫ﮔﺮد‬ ‫وﺟﻮد‬)‫ﺧﺎك‬ ‫و‬ ‫ﮔﺮد‬ ‫ﻣﻘﺪار‬ ‫ﮔﺮﻓﺘﻦ‬ ‫ﻧﻈﺮ‬ ‫در‬ ‫ﺑﺪون‬(
•‫ﺎل؟‬ ‫اﻋ‬Left Right Suck •‫اﻋﻤﺎل؟‬Left, Right, Suck
•‫ﻫﺪف؟‬ ‫ﺗﺴﺖ‬‫ﺧﺎك‬ ‫و‬ ‫ﮔﺮد‬ ‫ﻧﺒﻮدن‬
•‫ﻣﺴﻴﺮ؟‬ ‫ﻫﺰﻳﻨﻪ‬‫ﻋﻤﻞ‬ ‫ﻫﺮ‬ ‫ﺑﺎزاء‬1
‫ﻣﺴﻴﺮ؟‬ ‫ﻫﺰﻳﻨﻪ‬‫ﻋﻤﻞ‬ ‫ﻫﺮ‬ ‫ﺑﺎزاء‬1
‫ﻣﺜﺎل‬‫ﻫﺸﺖ‬ ‫ﻣﻌﻤﺎي‬ ‫ﻣﺜﺎل‬‫ﻫﺸﺖ‬ ‫ﻣﻌﻤﺎي‬ ‫ﻣﺜﺎل‬:‫ﻫﺸﺖ‬ ‫ﻣﻌﻤﺎي‬ ‫ﻣﺜﺎل‬:‫ﻫﺸﺖ‬ ‫ﻣﻌﻤﺎي‬
•‫ﺎﻻت؟‬ •‫ﺣﺎﻻت؟‬
•‫اﻋﻤﺎل؟‬
•‫ﻫﺪف؟‬ ‫ﺖ‬ ‫ﺗ‬ •‫ﻫﺪف؟‬ ‫ﺗﺴﺖ‬
•‫ﻣﺴﻴﺮ؟‬ ‫ﻫﺰﻳﻨﻪ‬
‫ﻣﺜﺎل‬‫ﻫﺸﺖ‬ ‫ﻣﻌﻤﺎي‬ ‫ﻣﺜﺎل‬‫ﻫﺸﺖ‬ ‫ﻣﻌﻤﺎي‬ ‫ﻣﺜﺎل‬:‫ﻫﺸﺖ‬ ‫ﻣﻌﻤﺎي‬ ‫ﻣﺜﺎل‬:‫ﻫﺸﺖ‬ ‫ﻣﻌﻤﺎي‬
•‫ﺎﻻت؟‬‫ﺎ‬ ‫ﻛﺎﺷ‬ ‫ﻞ‬ ‫ﺎﻧﮕ‬ ‫ﺪا‬ ‫ا‬ •‫ﺣﺎﻻت؟‬‫ﻫﺎ‬ ‫ﻛﺎﺷﻲ‬ ‫ﻣﺤﻞ‬ ‫ﺑﻴﺎﻧﮕﺮ‬ ‫ﺻﺤﻴﺢ‬ ‫اﻋﺪاد‬
•‫اﻋﻤﺎل؟‬‫ﭘﺎﻳﻴﻦ‬ ‫و‬ ‫راﺳﺖ‬ ،‫ﺑﺎﻻ‬ ،‫ﭼﭗ‬ ‫ﺑﻪ‬ ‫ﺧﺎﻟﻲ‬ ‫ﺧﺎﻧﻪ‬ ‫ﺣﺮﻛﺖ‬
•‫ﻫﺪف؟‬ ‫ﺖ‬ ‫ﺗ‬‫ﻫﺪف‬ ‫ﺎﻟﺖ‬)‫ﺷﺪ‬ ‫داد‬( •‫ﻫﺪف؟‬ ‫ﺗﺴﺖ‬‫ﻫﺪف‬ ‫ﺣﺎﻟﺖ‬)‫ﺷﺪه‬ ‫داده‬(
•‫ﻣﺴﻴﺮ؟‬ ‫ﻫﺰﻳﻨﻪ‬‫ﺣﺮﻛﺖ‬ ‫ﻫﺮ‬ ‫ﺑﺎزاء‬1
]‫ﻪ‬ ‫ﺗ‬:‫ﺎي‬ ‫اد‬ ‫ﺧﺎﻧ‬ ‫ﻨﻪ‬ ‫ﻞ‬ ‫ا‬n‫ﺄﻟﻪ‬ ‫ﻚ‬NP hard‫ﺎﺷﺪ‬[
]‫ﺗﻮﺟﻪ‬:‫ﻣﻌﻤﺎي‬ ‫ﺧﺎﻧﻮاده‬ ‫ﺑﻬﻴﻨﻪ‬ ‫ﺣﻞ‬ ‫راه‬n‫ﻣﺴﺄﻟﻪ‬ ‫ﻳﻚ‬NP-hard‫ﺑﺎﺷﺪ‬ ‫ﻣﻲ‬[
‫ﻣﺜﺎل‬:‫ﻛﻨﻨﺪه‬ ‫اﺳﻤﺒﻞ‬ ‫روﺑﺎت‬ ‫ﻣﺜﺎل‬:‫ﻛﻨﻨﺪه‬ ‫اﺳﻤﺒﻞ‬ ‫روﺑﺎت‬ ‫ﻣﺜﺎل‬:‫ﻛﻨﻨﺪه‬ ‫اﺳﻤﺒﻞ‬ ‫روﺑﺎت‬ ‫ﻣﺜﺎل‬:‫ﻛﻨﻨﺪه‬ ‫اﺳﻤﺒﻞ‬ ‫روﺑﺎت‬
•‫ﺣﺎﻻت؟‬‫ﻗﻄﻌﺎت‬ ‫ﻣﺨﺘﺼﺎت‬ ،‫روﺑﺎت‬ ‫ﻣﻔﺎﺻﻞ‬ ‫زاوﻳﻪ‬‫ﺼ‬ ‫روﺑ‬ ‫ﺻﻞ‬ ‫وﻳ‬ ‫ز‬
•‫اﻋﻤﺎل؟‬‫روﺑﺎت‬ ‫ﻣﻔﺎﺻﻞ‬ ‫ﭘﻴﻮﺳﺘﻪ‬ ‫ﺣﺮﻛﺖ‬
•‫ﻫﺪف؟‬ ‫ﺗﺴﺖ‬‫ﻛﺎﻣﻞ‬ ‫ﺑﻨﺪي‬ ‫ﺳﺮﻫﻢ‬‫ﻞ‬ ‫ي‬ ‫ﺑ‬ ‫ﻢ‬ ‫ﺮ‬
•‫ﻣﺴﻴﺮ؟‬ ‫ﻫﺰﻳﻨﻪ‬‫اﺟﺮا‬ ‫زﻣﺎن‬

‫وزﻳﺮ‬ ‫ﻫﺸﺖ‬ ‫ﻣﺴﺄﻟﻪ‬‫وزﻳﺮ‬ ‫ﻫﺸﺖ‬ ‫ﻣﺴﺄﻟﻪ‬‫وزﻳﺮ‬ ‫ﻫﺸﺖ‬ ‫ﻣﺴﺄﻟﻪ‬‫وزﻳﺮ‬ ‫ﻫﺸﺖ‬ ‫ﻣﺴﺄﻟﻪ‬
•‫ﻗﺮاردادن‬‫ﻫﺸﺖ‬‫وزﻳﺮ‬‫در‬‫ﺻﻔﺤﻪ‬‫ﺷﻄﺮﻧﺞ‬‫ﺑﻪ‬‫ﻃﻮرﻳﻜﻪ‬‫ﻫﻴﭻ‬‫وزﻳﺮي‬‫ﻧﺘﻮاﻧﺪ‬‫ﺑﻪ‬
‫وزﻳﺮ‬‫دﻳﮕﺮي‬‫ﺣﻤﻠﻪ‬‫ﻛﻨﺪ‬ ‫وزﻳﺮ‬‫دﻳﮕﺮي‬‫ﺣﻤﻠﻪ‬‫ﻛﻨﺪ‬.
‫آ‬‫آ‬‫ﻄ‬ ••‫آزﻣﻮن‬‫آزﻣﻮن‬‫ﻫﺪف‬‫ﻫﺪف‬::8‫وزﻳﺮ‬‫روي‬‫ﺻﻔﺤﻪ‬‫ﺷﻄﺮﻧﺞ‬
‫ﻛﻪ‬‫ﺑﺎ‬‫ﻫﻢ‬‫ﺑﺮﺧﻮرد‬‫ﻧﺪارﻧﺪ‬.
••‫ﻫﺰﻳﻨﻪ‬‫ﻫﺰﻳﻨﻪ‬‫ﻣﺴﻴﺮ‬‫ﻣﺴﻴﺮ‬::‫ﺻﻔﺮ‬
••‫ﺣﺎﻻت‬‫ﺣﺎﻻت‬::‫ﺗﺮﺗﻴﺐ‬8‫وزﻳﺮ‬‫ﻫﺮ‬‫ﻛﺪام‬‫در‬‫ﻳﻚ‬‫ﺳﺘﻮن‬ ‫ﻴﺐ‬ ‫ﺮ‬‫وزﻳﺮ‬‫ﺮ‬‫م‬‫ر‬‫ﻳ‬‫ﻮن‬
‫ﻣﺜﺎل‬‫روﺑﺮو‬:{8, 6, 4, 2, 7, 5, 3, 1}
••‫ﻫﺎ‬ ‫ﻠﮕ‬ ‫ﻋ‬‫ﻫﺎ‬ ‫ﻠﮕ‬ ‫ﻋ‬:‫اﻧﺘﻘﺎل‬‫ﻚ‬‫ز‬‫اي‬ ‫دا‬‫د‬ ‫ﺧ‬‫ﻪ‬ ••‫ﻋﻤﻠﮕﺮﻫﺎ‬‫ﻋﻤﻠﮕﺮﻫﺎ‬:‫اﻧﺘﻘﺎل‬‫ﻳﻚ‬‫وزﻳﺮ‬‫داراي‬‫ﺑﺮﺧﻮرد‬‫ﺑﻪ‬
‫ﻣﺮﺑﻊ‬‫دﻳﮕﺮي‬‫در‬‫ﻫﻤﺎن‬‫ﺳﺘﻮن‬
‫درﺧﺖ‬ ‫ﺟﺴﺘﺠﻮي‬ ‫ﻫﺎي‬ ‫اﻟﮕﻮرﻳﺘﻢ‬‫درﺧﺖ‬ ‫ﺟﺴﺘﺠﻮي‬ ‫ﻫﺎي‬ ‫اﻟﮕﻮرﻳﺘﻢ‬‫درﺧﺖ‬ ‫ﺟﺴﺘﺠﻮي‬ ‫ﻫﺎي‬ ‫اﻟﮕﻮرﻳﺘﻢ‬‫درﺧﺖ‬ ‫ﺟﺴﺘﺠﻮي‬ ‫ﻫﺎي‬ ‫اﻟﮕﻮرﻳﺘﻢ‬
•‫اﻳﺪه‬‫اﺻﻠﻲ‬:‫ﻛﺎوش‬offline‫و‬‫ﺷﺒﻴﻪ‬‫ﺳﺎزي‬‫ﺷﺪه‬‫ﻓﻀﺎي‬‫ﺣﺎﻟﺖ‬‫ﺑﻮﺳﻴﻠﻪ‬‫ﺗﻮﻟﻴﺪ‬‫ﺣﺎﻻت‬
‫ﺑﻌﺪي‬‫ﺣﺎﻟﺖ‬‫ﻫﺎﻳﻲ‬‫ﻛﻪ‬‫ﺗﺎ‬‫ﻛﻨﻮن‬‫ﺗﻮﻟﻴﺪ‬‫ﺷﺪه‬‫اﻧﺪ‬. ‫ي‬ ‫ﺑ‬‫ﻳﻲ‬‫ﻮ‬‫ﻴ‬ ‫ﻮ‬
‫درﺧﺖ‬ ‫ﺟﺴﺘﺠﻮي‬ ‫ﻣﺜﺎل‬‫درﺧﺖ‬ ‫ﺟﺴﺘﺠﻮي‬ ‫ﻣﺜﺎل‬‫درﺧﺖ‬ ‫ﺟﺴﺘﺠﻮي‬ ‫ﻣﺜﺎل‬‫درﺧﺖ‬ ‫ﺟﺴﺘﺠﻮي‬ ‫ﻣﺜﺎل‬

‫ﺳﺎزي‬ ‫ﭘﻴﺎده‬‫درﺧﺖ‬ ‫ﻋﻤﻮﻣ‬ ‫ﺟﺴﺘﺠﻮي‬ ‫ﺳﺎزي‬ ‫ﭘﻴﺎده‬‫درﺧﺖ‬ ‫ﻋﻤﻮﻣ‬ ‫ﺟﺴﺘﺠﻮي‬ ‫ﺳﺎزي‬ ‫ﭘﻴﺎده‬:‫درﺧﺖ‬ ‫ﻋﻤﻮﻣﻲ‬ ‫ﺟﺴﺘﺠﻮي‬ ‫ﺳﺎزي‬ ‫ﭘﻴﺎده‬:‫درﺧﺖ‬ ‫ﻋﻤﻮﻣﻲ‬ ‫ﺟﺴﺘﺠﻮي‬
‫ﺳﺎزي‬ ‫ﭘﻴﺎده‬‫ﮔﺮه‬ ‫و‬ ‫ﺣﺎﻟﺖ‬ ‫ﺳﺎزي‬ ‫ﭘﻴﺎده‬‫ﮔﺮه‬ ‫و‬ ‫ﺣﺎﻟﺖ‬ ‫ﺳﺎزي‬ ‫ﭘﻴﺎده‬:‫ﮔﺮه‬ ‫و‬ ‫ﺣﺎﻟﺖ‬ ‫ﺳﺎزي‬ ‫ﭘﻴﺎده‬:‫ﮔﺮه‬ ‫و‬ ‫ﺣﺎﻟﺖ‬
•‫ﻳﻚ‬‫ﺣﺎﻟﺖ‬)‫ﺑﻴﺎﻧﮕﺮ‬(‫ﻳﻚ‬‫ﭘﻴﻜﺮه‬‫ﺑﻨﺪي‬‫ﻓﻴﺰﻳﻜﻲ‬‫ﻣﻲ‬‫ﺑﺎﺷﺪ‬
•‫ﻳﻚ‬‫ﮔﺮه‬‫ﻳﻚ‬‫ﺳﺎﺧﺘﺎر‬‫داده‬‫اي‬‫ﺗﺸﻜﻴﻞ‬‫دﻫﻨﺪه‬‫ﺑﺨﺸﻲ‬‫از‬‫درﺧﺖ‬‫ﺟﺴﺘﺠﻮ‬‫ﺷﺎﻣﻞ‬:‫ﭘﺪر‬، ‫ﻳﻚ‬‫ﮔﺮه‬‫ﻳﻚ‬‫ﺳﺎﺧﺘﺎر‬‫داده‬‫اي‬‫ﺗﺸﻜﻴﻞ‬‫دﻫﻨﺪه‬‫ﺑﺨﺸﻲ‬‫از‬‫درﺧﺖ‬‫ﺟﺴﺘﺠﻮ‬‫ﺷﺎﻣﻞ‬:‫ﭘﺪر‬،
‫ﻓﺮزﻧﺪان‬،‫ﻋﻤﻖ‬‫و‬‫ﻫﺰﻳﻨﻪ‬‫ﻣﺴﻴﺮ‬g( x)‫اﺳﺖ‬.
•‫ﺣﺎﻟﺖ‬‫ﻫﺎ‬: ‫ﺣﺎﻟﺖ‬‫ﻫﺎ‬:
،‫ﭘﺪر‬،‫ﻓﺮزﻧﺪ‬‫ﻋﻤﻖ‬‫و‬‫ﻫﺰﻳﻨﻪ‬‫ﻣﺴﻴﺮ‬‫ﻧﺪارﻧﺪ‬!
•‫ﺗﺎﺑﻊ‬EXPAND‫ه‬ ‫ﮔ‬‫ﻫﺎي‬‫ﺟﺪﻳﺪ‬‫اﻳﺠﺎد‬‫ﻣ‬،‫ﻛﻨﺪ‬‫ﻠﺪﻫﺎي‬ ‫ﻓ‬‫ﻣﺨﺘﻠﻒ‬‫را‬‫ﻣﻘﺪار‬‫ﻣ‬‫دﻫﺪ‬‫و‬ •‫ﺗﺎﺑﻊ‬EXPAND‫ﮔﺮه‬‫ﻫﺎي‬‫ﺟﺪﻳﺪ‬‫اﻳﺠﺎد‬‫ﻣﻲ‬،‫ﻛﻨﺪ‬‫ﻓﻴﻠﺪﻫﺎي‬‫ﻣﺨﺘﻠﻒ‬‫را‬‫ﻣﻘﺪار‬‫ﻣﻲ‬‫دﻫﺪ‬‫و‬
‫ﺑﺎ‬‫اﺳﺘﻔﺎده‬‫از‬‫ﺗﺎﺑﻊ‬SUCCESSORS-FN،‫ﻣﺴﺄﻟﻪ‬‫ﺣﺎﻟﺖ‬‫ﻫﺎي‬‫ﻣﺮﺑﻮﻃﻪ‬‫اﻳﺠﺎد‬‫ﻣﻲ‬‫ﺷﻮد‬.
‫ﺟﺴﺘﺠﻮ‬ ‫ﻫﺎي‬ ‫اﺳﺘﺮاﺗﮋي‬‫ﺟﺴﺘﺠﻮ‬ ‫ﻫﺎي‬ ‫اﺳﺘﺮاﺗﮋي‬‫ﺟﺴﺘﺠﻮ‬ ‫ﻫﺎي‬ ‫اﺳﺘﺮاﺗﮋي‬‫ﺟﺴﺘﺠﻮ‬ ‫ﻫﺎي‬ ‫اﺳﺘﺮاﺗﮋي‬
•‫ﻳﻚ‬‫اﺳﺘﺮاﺗﮋي‬‫ﺑﻮﺳﻴﻠﻪ‬‫ﺗﺮﺗﻴﺐ‬‫ﮔﺴﺘﺮش‬‫ﮔﺮه‬‫ﻫﺎ‬‫ﺗﻌﺮﻳﻒ‬‫ﻣﻲ‬‫ﺷﻮد‬.
•‫اﺑﻌﺎد‬‫ارزﻳﺎﺑﻲ‬‫اﺳﺘﺮاﺗﮋي‬‫ﻫﺎ‬: ‫ﺑ‬‫ﺑﻲ‬ ‫رزﻳ‬‫ﮋي‬ ‫ﺮ‬
–‫ﻛﺎﻣﻞ‬‫ﺑﻮدن‬–‫آﻳﺎ‬‫در‬‫ﺻﻮرت‬‫وﺟﻮد‬‫راه‬،‫ﺣﻞ‬‫ﻫﻤﻴﺸﻪ‬‫راه‬‫ﺣﻠﻲ‬‫ﭘﻴﺪا‬‫ﻣﻲ‬‫ﻛﻨﺪ؟‬
–‫ﭘﻴﭽﻴﺪﮔﻲ‬‫زﻣﺎﻧﻲ‬–‫ﺗﻌﺪاد‬‫ﮔﺮه‬‫ﻫﺎي‬‫ﺗﻮﻟﻴﺪ‬‫ﺷﺪه‬/‫ﮔﺴﺘﺮش‬‫ﻳﺎﻓﺘﻪ‬ ‫ﻲ‬ ‫ﭘﻴﭽﻴ‬‫ﻲ‬ ‫ز‬‫ﺮ‬‫ي‬‫ﻴ‬ ‫ﻮ‬/‫ﺮش‬‫ﻳ‬
–‫ﭘﻴﭽﻴﺪﮔﻲ‬‫ﺣﺎﻓﻈﻪ‬–‫ﺣﺪاﻛﺜﺮ‬‫ﺗﻌﺪاد‬‫ﮔﺮه‬‫ﻫﺎ‬‫در‬‫ﺣﺎﻓﻈﻪ‬
–‫ﺑﻬﻴﻨﮕﻲ‬–‫آﻳﺎ‬‫ﻫﻤﻴﺸﻪ‬‫ﻛﻢ‬‫ﻫﺰﻳﻨﻪ‬‫ﺗﺮﻳﻦ‬‫راه‬‫ﺣﻞ‬‫را‬‫ﭘﻴﺪا‬‫ﻣﻲ‬‫ﻛﻨﺪ؟‬ ‫ﻲ‬ ‫ﺑﻬﻴ‬‫ﻳ‬‫ﻴ‬‫ﻢ‬‫ﺰﻳ‬‫ﺮﻳﻦ‬‫ر‬‫ﻞ‬‫ر‬‫ﭘﻴ‬‫ﻲ‬
•‫ﭘﻴﭽﻴﺪﮔﻲ‬‫زﻣﺎن‬‫و‬‫ﻓﻀﺎ‬‫ﺑﺮﺣﺴﺐ‬‫ﭘﺎراﻣﺘﺮﻫﺎي‬‫زﻳﺮ‬‫ﺳﻨﺠﻴﺪه‬‫ﻣﻲ‬‫ﺷﻮﻧﺪ‬: ‫ﭘﻴﭽﻴﺪﮔﻲ‬‫زﻣﺎن‬‫و‬‫ﻓﻀﺎ‬‫ﺑﺮﺣﺴﺐ‬‫ﭘﺎراﻣﺘﺮﻫﺎي‬‫زﻳﺮ‬‫ﺳﻨﺠﻴﺪه‬‫ﻣﻲ‬‫ﺷﻮﻧﺪ‬:
–b:‫ﺣﺪاﻛﺜﺮ‬‫ﻓﺎﻛﺘﻮر‬‫اﻧﺸﻌﺎب‬‫درﺧﺖ‬‫ﺟﺴﺘﺠﻮ‬
–d:‫ﻋﻤﻖ‬‫ﻛﻢ‬‫ﻫﺰﻳﻨﻪ‬‫ﺗﺮﻳﻦ‬‫راه‬‫ﺣﻞ‬ d:‫ﻋﻤﻖ‬‫ﻛﻢ‬‫ﻫﺰﻳﻨﻪ‬‫ﺗﺮﻳﻦ‬‫راه‬‫ﺣﻞ‬
–m:‫ﺣﺪاﻛﺜﺮ‬‫ﻋﻤﻖ‬‫ﻓﻀﺎي‬‫ﺣﺎﻟﺖ‬)‫ﻣﻤﻜﻦ‬‫اﺳﺖ‬∞‫ﺑﺎﺷﺪ‬(

‫ﻧﺎآﮔﺎﻫﺎﻧﻪ‬ ‫ﺟﺴﺘﺠﻮي‬ ‫ﻫﺎي‬ ‫اﺳﺘﺮﺗﮋي‬‫ﻧﺎآﮔﺎﻫﺎﻧﻪ‬ ‫ﺟﺴﺘﺠﻮي‬ ‫ﻫﺎي‬ ‫اﺳﺘﺮﺗﮋي‬‫ﻧﺎآﮔﺎﻫﺎﻧﻪ‬ ‫ﺟﺴﺘﺠﻮي‬ ‫ﻫﺎي‬ ‫اﺳﺘﺮﺗﮋي‬‫ﻧﺎآﮔﺎﻫﺎﻧﻪ‬ ‫ﺟﺴﺘﺠﻮي‬ ‫ﻫﺎي‬ ‫اﺳﺘﺮﺗﮋي‬
•‫اﺳﺘﺮاﺗﮋي‬‫ﻫﺎي‬‫ﻧﺎآﮔﺎﻫﺎﻧﻪ‬‫ﺗﻨﻬﺎ‬‫از‬‫اﻃﻼﻋﺎت‬‫ﻣﻮﺟﻮد‬‫در‬‫ﺗﻌﺮﻳﻒ‬
‫ﻣﺴﺄﻟﻪ‬‫اﺳﺘﻔﺎده‬‫ﻣ‬‫ﻛﻨﻨﺪ‬ ‫ﻣﺴﺄﻟﻪ‬‫اﺳﺘﻔﺎده‬‫ﻣﻲ‬‫ﻛﻨﻨﺪ‬.
•‫ﺟﺴﺘﺠﻮي‬‫اول‬-‫ﺳﻄﺢ‬(BFS)
•‫اﺧﺖ‬ ‫ﻜ‬(UCS) •‫ﺟﺴﺘﺠﻮي‬‫ﻫﺰﻳﻨﻪ‬-‫ﻳﻜﻨﻮاﺧﺖ‬(UCS)
•‫ﺟﺴﺘﺠﻮي‬‫اول‬-‫ﻋﻤﻖ‬)‫ﻋﻤﻘﻲ‬((DFS) ‫ﺠﻮي‬ ‫ﺟ‬‫و‬‫ﻖ‬‫ﻲ‬( )
•‫ﺟﺴﺘﺠﻮي‬‫ﺑﺎ‬‫ﻋﻤﻖ‬‫ﻣﺤﺪود‬(DLS)
‫ﻜ‬(IDS) •‫ﺟﺴﺘﺠﻮي‬‫ﻋﻤﻴﻖ‬‫ﻛﻨﻨﺪه‬‫ﺗﻜﺮاري‬(IDS)
‫ﺳﻄﺤ‬ ‫ﺟﺴﺘﺠﻮي‬‫ﺳﻄﺤ‬ ‫ﺟﺴﺘﺠﻮي‬‫ﺳﻄﺤﻲ‬ ‫ﺟﺴﺘﺠﻮي‬‫ﺳﻄﺤﻲ‬ ‫ﺟﺴﺘﺠﻮي‬
•‫ﻫﺮﺑﺎر‬‫ﺳﻄﺤﻲ‬‫ﺗﺮﻳﻦ‬‫ﮔﺮه‬‫ﮔﺴﺘﺮش‬‫ﻧﻴﺎﻓﺘﻪ‬‫را‬‫ﮔﺴﺘﺮش‬‫ﻣﻲ‬‫دﻫﺪ‬.
••‫ﺎد‬‫ﺎزي‬: ••‫ﭘﻴﺎده‬‫ﺳﺎزي‬:
–fringe‫ﻳﻚ‬‫ﺻﻒ‬FIFO‫ﻣﻲ‬‫ﺑﺎﺷﺪ‬.،‫ﻳﻌﻨﻲ‬‫ﻓﺮزﻧﺪان‬‫ﺟﺪﻳﺪ‬‫ﺑﻪ‬‫اﻧﺘﻬﺎي‬‫ﺻﻒ‬‫اﺿﺎﻓﻪ‬
‫ﻣﻲ‬‫ﺷﻮﻧﺪ‬.
0: [A]
•‫ﺎد‬‫ﺎزي‬: •‫ﭘﻴﺎده‬‫ﺳﺎزي‬:
1: [B, C]
2: [C, D, E]

3: [D, E, F, G]
‫ﻣﺜﺎل‬‫ﺳﻄﺤ‬ ‫ﺟﺴﺘﺠﻮي‬ ‫ﻣﺜﺎل‬‫ﺳﻄﺤ‬ ‫ﺟﺴﺘﺠﻮي‬ ‫ﻣﺜﺎل‬:‫ﺳﻄﺤﻲ‬ ‫ﺟﺴﺘﺠﻮي‬ ‫ﻣﺜﺎل‬:‫ﺳﻄﺤﻲ‬ ‫ﺟﺴﺘﺠﻮي‬
Arad
Zerind Sibiu Timisoara
Arad LugojArad Oradea Fagaras
Rimnicu
VilceaArad Oradea
‫ﺳﻄﺤ‬ ‫ﺟﺴﺘﺠﻮي‬ ‫ﺧﺼﻮﺻﻴﺎت‬‫ﺳﻄﺤ‬ ‫ﺟﺴﺘﺠﻮي‬ ‫ﺧﺼﻮﺻﻴﺎت‬‫ﺳﻄﺤﻲ‬ ‫ﺟﺴﺘﺠﻮي‬ ‫ﺧﺼﻮﺻﻴﺎت‬‫ﺳﻄﺤﻲ‬ ‫ﺟﺴﺘﺠﻮي‬ ‫ﺧﺼﻮﺻﻴﺎت‬
•‫ﻛﺎﻣﻞ؟‬
‫ﮔ‬
‫ﺑﻠﻪ‬)‫ﺑﻮدن‬ ‫ﻣﺤﺪود‬ ‫ﺷﺮط‬ ‫ﺑﻪ‬b(
•‫ﭘﻴﭽﻴﺪﮔﻲ‬‫زﻣﺎﻧﻲ؟‬
•‫ﺪﮔ‬ ‫ﭽ‬ ‫ﭘ‬‫ﺣﺎﻓﻈﻪ؟‬
b + b2 + … + bd + b(bd-1) = O( bd+1)
O(bd+1)‫دارد‬ ‫ﻣ‬ ‫ﻧﮕﻪ‬ ‫ﺣﺎﻓﻈﻪ‬ ‫در‬ ‫را‬ ‫ﻫﺎ‬ ‫ﮔﺮه‬ ‫ﻫﻤﻪ‬ ‫ﭼﻮن‬ ‫ﭘﻴﭽﻴﺪﮔﻲ‬‫ﺣﺎﻓﻈﻪ؟‬
•‫ﺑﻬﻴﻨﻪ؟‬‫ﺑﻠﻪ‬)‫ﻫﺰﻳﻨﻪ‬ ،‫ﻋﻤﻞ‬ ‫ﻫﺮ‬ ‫ﺑﺎزاء‬ ‫اﮔﺮ‬ ‫ﻣﺜﻼ‬=1(
O(b )‫دارد‬ ‫ﻣﻲ‬ ‫ﻧﮕﻪ‬ ‫ﺣﺎﻓﻈﻪ‬ ‫در‬ ‫را‬ ‫ﻫﺎ‬ ‫ﮔﺮه‬ ‫ﻫﻤﻪ‬ ‫ﭼﻮن‬
•‫ﻠ‬ ‫ا‬ ‫ﺸﻜﻞ‬‫ﺣﺎﻓﻈﻪ‬‫ﺎﺷﺪ‬)‫ﺖ‬ ‫ﻧ‬ •‫اﺻﻠﻲ‬ ‫ﻣﺸﻜﻞ‬‫ﺣﺎﻓﻈﻪ‬‫ﺑﺎﺷﺪ‬ ‫ﻣﻲ‬) .‫ﺑﻪ‬ ‫ﻧﺴﺒﺖ‬
‫زﻣﺎن‬(
‫ﺳﻄﺤ‬ ‫ﺟﺴﺘﺠﻮي‬ ‫ﺣﺎﻓﻈﻪ‬ ‫و‬ ‫زﻣﺎﻧ‬ ‫ﭘﻴﭽﻴﺪﮔ‬‫ﺳﻄﺤ‬ ‫ﺟﺴﺘﺠﻮي‬ ‫ﺣﺎﻓﻈﻪ‬ ‫و‬ ‫زﻣﺎﻧ‬ ‫ﭘﻴﭽﻴﺪﮔ‬‫ﺳﻄﺤﻲ‬ ‫ﺟﺴﺘﺠﻮي‬ ‫ﺣﺎﻓﻈﻪ‬ ‫و‬ ‫زﻣﺎﻧﻲ‬ ‫ﭘﻴﭽﻴﺪﮔﻲ‬‫ﺳﻄﺤﻲ‬ ‫ﺟﺴﺘﺠﻮي‬ ‫ﺣﺎﻓﻈﻪ‬ ‫و‬ ‫زﻣﺎﻧﻲ‬ ‫ﭘﻴﭽﻴﺪﮔﻲ‬
1 b11 b1
2 b2
3 b3
…
d - 1 bd - 1
d bdd b
…
d + 1 b(bd – 1)
b + b2 + … + bd + b(bd -1) = O(bd+1)
( ) ( )

‫ﺳﻄﺤ‬ ‫ﺟﺴﺘﺠﻮي‬ ‫در‬ ‫ﻻزم‬ ‫ﻓﻀﺎي‬ ‫و‬ ‫زﻣﺎن‬‫ﺳﻄﺤ‬ ‫ﺟﺴﺘﺠﻮي‬ ‫در‬ ‫ﻻزم‬ ‫ﻓﻀﺎي‬ ‫و‬ ‫زﻣﺎن‬‫ﺳﻄﺤﻲ‬ ‫ﺟﺴﺘﺠﻮي‬ ‫در‬ ‫ﻻزم‬ ‫ﻓﻀﺎي‬ ‫و‬ ‫زﻣﺎن‬‫ﺳﻄﺤﻲ‬ ‫ﺟﺴﺘﺠﻮي‬ ‫در‬ ‫ﻻزم‬ ‫ﻓﻀﺎي‬ ‫و‬ ‫زﻣﺎن‬
‫ﺣﺎﻓﻈﻪ‬ ‫زﻣﺎن‬ ‫ﻫﺎ‬ ‫ﮔﺮه‬ ‫ﺗﻌﺪاد‬ ‫ﻋﻤﻖ‬
1‫ﺑﺎﻳﺖ‬ ‫ﻣﮕﺎ‬ 11/0‫ﺛﺎﻧﻴﻪ‬ 1100 21‫ﺑﺎﻳﺖ‬ ‫ﻣﮕﺎ‬ 11/‫ﺛﺎﻧﻴﻪ‬ 11 2
106‫ﺑﺎﻳﺖ‬ ‫ﻣﮕﺎ‬ 11‫ﺛﺎﻧﻴﻪ‬ 111100 4
10‫ﺑﺎﻳﺖ‬ ‫ﮔﻴﮕﺎ‬ 19‫دﻗﻴﻘﻪ‬ 107 6‫ﻳ‬ ‫ﺑ‬ ‫ﻴ‬ ‫ﻴ‬
1‫ﺑﺎﻳﺖ‬ ‫ﺗﺮا‬ 31‫ﺳﺎﻋﺖ‬ 109 8
101‫ﺑﺎﻳﺖ‬ ‫ﺗﺮا‬ 129‫روز‬ 1011 10‫ﻳ‬ ‫ﺑ‬ ‫ﺮ‬
10‫ﺑﺎﻳﺖ‬ ‫ﭘﺘﺎ‬ 35‫ﺳﺎل‬ 1013 12
1‫ﺑﺎﻳﺖ‬ ‫ﻫﮕﺰا‬ 3523‫ﺳﺎل‬ 1015 14
10=b
10000‫ﺛﺎﻧﻴﻪ‬ ‫ﻫﺮ‬ ‫در‬ ‫ﮔﺮه‬
‫ه‬ ‫ﮔ‬ ‫ﻫ‬1000‫ﺑﺎﻳﺖ‬
‫ﮔﺮه‬ ‫ﻫﺮ‬1000‫ﺑﺎﻳﺖ‬
‫ﻫﺰﻳﻨﻪ‬ ‫ﺟﺴﺘﺠﻮي‬‫ﻳﻜﻨﻮاﺧﺖ‬ ‫ﻫﺰﻳﻨﻪ‬ ‫ﺟﺴﺘﺠﻮي‬‫ﻳﻜﻨﻮاﺧﺖ‬ ‫ﻫﺰﻳﻨﻪ‬ ‫ﺟﺴﺘﺠﻮي‬-‫ﻳﻜﻨﻮاﺧﺖ‬ ‫ﻫﺰﻳﻨﻪ‬ ‫ﺟﺴﺘﺠﻮي‬-‫ﻳﻜﻨﻮاﺧﺖ‬
•‫ﻫﺮﺑﺎر‬‫ﻛﻢ‬‫ﻫﺰﻳﻨﻪ‬‫ﺗﺮﻳﻦ‬‫ﮔﺮه‬‫ﮔﺴﺘﺮش‬‫ﻧﻴﺎﻓﺘﻪ‬‫را‬‫ﮔﺴﺘﺮش‬‫ﻣﻲ‬‫دﻫﺪ‬.
•‫ﭘﻴﺎده‬‫ﺳﺎزي‬: ‫ﭘﻴﺎده‬‫ﺳﺎزي‬:
–fringe=‫ﺻﻔﻲ‬‫ﻛﻪ‬‫ﺑﺮاﺳﺎس‬‫ﻫﺰﻳﻨﻪ‬‫ﻣﺴﻴﺮ‬‫ﻣﺮﺗﺐ‬‫ﺷﺪه‬‫ﺑﺎﺷﺪ‬.
•‫ﺎدل‬‫ي‬ ‫ﺘ‬‫ﻄ‬‫اﮔ‬‫ﻨﻪ‬ ‫ﻫﺰ‬‫ﮔﺎ‬‫ﻫﺎ‬‫ي‬ ‫ﺎ‬‫ﺎﺷﻨﺪ‬ •‫ﻣﻌﺎدل‬‫ﺟﺴﺘﺠﻮي‬‫ﺳﻄﺤﻲ‬‫اﮔﺮ‬‫ﻫﺰﻳﻨﻪ‬‫ﮔﺎم‬‫ﻫﺎ‬‫ﻣﺴﺎوي‬‫ﺑﺎﺷﻨﺪ‬.
‫ﮔ‬‫ﮔ‬ •‫ﻛﺎﻣﻞ؟‬‫ﺑﻠﻪ‬‫اﮔﺮ‬‫ﻫﺰﻳﻨﻪ‬‫ﮔﺎﻣﻬﺎ‬≤ε
•‫ﭘﻴﭽﻴﺪﮔﻲ‬‫زﻣﺎﻧﻲ؟‬‫ﺗﻌﺪاد‬‫ﮔﺮه‬‫ﻫﺎﻳﻲ‬‫ﻛﻪ‬‫ﻫﺰﻳﻨﻪ‬‫ﻣﺴﻴﺮ‬‫آﻧﻬﺎ‬‫ﻛﻮﭼﻜﺘﺮ‬‫ﻳﺎ‬‫ﻣﺴﺎوي‬‫ﻫﺰﻳﻨﻪ‬‫راه‬
‫ﺣﻞ‬‫ﺑﻬﻴﻨﻪ‬‫ﺑﺎﺷﺪ‬.
•‫ﭘﻴﭽﻴﺪﮔﻲ‬‫ﺣﺎﻓﻈﻪ؟‬‫ﻣﺎﻧﻨﺪ‬‫ﭘﻴﭽﻴﺪﮔﻲ‬‫زﻣﺎﻧﻲ‬
⎡ ⎤
)( /* εC
bO
•‫ﺑﻬﻴﻨﻪ؟‬‫ﺑﻠﻪ‬)‫ﮔﺮه‬‫ﻫﺎ‬‫ﺑﻪ‬‫ﺗﺮﺗﻴﺐ‬‫ﺻﻌﻮدي‬g( n)‫ﮔﺴﺘﺮش‬‫ﻣﻲ‬‫ﻳﺎﺑﻨﺪ‬(.
‫ﻣﺜﺎل‬‫ﻳﻜﻨﻮاﺧﺖ‬ ‫ﻫﺰﻳﻨﻪ‬ ‫ﺟﺴﺘﺠﻮي‬ ‫ﻣﺜﺎل‬‫ﻳﻜﻨﻮاﺧﺖ‬ ‫ﻫﺰﻳﻨﻪ‬ ‫ﺟﺴﺘﺠﻮي‬ ‫ﻣﺜﺎل‬:‫ﻳﻜﻨﻮاﺧﺖ‬ ‫ﻫﺰﻳﻨﻪ‬ ‫ﺟﺴﺘﺠﻮي‬ ‫ﻣﺜﺎل‬:‫ﻳﻜﻨﻮاﺧﺖ‬ ‫ﻫﺰﻳﻨﻪ‬ ‫ﺟﺴﺘﺠﻮي‬
Arad
75 140 118
140 151 99 80
118 11175
71
Arad Oradea Fagaras
Rimnicu
Vilcea Arad LugojArad Oradea
‫ﻣﺜﺎل‬‫ﻳﻜﻨﻮاﺧﺖ‬ ‫ﻫﺰﻳﻨﻪ‬ ‫ﺟﺴﺘﺠﻮي‬ ‫ﻣﺜﺎل‬‫ﻳﻜﻨﻮاﺧﺖ‬ ‫ﻫﺰﻳﻨﻪ‬ ‫ﺟﺴﺘﺠﻮي‬ ‫ﻣﺜﺎل‬:‫ﻳﻜﻨﻮاﺧﺖ‬ ‫ﻫﺰﻳﻨﻪ‬ ‫ﺟﺴﺘﺠﻮي‬ ‫ﻣﺜﺎل‬:‫ﻳﻜﻨﻮاﺧﺖ‬ ‫ﻫﺰﻳﻨﻪ‬ ‫ﺟﺴﺘﺠﻮي‬
SA
1 10
0
S
S
B
G
1 10
5 5 A B C
1 5 15
C
15 5
15
G G
C 11 10
0: [S(0)]
1: [A(1), B(5), C(15)]
2: [B(5), G(11), C(15)]
3: [G(10), G(11), C(15)]
4: [G(11), C(15)]

‫ﻋﻤﻘ‬ ‫ﺟﺴﺘﺠﻮي‬‫ﻋﻤﻘ‬ ‫ﺟﺴﺘﺠﻮي‬‫ﻋﻤﻘﻲ‬ ‫ﺟﺴﺘﺠﻮي‬‫ﻋﻤﻘﻲ‬ ‫ﺟﺴﺘﺠﻮي‬
•‫ﻫﺮﺑﺎر‬‫ﻋﻤﻴﻖ‬‫ﺗﺮﻳﻦ‬‫ﮔﺮه‬‫ﮔﺴﺘﺮش‬‫ﻧﻴﺎﻓﺘﻪ‬‫را‬‫ﮔﺴﺘﺮش‬‫ﻣﻲ‬‫دﻫﺪ‬.
•‫ﺎ‬‫ﺎز‬: •‫ﭘﻴﺎده‬‫ﺳﺎزي‬:
–fringe=‫ﭘﺸﺘﻪ‬LIFO،‫ﻓﺮزﻧﺪان‬‫ﺟﺪﻳﺪ‬‫را‬‫در‬‫اﺑﺘﺪا‬‫درج‬‫ﻣﻲ‬‫ﻛﻨﺪ‬.
0: [A]
1: [B, C]
2: [D, E, C]
3: [H, I, E, C]

4: [I, E, C]
5: [E, C]
6: [J, K, C]
7: [K, C]

8: [C]
9: [F, G]
10: [L, M, G]
11: [M, G]

‫ﻣﺜﺎل‬‫ﻋﻤﻘ‬ ‫ﺟﺴﺘﺠﻮي‬ ‫ﻣﺜﺎل‬‫ﻋﻤﻘ‬ ‫ﺟﺴﺘﺠﻮي‬ ‫ﻣﺜﺎل‬:‫ﻋﻤﻘﻲ‬ ‫ﺟﺴﺘﺠﻮي‬ ‫ﻣﺜﺎل‬:‫ﻋﻤﻘﻲ‬ ‫ﺟﺴﺘﺠﻮي‬
Arad
Arad Oradea
••‫ﭘﺎﻳﺎن‬ ‫ﺑﻲ‬ ‫ﺣﻠﻘﻪ‬!
Arad Oradea
‫ﺑﺪون‬ ‫و‬ ‫ﻣﺤﺪود‬ ‫ﺣﺎﻟﺖ‬ ‫ﻓﻀﺎي‬ ‫ﺑﻪ‬ ‫ﻧﻴﺎز‬ ‫ﺟﺴﺘﺠﻮ‬ ‫اﻳﻦ‬ ‫در‬
،‫دارﻳﻢ‬ ‫ﭼﺮﺧﻪ‬‫ﺷﻮﻧﺪ‬ ‫ﭼﻚ‬ ‫ﺗﻜﺮاري‬ ‫ﺣﺎﻻت‬ ‫ﺑﺎﻳﺪ‬ ‫ﻳﺎ‬.
‫رﻳﻢ‬ ‫ﭼﺮ‬‫ﻮ‬ ‫ﭼ‬ ‫ري‬ ‫ﺮ‬ ‫ﻳ‬ ‫ﺑ‬ ‫ﻳ‬
‫ﻋﻤﻘﻲ‬ ‫ﺟﺴﺘﺠﻮي‬ ‫ﺧﺼﻮﺻﻴﺎت‬‫ﻋﻤﻘﻲ‬ ‫ﺟﺴﺘﺠﻮي‬ ‫ﺧﺼﻮﺻﻴﺎت‬‫ﻋﻤﻘﻲ‬ ‫ﺟﺴﺘﺠﻮي‬ ‫ﺧﺼﻮﺻﻴﺎت‬‫ﻋﻤﻘﻲ‬ ‫ﺟﺴﺘﺠﻮي‬ ‫ﺧﺼﻮﺻﻴﺎت‬
••‫ﻛﺎﻣﻞ‬‫؟‬‫؟‬
–‫ﺧﻴﺮ‬)‫در‬‫ﻓﻀﺎﻫﺎي‬‫ﺣﺎﻟﺖ‬‫ﺑﺎ‬‫ﻋﻤﻖ‬،‫ﻧﺎﻣﺤﺪود‬‫داراي‬‫ﺣﻠﻘﻪ‬(
–‫ﺑﺮاي‬‫اﺟﺘﻨﺎب‬‫از‬‫ﺣﺎﻻت‬‫ﺗﻜﺮاي‬‫در‬‫ﻃﻮل‬،‫ﻣﺴﻴﺮ‬‫ﻧﻴﺎز‬‫ﺑﻪ‬‫اﺻﻼح‬‫دارد‬. ‫ي‬ ‫ﺑﺮ‬‫ب‬ ‫ﺟ‬‫ز‬‫ي‬ ‫ﺮ‬‫ر‬‫ﻮ‬‫ﻴﺮ‬‫ز‬ ‫ﻴ‬‫ﺑ‬‫ح‬‫ر‬
–،‫ﺑﻨﺎﺑﺮاﻳﻦ‬‫در‬‫ﻓﻀﺎي‬‫ﺣﺎﻟﺖ‬‫ﻣﺤﺪود‬‫ﻛﺎﻣﻞ‬‫اﺳﺖ‬.
•‫ﺪﮔ‬‫ﺎﻧ‬ ‫ز‬‫؟‬‫؟‬O( bm) •‫ﭘﻴﭽﻴﺪﮔﻲ‬‫زﻣﺎﻧﻲ‬‫؟‬‫؟‬O( bm)
–‫در‬‫ﺑﺪﺗﺮﻳﻦ‬‫ﺣﺎﻟﺖ‬‫ﺗﻤﺎم‬‫ﮔﺮه‬‫ﻫﺎي‬‫درﺧﺖ‬‫ﺟﺴﺘﺠﻮ‬‫ﺗﻮﻟﻴﺪ‬‫ﻣﻲ‬‫ﺷﻮﻧﺪ‬
‫ﮔ‬ –‫اﮔﺮ‬m‫ﺧﻴﻠﻲ‬‫ﺑﻴﺸﺘﺮ‬‫از‬d،‫ﺑﺎﺷﺪ‬‫ﺑﺴﻴﺎر‬‫زﻳﺎد‬
–‫اﮔﺮ‬‫ﺗﻌﺪاد‬‫راه‬‫ﺣﻞ‬‫ﻫﺎ‬‫زﻳﺎد‬،‫ﺑﺎﺷﺪ‬‫ﻣﻲ‬‫ﺗﻮاﻧﺪ‬‫ﺑﺴﻴﺎر‬‫ﺳﺮﻳﻌﺘﺮ‬‫از‬‫ﺟﺴﺘﺠﻮي‬‫ﺳﻄﺤﻲ‬‫ﺑﺎﺷﺪ‬
•‫ﭘﻴﭽﻴﺪﮔﻲ‬‫ﺣﺎﻓﻈﻪ‬‫؟‬
O( bm)،‫ﻪ‬‫ت‬ ‫ﺻ‬‫ﺧﻄ‬! –O( bm)،‫ﺑﻪ‬‫ﺻﻮرت‬‫ﺧﻄﻲ‬!
•‫ﺑﻬﻴﻨﻪ‬‫؟‬‫؟‬‫ﺧﻴﺮ‬
‫ﻣﺤﺪود‬ ‫ﻋﻤﻖ‬ ‫ﺑﺎ‬ ‫ﺟﺴﺘﺠﻮي‬‫ﻣﺤﺪود‬ ‫ﻋﻤﻖ‬ ‫ﺑﺎ‬ ‫ﺟﺴﺘﺠﻮي‬‫و‬ ‫ﻖ‬ ‫ﺑ‬ ‫ﺠﻮي‬ ‫ﺟ‬‫و‬ ‫ﻖ‬ ‫ﺑ‬ ‫ﺠﻮي‬ ‫ﺟ‬
=‫ﺟﺴﺘﺠﻮي‬‫ﻋﻤﻘﻲ‬‫ﺑﺎ‬‫ﻣﺤﺪوده‬‫ﻋﻤﻘﻲ‬l
،‫ﻳﻌﻨﻲ‬‫ﻓﺮزﻧﺪان‬‫ﮔﺮه‬‫ﻫﺎي‬‫واﻗﻊ‬‫در‬‫ﻋﻤﻖ‬l‫ﺗﻮﻟﻴﺪ‬‫ﻧﺨﻮاﻫﻨﺪ‬‫ﺷﺪ‬.
•‫در‬‫اﻳﻦ‬‫اﺳﺘﺮاﺗﮋي‬‫ﺑﺎ‬‫در‬‫ﻧﻈﺮ‬‫ﮔﺮﻓﺘﻦ‬‫ﻳﻚ‬‫ﻣﺤﺪوده‬‫ﻋﻤﻘﻲ‬‫ﻣﺎﻧﻨﺪ‬l‫از‬‫ﺑﻪ‬‫دام‬
‫اﻓﺘﺎدن‬‫ﺟﺴﺘﺠﻮي‬‫ﻋﻤﻘﻲ‬‫در‬‫ﻳﻚ‬‫ﺣﻠﻘﻪ‬‫ﺑﻲ‬‫ﭘﺎﻳﺎن‬‫ﺟﻠﻮﮔﻴﺮي‬‫ﻣﻲ‬‫ﺷﻮد‬.)‫ﺑﺮش‬ ‫ﻮ‬‫ﻲ‬‫ر‬‫ﻳ‬‫ﺑﻲ‬‫ﻳ‬ ‫ﭘ‬‫ﻴﺮ‬ ‫ﻮ‬‫ﻲ‬‫ﻮ‬‫ﺑﺮش‬
‫روي‬‫درﺧﺖ‬‫ﺟﺴﺘﺠﻮ‬(
•‫ﻣﺜﻼ‬‫در‬‫ﻧﻘﺸﻪ‬‫روﻣﺎﻧﻲ‬‫ﭼﻮن‬20‫ﺷﻬﺮ‬‫وﺟﻮد‬‫دارد‬‫ﺑﻨﺎﺑﺮاﻳﻦ‬‫ﻃﻮل‬‫راه‬‫ﺣﻞ‬‫ﺑﺎﻳﺪ‬
‫ﺣﺪاﻛﺜﺮ‬19‫ﺑﺎﺷﺪ‬. ‫ﺮ‬‫ﺑ‬
•‫ﺑﻨﺎﺑﺮاﻳﻦ‬‫ﻫﻴﭻ‬‫وﻗﺖ‬‫ﮔﺮه‬‫اي‬‫ﺑﺎ‬‫ﻋﻤﻖ‬‫ﺑﻴﺶ‬‫از‬19‫ﺑﺮرﺳﻲ‬‫ﻧﺨﻮاﻫﺪ‬‫ﺷﺪ‬.
•‫اﮔ‬‫در‬‫ﻣﺤﺪوده‬‫ﻘ‬ ‫ﻋ‬l‫راه‬‫ﺣﻠ‬‫وﺟﻮد‬‫داﺷﺘﻪ‬،‫ﺑﺎﺷﺪ‬‫ه‬ ‫ﺑﺎﻻﺧ‬‫ﺪا‬ ‫ﭘ‬‫ﺧﻮاﻫﺪ‬ ‫اﮔﺮ‬‫در‬‫ﻣﺤﺪوده‬‫ﻋﻤﻘﻲ‬l‫راه‬‫ﺣﻠﻲ‬‫وﺟﻮد‬‫داﺷﺘﻪ‬،‫ﺑﺎﺷﺪ‬‫ﺑﺎﻻﺧﺮه‬‫ﭘﻴﺪا‬‫ﺧﻮاﻫﺪ‬
،‫ﺷﺪ‬‫اﻣﺎ‬‫ﻫﻴﭻ‬‫ﺗﻀﻤﻴﻨﻲ‬‫ﺑﺮاي‬‫ﻳﺎﻓﺘﻦ‬‫راه‬‫ﺣﻞ‬‫ﺑﻬﻴﻨﻪ‬‫وﺟﻮد‬‫ﻧﺪارد‬.
‫ﻣﺤﺪود‬ ‫ﻋﻤﻖ‬ ‫ﺑﺎ‬ ‫ﺟﺴﺘﺠﻮي‬‫ﻣﺤﺪود‬ ‫ﻋﻤﻖ‬ ‫ﺑﺎ‬ ‫ﺟﺴﺘﺠﻮي‬‫و‬ ‫ﻖ‬ ‫ﺑ‬ ‫ﺠﻮي‬ ‫ﺟ‬‫و‬ ‫ﻖ‬ ‫ﺑ‬ ‫ﺠﻮي‬ ‫ﺟ‬
•‫ﻛﺎﻣﻞ؟‬‫ﻛﺎﻣﻞ؟‬
–‫ﺑﻠﻪ‬)‫اﮔﺮ‬l ≥ d(
•‫ﭘﻴﭽﻴﺪﮔﻲ‬‫زﻣﺎﻧﻲ؟‬
O(bl) –O(bl)
•‫ﺪﮔ‬‫؟‬ ‫ﺎﻓﻈ‬ •‫ﭘﻴﭽﻴﺪﮔﻲ‬‫ﺣﺎﻓﻈﻪ؟‬
–O(bl)
•‫ﺑﻬﻴﻨﻪ؟‬
–‫ﺧﻴﺮ‬

‫ﻣﺤﺪود‬ ‫ﻋﻤﻖ‬ ‫ﺑﺎ‬ ‫ﺟﺴﺘﺠﻮي‬‫ﻣﺤﺪود‬ ‫ﻋﻤﻖ‬ ‫ﺑﺎ‬ ‫ﺟﺴﺘﺠﻮي‬
‫ﺑﺎزﮔﺸﺘﻲ‬ ‫ﺳﺎزي‬ ‫ﭘﻴﺎده‬‫ﺑﺎزﮔﺸﺘﻲ‬ ‫ﺳﺎزي‬ ‫ﭘﻴﺎده‬
‫ﺗﻜﺮاري‬ ‫ﻛﻨﻨﺪه‬ ‫ﻋﻤﻴﻖ‬ ‫ﺟﺴﺘﺠﻮي‬‫ﺗﻜﺮاري‬ ‫ﻛﻨﻨﺪه‬ ‫ﻋﻤﻴﻖ‬ ‫ﺟﺴﺘﺠﻮي‬‫ﺗﻜﺮاري‬ ‫ﻛﻨﻨﺪه‬ ‫ﻋﻤﻴﻖ‬ ‫ﺟﺴﺘﺠﻮي‬‫ﺗﻜﺮاري‬ ‫ﻛﻨﻨﺪه‬ ‫ﻋﻤﻴﻖ‬ ‫ﺟﺴﺘﺠﻮي‬
•‫ﻣﺸﻜﻞ‬‫اﺻﻠﻲ‬‫در‬‫ﺟﺴﺘﺠﻮي‬‫ﻋﻤﻘﻲ‬‫ﺑﺎ‬‫ﻋﻤﻖ‬‫ﻣﺤﺪود‬‫ﺷﺪه‬(DLS)‫اﻧﺘﺨﺎب‬
‫ﻳﻚ‬‫ﻣﺤﺪوده‬‫ﻋﻤﻘﻲ‬‫ﻣﻨﺎﺳﺐ‬‫اﺳﺖ‬. ‫ﻳ‬‫و‬‫ﻲ‬‫ﺐ‬
•‫ﻧﻘﺸ‬‫ﺎﻧ‬‫ل‬ ‫ﻃ‬‫ﮔ‬‫ﺷ‬9‫ﺎﺷﺪ‬)‫ﻗﻄ‬(‫ا‬ •‫در‬‫ﻧﻘﺸﻪ‬‫روﻣﺎﻧﻲ‬‫ﻃﻮل‬‫ﺑﺰرﮔﺘﺮﻳﻦ‬‫ﻣﺴﻴﺮ‬‫ﺑﻴﻦ‬‫دو‬‫ﺷﻬﺮ‬9‫ﻣﻲ‬‫ﺑﺎﺷﺪ‬)‫ﻗﻄﺮ‬(،‫و‬‫اﻳﻦ‬
‫ﻣﺤﺪوده‬‫ﻋﻤﻘﻲ‬‫ﻣﻨﺎﺳﺐ‬‫ﺗﺮ‬‫از‬19‫ﻣﻲ‬‫ﺑﺎﺷﺪ‬.‫اﻣﺎ‬‫در‬‫ﺑﻴﺸﺘﺮ‬‫ﻓﻀﺎﻫﺎي‬‫ﺣﺎﻟﺖ‬
‫ﺨﺎ‬ ‫اﻧ‬‫ﺪ‬‫ﺎ‬‫ﻞ‬ ‫ﻗ‬‫از‬‫ﻞ‬‫ﺄﻟ‬‫ﻧ‬‫ﺎﺷﺪ‬ ‫اﻧﺘﺨﺎب‬‫ﻣﺤﺪوده‬‫ﻣﻨﺎﺳﺐ‬‫ﻗﺒﻞ‬‫از‬‫ﺣﻞ‬‫ﻣﺴﺄﻟﻪ‬‫ﻣﻴﺴﺮ‬‫ﻧﻤﻲ‬‫ﺑﺎﺷﺪ‬.
•‫ﺟﺴﺘﺠﻮي‬‫ﻋﻤﻴﻖ‬‫ﻛﻨﻨﺪه‬‫ﺗﻜﺮاري‬‫روﺷﻲ‬‫ﺑﺮاي‬‫ﺗﻌﻴﻴﻦ‬‫ﻣﺤﺪوده‬‫ﻋﻤﻘﻲ‬‫ﻣﻨﺎﺳﺐ‬
‫ﺑﺎ‬‫اﻣﺘﺤﺎن‬‫ﻛﺮدن‬‫ﺗﻤﺎﻣﻲ‬‫ﻣﺤﺪوده‬‫ﻫﺎ‬)‫از‬‫ﺻﻔﺮ‬‫ﺑﻪ‬‫ﺑﺎﻻ‬(‫ﻣﻲ‬‫ﺑﺎﺷﺪ‬.‫ﻳﻌﻨﻲ‬‫اول‬ ‫ﺑ‬‫ﺮ‬‫ﻲ‬‫و‬‫ز‬‫ﺮ‬‫ﺑ‬‫ﺑ‬‫ﻲ‬‫ﺑ‬‫ﻲ‬ ‫ﻳ‬‫و‬
‫ﻋﻤﻖ‬،‫ﺻﻔﺮ‬‫ﺑﻌﺪ‬‫ﻋﻤﻖ‬1،‫ﺑﻌﺪ‬‫ﻋﻤﻖ‬2‫و‬...
•‫ﺟﺴﺘﺠﻮي‬‫ﻋﻤﻴﻖ‬‫ﻛﻨﻨﺪه‬‫ﺗﻜﺮاري‬‫ﻣﺰاﻳﺎي‬‫ﺟﺴﺘﺠﻮي‬‫ﺳﻄﺤﻲ‬‫و‬‫ﻋﻤﻘﻲ‬
‫ا‬‫ﺎ‬‫ﻛ‬ ‫ﺗ‬‫ﻛﻨﺪ‬: ‫را‬‫ﺑﺎ‬‫ﻫﻢ‬‫ﺗﺮﻛﻴﺐ‬‫ﻣﻲ‬‫ﻛﻨﺪ‬:
–‫ﻣﺎﻧﻨﺪ‬‫ﺟﺴﺘﺠﻮي‬‫ﺳﻄﺤﻲ‬‫ﻛﺎﻣﻞ‬)‫اﮔﺮ‬‫ﻓﺎﻛﺘﻮر‬‫اﻧﺸﻌﺎب‬‫ﻣﺤﺪود‬‫ﺑﺎﺷﺪ‬(‫و‬ ‫ﻲ‬‫ﻞ‬‫ﺮ‬‫ب‬
‫ﺑﻬﻴﻨﻪ‬)‫اﮔﺮ‬‫ﻫﺰﻳﻨﻪ‬‫ﻣﺴﻴﺮ‬‫ﻳﻚ‬‫ﺗﺎﺑﻊ‬‫ﻏﻴﺮ‬‫ﻧﺰوﻟﻲ‬‫ﺑﺮﺣﺴﺐ‬‫ﻋﻤﻖ‬‫ﺑﺎﺷﺪ‬(‫اﺳﺖ‬.
‫ﺘ‬‫ﻘ‬‫ا‬ ‫ا‬‫ف‬‫ﺎﻓﻈﻪ‬‫ﺧﻄ‬O(bd)‫ﺎﺷﺪ‬ –‫ﺟﺴﺘﺠﻮي‬‫ﻋﻤﻘﻲ‬‫داراي‬‫ﻣﺼﺮف‬‫ﺣﺎﻓﻈﻪ‬‫ﺧﻄﻲ‬O(bd)‫ﻣﻲ‬‫ﺑﺎﺷﺪ‬.
•‫اﻳﻦ‬‫ﺟﺴﺘﺠﻮ‬‫از‬‫ﻧﻈﺮ‬‫ﭘﻴﭽﻴﺪﮔﻲ‬‫زﻣﺎﻧﻲ‬‫ﻣﺎﻧﻨﺪ‬‫ﺟﺴﺘﺠﻮي‬‫ﻣﺤﺪود‬‫ﺷﺪه‬
‫ﻜ‬‫ﻻ‬‫ﻂ‬ ‫ﻣﻲ‬،‫ﺑﺎﺷﺪ‬‫ﺑﻪ‬‫ﺟﺰ‬‫اﻳﻨﻜﻪ‬‫ﺑﺮﺧﻲ‬‫ﺣﺎﻻت‬‫ﭼﻨﺪ‬‫ﺑﺎر‬‫ﺑﺴﻂ‬‫داده‬‫ﻣﻲ‬‫ﺷﻮﻧﺪ‬..

‫ﺗﻜﺮاري‬ ‫ﻛﻨﻨﺪه‬ ‫ﻋﻤﻴﻖ‬ ‫ﺟﺴﺘﺠﻮي‬(l = 0) ‫ﺗﻜﺮاري‬ ‫ﻛﻨﻨﺪه‬ ‫ﻋﻤﻴﻖ‬ ‫ﺟﺴﺘﺠﻮي‬(l = 0) ‫ﺗﻜﺮاري‬ ‫ﻛﻨﻨﺪه‬ ‫ﻋﻤﻴﻖ‬ ‫ﺟﺴﺘﺠﻮي‬(l = 0) ‫ﺗﻜﺮاري‬ ‫ﻛﻨﻨﺪه‬ ‫ﻋﻤﻴﻖ‬ ‫ﺟﺴﺘﺠﻮي‬(l = 0)

‫ﺗﻜﺮاري‬ ‫ﻛﻨﻨﺪه‬ ‫ﻋﻤﻴﻖ‬ ‫ﺟﺴﺘﺠﻮي‬ ‫ﺧﻮاص‬‫ﺗﻜﺮاري‬ ‫ﻛﻨﻨﺪه‬ ‫ﻋﻤﻴﻖ‬ ‫ﺟﺴﺘﺠﻮي‬ ‫ﺧﻮاص‬‫ﺗﻜﺮاري‬ ‫ﻛﻨﻨﺪه‬ ‫ﻋﻤﻴﻖ‬ ‫ﺟﺴﺘﺠﻮي‬ ‫ﺧﻮاص‬‫ﺗﻜﺮاري‬ ‫ﻛﻨﻨﺪه‬ ‫ﻋﻤﻴﻖ‬ ‫ﺟﺴﺘﺠﻮي‬ ‫ﺧﻮاص‬
•‫ﻛﺎﻣﻞ؟؟‬‫ﺑﻠﻪ‬)‫ﻣﺎﻧﻨﺪ‬‫ﺟﺴﺘﺠﻮي‬‫ﺳﻄﺤﻲ‬(
•‫ﺪﮔ‬‫ﺎﻧ‬ ‫ز‬‫؟؟‬ •‫ﭘﻴﭽﻴﺪﮔﻲ‬‫زﻣﺎﻧﻲ‬‫؟؟‬
db1 + (d – 1) b2 + … + bd = O(bd)
•‫ﭘﻴﭽﻴﺪﮔﻲ‬‫ﺣﺎﻓﻈﻪ؟؟‬O(bd)
•‫ﺑﻬﻴﻨﻪ‬‫؟؟‬،‫ﺑﻠﻪ‬)‫ﻣﺎﻧﻨﺪ‬‫ﺟﺴﺘﺠﻮي‬‫ﺳﻄﺤﻲ‬(
•‫ﻣﻲ‬‫ﺗﻮاﻧﺪ‬‫ﺑﺮاي‬‫ﻛﺎوش‬‫درﺧﺖ‬‫ﺟﺴﺘﺠﻮي‬‫ﻫﺰﻳﻨﻪ‬‫ﻳﻜﻨﻮاﺧﺖ‬‫اﺻﻼح‬‫ﺷﻮد‬!!!
‫ﺗﻜﺮاري‬ ‫ﻛﻨﻨﺪه‬ ‫ﻋﻤﻴﻖ‬ ‫زﻣﺎﻧ‬ ‫ﭘﻴﭽﻴﺪﮔ‬‫ﺗﻜﺮاري‬ ‫ﻛﻨﻨﺪه‬ ‫ﻋﻤﻴﻖ‬ ‫زﻣﺎﻧ‬ ‫ﭘﻴﭽﻴﺪﮔ‬‫ﺗﻜﺮاري‬ ‫ﻛﻨﻨﺪه‬ ‫ﻋﻤﻴﻖ‬ ‫زﻣﺎﻧﻲ‬ ‫ﭘﻴﭽﻴﺪﮔﻲ‬‫ﺗﻜﺮاري‬ ‫ﻛﻨﻨﺪه‬ ‫ﻋﻤﻴﻖ‬ ‫زﻣﺎﻧﻲ‬ ‫ﭘﻴﭽﻴﺪﮔﻲ‬
0DLS (l = 0)
b1DLS (l = 1)
‫ﺳﺮﺑﺎر‬ ≤ NDLS (l = d)
b1 + b2
DLS (l = 2)
‫ر‬ ‫ﺮﺑ‬ DLS (l d)
.
.
.
.
.
.
b1 + b2 + b3 + … + bd – 1DLS (l = d - 1)
b1 + b2 + b3 + + bd – 1 + bdDLS (l = d)
N = db1 + (d 1)b2 + (d 2)b3 + + 2bd – 1 + bd
b1 + b2 + b3 + … + bd 1 + bdDLS (l d)
NIDS = db1 + (d – 1)b2 + (d – 2)b3 + … + 2bd 1 + bd
‫ﻛﺎرآﻳﻲ‬IDS ‫ﻛﺎرآﻳﻲ‬IDS
•‫ﺗﻌﺪاد‬‫ﮔﺮه‬‫ﻫﺎي‬‫ﺗﻮﻟﻴﺪ‬‫ﺷﺪه‬‫ﺗﻮﺳﻂ‬DLS‫در‬‫ﻋﻤﻖ‬d‫ﺑﺎ‬‫ﻓﺎﻛﺘﻮر‬‫اﻧﺸﻌﺎب‬b: ‫ﺮ‬‫ﻴ‬ ‫ﻮ‬‫ﻮ‬‫ﻖ‬‫ﺑ‬‫ﻮ‬‫ب‬
NDLS= b + b2 + … + bd-1 + bd
•‫ﺗﻌﺪاد‬‫ﮔﺮه‬‫ﻫﺎي‬‫ﺗﻮﻟﻴﺪ‬‫ﺷﺪه‬‫ﺗﻮﺳﻂ‬IDS‫در‬‫ﻋﻤﻖ‬d‫ﺑﺎ‬‫ﻓﺎﻛﺘﻮر‬‫اﻧﺸﻌﺎب‬b: ‫ﺮ‬‫ي‬‫ﻴ‬ ‫ﻮ‬‫ﻮ‬‫ر‬‫ﻖ‬‫ﺑ‬‫ﻮر‬‫ب‬
NIDS= db1 +(d-1) b2 + … + 2bd-1 + 1bd
•‫اﮔﺮ‬b = 10‫و‬d = 5:
NDLS=10 + 100 + 1,000 + 10,000 + 100,000 = 111,110DLS , , , ,
NIDS= 50 + 400 + 3,000 + 20,000 + 100,000 = 123,450
•‫ﻣﺤﺎﺳﺒﻪ‬‫ﻣﻴﺰان‬‫ﺳﺮﺑﺎر‬:
((123450 – 111110)/111110)* 100 = 11%((123450 111110)/111110) 100 11%
–‫ﺑﺎ‬‫اﻓﺰاﻳﺶ‬‫ﻓﺎﻛﺘﻮر‬‫اﻧﺸﻌﺎب‬b‫ﻣﻴﺰان‬‫ﺳﺮﺑﺎر‬‫ﻛﺎﻫﺶ‬‫ﻣﻲ‬‫ﻳﺎﺑﺪ‬.
–‫در‬‫ﺑﺪﺗﺮﻳﻦ‬‫ﺣﺎﻟﺖ‬b = 2،‫ﺳﺮﺑﺎر‬100%‫اﺳﺖ‬‫و‬‫اﻳﻦ‬‫ﺟﺴﺘﺠﻮ‬‫دو‬‫ﺑﺮاﺑﺮ‬‫زﻣﺎن‬‫ﻣﻲ‬‫ﺑﺮد‬.
‫ﺮﻳﻦ‬ ‫ﺑ‬‫ﺮﺑ‬‫ﻳﻦ‬‫ﻮ‬‫ﺑﺮ‬ ‫ﺑﺮ‬‫ﻲ‬‫ﺑﺮ‬
‫دوﻃﺮﻓﻪ‬ ‫ﺟﺴﺘﺠﻮي‬‫دوﻃﺮﻓﻪ‬ ‫ﺟﺴﺘﺠﻮي‬‫دوﻃﺮﻓﻪ‬ ‫ﺟﺴﺘﺠﻮي‬‫دوﻃﺮﻓﻪ‬ ‫ﺟﺴﺘﺠﻮي‬
•‫اﻳﺪه‬:‫اﻧﺠﺎم‬‫ﺟﺴﺘﺠﻮ‬‫در‬‫دو‬‫ﺟﻬﺖ‬‫ﺑﻪ‬‫ﻃﻮر‬‫ﻫﻤﺰﻣﺎن‬
–‫و‬‫ﻪ‬‫ﺟﻠ‬:‫از‬‫ﺣﺎﻟﺖ‬‫ﻪ‬ ‫اوﻟ‬‫ﻪ‬‫ﺖ‬‫ﺣﺎﻟﺖ‬‫ﻫﺪف‬ –‫رو‬‫ﺑﻪ‬‫ﺟﻠﻮ‬:‫از‬‫ﺣﺎﻟﺖ‬‫اوﻟﻴﻪ‬‫ﺑﻪ‬‫ﺳﻤﺖ‬‫ﺣﺎﻟﺖ‬‫ﻫﺪف‬
–‫رو‬‫ﺑﻪ‬‫ﻋﻘﺐ‬:‫از‬‫ﺣﺎﻟﺖ‬‫ﻫﺪف‬‫ﺑﻪ‬‫ﺳﻤﺖ‬‫ﺣﺎﻟﺖ‬‫اوﻟﻴﻪ‬
‫ﮕ‬ •‫اﻧﮕﻴﺰه‬:bd/2 + bd/2‫ﺑﺴﻴﺎر‬‫ﻛﻤﺘﺮ‬‫از‬bd‫ﻣﻲ‬‫ﺑﺎﺷﺪ‬
•‫ﻣﺜﺎل‬:‫اﮔﺮ‬‫راه‬‫ﺣﻞ‬‫ﻳﻚ‬‫ﻣﺴﺄﻟﻪ‬‫در‬‫ﻋﻤﻖ‬d = 6‫ﺑﺎﺷﺪ‬‫و‬b = 10‫آﻧﮕﺎه‬
–‫ﺟﺴﺘﺠﻮي‬‫دو‬‫ﻃﺮﻓﻪ‬)‫در‬‫ﻫﺮ‬‫دو‬‫ﻃﺮف‬‫ﺟﺴﺘﺠﻮي‬‫ﺳﻄﺤﻲ‬(22,200‫ﮔﺮه‬
–‫ﺟﺴﺘﺠﻮي‬‫ﺳﻄﺤﻲ‬11,111,000‫ﮔﺮه‬

‫دوﻃﺮﻓﻪ‬ ‫ﺟﺴﺘﺠﻮي‬‫دوﻃﺮﻓﻪ‬ ‫ﺟﺴﺘﺠﻮي‬‫دوﻃﺮﻓﻪ‬ ‫ﺟﺴﺘﺠﻮي‬‫دوﻃﺮﻓﻪ‬ ‫ﺟﺴﺘﺠﻮي‬
•‫ﭘﻴﭽﻴﺪﮔﻲ‬‫زﻣﺎﻧﻲ‬:O(bd/2)
•‫ﭘﻴﭽﻴﺪﮔﻲ‬‫ﺣﺎﻓﻈﻪ‬:O(bd/2) ‫ﻲ‬ ‫ﭘ‬
–‫ﺑﻪ‬‫ﻣﻨﻈﻮر‬‫ﺑﺮرﺳﻲ‬‫ﺗﻌﻠﻖ‬‫ﺣﺪاﻗﻞ‬‫ﻳﻜﻲ‬‫از‬‫درﺧﺖ‬‫ﻫﺎ‬‫ﺑﺎﻳﺪ‬‫در‬‫ﺣﺎﻓﻈﻪ‬‫ﻧﮕﻬﺪاري‬‫ﺷﻮد‬
–‫ﻣﺼﺮف‬‫ﺣﺎﻓﻈﻪ‬،‫ﻧﻤﺎﻳﻲ‬‫ﺑﺰرﮔﺘﺮﻳﻦ‬‫ﺿﻌﻒ‬‫ﺟﺴﺘﺠﻮي‬‫دوﻃﺮﻓﻪ‬‫ﻣﻲ‬‫ﺑﺎﺷﺪ‬ ‫ﻣﺼﺮف‬‫ﺣﺎﻓﻈﻪ‬،‫ﻧﻤﺎﻳﻲ‬‫ﺑﺰرﮔﺘﺮﻳﻦ‬‫ﺿﻌﻒ‬‫ﺟﺴﺘﺠﻮي‬‫دوﻃﺮﻓﻪ‬‫ﻣﻲ‬‫ﺑﺎﺷﺪ‬
‫ﻞ‬ ‫ﻛﺎ‬‫ﮕ‬)‫ا‬‫ﺎ‬‫ﮔﺎ‬‫ﺎ‬ ‫ﻜ‬( •‫ﻛﺎﻣﻞ‬‫ﺑﻮدن‬‫و‬‫ﺑﻬﻴﻨﮕﻲ‬)‫ﺑﺮاي‬‫ﻫﺰﻳﻨﻪ‬‫ﻫﺎي‬‫ﮔﺎم‬‫ﻳﻜﺴﺎن‬(:
–‫اﮔﺮ‬‫در‬‫ﻫﺮ‬‫دو‬‫ﻃﺮف‬‫از‬‫ﺟﺴﺘﺠﻮي‬‫ﺳﻄﺤﻲ‬‫اﺳﺘﻔﺎده‬‫ﺷﻮد‬
‫ﻫﺎ‬ ‫اﻟﮕﻮرﻳﺘﻢ‬ ‫ﺧﻼﺻﻪ‬‫ﻫﺎ‬ ‫اﻟﮕﻮرﻳﺘﻢ‬ ‫ﺧﻼﺻﻪ‬‫ﻫﺎ‬ ‫اﻟﮕﻮرﻳﺘﻢ‬ ‫ﺧﻼﺻﻪ‬‫ﻫﺎ‬ ‫اﻟﮕﻮرﻳﺘﻢ‬ ‫ﺧﻼﺻﻪ‬
‫ﺗﻜﺮاري‬ ‫ﺣﺎﻻت‬‫ﺗﻜﺮاري‬ ‫ﺣﺎﻻت‬‫ﺗﻜﺮاري‬ ‫ﺣﺎﻻت‬‫ﺗﻜﺮاري‬ ‫ﺣﺎﻻت‬
•‫ﺷﻜﺴﺖ‬‫در‬‫ﺗﺸﺨﻴﺺ‬‫ﺣﺎﻟﺖ‬‫ﻫﺎي‬‫ﺗﻜﺮاي‬‫ﻣﻲ‬‫ﺗﻮاﻧﺪ‬‫ﻳﻚ‬‫ﻣﺴﺄﻟﻪ‬‫ﺧﻄﻲ‬‫را‬‫ﺑﻪ‬
‫ﻳﻚ‬‫ﺄﻟﻪ‬ ‫ﻣ‬‫ﺎﻳ‬ ‫ﻧ‬‫ﺪﻳﻞ‬ ‫ﺗ‬‫ﻛﻨﺪ‬! ‫ﻳﻚ‬‫ﻣﺴﺄﻟﻪ‬‫ﻧﻤﺎﻳﻲ‬‫ﺗﺒﺪﻳﻞ‬‫ﻛﻨﺪ‬!
‫ﮔﺮاف‬ ‫ﺟﺴﺘﺠﻮي‬‫ﮔﺮاف‬ ‫ﺟﺴﺘﺠﻮي‬‫ﮔﺮاف‬ ‫ﺟﺴﺘﺠﻮي‬‫ﮔﺮاف‬ ‫ﺟﺴﺘﺠﻮي‬

‫ﺧﻼﺻﻪ‬‫ﺧﻼﺻﻪ‬‫ﺧﻼﺻﻪ‬‫ﺧﻼﺻﻪ‬
•‫ﻓﺮﻣﻮﻟﻪ‬‫ﺳﺎزي‬‫ﻣﺴﺄﻟﻪ‬‫اﻏﻠﺐ‬‫ﻧﻴﺎز‬‫ﺑﻪ‬‫اﻧﺘﺰاع‬‫ﺟﺰﻳﻴﺎت‬‫ﻣﺴﺄﻟﻪ‬،‫دارد‬‫ﺗﺎ‬
‫ﺑﺘﻮان‬‫ﻓﻀﺎي‬‫ﺣﺎﻟﺘ‬‫ﺑﺪﺳﺖ‬‫آوردﻛﻪ‬‫ﺑﻪ‬‫ﺻﻮرت‬‫ون‬ ‫ﻣﻘ‬‫ﺑﻪ‬‫ﻓﻪ‬ ‫ﺻ‬‫اي‬ ‫ﺑﺘﻮان‬‫ﻓﻀﺎي‬‫ﺣﺎﻟﺘﻲ‬‫ﺑﺪﺳﺖ‬‫آوردﻛﻪ‬‫ﺑﻪ‬‫ﺻﻮرت‬‫ﻣﻘﺮون‬‫ﺑﻪ‬‫ﺻﺮﻓﻪ‬‫اي‬
‫ﻗﺎﺑﻞ‬‫ﻛﺎوش‬‫ﻛﺮد‬‫ن‬‫و‬‫ﺟﺴﺘﺠﻮ‬‫ﺑﺎﺷﺪ‬.
•‫اﻧﻮاع‬‫اﺳﺘﺮاﺗﮋي‬‫ﻫﺎي‬‫ﻧﺎآﮔﺎﻫﺎﻧﻪ‬‫وﺟﻮد‬‫دارد‬ ‫اﻧﻮاع‬‫اﺳﺘﺮاﺗﮋي‬‫ﻫﺎي‬‫ﻧﺎآﮔﺎﻫﺎﻧﻪ‬‫وﺟﻮد‬‫دارد‬.
•‫ﻣﺼﺮف‬‫ﺣﺎﻓﻈﻪ‬‫ﺟﺴﺘﺠﻮي‬‫ﻋﻤﻴﻖ‬‫ﻛﻨﻨﺪه‬‫ﺗﻜﺮاري‬‫داراي‬‫ﻣﺮﺗﺒﻪ‬‫ﺧﻄﻲ‬
‫ﻣﻲ‬‫ﺑﺎﺷﺪ‬‫و‬‫زﻣﺎن‬‫ﺧﻴﻠﻲ‬‫ﺑﻴﺸﺘﺮي‬‫ﻧﺴﺒﺖ‬‫ﺑﻪ‬‫ﺳﺎﻳﺮ‬‫روﺷﻬﺎي‬‫ﻧﺎآﮔﺎﻫﺎﻧﻪ‬ ‫ﻣﻲ‬‫ﺑﺎﺷﺪ‬‫و‬‫زﻣﺎن‬‫ﺧﻴﻠﻲ‬‫ﺑﻴﺸﺘﺮي‬‫ﻧﺴﺒﺖ‬‫ﺑﻪ‬‫ﺳﺎﻳﺮ‬‫روﺷﻬﺎي‬‫ﻧﺎآﮔﺎﻫﺎﻧﻪ‬
‫ﻣﺼﺮف‬‫ﻧﻤﻲ‬‫ﻛﻨﺪ‬.

�ݺ�ߣ

AI ch3

More Related Content

More from Mhd Sb (7)

AI ch3