خوارزمية خريطة الفرق

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

على الرغم من أن خوارزمية خريطة الفرق صُممت في الأصل كطريقة عامة لحل مشكلة الطور ، فقد استُخدمت في حل مشكلة الإرضاء البولياني ، والتنبؤ ببنية البروتين ، وأعداد رامزي ، والمعادلات الديوفانتية ، ولعبة سودوكو ، ^{[ 1 ]} بالإضافة إلى مشاكل تعبئة الكرات والأقراص. ^{[ 2 ]} ولأن هذه التطبيقات تشمل مسائل NP-كاملة ، فإن نطاق خريطة الفرق هو نطاق خوارزمية غير كاملة . في حين أن الخوارزميات غير الكاملة يمكنها التحقق بكفاءة من الحلول (بمجرد العثور على حل مرشح)، إلا أنها لا تستطيع إثبات عدم وجود حل.

تُعدّ خوارزمية خريطة الفرق تعميمًا لطريقتين تكراريتين : خوارزمية فينوب الهجينة للإدخال والإخراج (HIO) لاسترجاع الطور ^{[ 3 ]} ، وخوارزمية دوغلاس-راشفورد ^{[ 4 ]} للتحسين المحدب . وللطرق التكرارية، عمومًا، تاريخ طويل في استرجاع الطور والتحسين المحدب. أما استخدام هذا النمط من الخوارزميات للمسائل الصعبة غير المحدبة فهو تطور حديث نسبيًا.

يجب أولاً صياغة المشكلة المراد حلها كمشكلة تقاطع مجموعات في الفضاء الإقليدي: إيجاد${\displaystyle x}$في تقاطع المجموعات${\displaystyle A}$و${\displaystyle B}$ومن المتطلبات الأساسية الأخرى تنفيذ عمليات الإسقاط.${\displaystyle P_{A}}$و${\displaystyle P_{B}}$أنه، بالنظر إلى نقطة إدخال عشوائية${\displaystyle x}$، أعد نقطة في مجموعة القيود${\displaystyle A}$أو${\displaystyle B}$الأقرب إلى${\displaystyle x}$تُعطى إحدى دورات الخوارزمية بواسطة عملية الربط التالية:

${\displaystyle {\begin{aligned}x\mapsto D(x)&=x+\beta \left[P_{A}\left(f_{B}(x)\right)-P_{B}\left(f_{A}(x)\right)\right],\\f_{A}(x)&=P_{A}(x)-{\frac {1}{\beta }}\left(P_{A}(x)-x\right),\\f_{B}(x)&=P_{B}(x)+{\frac {1}{\beta }}\left(P_{B}(x)-x\right)\end{aligned}}}$

المعلمة الحقيقية${\displaystyle \beta }$لا ينبغي أن تساوي القيمة صفرًا، ولكن يمكن أن تأخذ أيًا من الإشارتين؛ وتعتمد القيم المثلى على التطبيق ويتم تحديدها من خلال التجربة. كتخمين أولي، فإن الاختيار${\displaystyle \beta =1}$(أو${\displaystyle \beta =-1}$يُوصى باستخدام ) لأنه يقلل من عدد عمليات حساب الإسقاط لكل تكرار:

${\displaystyle D(x)=x+P_{A}\left(2P_{B}(x)-x\right)-P_{B}(x)}$

نقطة ${\displaystyle x}$هي نقطة ثابتة على الخريطة${\displaystyle x\mapsto D(x)}$متى بالضبط${\displaystyle P_{A}\left(f_{B}(x)\right)=P_{B}\left(f_{A}(x)\right)}$بما أن الجانب الأيسر هو عنصر من${\displaystyle A}$والجانب الأيمن هو عنصر من${\displaystyle B}$، تشير المساواة إلى أننا وجدنا عنصرًا مشتركًا بين مجموعتي القيود. لاحظ أن النقطة الثابتة${\displaystyle x}$لا يشترط أن تنتمي هي نفسها إلى أي منهما${\displaystyle A}$أو${\displaystyle B}$. عادةً ما يكون لمجموعة النقاط الثابتة أبعاد أعلى بكثير من مجموعة الحلول.

يمكن مراقبة تقدم الخوارزمية من خلال فحص معيار الفرق بين الإسقاطين:

${\displaystyle \Delta =\left|P_{A}\left(f_{B}(x)\right)-P_{B}\left(f_{A}(x)\right)\right|}$.

عندما يختفي هذا، يتم العثور على نقطة مشتركة بين مجموعتي القيود ويمكن إنهاء الخوارزمية.

تُستخدم الخوارزميات غير الكاملة، مثل البحث المحلي العشوائي ، على نطاق واسع لإيجاد قيم منطقية مُرضية للصيغ المنطقية. كمثال على حل مسألة 2-SAT باستخدام خوارزمية خريطة الفرق، انظر إلى الصيغة التالية (~ تشير إلى النفي):

