در UCS هر بار راسی که کمترین فاصله رو داره انتخاب می کنیم و چک می کنیم که آیا راس هدف هست یا نه اگر راس هدف نبود گسترش داده میشه و تا رسیدن به هدف این کار رو ادامه میدیم
در BFS ما اول همه ی راس های متصل به یک Node رو گسترش میدادیم بعد از گسترش دادن چک می کنیم که به هدف رسیدیم یا نه واین کارو تا رسیدن به هدف ادامه میدیم.
پس تفاوت BFS و UCS دو مورد هست :
-
در UCS راسی که گسترش داده میشه راس با کمترین cost هست در حالی که در BFS بترتیب ورود گسترش داده میشن
-
در BFS ما بعد از گسترش این که به هدف رسیدیم چک میشه ولی در UFS قبل از گسترش
این گراف رو در نظر بگیرید :
فرض کنید که از راس A شروع کردیم و می خواهیم به G برسیم
الگوریتم UCS به این شکل عمل می کنه :
مرحله 1 : 2 مسیر A_B , A_D رو به عنوان مسیر اولیه به راس های پیموده شده اضافه می کنیم :
A_B
A_D
مرحله 2 : این جا ما 2 مسیر A_B داریم و A_D چون مسیر A_D طولش از A_B کمتر هست اونو گسترش میدیم
A_B
A_D_F
A_D_E
مرحله 3 : این جا طول مسیر A_B از 2 مسیر A_D_E , A_D_F کمتر هست پس مسیر A_B گسترش داده میشه
A_B_C
A_D_F
A_D_E
مرحله 4 :این جا مسیر A_D_F کمترین طول روداره (طول از A_D که 3 هست + D_F که 2 هست یعنی در مجموع 5
A_B_C
A_D_F_G
A_D_E
مرحله 5 : در این مرحله چون A_D_E کمترین طول رو داره گسترش داده میشه (دقت کنید با این که حتی به Goal رسیدیم ولی جست و جو ادامه داره)
A_B_C
A_D_F_G
A_D_E_B چون قبلا به B رفتیم و این مسیر از A_B بلند تر هست اضافه نمیشه
مرحله 6 : در این مرحله چون A_B_C کمترین طول رو داره گسترش داده میشه
A_B_C_G
A_D_F_G
مرحله 7 : در این مرحله چون A_D_F_G کمترین طول رو داره گسترش داده میشه ولی چون داخل مسیر G هم وجود داره یعنی به goal رسیدیم و مسیر مورد نظر برگشت داده میشه .
شَبه کد الگوریتم به این شکل میشه :