خوارزمية دقيقة لمشكلة شجرة ستاينر المستوية k

مشكلة شجرة ستاينر المستوية k تسأل عن شبكة بتكلفة دنيا تربط بين n نقطة معينة في المستوى، مع السماح بحد أقصى k من العقد الإضافية المعروفة بنقاط ستاينر. في مشكلة شجرة ستاينر الكلاسيكية، حيث لا توجد قيود على عدد العقد، يجب أن تكون كل نقطة ستاينر من الدرجة 3. تختلف مشكلة الكي-ستاينر في أن نقاط ستاينر من الدرجة 4 قد تُدرج في حل أمثل. يؤدي هذا التغيير البسيط إلى عدد من التعقيدات عند محاولة إنشاء خوارزمية توليد لشجرات الكي-ستاينر المثلى، والتي أثبتت أنها عنصر فعال في الخوارزمية الرائدة، وهي GeoSteiner، لحل مشكلة شجرة ستاينر الكلاسيكية. في الورقة الحالية، نقوم أولاً بتمديد الإطار الأساسي لخوارزمية توليد GeoSteiner لتضمين نقاط ستاينر من الدرجة 4. ثم نقدم عددًا من النتائج الجديدة التي تقيد الخصائص الهيكلية والهندسية لشجرات الكي-ستاينر المثلى، ثم نوضح كيف يمكن استخدام هذه الخصائص كطرق تقليم طوبولوجية تدعم خوارزمية التوليد لدينا. أخيرًا، نقدم بيانات تجريبية لإظهار فعالية طرق التقليم لدينا في تقليل عدد طوبولوجيات الحلول دون الأمثل.