منتدي لمناقشه الموضوعات الجامعيه.


    بحث ثنائي موسع

    شاطر

    Admin
    المدير العام
    المدير العام

    المساهمات : 81
    تاريخ التسجيل : 13/04/2010

    بحث ثنائي موسع

    مُساهمة  Admin في الثلاثاء أبريل 13, 2010 10:05 am

    [size=29] شبكة الخوارزمي
    [/size]
    [size=16]مدخل سريع لخوارزميات البحث و الترتيب المختلفة
    [/size]
    [size=16]مقدمة[/size]:
    من بنى المعطيات الأساسية التي ُتستخدم لتخزين المعلومات. و من likned lists و القوائم المرتبطة Arrays المصفوفات
    العمليات الأساسية على بنى المعطيات هذه، البحث عن قيمة محددة من بين القيم المخزنة ضمن هذه البنى.
    سنتحدث فيما يلي عن الطرق المختلفة المستخدمة لإجراء عملية البحث هذه.
    :Arrays -1 المصفوفات
    لنأخذ على سبيل المثال مصفوفة رقمية مكونة من سبعة عناصر. المشكلة المطروحة إيجاد عنصر محدد في هذه المصفوفة.
    أسهل طرق البحث ُتدعى "ا
    لبحث التسلسلي". و الموضحة بالخوارزمية التالية.
    int function
    SequentialSearch ( Array A, int Lb, int Ub, int Key) ;
    begin
    for
    i = Lb to Ub do
    if
    A[i] =Key then
    return
    i ;
    returen
    - /*العنصر المطلوب غير موجود*/ ; 1
    end;
    إذا كان العنصر المراد البحث عنه موجود في آخر المصفوفة أو إذا كان العنصر غير موجود في المصفوفة نحتاج في هذه
    يساوي إلى عدد عناصر المصفوفة و هذه هي أسوء حالة (if
    A[i] =Key then) الحالة إلى عدد من عمليات المقارنة
    ممكنة. أما الحالة الأحسن فتكون إذا كان العنصر المطلوب في أول المصفوفة حيث يتم العثور عليه بعد عملية مقارنة واحدة
    فقط. طبعَا عدد عمليات المقارنة يعبر عن زمن أو سرعة تنفيذ هذه الخوارزمية.
    إذا كانت عناصر المصفوفة مرتبة تسلسليًا فيمكن إستخدام خوارزمية
    البحث الثنائي و التي يمكن تلخيصها على الشكل
    التالي:
    فإذا كان العنصر ( M=Array length/ نبدأ بفحص العنصر الموجود في منتصف المصفوفة ( أي العنصر ذو الترتيب 2
    المطلوب إيجاده أصغر من العنصر الموجود في الوسط (و على إعتبار أن المصفوفة مرتبة تصاعديًا أي من العنصر الأصغر
    للعنصر الأكبر) فهذا يعني أن العنصر المطلوب موجود في النصف الأعلى من المصفوفة الأصلية. و بالتالي يتم البحث عن
    العنصر المطلوب في القسم العلوي من المصفوفة و ينقص عدد العناصر المطلوب فحصها بمقدار النصف.
    يمكننا أن نتصور الآن أن المشكلة أصبحت إيجاد العنصر المطلوب في مصفوفة مرتبة تصاعديًا ُتشكل مصفوفة جزئية من
    المصفوفة الأصلية (النصف العلوي أو السفلي فقط). و يتم تكرار نفس العملية السابقة على المصفوفة الجزئية الجديدة و
    هكذا حتى الوصول للعنصر المطلوب.
    int function BinarySearch (Array A, int Lb, int Ub, int Key);
    begin
    do forever
    M=(Lb+Ub)/ /*تحديد ترتيب العنصر المتوسط */ ; 2
    if (key< A[M]) then
    Ub = M- تحديد الحد الأعلى */ ; 1
    /* للمصفوفة الجديدة
    else if (Key > A[M]) then
    Lb=M+ تحديد الحد الأدنى للمصفوفة */ ; 1
    /* الجديدة
    else
    return M; /* /* العنصر موجود
    if (Lb > Ub) then
    return - /* العنصر غير موجود */ ; 1
    end;
    لنفترض أنه لدينا مصفوفة من 1023 عنصر بعد عملية المقارنة الأولى يتم تضييق نطاق البحث ليشمل 511 عنصر فقط و
    في عملية المقارنة الثانية يصبح لدينا 255 عنصر فقط و هكذا. و بالتالي نحتاج إلى عشر عمليات مقارنة فقط لفحص كامل
    المصفوفة و هذا أفضل بكثير من عملية البحث التسلسلي التي تحتاج في هذه الحالة إلى 1023 عملية مقارنة (
    لاحظ الفرق
    الكبير في عدد عمليات المقارنة
    ) .
    بالطبع عند استخدام خوارزمية البحث الثنائي تبرز مشكلة جديدة هي مشكلة ترتيب العناصر تصاعديًا أو تنازليًا. و عند حذف
    أو إضافة عنصر جديد لابد من إعادة ترتيب المصفوفة من جديد.
    كبنى معطيات ف  عالة تتمتع ببعض المرونة التي تسمح بحذف أو إضافة عناصر linked lists هنا تبرز القوائم المتسلسلة
    جديدة.
    ( Linked list ) -2 القوائم المرتبطة
    على عكس المصفوفات فإننا لا نحتاج لمعرفة عدد العناصر المراد تخزينها في القوائم المرتبطة لأن هذه القوائم تمتاز
    بقدرتها على التوسع الغير محدود (و بشكل أدق التوسع بما تسمح به ذاكرة الحاسب المستخدم)
    كل عنصر من القائمة يحوي قيمتين ( و في القوائم الأكثر تعقيدًا تستخدم ثلاث قيم) القيمة الأولى تمثل المعلومات المراد
    المستخدم في لغة Structure المستخدم في لغة باسكال او البنية Record تخزينها و التي قد تكون بنية معقدة مثل السجل
    كما هو Pointer القيمة الثانية تحوي رقم الذاكرة المستخدمة في تخزين العنصر التالي هذه القيمة عادة تدعى مؤشر C
    موضح في الشكل التالي:
    كمؤشر على إنتهاء NULL من المهم ملاحظة أن العنصر الأخير في القائمة لا يشير إلى أي موقع و إنما يحوي القيمة
    القائمة
    هناك العديد من المهام الأساسية التي يجب القيام بها على القوائم المرتبطة هذه العمليات تشمل:
    أ- إضافة عنصر جديد
    يتم ذلك كما يلي P بعد العنصر المخزن في الموقع X على افتراض اننا نريد اضافة عنصر مخزن في الموقع
    X- > next = P - > next;
    P - > next = X;
    ب- حذف عنصر
    سنترك هذه العملية كتدريب للأخ القارئ
    ج- ترتيب القائمة
    ترتيب القائمة يتم عن طريق اجراء مسح تسلسلي على عناصر القائمة حتى يتم العثور على الموقع المناسب و هذا بالطبع
    يتم على حساب الوقت
    كما لاحظنا فإن خوارزميات البحث تعتمد على كون المعلومات مخزنة بشكل مرتب لذلك سنورد الآن بإيجاز الخوارزميات

    المستخدمة لترتيب المعطيات.

      الوقت/التاريخ الآن هو الأربعاء أكتوبر 18, 2017 5:40 pm