مشكلة ديناميكية (خوارزميات)

في علوم الحاسوب ، تُعرَّف المشكلات الديناميكية بأنها المشكلات التي تُصاغ بدلالة بيانات الإدخال المتغيرة. وفي أبسط صورها، تُصاغ المشكلة في هذه الفئة عادةً على النحو التالي:

بالنظر إلى بنية تتكون من كائنات، ابحث عن خوارزميات وهياكل بيانات فعالة للإجابة على استعلامات معينة حول البنية، مع دعم عمليات التحديث بكفاءة مثل إدراج أو حذف أو تعديل الكائنات في البنية.

تتضمن المسائل في هذه الفئة مقاييس التعقيد التالية:

المساحة - مقدار مساحة الذاكرة المطلوبة لتخزين بنية البيانات؛
وقت التهيئة - الوقت اللازم للإنشاء الأولي لهيكل البيانات؛
وقت الإدخال – الوقت اللازم لتحديث بنية البيانات عند إضافة عنصر إدخال آخر؛
وقت الحذف – الوقت اللازم لتحديث بنية البيانات عند حذف عنصر إدخال؛
وقت الاستعلام – الوقت اللازم للإجابة على الاستعلام؛
عمليات أخرى خاصة بالمشكلة المطروحة

تُسمى المجموعة الكاملة من العمليات الحسابية لمسألة ديناميكية بالخوارزمية الديناميكية .

العديد من المشكلات الخوارزمية التي يتم طرحها من حيث بيانات الإدخال الثابتة (تسمى المشكلات الثابتة في هذا السياق ويتم حلها بواسطة الخوارزميات الثابتة ) لها إصدارات ديناميكية ذات معنى.

حالات خاصة

الخوارزميات التزايدية ، أو الخوارزميات عبر الإنترنت ، هي خوارزميات لا يُسمح فيها إلا بإضافة العناصر، وربما تبدأ من بيانات إدخال فارغة/تافهة.

الخوارزميات التناقصية هي خوارزميات لا يُسمح فيها إلا بحذف العناصر، بدءًا من تهيئة بنية بيانات كاملة.

إذا سُمح بكل من الإضافات والحذف، فإن الخوارزمية تسمى أحيانًا بالديناميكية الكاملة .

أمثلة

العنصر الأقصى

مشكلة ثابتة: بالنسبة لمجموعة من N عدد، أوجد العدد الأقصى.

يمكن حل المشكلة في زمن O( N ).

مشكلة ديناميكية: بالنسبة لمجموعة أولية من N رقم، يتم الحفاظ ديناميكيًا على الرقم الأقصى عند السماح بالإدخالات والحذف.

هذه مجرد مشكلة صيانة قائمة الانتظار ذات الأولوية، والتي تسمح بعمليات الإضافة والحذف؛ ويمكن حلها، على سبيل المثال، باستخدام كومة ثنائية في $O(\log N)$ حان وقت التحديث و $O(1)$ حان وقت الاستفسار، مع $O(N)$ وقت الإعداد (أي المعالجة الأولية للبيانات). لاحظ أن قيمة N قد تتغير خلال عمر الهيكل.

الرسوم البيانية

بالنظر إلى رسم بياني، حافظ على معاييره، مثل الاتصال، والدرجة القصوى، وأقصر المسارات، وما إلى ذلك، عندما يُسمح بإضافة وحذف حوافه. ^{[ 1 ]}

أمثلة:

توجد خوارزمية تحافظ على الحد الأدنى للغابة الممتدة في رسم بياني غير موجه وموزون، مع مراعاة حذف الحواف وإدراجها، في $O(n^{1/2})$ الوقت لكل تحديث. ^{[ 2 ]}
توجد خوارزمية تحافظ على الحد الأدنى للغابة الممتدة في رسم بياني غير موجه وموزون، مع مراعاة حذف الحواف وإدراجها، في $O(n^{1/3}\log n)$ الوقت المستهلك لكل تحديث. ^{[ 3 ]}

انظر أيضاً

مراجع

↑ د. إبستين ، ز. جليل ، و ج. ف. إيتاليانو . "خوارزميات الرسوم البيانية الديناميكية". في كتاب CRC Handbook of Algorithms and Theory of Computation ، الفصل 22. مطبعة CRC، 1997.
↑ إبستين، ديفيد؛ إيتاليانو، جوزيبي؛ نيسنزويغ، أمنون (1997). "التخفيف - تقنية لتسريع خوارزميات الرسوم البيانية الديناميكية". مجلة ACM . 44 (5): 669-696 . doi : 10.1145/265910.265914 .
↑ هينزينجر، مونيكا؛ كينج، فاليري (2001). "الحفاظ على الغابات الممتدة الدنيا في الرسوم البيانية الديناميكية" . مجلة SIAM للحوسبة . 31 (2): 364-374 . doi : 10.1137/S0097539797327209 .

[1] د. إبستين ، ز. جليل ، و ج. ف. إيتاليانو . "خوارزميات الرسوم البيانية الديناميكية". في كتاب CRC Handbook of Algorithms and Theory of Computation ، الفصل 22. مطبعة CRC، 1997.

[sparsification-2] إبستين، ديفيد؛ إيتاليانو، جوزيبي؛ نيسنزويغ، أمنون (1997). "التخفيف - تقنية لتسريع خوارزميات الرسوم البيانية الديناميكية". مجلة ACM . 44 (5): 669-696 . doi : 10.1145/265910.265914 .

[HK2001-3] هينزينجر، مونيكا؛ كينج، فاليري (2001). "الحفاظ على الغابات الممتدة الدنيا في الرسوم البيانية الديناميكية" . مجلة SIAM للحوسبة . 31 (2): 364-374 . doi : 10.1137/S0097539797327209 .

[ 1 ]

[ 2 ]

[ 3 ]