جستجو فرینگ

از ویکی‌پدیا، دانشنامهٔ آزاد

در علوم رایانه، جستجو فرینگ، یک الگوریتم پیمایش گراف است که کم هزینه‌ترین مسیر از گره معلوم تا یک گره مقصد را می‌دهد.

تعریف الگوریتم[ویرایش]

این الگوریتم، سطحی مابین الگوریتم‌های جست و جوی آگاهانهٔ آ* و نوعی عمیق کنندهٔ تکراری آ* می‌باشد. اگر x)g) هزینه مسیرهای طی شده از گره مشخص شده وx)h) تخمین بهینه (heuristic) هزینه مشخص شده تا هدف باشد، آنگاه داریم:

ƒ(x) = g(x) + h(x)

و h* هزینه فعلی و واقعی مسیر طی شده تا هدف است.

پس نسبتاً یک الگوریتم جست و جوی IDA* نیز داریم (:الگوریتمی که کوتاهترین مسیر را از یک گره مشخص شده تا هریک از گره‌های عضو مجموعه گره‌های هدف می‌یابد) که یک تابع جست و جوی بازگشتی عمق اول(DFS) از گره ریشه می‌سازد. هنگامی این الگوریتم متوقف می‌شود که یا گره هدف یافت شده یا به مقدار بیشینهٔ f برسیم. اگر بار اولی که به آستانهٔ بیشینهٔ f رسیدیم، گره هدف هنوز یافت نشده بود، آستانهٔ بیشینه افزایش میابد و الگوریتم دوباره تکرار شده و مجدداً جستجو می‌کند. الگوریتم فرینگ با استفاده از ساختمان داده‌ای که در آن یک یا دو لیست پیوندی جهت اشاره به قسمت‌های مختلف درخت جستجو به الگوریتم IDA* بهبود بخشیده است. لیست now حاوی مکان فعلیه اشاره گر و لیست later حاوی نقاط طی شده اشاره گر است. پس هنگام شروع از ریشهٔ درخت جستجوnow شامل ریشه و later خالی است. سپس الگوریتم یکی از دو عمل زیر را انجام می‌دهد: - اگر F ریشه بیشتر از مقدار آستانه تعیین شدهٔ F باشد از لیست now حذف می‌شود و به انتهای لیست later الحاق شود به عبارتی ریشه را برای اشارهٔ بعدی نگه می‌داریم - اگر F برابر یا کمتر از آستانه بود، ریشه را حذف کرده و فرزندان آن را به ابتدای لیست now اضافه می‌کنیم در انتهای یک پیمایش اشاره‌گر مقدار آستانه F افزایش یافت، لیست now برابر با later و لیست later خالی می‌شود. یک تفاوت اصلی بین فرینگ و A* این است که در الگوریتم فرینگ محتوای لیست لزوماً چیده شده و به ترتیب نیستند. بر خلاف A* الگوریتم فرینج باید همان گره‌های قبلی را مجدداً رویت کند، اما هزینهٔ هر یک از این دیدارها مرتباً با بدترین حالت لگاریتمی زمان مرتب‌سازی لیست در A* مقایسه می‌شود.

شبه کد[ویرایش]

دو لیست now و later را در یک لیست دو پیوندی اجرا می‌کنیم، به طوریکه گره‌های قبل از گره فعلی مربوط به later و بقیه مربوط به now هستند. استفاده از یک آرایهٔ گره‌های از پیش اختصاص داده شده برای لیست، برای هر گره درصف، زمان دسترسی به هر گره را در الگوریتم مرتباً کاهش می‌دهد. 

init(start, goal)
    fringe F = s
    cache C[start] = (0, null)
    flimit = h(start)
    found = false

    while (found == false) AND (F not empty)
        fmin = ∞
        for node in F, from left to right
            (g, parent) = C[node]
            f = g + h(node)
            if f > flimit
                fmin = min(f, fmin)
                continue
            if node == goal
                found = true
                break
            for child in children(node), from right to left
                g_child = g + cost(node, child)
                if C[child] != null
                    (g_cached, parent) = C[child]
                    if g_child >= g_cached
                        continue
                if child in F
                    remove child from F
                insert child in F past node
                C[child] = (g_child, node)
            remove node from F
        flimit = fmin

    if reachedgoal == true
        reverse_path(goal)

Reverse pseudo-code. 

reverse_path(node)
    (g, parent) = C[node]
    if parent != null
        reverse_path(parent)
    print node

جستارهای وابسته[ویرایش]

منابع[ویرایش]

برگرفته از «https://fa.wikipedia.org/w/index.php?title=جستجو_فرینگ&oldid=34934183»