مقاله ، تحقیق ، پروژه ، پایان نامه

جستجوی دوجهته

الگوریتم جستجوی دو جهته الگوریتمی برای جستجوی گراف است که کوتاهترین مسیر در یک گراف جهت دار را از راس اولیه به راس هدف می یابد.

پیچیدگی:

این الگوریتم دو جستجوی همزمان ر اجرا می کند: یکی جلورونده از راس اولیه ، و یکی عقب رونده از راس هدف، توقف هنگامی صورت می گیرد که دو جستجو در میان راه یکدیگر را ملاقات کنند. دلیل برای این رویکرد این است که در بسیاری از موارد بسیار سریع تر است: به عنوان مثال، در یک مدل ساده از مساله ی پیچیدگی جستجو که در آن هر دو جستجوها یک درخت با ضریب انشعاب B گسترش پیدا می کنند، و فاصله از راس اولیه به راس هدف d می باشد، هر یک از دو جستجو دارای پیچیدگی O (b^{d/2})  (در نماد O بزرگ) می باشند ، و مجموع پیجیدگی این دو جستجو بسیار کمتر از پیچیدگی O (b^d)  می باشد که پیچیدگی یک جستجوی تنها از همان راس ابتدا به راس هدف است.

معایب:

این تسریع در امر پاسخگویی با دادن یک هزینه همراه است: یک الگوریتم جستجوی دو جهته باید شامل منطق اضافی باشد تا تصمیم بگیرد که در هر مرحله ی جستجو کدام درخت جستجو گسترش یابد، مشکلات پیاده سازی افزایش می یابد، راس هدف باید شناخته شده باشد (به جای داشتن یک هدف کلی که ممکن است توسط بسیاری از حالات ملاقات شود) ، الگوریتم باید قادر به بازگشتن از راس هدف به راس اولیه باشد (که بدون کار اضافی ممکن نیست)، و الگوریتم نیاز به یک راه موثر برای پیدا کردن محل تقاطع دو درخت جستجو دارد. علاوه بر این، ضریب انشعاب جستجوی عقب رونده ممکن است با جستجوی جلو رونده متفاوت باشد. پیچیدگی اضافی برای انجام یک جستجوی دو جهته بدان معنی است که یک الگوریتم جستجوی A* اغلب یک انتخاب بهتر است اگر تابع شهودی ما (هیورستیک) یک تابع منطقی باشد.

ویژگی ها:

همانند جستجوی A* ، جستجوی دو جهته می تواند با برآورد اکتشافی از فاصله باقی‌مانده تا راس هدف (در درخت جلورنده) و یا ازراس اولیه (در درخت عقب رونده) هدایت شود.یک اکتشاف قابل قبول همچنین می تواند کوتاه ترین راه حل را به دست آورد، همان طور که برای A* به اثبات رسیده است.

گره ای که از جلو در حال گسترش است دارای کمترین تعداد گره ی باز و محتمل ترین گره است. پایان اگوریتم زمانی اتفاق می افتد که یک گره در گروه دیگر هم باشد. ارزش F - فرزندان گره را باید در ارزش G – همه ی گره ها در گروه دیگرحساب شود. از این رو گسترش گره در این روش از A* پر هزینه تر است. همان طور که در بالا ذکر شد می توان الگوریتم را به گونه ای هدایت کرد که مجموعه ی گره های ملاقات شده کوچکتر شود. بنابراین می توانیم در فضای کمتری محاسبه ی بیشتری انجام دهیم. مرجع 1977 نشان می دهد که الگوریتم دو جهته پاسخ را می یابد در حالی که الگوریتم A* از فضای داده شده، فضای بیشتری را اشغال می کند. همچنین مسیرهای کوتاه تری نیز پیدا می شوند اگر از تابع های شهودی غیر منطقی استفاده شود. این تست ها توسط Ira Pohl در 15-پازل انجام گرفته است.

Ira Pohl اولین کسی بود که یک الگوریتم جستجوی دو طرفه ی هیورستیک را طراحی و پیاده سازی کرد. در این پیاده سازی یک گره ی فرزند در یک مرز جستجو فقط به گره ها در گروه دیگر مرتبط است. او گزارش کرد که دو درختی که از هر یک از جستجو ها تشکیل می شود در فضای میانی همدیگر را ملاقات نکردند. بعدها او و یکی از شاگردانش به نام George Politowski الگوریتم او را با گرفتن D  - گره به عنوان واسطه ی طبیعی اصلاح کردند.

