هذه المقالة يتيمة. ساعد بإضافة وصلة إليها في مقالة متعلقة بها
يفتقر محتوى هذه المقالة إلى مصادر موثوقة.

محاكاة بارنز هت

من أرابيكا، الموسوعة الحرة
اذهب إلى التنقل اذهب إلى البحث
محاكاة 100جسم بشجرة بارنز هت ممثلة في صورة مربعات زرقاء

محاكاة بارنز هت (جوش بارنز (Josh Barnes) وبيت هات (Piet Hut)) هي خوارزمية لتنفيذ محاكاة جسم n. ويشهر استخدامها في الحصول على تمثيل (On log n) مقارنة بخوارزمية الجمع المباشر الذي قد يكون (O n2).

عادة ما يقسم حجم المحاكاة إلى خلايا مكعبة عبر التكميم (فراغ ثلاثي الأبعاد)، ولذلك يتعين معالجة أجسام فقط من الخلايا المجاورة بشكل منفرد، والأجسام الموجودة في الخلايا البعيدة من الممكن معالجتها كأجسام ضخمة مفردة موجودة في محور ثقل الخلية (أو أمر أقل التمديد المتعدد). وذلك قد يقلل إلى حد كبير عدد أجسام التفاعلات الثنائية التي يجب حسابها.

الخوارزمية

شجرة بارنز هت

في محاكاة جسمn، تقسم خوارزمية بارنز هت بشكل تكراري إلى أجسام n إلى مجموعات من خلال تخزينها في شجرة رباعية. وتمثل كل عقدة في هذه الشجرة منطقة من مساحة ثنائية الأبعاد. تمثل العقدة العليا المساحة بأكملها، وتوابعها الأربعة أرباع الدائرة الأربعة للمساحة ومن الممكن تقسيم كل ربع دائرة مرة أخرى إلى أربعة أرباع دائرة. تقسم المساحة بشكل مطرد إلى أربعة دوائر حتى يحتوي كل تقسيم فرعي على 0 أو 1 جسم (بعض المناطق لا يوجد بها أجسام في كل أرباع الدائرة بها). هناك نوعان من أنواع العقد في الربع الثالث: العقد الداخلية والخارجية. أما العقدة الداخلية فلا يوجد لها توابع وإما أن تكون فارغة أو تمثل جسمًا واحدًا. وتمثل كل عقدة داخلية مجموعة الأجسام خلفها وتقوم بتخزين مركز الثقل والثقل الكلي لجميع الأجسام التابعة.

حساب القوة الفاعلة في جسم

لحساب القوة الكلية في جسم معين، فإن رؤوس الشجرة تعبر بداية من الجذر. في مركز كتلة رأس داخلي بعيدة بشكل كافٍ عن الجسم، تُعامل الأجسام الموجودة في هذا الجزء من الشجرة كجسم فردي، والتي يكون موضعها وكتلتها في مركز الكتلة والكتلة الكلية للرأس الداخلي على التوالي. وإذا لم تكن الرأس الداخلية بعيدة بشكل كافي عن الجسم، فإن العملية تُكرر لكل طفل من أطفالها.

سواء أكانت العقدة بعيدة أو غير بعيدة بشكل كافٍ عن الجسم، وذلك يعتمد على حاصل القسمة s / d، حيث s هي عرض المنطقة الممثلة بالرأس الداخلي، وd هي المسافة بين الجسم ومركز كتلة الرأس. وتكون الرأس بعيد بشكل كافي عن الجسم عندما تكون هذه النسبة أقل من قيمة القيمة العتبية θ. وتحدد القيمة الوسطية θ دقة المحاكاة؛ القيم الأكبر لـθ تزيد سرعة المحاكاة لكن تقلل من الدقة. إذا كانت θ = 0، لا يتم معالجة أي رؤوس داخلية على أنها أجسام فردية وتنحل الخوارزمية إلى خوارزمية الجمع المباشر.

مراجع