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

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

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

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

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

الخوارزمية[عدل]

شجرة بارنز هت[عدل]

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

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

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

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

انظر أيضًا[عدل]

  • 'محاكاة جسم n
  • الطرق متعددة الأقطاب

المراجع[عدل]

  • J. Barnes and P. Hut (December 1986). "A hierarchical O(N log N) force-calculation algorithm". Nature 324 (4): 446–449. doi:10.1038/324446a0. 
  • J. Dubinski (October 1996). "A Parallel Tree Code". New Astronomy 1 (2): 133–147. doi:10.1016/S1384-1076(96)00009-7. أرشيف خي:astro-ph/9603097v1. 
  • U. Becciani, R. Ansalonib, V. Antonuccio-Delogua, G. Erbaccic, M. Gamberaa, and A. Pagliarod (October 1997). "A parallel tree code for large N-body simulation: dynamic load balance and data distribution on a CRAY T3D system". Computer Physics Communications 106 (1–2): 105–113. doi:10.1016/S0010-4655(97)00102-1. 
  • T. Ventimiglia, and K. Wayne. "The Barnes-Hut Algorithm". اطلع عليه بتاريخ 30 March 2012. 

وصلات خارجية[عدل]