پياده سازي ليست پيوندي دو طرفه به زبان C++

--------------------------------------------------------------------------------

// dLinkList.cpp: implementation of the dLinkList class.

//

//////////////////////////////////////////////////////////////////////

#include "dLinkList.h"

#include

#include

//////////////////////////////////////////////////////////////////////

// Construction/Destruction

//////////////////////////////////////////////////////////////////////

dLinkList::dLinkList()

{

   Front = NULL;

   Rear = Front;

   Count = 0;

}

dLinkList::~dLinkList()

{

  NodePtr current, temp;

   current = Front;

   while (current != NULL)

      {

      temp = current;

      current = current->Right;

      delete temp;

      }

   Front = NULL;

   Rear = Front;

   Count = 0;

}

/*+++++++++++++++++++++++++++++++++++++++++++++++++++*/

/*                           InsertFirst                                */

/* Task:   To insert a new node containing Item at the front of the list*/

/* Given:  Item:  A data item                   */

/* Return: Nothing       */

/*+++++++++++++++++++++++++++++++++++++++++++++++++++++*/

void dLinkList::InsertFirst(char item)

   {

   NodePtr current;

   current = new Node;

   if (current == NULL)

      {

      cerr << "Memory allocation error!" << endl;

      exit(1);

      }

   current->Right = Front;

   current->Left  = NULL;

   current->Info  = item;

   Front = current;

   if (Count == 0)

      Rear = current;

   else

      Front->Left = current;

   Count++;

   }

/*+++++++++++++++++++++++++++++++++++++++++++++++*/

/*                           InsertLast                                 */

/* Task:   To insert Item into a new node added to the rear of the list.*/

/* Given:  Item   A data item                   */

/* Return: Nothing       */

/*++++++++++++++++++++++++++++++++++++++++++++++++++*/

void dLinkList::InsertLast(char item)

   {

    NodePtr current;

   current = new Node;

   if (current == NULL)

      {

      cerr << "Memory allocation error!" << endl;

      exit(1);

      }

   current->Right = NULL;

   current->Left  = Rear;

   current->Info  = item;

   if (Count == 0)

      Front = current;

   else

      Rear->Right = current;

   Rear = current;

   Count++;

   }

/*++++++++++++++++++++++++++++++++++++++++++++++++++*/

/*                           RemoveFirst                                */

/* Task:   To remove first node from the list.                          */

/* Given:  Nothing                              */

/* Return: Data item that removed from the list    */

/*++++++++++++++++++++++++++++++++++++++++++++++++++++*/

void dLinkList::RemoveFirst(char &item)

   {

   NodePtr current;

   if (Count == 0)

      {

      cerr << "ERROR: there is no item to remove in the list!" << endl;

      exit(1);

      }

   current = Front;

   item = current->Info;

   Front = current->Right;

   Front->Left = NULL;

   Count--;

   if (Count == 0)

      Rear = Front;

   delete current;

   }

/*++++++++++++++++++++++++++++++++++++++++++++++++*/

/*                           ShowList                                   */

/* Task:   Show all data item of the list.                         */

/* Given:  Nothing        */

/* Return: Nothing                         */

/*+++++++++++++++++++++++++++++++++++++++++++++++++++*/

void dLinkList::ShowFirstToLast(void)

   {

   NodePtr current;

   current = Front;

   while (current != NULL)

      {

      cout<< current->Info<      current = current->Right;

      }

   }

منابع:

de Champeaux, Dennis; Sint, Lenie (1977), "An improved bidirectional heuristic search algorithm", Journal of the ACM 24 (2): 177–191, DOI:10.1145/322003.322004 .

de Champeaux, Dennis (1983), "Bidirectional heuristic search again", Journal of the ACM 30 (1): 22–32, DOI:10.1145/322358.322360 .

Pohl, Ira (1971), "Bi-directional Search", in Meltzer, Bernard; Michie, Donald, Machine Intelligence, 6, Edinburgh University Press, pp. 127–140 .

Russell, Stuart J.; Norvig, Peter (2002), "3.4 Uninformed search strategies", Artificial Intelligence: A Modern Approach (2nd ed.), Prentice Hall .