تقوم خوارزمية انهيار الموجة بتعليم الكمبيوتر الارتجال. عند الإدخال ، يتلقى البيانات النموذجية ويقوم بإنشاء بيانات تم إنشاؤها من الناحية الإجرائية مشابهة للنسخة الأصلية.
( المصدر )غالبًا ما يتم استخدامه لإنشاء الصور ، ولكن يمكنه أيضًا إنشاء
مدن وتزلجات ضوئية وكتابة
قصائد فظيعة .
( المصدر )انهيار وظيفة الموجة هو خوارزمية مستقلة عن التفكير ولا تتطلب مساعدة أو تعليمات من الخارج. تحتاج فقط إلى مثال للأسلوب الذي تريد تحقيقه ، وسيقوم بالباقي. على الرغم من اكتفائه الذاتي ، إلا أنه بسيط للغاية. لا يستخدم أي شبكات عصبية أو غابات عشوائية أو أي شيء آخر يشبه التعلم الآلي. إذا تعاملت مع الفكرة ، فستصبح مفهومة للغاية وبديهية بالنسبة لك.
تعد معظم التطبيقات والشروحات الخاصة بانهيار دالة الموجات إصدارًا كاملاً ومزودًا بالسرعة من الخوارزمية. بالطبع ، كلها مهمة وضرورية ، لكن من الصعب فهمها من نقطة الصفر. في هذا المنشور ، سوف أشرح كل شيء بلغة بسيطة أفهمها ، مع التركيز على الإصدار المحدود من Wavefunction ، والتي أسميتها
حتى نموذج Simpler
Tiled Model . بالإضافة إلى ذلك ، قمت بنشر
مثال لتنفيذ ESTM على جيثب . الكود الموجود فيه غير فعال وبطيء ، ولكنه قابل للقراءة للغاية وقد علق بالتفصيل. بمجرد فهمك للتكنولوجيا التي تقوم عليها ESTM ، ستصبح أقرب إلى فهم إصدارات أكثر تعقيدًا من الخوارزمية. إذا كنت ترغب في فهم خوارزمية انهيار دالة الموج ، فستكون هذه المقالة بداية جيدة.
لنبدأ بالقصة.
العرس
تخيل أنك تخطط لحفل الزفاف الخاص بك. بالإضافة إلى مجموعة المجوهرات والموسيقى ، تحتاج إلى وضع خطة جلوس للضيوف لتناول العشاء. تحب عائلتك المجادلة وتكون شقيًا ، لذلك قد يكون من الصعب. لا يمكن للأب الجلوس بالقرب من طاولتين من والدته. يصبح ابن العم وحيدًا إذا لم تجلس مع ابن عم آخر. ومن الأفضل عدم زرع Uncle Roy بجوار أعضاء عائلة شريكك الصديقين للبيئة. يبقى فقط 5 ساعات قبل وصول الطعام ، لذلك قررت مهاجمة هذه المهمة العنيدة باستخدام خوارزمية انهيار وظيفة الموجة.
عليك أن تبدأ بقائمة طويلة من القواعد وخطة جلوس فارغة.
يمكنك إنشاء
وظيفة الموجة الأصلية للخطة. إنها تربط كل كرسي بقائمة من الأشخاص الذين يمكنهم الجلوس عليها. بينما يمكن لأي شخص الجلوس على أي كرسي. تبدأ وظيفة الموجة المتمثلة في جلوس الضيوف
بالتراكب الكامل (يتم استعارة المفهوم من فيزياء الكم) لكل مخطط ممكن.
كانت قطة شرودنغر ميتة وبقيت على قيد الحياة في نفس الوقت حتى فتح شخص ما الصندوق وراجعه. خطتك هي في نفس الوقت كل مخطط ممكن حتى تقوم بترتيب الأمور. التراكب الكامل هو بناء نظري مفيد ، لكنه لن يساعد جدتك في معرفة مكان جلوسها. تحتاج إلى إحضار وظيفة الموجة لموقع الضيوف إلى حالة معينة واحدة ، والتي يمكن بعد ذلك تحويلها إلى بطاقات اسم عادية غير كمومية.
نبدأ في القيام بذلك عن طريق إجراء
انهيار وظيفة الموجة لكرسي واحد. نختار كرسيًا وننظر إلى قائمة الأشخاص الذين يمكنهم الجلوس عليه ، ونخصصه عشوائيًا لأحدهم. في هذه الحالة ، تنهار وظيفة الموجة في البراز.
هذا الاختيار له عواقب تمتد إلى وظائف موجة الكراسي المتبقية. إذا كان العم روي يجلس على الطاولة 2 ، فلن يكون ابن عمه فرانك وميشيل أوباما (صديق لعائلة شريكك) بالتأكيد معه. وإذا لم تجلس ميشيل على الطاولة 2 ، فلن يكون باراك وراءه أيضًا. نقوم بتحديث وظيفة الموجة لخطة الموقع عن طريق حذف الأشخاص من قوائم المرشحين المحتملين.
بمجرد تسوية الاهتزازات ، نكرر هذه العملية. نختار كرسيًا آخر مع العديد من المرشحين المحتملين وننهي وظيفة الموجة ، ونختار عشوائيًا أحد الأشخاص المقبولين له. مرة أخرى ، نمد الاهتزازات الناتجة عن هذا الاختيار إلى بقية الخطة ، ونزيل الأشخاص من وظيفة الموجة في الكرسي إذا لم يعد بإمكانهم الجلوس عليها.
نكرر هذه العملية إما حتى تنهار وظيفة الموجة (أي ، يظل شخص واحد يجلس عليها بالضبط) ، أو حتى نصل إلى
تناقض . التناقض هو كرسي لا يمكن لأحد أن يجلس فيه ، لأنهم طردوا جميعًا بسبب الانتخابات السابقة. التناقض يجعل استحالة انهيار وظيفة الموجة بأكملها.
إذا وصلت إلى تناقض ، فإن أسهل طريقة هي البدء من جديد. تجاهل كل الأعمال السابقة ، وابحث عن خطة جديدة فارغة وابدأ الخوارزمية مرة أخرى ، مع استكمال انهيار وظيفة الموجة لكرسي عشوائي آخر. يمكنك أيضًا تطبيق نظام التراجع الذي يسمح لك بإلغاء خيار معين ، بدلاً من التخلي عن كل شيء على الفور ("ماذا لو تم نقل شيلا إلى كرسي 54؟").
بعد بضع بدايات خاطئة ، ستصل أخيرًا إلى حالة من الانهيار التام يتم فيها تعيين كل رئيس لشخص واحد تمامًا ويتم اتباع جميع القواعد. القيام به!
من الزفاف إلى الصور النقطية
هذا ليس مثالا نظريا. يمكنك حقًا إدراك متغير من انهيار وظيفة الموجة ، والتي ستنشئ خطة جلوس للضيوف لحفل الزفاف. ومع ذلك ، في تقليص Wavefunction الأكثر تقليدية ، عادة ما نحاول عدم وضع الأشخاص في حفل الزفاف ، ولكن لترتيب وحدات البكسل في صورة الإخراج. ومع ذلك ، فإن العملية ستكون مشابهة جدا. نحن نعلم الخوارزمية مجموعة من القواعد التي يجب أن تفي بها المخرجات. نحن تهيئة وظيفة الموجة. نقوم بإجراء انهيار عنصر واحد ونمد العواقب إلى بقية وظيفة الموجة. ونواصل القيام بذلك ، إما حتى تنهار وظيفة الموجة تمامًا ، أو حتى نصل إلى تناقض.
يختلف الانهيار التقليدي لوظيفة الموجة عن انهيار الزفاف بالطريقة التي نعلم بها الخوارزمية القواعد التي يجب اتباعها. في نسخة الزفاف ، كان علينا أن نكتب القواعد بأنفسنا. ولكن في الإصدار التقليدي ، نعطي الخوارزمية مثالًا للصورة ، وبناءً عليها ، تقوم الخوارزمية بإنشاء الباقي. يوزع مثالاً ، ويحلل أنماطه ويكتشف كيف يجب أن تصطف البكسلات أو
البلاط .
دعنا نبدأ في البحث عن الانهيار الحقيقي لوظيفة الموجات من خلال النظر في حالة خاصة بسيطة ، والتي
ExUtumno (منشئ الخوارزمية) "
نموذج بسيط من البلاط" .
نموذج البلاط بسيط
في نموذج التبليط البسيط ، يتم إنشاء صور المدخلات والمخرجات من عدد صغير من التجانيد المحددة مسبقًا ، وكل مربع في صورة المخرجات يقتصر على أقرب أربعة جارات فقط. على سبيل المثال ، لنفترض أننا نولد عوالم عشوائية للعبة ثنائية الأبعاد ذات منظر علوي. يمكن أن يكون لدينا بلاط للأرض والساحل والبحر ، بالإضافة إلى مجموعة من القواعد مثل "الساحل يمكن أن يكون بالقرب من البحر" ، "يمكن أن تكون الأرض بالقرب من الساحل" و "يمكن أن يكون البحر بجوار بحر آخر".
يأخذ
نموذج البلاط البسيط في الاعتبار التماثل والتناوب بين البلاط. على سبيل المثال ، قد تكون الأرض بالقرب من الساحل ، ولكن فقط في الاتجاه الصحيح.
توفر معالجة التناظر هذه صورًا أفضل للمخرجات ، ولكنها تعقد الكود. لإبقاء الأمور بسيطة ، دعنا ننظر إلى نظرة أبسط من انهيار وظيفة الموجة ، والتي
أسميتها "نموذج البلاط البسيط" .
حتى أبسط نموذج البلاط
حتى نموذج البلاط المبسط ("نموذج البلاط أكثر بساطة") يشبه نموذج البلاط البسيط ، ولكن البلاط الخاص به لا يحتوي على خصائص التناظر. كل تجانب هو بكسل واحد من نفس اللون ، أي أننا لن نتمكن من الخلط بين حوافهم بأي شكل من الأشكال.
تحدد حتى قواعد نموذج البلاط المبسط Simpler Tiled Model المربعات التي يمكن وضعها بجوار بعضها وفي أي اتجاه. كل قاعدة عبارة عن مجموعة مكونة من ثلاثة عناصر (3-tuple): اثنين من البلاط واتجاه. على سبيل المثال ،
(SEA, COAST, LEFT) تعني أن بلاط
SEA (البحر) يمكن أن يكون
من البلاط
COAST (الساحل). يجب أن تكون هذه القاعدة مصحوبة بقاعدة أخرى تصف الموقف من حيث
COAST -
(COAST, SEA, RIGHT) .
إذا كنت تريد أن تكون بلاطات
SEA موجودة ليس فقط
، ولكن أيضًا
من بلاطات
COAST . ثم يحتاجون إلى قواعد إضافية:
(SEA, COAST, RIGHT) و
(COAST, SEA, LEFT) .
كما قلت أعلاه ، لسنا بحاجة إلى إنشاء قائمة بكل هذه القواعد بأنفسنا. يمكن أن يؤدي انهيار دالة الموجات إلى إنشاء مجموعة من القواعد لـ "نموذج البلاط البسيط" من خلال تحليل صورة مثال وجمع قائمة بجميع الفئات الثلاثية التي تحتوي عليها.
بعد فحص مثال الصورة الموضح أعلاه ، تلاحظ حتى نموذج Simpler Tiled أن بلاط البحر يمكن أن يكون فقط أسفل أو إلى جانب البلاط الساحلي ، أو في أي مكان بالقرب من بلاطات البحر الأخرى. كما تشير إلى أنه يمكن العثور على بلاطات الساحل بجوار اليابسة أو البحر أو بلاطات الساحل الأخرى ، ولكن فقط فوق بلاطات البحر وتحت البلاط الأرضي. إنها لا تحاول استنباط أي قواعد أكثر تعقيدًا ، على سبيل المثال ، "يجب أن يكون بلاط البحر بالقرب من بلاطة بحرية واحدة على الأقل" أو "يجب أن تحتوي كل جزيرة على بلاطة أرضية واحدة على الأقل." لا يمكن لأي من المربعات التأثير على حقيقة أن بعض أنواع المربعات يمكن أو لا يمكن تحديد موقع مربعين أو أكثر منها. يشبه هذا نموذج خطة الزفاف حيث تكون القاعدة الوحيدة هي: "يمكن لـ X الجلوس بجانب Y".
عند تحليل الصورة الواردة ، نحتاج أيضًا إلى تسجيل التردد الذي يجتمع به كل مربع من البلاط. في وقت لاحق ، نستخدم هذه الأرقام كأوزان عند اختيار الدالة الموجية للمربع ، والتي يجب إجراء انهيارها ، وكذلك عند اختيار التجانب المخصص للمربع عند إنهائه.
بعد أن تعلمت القواعد التي يجب أن تلتزم بها صورة الإخراج ، نحن على استعداد لبناء انهيار وظيفة الموجة لصورة الإخراج.
انهيار
كما هو الحال في مثال الزفاف ، نبدأ عملية الانهيار بوظيفة موجية يكون فيها كل مربع من الصورة الناتجة في تراكب لكل نوع من أنواع البلاط.
نبدأ باختيار مربع تنهار وظيفته الموجية. في مثال الزفاف ، تم هذا الاختيار عن طريق الصدفة. ومع ذلك ، كما لاحظ
ExUtumno ، عادة ما
ExUtumno الناس مع هذه المهام بشكل مختلف. بدلاً من ذلك ، يبحثون عن المربعات مع أدنى
إنتروبيا . الانتروبيا هو مقياس من عدم اليقين والاضطراب. بشكل عام ، المربع ذو الانتروبيا العالية هو مربع مع وجود العديد من البلاط المحتمل في وظيفة الموجة. لا يزال من غير الواضح إلى أي بلاط ينهار في النهاية. مربع الانتروبيا المنخفض هو مربع يحتوي على أقل عدد ممكن من البلاط في وظيفة الموجة. مجموعة البلاط ، التي ينهار نتيجة لذلك ، محدودة للغاية بالفعل.
على سبيل المثال ، في Even Simpler Tile Model ، فإن المربع الذي لا يحتوي على معلومات حول المربعات المحيطة غير محدود ويمكن أن يصبح أي مربع. لذلك ، لديها الانتروبيا عالية جدا. ولكن يمكن أن يكون للمربّع الذي انهار حوله العديد من المربعات اختيار من بلاطات اثنين فقط.
لم تنهار وظيفة الموجة للساحة المركزية في الشكل أعلاه تمامًا ، لكننا نعلم بالفعل أنه لا يمكن أن يكون بلاطة أرضية. ومع ذلك ، فهي محدودة بالفعل ، مما يعني أن لديها
إنتروبيا أقل من تلك الموجودة في المربع الأيمن العلوي ، والتي يمكن أن تظل برية أو بحر أو ساحل.
إنها بلاطات محدودة ذات إنتروبيا منخفضة عادةً ما ينتبه الأشخاص إليها عندما يحلون هذه المشكلات يدويًا. حتى إذا كنت لا تستخدم انهيار دالة الموجات لإنشاء خطة لوضع الضيوف في حفل الزفاف وستضعها بنفسك ، فلا تزال تركز على مجالات الخطة التي لديها بالفعل أكبر عدد من القيود. لن تضع دواين في الجدول 1 ، ثم تقفز عشوائيًا للحصول على كاتي في الجدول 7 (فارغ حتى الآن). لقد وضعت دواين أولاً ، ثم ستكتشف من يمكنه الجلوس بجانبه ، ثم من يمكنه الجلوس بجانب هذا الشخص ، وهكذا. لم أر أي مبرر لذلك حتى الآن ، ولكن حدسي يقول أن استخدام هذا
الكشف عن مجريات الأمور في الحد الأدنى من الانتروبيا من المرجح أن يؤدي إلى
تناقضات أقل مما لو كنت قد اخترت بشكل عشوائي المربعات للانهيار.
يتم استخدام
صيغة شانون كصيغة إنتروبيا في خوارزمية انهيار دالة الموجة. يستخدم أوزان المربعات التي قمنا بتحليلها من الصورة الواردة في الخطوة السابقة:
# Sums are over the weights of each remaining # allowed tile type for the square whose # entropy we are calculating. shannon_entropy_for_square = log(sum(weight)) - (sum(weight * log(weight)) / sum(weight))
بعد حساب مربع دالة الموجة مع أصغر الانتروبيا ، فإننا ننهار دالة الموجة. نقوم بذلك عن طريق اختيار عشوائي لأحد المربعات التي لا تزال متاحة للمربع ، موزونة بأوزان المربعات التي قمنا بتحليلها من الصورة الواردة. تستخدم الأوزان لأنها توفر صورة إخراج أكثر واقعية. لنفترض أن الدالة الموجية لتقارير مربعة يمكن أن تكون برية أو ساحلية. ليس لدينا دائمًا اختيار أحد الخيارات باحتمال 50٪. إذا كانت صورة الإدخال تحتوي على بلاطات أرضية أكثر من الساحل ، فينبغي لنا أن نعكس هذه الميزة في صورة الإخراج. يتم تحقيق ذلك باستخدام الأوزان العالمية البسيطة. إذا كان في الصورة المثالية
20 بلاط أرضي و
10 قرميد ساحلي ، فإن المربع ينهار إلى الأرض باحتمال
2/3 ، وفي الساحل مع وجود احتمال متبقٍ قدره
1/3 .
ثم نمد عواقب الاختيار إلى بقية دالة الموجة للناتج ("إذا تبين أن هذا البلاط هو البحر ، فإن هذه البلاطة لا يمكن أن تكون برية ، أي ، هذا لا يمكن أن يكون الساحل"). عندما تستقر كل هذه الهزات ، نكرر العملية باستخدام الحد الأدنى من مجريات البحث عن الانحدار لتحديد البلاط المنهار التالي. نكرر دورة الانتشار ، إما حتى تنهار وظيفة الموجة بأكملها لصورة الإخراج تمامًا ويمكننا إرجاع النتيجة ، أو حتى نصل إلى تناقض ونرجع خطأً.
نتيجة لذلك ، أنشأنا عالما (أو خطأ).
إلى أين أذهب بعد ذلك
بعد أن تعاملت مع نموذج البلاط المبسط ، فأنت مستعد لتسلق سلم القوة وتعقيد الخوارزمية. ابدأ بالنموذج المبلط البسيط الذي ذكرناه في بداية هذا المنشور ، ثم انتقل إلى نموذج التداخل الكامل. في نموذج التداخل ، تؤثر المربعات أو البيكسلات على بعضها البعض من مسافة بعيدة. إذا فهمت مثل هذه الأشياء ، يلاحظ
ExUtumno أن نموذج
ExUtumno البسيط مشابه لسلسلة Markov الخاصة بالترتيب 1 ، وأن النماذج الأكثر تعقيدًا تشبه السلاسل ذات الترتيب الأكبر.
يمكن أن يأخذ Collfunction في الحسبان قيودًا إضافية ، على سبيل المثال ، "يجب أن يكون هذا البلاط بحرًا" أو "يجب أن يكون هذا البكسل أحمر" أو "يمكن أن يكون هناك وحش واحد فقط في الإخراج". كل هذا موصوف في
README للمشروع الرئيسي . يمكنك أيضًا دراسة تحسينات السرعة التي تم إجراؤها للتنفيذ الكامل. ليس من الضروري إعادة حساب إنتروبيا كل مربع في كل تكرار ، ويمكن أن يتم نشر المعلومات بواسطة دالة الموجات بشكل أسرع. تصبح هذه الجوانب أكثر أهمية مع زيادة حجم صور المخرجات.
انهيار وظيفة الموجة هو أداة جميلة وقوية تستحق السيطرة عليها. فكر في الأمر في المرة القادمة التي تخطط فيها لإقامة حفل زفاف أو إنشاء عالم إجرائي.