( q1 _أو q2 ₎ و (~ _q1 أو q3 ) _و ( ~ _q2 أو ~ q3 ₎ و( _q1 أو ~ q2 ₎

نُسند لكلٍّ من المتغيرات الثمانية في هذه الصيغة متغيرًا حقيقيًا واحدًا في فضاء إقليدي ثماني الأبعاد. ويمكن استعادة بنية صيغة 2-SAT عند ترتيب هذه المتغيرات في جدول.

11 ×	12 ×
( x 21 )		22 ×
	( x 31 )	( x 32 )
41 ×	( x 42 )

تمثل الصفوف بنود صيغة 2-SAT، بينما تُرتّب القيم الحرفية المقابلة لنفس المتغير المنطقي في أعمدة، مع الإشارة إلى النفي بأقواس. على سبيل المثال، تُقابل المتغيرات الحقيقية x11 _و x21 و _x41 نفس المتغير المنطقي ( q1 ) أو نفيه، وتُسمى نسخًا متماثلة . من الأنسب ربط القيمتين 1 و -1 بالقيمتين TRUE و FALSE على _{التوالي ، بدلًا من 1 و 0 التقليديتين} . وفقًا لهذا الاصطلاح، تأخذ التوافقية بين النسخ المتماثلة شكل المعادلات الخطية التالية:

x ₁₁ = - x ₂₁ = x ₄₁

x ₁₂ = - x ₃₁ = - x ₄₂

س _٢٢ = - س _٣٢

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

أ ₁ = ( س ₁₁ - س ₂₁ + س ₄₁ ) / 3

x ₁₁ → a ₁ x ₂₁ → - a ₁ x ₄₁ → a ₁  

ينطبق قيد خريطة الفرق الثاني على صفوف الجدول، أي البنود. في عملية إسناد مُرضية، يجب إسناد القيم (1، 1) أو (1، -1) أو (-1، 1) إلى المتغيرين في كل صف. وبالتالي، فإن مجموعة القيود المقابلة، B ، هي مجموعة من ⁸¹ نقطة. عند إسقاط هذه المجموعة على هذا القيد، تُطبق العملية التالية على كل صف: أولًا، تُقرّب القيمتان الحقيقيتان إلى 1 أو -1؛ ثم، إذا كانت النتيجة (-1، -1)، تُستبدل القيمة الأكبر من القيمتين الأصليتين بالقيمة 1. أمثلة:

(-.2, 1.2) → (-1, 1)

(-0.2، -0.8) → (1، -1)

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

لتشغيل الخوارزمية، يتم أولاً إنشاء نقطة ابتدائية x ₀ ، على سبيل المثال

-0.5	-0.8
(-0.4)		-0.6
	(0.3)	(-0.8)
0.5	(0.1)

باستخدام β = 1، فإن الخطوة التالية هي حساب P _B ( x ₀ )  :

1	-1
(1)		-1
	(1)	(-1)
1	(1)

ويتبع ذلك 2 P _B ( x ₀ ) - x ₀ ،

2.5	-1.2
(2.4)		-1.4
	(1.7)	(-1.2)
1.5	(1.9)

ثم يتم إسقاطها على القيد الآخر، P _A (2 P _B ( x ₀ ) - x ₀ )  :

0.53333	-1.6
(-0.53333)		-0.1
	(1.6)	(0.1)
0.53333	(1.6)

زيادة x ₀ بمقدار الفرق بين الإسقاطين تعطي التكرار الأول لخريطة الفرق، D ( x ₀ ) = x ₁  :

-0.96666	-1.4
(-1.93333)		0.3
	(0.9)	(0.3)
0.03333	(0.7)

إليك التكرار الثاني، D ( x ₁ ) = x ₂  :

-0.3	-1.4
(-2.6)		-0.7
	(0.9)	(-0.7)
0.7	(0.7)

هذه نقطة ثابتة: D ( x² ) = x² . لا يتغير معدل التكرار لأن الإسقاطين متطابقان. من P _{( b} ( x² _{) )} ،

1	-1
(-1)		1
	(1)	(-1)
1	(1)

يمكننا قراءة تعيين الحقيقة المرضي: q ₁ = صحيح ، q ₂ = خطأ ، q ₃ = صحيح .

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

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

يتم إسقاط الإشارة على قيد معامل فورييه، ولنقل P _A ، عن طريق حساب تحويل فورييه المنفصل للإشارة أو الصورة أولاً، ثم إعادة تحجيم المعاملات لتتوافق مع البيانات، ثم عكس التحويل الناتج. يُعد هذا إسقاطًا، بمعنى أن المسافة الإقليدية إلى القيد تكون في أدنى حد، لأن (أ) تحويل فورييه المنفصل، باعتباره تحويلًا وحدويًا ، يحافظ على المسافة، و(ب) إعادة تحجيم المعامل (دون تغيير الطور) هو أصغر تغيير يحقق قيد المعامل.

لاستعادة الأطوار المجهولة لتحويل فورييه، تعتمد خريطة الفرق على الإسقاط على قيد آخر، P _B. قد يتخذ هذا عدة أشكال، حيث قد يكون من المعروف أن الكائن المراد إعادة بنائه موجب، أو له نطاق محدود ، وما إلى ذلك. في إعادة بناء صورة السطح، على سبيل المثال، كان تأثير الإسقاط P _B هو إلغاء جميع القيم خارج نطاق مستطيل، وكذلك إلغاء جميع القيم السالبة داخل النطاق.

• برنامج حل سودوكو - برنامج لحل سودوكو يعتمد على خوارزمية خريطة الفرق.