تَرزالش - 2
رو هم رفته سه فرایافت بُنیادین در هر رویکرد خوارزمیک در راهکاریابی داریم که جدا از شیوه بکاررفته در یافتن راهکار، هنباز هستند:
- بازنمایش دشواری (representation)
- آماج برآختی (objective)
- پردازه ارزیابی (evaluate function)
بازنمایش دربرگیرنده راهکارهای نامزد دگرگزینه برای دستکاری و اندیشیدن است.
برآختی از آماج ما در راهکاریابی میگوید، آنچه بدنبال آن هستیم.
پردازه ارزیابی نیز یک «ارزش ویژه» که نمایانگر هوتاد راهکار یافته از بازنمایش دشواری بوده را برگردانده، یا سادهتر به ما توانایی همسنجی هوتاد دو راهکار دگرگزینه را میدهد.
در دنباله برای بازنمود چند دشواری را آورده و سپس هر سه فرایافت بالا را در آنها نشان میدهیم.
دشواری: راستین بولین (boolean)
یکی از دشواریهای بنیادین در منطق، دشواری خوشنودپذیری است. در اینجا کار، ساختن یک گزاره بولین از ورتندههایی است که به راستین بیارزیابند.
برای نمونه:
چالش در اینجا یافتن گُمارش راستینگی برای هر ورتنده Xi، برای i = 1,...,100، بریختی که F(x) = TRUE شود.
اِسپاش جستجو
اِسپاش جستجو به اسپاشی گفته میشود که اگر همه آن را جستجو کنیم بیگمان به پاسخ یا راهکار دلخواه خواسته شده میرسیم.
در فرایند راهکاریابی کارآمد است که پیش از پرداختن به دشواری، اِسپاش جستجوی آن را برایانیم تا یک دورنمای هماگ از دشواری در مندار داشته باشیم.
در دشواری بولین بالا، میتوانیم بیافماریم که هر رشته دودویی بدرازای 100، خود یک راهکار تَوند برای دشواری ما بشمار میرود.
از آنجاییکه برای هر ورتنده ما دو گزینه (0 و 1) بیشتر نداریم، پس برای 100 ورتنده خواهیم داشت 30^10 ≈ 100^2 شایندگی.
چنانکه میتوان دید شمار شایندهها
بسیار بالا بوده و شدنی نیست که همه آنها را برشمارید!
در کنار آن، یافتن "پردازه ارزیابی" نیز آن اندازه سرراست نمیزند. یک پردازه ارزیابی میباید به ما یک راهنماییای از نزدیک شدن به پاسخ خواستنی بدهد، هنگامیکه در
این دشواری از برآیند همه ورتندهها در کنار یکدیگر است که واپسین پاسخ به درستین یا دروغین میارزیابد، با دگراندن یک ورتنده پاسخ نهایی نیز وارونه میشود!
تا دنبال شود ...
- فرایافت = پنداره؛ concept؛ مفهوم
- خوارزمیک = algorithmic
- هنباز = مشترک، common, shared
- برآختی = objective
- آماج = هدف، objective
- همسنجی = مقایسه
- هوتاد = کیفیت، quality
- دگرگزینه = alternative
- راستین = true
- خوشنودپذیری = satisfiability
- ورتَنده = متغیر = variable
- میارزیابند = ارزیافتن = to evaluate
- چالش = challenge
- راستینگی = فرهود؛ truth
- گُمارش = assignment
- اِسپاش = space
- هَماگ = کلی
- اَفماردن = calculate (An Etymological Dictionary of Astronomy and Astrophysics - English-French-Persian)
- تَوَند = پتنسیال
- شایندگی = امکان، possibility