جستجو فرینگ

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

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

*ƒ*(*x*)&nbsp;=&nbsp;*g*(*x*)&nbsp;+&nbsp;*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* هستند. استفاده از یک آرایهٔ گره‌های از پیش اختصاص داده شده برای لیست، برای هر گره درصف، زمان دسترسی به هر گره را در الگوریتم مرتباً کاهش می‌دهد.


```cpp
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.

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


## جستارهای وابسته
* هوش مصنوعی
* طراحی الگوریتم

## منابع
* Björnsson, Yngvi; Enzenberger, Markus; Holte, Robert C. ; Schaeffer, Johnathan. Fringe Search: Beating A* at Pathfinding on Game Maps. Proceedings of the 2005 IEEE Symposium on Computational Intelligence and Games (CIG05). Essex University, Colchester, Essex, UK, 4&ndash;6 April, 2005. IEEE 2005. https://web.archive.org/web/20090219220415/http://www.cs.ualberta.ca/~games/pathfind/publications/cig2005.pdf
* https://en.wikipedia.org/wiki/Fringe_search
رده:الگوریتم‌های گراف
رده:الگوریتم‌های جستجو