محاكاة بارنز هت (جوش بارنز (Josh Barnes) وبيت هات (Piet Hut)) هي خوارزمية لتنفيذ محاكاة جسم n.[1] ويشهر استخدامها في الحصول على تمثيل (On log n) مقارنة بخوارزمية الجمع المباشر الذي قد يكون (O n2).
عادة ما يقسم حجم المحاكاة إلى خلايا مكعبة عبر التكميم (فراغ ثلاثي الأبعاد)، ولذلك يتعين معالجة أجسام فقط من الخلايا المجاورة بشكل منفرد، والأجسام الموجودة في الخلايا البعيدة من الممكن معالجتها كأجسام ضخمة مفردة موجودة في محور ثقل الخلية (أو أمر أقل التمديد المتعدد). وذلك قد يقلل إلى حد كبير عدد أجسام التفاعلات الثنائية التي يجب حسابها.
الخوارزمية
شجرة بارنز هت
في محاكاة جسمn، تقسم خوارزمية بارنز هت بشكل تكراري إلى أجسام n إلى مجموعات من خلال تخزينها في شجرة رباعية. وتمثل كل عقدة في هذه الشجرة منطقة من مساحة ثنائية الأبعاد. تمثل العقدة العليا المساحة بأكملها، وتوابعها الأربعة أرباع الدائرة الأربعة للمساحة ومن الممكن تقسيم كل ربع دائرة مرة أخرى إلى أربعة أرباع دائرة. تقسم المساحة بشكل مطرد إلى أربعة دوائر حتى يحتوي كل تقسيم فرعي على 0 أو 1 جسم (بعض المناطق لا يوجد بها أجسام في كل أرباع الدائرة بها). هناك نوعان من أنواع العقد في الربع الثالث: العقد الداخلية والخارجية. أما العقدة الداخلية فلا يوجد لها توابع وإما أن تكون فارغة أو تمثل جسمًا واحدًا. وتمثل كل عقدة داخلية مجموعة الأجسام خلفها وتقوم بتخزين مركز الثقل والثقل الكلي لجميع الأجسام التابعة.
توزيع الأجسام يشبه مجرتين متجاورتين.
شجرة بارنز هت كاملة. (العقد التي لا تحتوي على جسيمات غير مرسومة)
رؤوس شجرة بارنز -هت مستخدمة لحساب القوة الفاعلة في جسيم في نقطة الأصل.
حساب القوة الفاعلة في جسم
لحساب القوة الكلية في جسم معين، فإن رؤوس الشجرة تعبر بداية من الجذر. في مركز كتلة رأس داخلي بعيدة بشكل كافٍ عن الجسم، تُعامل الأجسام الموجودة في هذا الجزء من الشجرة كجسم فردي، والتي يكون موضعها وكتلتها في مركز الكتلة والكتلة الكلية للرأس الداخلي على التوالي. وإذا لم تكن الرأس الداخلية بعيدة بشكل كافي عن الجسم، فإن العملية تُكرر لكل طفل من أطفالها.
سواء أكانت العقدة بعيدة أو غير بعيدة بشكل كافٍ عن الجسم، وذلك يعتمد على حاصل القسمة s / d، حيث s هي عرض المنطقة الممثلة بالرأس الداخلي، وd هي المسافة بين الجسم ومركز كتلة الرأس. وتكون الرأس بعيد بشكل كافي عن الجسم عندما تكون هذه النسبة أقل من قيمة القيمة العتبية θ. وتحدد القيمة الوسطية θ دقة المحاكاة؛ القيم الأكبر لـθ تزيد سرعة المحاكاة لكن تقلل من الدقة. إذا كانت θ = 0، لا يتم معالجة أي رؤوس داخلية على أنها أجسام فردية وتنحل الخوارزمية إلى خوارزمية الجمع المباشر.
مراجع
- "معلومات عن محاكاة بارنز هت على موقع academic.microsoft.com". academic.microsoft.com. مؤرشف من الأصل في 7 أبريل 2020.