سلاسل ماركوف لجيل البناء الإجرائي

ملاحظة: يمكن العثور على الكود المصدري الكامل لهذا المشروع [ هنا ]. نظرًا لأنه جزء من مشروع أكبر ، فإنني أوصي بمشاهدة الالتزام في وقت إصدار هذه المقالة ، أو ملف /source/helpers/arraymath.h ، وكذلك /source/world/blueprint.cpp .

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

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

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

سيتم استخدام النتائج في محرك voxel الخاص بي حتى تتمكن الروبوتات المهمة من بناء المباني ، ثم المدن. في نهاية المقال هناك مثال!


بضعة أمثلة مع النتائج.

الأساسيات

سلاسل ماركوف

سلاسل Markov هي سلسلة من الحالات التي يتحرك فيها النظام ، موصوفة بالتحولات في الوقت المناسب. التحولات بين الحالات عشوائية ، أي أنها توصف بالاحتمالات ، وهي سمة من سمات النظام.

يتم تعريف النظام من خلال مساحة الدولة ، والتي هي مساحة جميع تكوينات النظام الممكنة. إذا تم وصف النظام بشكل صحيح ، فيمكننا أيضًا وصف التحولات بين الحالات بأنها خطوات منفصلة.

تجدر الإشارة إلى أنه من حالة واحدة من النظام غالبا ما يكون هناك العديد من التحولات المنفصلة المحتملة ، كل منها يؤدي إلى حالة مختلفة من النظام.

احتمال الانتقال من الحالة i إلى الحالة j يساوي:

$$

$$P_ {ij}$$

عملية Markov هي عملية دراسة مساحة الدولة هذه بمساعدة الاحتمالات المنقولة إليها.

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

$$

$$P_ {ij} = P (i، j)$$

مثال: توليد النص

النظام عبارة عن سلسلة من البتات. مساحة الدولة هي كل التسلسلات الممكنة من البتات. سيتغير الانتقال المنفرد بت واحد من 0 إلى 1 أو من 1 إلى 0. إذا كان النظام يحتوي على n bits ، فعندئذٍ من كل ولاية ننتقل إلى حالة جديدة. ستتألف عملية Markov من دراسة مساحة الدولة عن طريق تغيير قيم البتات في تسلسل باستخدام بعض الاحتمالات.

مثال: التنبؤ بالطقس

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

طريقة مونت كارلو لسلاسل ماركوف

نظرًا لأن التحولات بين الولايات تحددها الاحتمالات ، يمكننا أيضًا تعيين احتمال وجود "مستقر" في أي ولاية (أو ، إذا كان الوقت يميل إلى ما لا نهاية ، فإن متوسط ​​الوقت الذي سنكون فيه في حالة معينة). هذا هو التوزيع الداخلي للدول.

ثم خوارزمية مونت كارلو لسلاسل ماركوف (ماركوف- سلسلة مونت كارلو ، MCMC) هي تقنية للحصول على عينة من مساحة الدولة. أخذ العينات (أخذ العينات) يعني اختيار الحالة بناءً على احتمال الاختيار ، مع مراعاة التوزيع الداخلي.

يقولون إن احتمال التواجد في ولاية يتناسب * مع دالة تكلفة معينة تعطي "تقدير" للحالة الحالية التي يوجد بها النظام. يُعتقد أنه إذا كانت التكاليف منخفضة ، فإن احتمال التواجد في هذه الحالة مرتفع ، وهذه النسبة رتابة. يتم تعريف وظيفة التكلفة على النحو التالي:

$$

$$R (i)$$

ملاحظة: لست متأكدًا مما إذا كانت كلمة "متناسبة" تُستخدم بشكل صحيح ، لأن النسبة ليست خطية بالضرورة.

ثم تقوم عينة من توزيع الحالة بإرجاع تكوين بتكاليف منخفضة (أو "تقدير" جيد) مع احتمال أكبر!

حتى مع وجود مساحة دولة كبيرة للغاية (ربما لا حصر لها ، ولكن "لا حصر له بشكل لا يصدق") ، بصرف النظر عن تعقيد النظام ، ستجد خوارزمية MCMC حلاً بتكاليف منخفضة إذا منحنا وقتًا كافيًا للالتقاء.

يعد إجراء مثل هذه الدراسة لمساحة الحالة تقنية قياسية للتحسين العشوائي وله العديد من التطبيقات في مجالات مثل التعلم الآلي.

توزيع جيبس

ملاحظة: إذا لم يكن هذا القسم واضحًا لك ، فيمكنك تخطيه بأمان. لا يزال بإمكانك الاستفادة من تنفيذ النظام.

بعد تحديد تكاليف حالة ممكنة ، كيف يمكننا تحديد احتمال حدوث هذا الشرط؟

الحل: إن توزيع Gibbs هو توزيع أقصى إنتروبيا لمجموعة معينة من القيود.

يعني هذا في جوهره أنه إذا وضعنا الكثير من القيود على احتمالات النظام ، فإن توزيع Gibbs سيخلق "أقل قدر من الافتراضات" حول شكل التوزيع.

ملاحظة: توزيع Gibbs هو أيضًا التوزيع الأقل حساسية للتغيرات في القيود (وفقًا لمقياس تباعد Kullback-Leibler).

القيد الوحيد الذي نفرضه على توزيع الحالات هو دالة التكلفة ، لذلك نستخدمها في توزيع جيبس ​​لحساب احتمال الانتقال بين الحالات:

$$

$$P_ {ij} = \ exp (- \ frac {R (j) -R (i)} {T}) * \ frac {1} {Z_i}$$

حيث Z هي وظيفة التقسيم لمجموعة التحولات من الحالة i. هذا عامل تطبيع يضمن أن مجموع احتمالات الانتقال من أي ولاية هو 1.

$$

$$Z_i = \ sum_j (P_ {ij})$$

لاحظ أنه إذا قررنا أن الحالة التالية ستكون هي نفس الحالة ، فإن التكاليف النسبية هي صفر ، أي أن الاحتمال بعد التطبيع سيكون غير صفري (بسبب شكل التوزيع مع المؤشر)! هذا يعني أنه في العديد من التحولات ، من الضروري تضمين احتمال الحالات التي لم تتغير.

تجدر الإشارة أيضًا إلى أن توزيع Gibbs محدد بواسطة "درجة الحرارة الحسابية" T.

واحدة من المزايا الرئيسية لاستخدام الاحتمالات في دراسة فضاء الحالة هو أن النظام يمكن أن يؤدي انتقالات إلى حالات أكثر تكلفة (نظرًا لوجود احتمال انتقال غير صفري) ، وتحويل الخوارزمية إلى طريقة تحسين "غير جشع".

لاحظ أنه نظرًا لأن درجة الحرارة تميل إلى ما لا نهاية ، فإن احتمال أي انتقال فردي يميل إلى الوحدة بطريقة تجعل مجموعة الاحتمالات لجميع عمليات الانتقال من حالة طبيعية أمرًا محتملاً (أو يقترب توزيع جيبس ​​من التوزيع الطبيعي) ، على الرغم من أن تكاليفها أكبر!

مع اقتراب درجة الحرارة الحسابية من الصفر ، تصبح التحولات ذات التكاليف الأقل أكثر احتمالًا ، أي يزيد احتمال التحولات المفضلة.

عند إجراء بحث / تحسين مساحة الدولة ، نخفض درجة الحرارة تدريجياً. وتسمى هذه العملية "محاكاة الصلب" . بفضل هذا ، في البداية يمكننا بسهولة الخروج من الحد الأدنى المحلي ، وفي النهاية يمكننا اختيار أفضل الحلول.

عندما تكون درجة الحرارة منخفضة بدرجة كافية ، فإن جميع الاحتمالات تميل إلى الصفر ، باستثناء احتمال عدم الانتقال!

وذلك لأن عدم وجود انتقال هو فقط فرق في التكلفة صفر ، أي أن الحالة في نفس الحالة لا تعتمد على درجة الحرارة. بسبب شكل الدالة الأسية في T = 0 ، يتضح أن هذا هو الاحتمال الوحيد بقيمة غير صفرية ، أي بعد التطبيع ، يتحول إلى وحدة. وبالتالي ، سيتقارب نظامنا إلى نقطة مستقرة ولن يكون هناك حاجة إلى مزيد من التبريد. هذه خاصية أساسية لتوليد الاحتمالات باستخدام توزيع Gibbs.

يمكن تعديل عملية تقارب النظام عن طريق تغيير معدل التبريد!

إذا كان التبريد أبطأ ، فنتيجة لذلك عادة ما نتوصل إلى حل بتكاليف أقل (إلى حد ما) ، ولكن على حساب مزيد من خطوات التقارب. إذا كان التبريد أسرع ، فمن الأرجح أن يقع النظام في المراحل المبكرة في مصيدة منطقة دون إقليمية بتكاليف أكبر ، أي أننا سنحصل على نتائج "أقل مثالية".

وبالتالي ، فإن عملية Markov لا تؤدي فقط إلى توليد نتائج عشوائية ، ولكنها تحاول توليد نتائج "جيدة" ، واحتمال كبير أنها ستنجح!

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

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

الجيل الإجرائي

كيف تكون هذه الطريقة مفيدة للجيل الإجرائي؟

في بعض الأنظمة ، يكون من الصعب تحديد خوارزمية بسيطة تؤدي إلى نتائج جيدة ، خاصة في حالة الأنظمة المعقدة.

إن وضع قواعد الجيل التعسفي ليس أمرًا صعبًا فحسب ، بل يقتصر فقط على تخيلنا ومعالجة الحالات الحدودية.

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

يتم تقديم المتطلبات التالية:

• قد يكون النظام بتكوين حالة منفصل (ربما لا نهائي).
• يمكننا تحديد التحولات المنفصلة بين الدول.
• يمكننا تعيين دالة تكلفة تقدر الحالة الحالية للنظام.

أدناه ، سأقدم بعض الأمثلة الأخرى التي ، في رأيي ، يمكن تطبيق هذه الطريقة.

تطبيق

الكود الزائف

في تطبيقنا ، نريد تحقيق ما يلي:

• ضبط حالة النظام.
• اضبط كل التحولات الممكنة على الحالة التالية.
• احسب تكاليف الحالة الحالية.
• احسب تكاليف جميع الحالات التالية الممكنة (أو مجموعة فرعية منها).
• باستخدام توزيع Gibbs ، احسب احتمالية الانتقال.
• انتقالات العينة (العينة) باستخدام الاحتمالات.
• إجراء انتقال العينات.
• خفض درجة الحرارة الحسابية.
• كرر الخطوات حتى تحصل على نتائج مرضية.

في شكل الشفرة الزائفة ، خوارزمية MCMC هي كما يلي:

 // MCMC    T = 200; //     State s = initialState(); Transitions t[n] = {...} //n   thresh = 0.01; //  ( ) // ,      while(T > thresh){ //    curcost = costfunc(s); newcost[n] = {0}; // newcost   0 probability[n] = {0}; //     0 //  for(i = 0; i < n; i++){ newcost[i] = costfunc(doTransition(s, t[i])); probability[i] = exp(-(newcost[i] - curcost)/T); } //  probability /= sum(probability); //  sampled = sample_transition(t, probability); //  s = doTransition(s, sampled); //  T *= 0.975; } 

بناء الجيل 3D

الدولة الفضاء والتحولات

لإنشاء مبانٍ ثلاثية الأبعاد ، أقوم بإنشاء العديد من الغرف بالحجم المحدد بواسطة المربع المحيط.

 struct Volume{ //   glm::vec3 a; glm::vec3 b; void translate(glm::vec3 shift); int getVol(); }; //   int Volume::getVol(){ return abs((bx-ax)*(by-ay)*(bz-az)); } //    void Volume::translate(glm::vec3 shift){ a += shift; b += shift; } 

إذا قمت بإنشاء غرف n ، فإن حالة النظام هي تكوين الصناديق المحيطية في الفضاء ثلاثي الأبعاد.

تجدر الإشارة إلى أن التكوينات المحتملة لهذه المجلدات لا حصر لها ، ولكن لا حصر لها لا تعد ولا تحصى (يمكن إدراجها في كمية لا حصر لها من الوقت)!

 //  (  !) std::vector<Volume> rooms; // N  for(int i = 0; i < n; i++){ //  Volume x; xa = glm::vec3(0); xb = glm::vec3(rand()%4+5); //   //  . rooms.push_back(x); } //... 

ستكون العديد من التحولات المحتملة بمثابة تغيير في الغرف في أحد الاتجاهات الستة للفضاء بخطوة واحدة ، بما في ذلك عدم وجود انتقال:

 //... //   std::array<glm::vec3, 7> moves = { glm::vec3( 0, 0, 0), //   ! glm::vec3( 1, 0, 0), glm::vec3(-1, 0, 0), glm::vec3( 0, 1, 0), glm::vec3( 0,-1, 0), glm::vec3( 0, 0, 1), glm::vec3( 0, 0,-1), }; //... 

ملاحظة: من المهم أن نبقي النظام قادرًا على البقاء في حالته الحالية!

وظيفة التكلفة

أردت أن تتصرف وحدات التخزين في الفضاء ثلاثي الأبعاد مثل "المغناطيس" ، أي:

• إذا كانت أحجامها تتقاطع ، فهذا أمر سيء.
• إذا لمست أسطحها ، فهذا أمر جيد.
• إذا لم يلمسوا على الإطلاق ، فهذا أمر سيء.
• إذا لمسوا الأرض ، فهذا جيد.

لاثنين من المكعبات في مساحة ثلاثية الأبعاد ، يمكننا بسهولة تحديد مربع محيط:

 Volume boundingBox(Volume v1, Volume v2){ //   Volume bb; //   bb.ax = (v1.ax < v2.ax)?v1.ax:v2.ax; bb.ay = (v1.ay < v2.ay)?v1.ay:v2.ay; bb.az = (v1.az < v2.az)?v1.az:v2.az; //   bb.bx = (v1.bx > v2.bx)?v1.bx:v2.bx; bb.by = (v1.by > v2.by)?v1.by:v2.by; bb.bz = (v1.bz > v2.bz)?v1.bz:v2.bz; return bb; } 

باستخدام المربع المحيط للمجلدات ، يمكننا حساب متجه ثلاثي الأبعاد يعطيني معلومات حول تقاطع مجلدين.

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

 //    3  glm::vec3 overlapVolumes(Volume v1, Volume v2){ //      Volume bb = boundingBox(v1, v2); //  glm::vec3 ext1 = glm::abs(v1.b - v1.a); // v1  3  glm::vec3 ext2 = glm::abs(v2.b - v2.a); // v2  3  glm::vec3 extbb = glm::abs(bb.b - bb.a); //   //  return ext1 + ext2 - extbb; } 

يتم استخدام هذا الرمز لحساب عدد الكميات التي أقوم بتكوين كمية مرجحة لها ، والتي يتم استخدامها في النهاية كتكلفة.

 int volumeCostFunction(std::vector<Volume> rooms){ // int metric[6] = { 0, //   0, //   0, //     0, //     0, // ,   0};//    int weight[6] = {2, 4, -5, -5, -5, 5}; //    for(unsigned int i = 0; i < rooms.size(); i++){ //     for(unsigned int j = 0; j < rooms.size(); j++){ //    ,  . if(i == j) continue; //    . glm::vec3 overlap = overlapVolumes(rooms[i], rooms[j]); //   glm::vec3 posOverlap = glm::clamp(overlap, glm::vec3(0), overlap); metric[0] += glm::abs(posOverlap.x*posOverlap.y*posOverlap.z); //   //   glm::vec3 negOverlap = glm::clamp(overlap, overlap, glm::vec3(0)); metric[1] += glm::abs(negOverlap.x*negOverlap.y*negOverlap.z); //   //   if(overlap.y == 0){ metric[2] += overlap.x*overlap.z; } //   (X) if(overlap.x == 0){ //      0,   , .. overlap.z = 0 metric[3] += overlap.z*overlap.y; } //   (Z) if(overlap.z == 0){ //      0,   , .. overlap.x = 0 metric[4] += overlap.x*overlap.y; } } //  ,   -   . if(rooms[i].ay == 0){ //  ,  ,    . metric[4] += rooms[i].ax*rooms[i].az; } //,     ! if(rooms[i].ay < 0){ //,        if(rooms[i].by < 0){ metric[5] += rooms[i].getVol(); } else{ metric[5] += abs(rooms[i].ay)*(rooms[i].bz-rooms[i].az)*(rooms[i].bx-rooms[i].ax); } } } // Metric * Weights return metric[0]*weight[0] + metric[1]*weight[1] + metric[2]*weight[2] + metric[3]*weight[3] + metric[4]*weight[4] + metric[5]*weight[5]; } 

ملاحظة: "حجم التقاطع الإيجابي" يعني أن وحدات التخزين تتقاطع بالفعل. "الحجم السلبي للتقاطع" يعني أنها لا تمس على الإطلاق ويتم تعريف التقاطع من خلال مستوى الصوت الموجود بين أقرب نقطتين من المكعبات في الفضاء ثلاثي الأبعاد.

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

أقوم بتكاليف جميع أزواج الغرف ، مع تجاهل الغرف المقترنة بأنفسهم.

إيجاد حل منخفض التكلفة

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

  //  float T = 250; while(T > 0.1){ //   std::vector<std::array<double, moves.size()>> probabilities; //   () int curEnergy = volumeCostFunction(rooms); //      ... for(int i = 0; i < n; i++){ //    std::array<double, moves.size()> probability; //      ,     for(unsigned int m = 0; m < moves.size(); m++){ //        . rooms[i].translate(moves[m]); //      ! probability[m] = exp(-(double)(volumeCostFunction(rooms) - curEnergy)/T); //   rooms[i].translate(-moves[m]); } //       probabilities.push_back(probability); } //  ( ) double Z = 0; for(unsigned int i = 0; i < probabilities.size(); i++){ for(unsigned int j = 0; j < probabilities[i].size(); j++){ Z += probabilities[i][j]; } } //  for(unsigned int i = 0; i < probabilities.size(); i++){ for(unsigned int j = 0; j < probabilities[i].size(); j++){ probabilities[i][j] /= Z; } } //    (CDF) ( ) std::vector<double> cdf; for(unsigned int i = 0; i < probabilities.size(); i++){ for(unsigned int j = 0; j < probabilities[i].size(); j++){ if(cdf.empty()) cdf.push_back(probabilities[i][j]); else cdf.push_back(probabilities[i][j] + cdf.back()); } } //      std::random_device rd; std::mt19937 e2(rd()); std::uniform_real_distribution<> dist(0, 1); double uniform = dist(e2); int sampled_index = 0; //   CDF for(unsigned int i = 0; i < cdf.size(); i++){ //    ,   ... if(cdf[i] > uniform){ sampled_index = i; break; } } //     int _roomindex = sampled_index/moves.size(); int _moveindex = sampled_index%moves.size(); //  rooms[_roomindex].translate(moves[_moveindex]); // T T *= 0.99; // !!! } //!! //... 

يتم أخذ العينات من خلال تشكيل وظيفة توزيع تراكمي على وظيفة التوزيع الشامل لجميع التحولات المحتملة ؛ تسمى هذه العملية "أخذ عينات التحويل العكسي".

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


بدلا من وظيفة مستمرة ، قد تكون هناك خطوات منفصلة. يمكن قراءة المزيد من التفاصيل هنا .

بالإضافة إلى ذلك ، لدي بيانات حجم الغرفة في مساحة ثلاثية الأبعاد!

أنا استخدامها لإنشاء "مخطط" باستخدام فئة مخطط ، وتطبيق سمة على البيانات المجمعة المعروفة. حتى المنازل الحصول على مظهرهم. تم توضيح فئة المخطط في المقال السابق [ هنا ] ([ الترجمة ] عن حبري). للحصول على جيل كامل من المنزل من هذه المجلدات ، انظر الكود المصدري.

النتائج

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


بعض الأمثلة على إنشاء المباني باستخدام هذه الخوارزمية والموضوع المطبق عليها.


( ).

, (3-5), .

, 3D- , MCMC.

, , , . , , .

. ( ).

, 3D- 2D-, .

, 2D- — , .

, , , , , .

MCMC, , ( , ..).

:

• ; , / .
• , , , .
• , !

ملاحظة مهمة: يمكن استخدام خوارزميات التلدين المحاكية و MCMC في مهام مثل "مشكلة البائع المتجول" ، وهي مشكلة NP-hard الشهيرة. حالة النظام عبارة عن طريق ، يمكن أن تنتقل التحولات إلى عقد المسار ، ويمكن أن تكون التكاليف هي المسافة الإجمالية!

طلب روبوتات المهمة

آمل أنه بفضل هذا النظام ، سيكون بإمكان روبوتات المهام إنشاء معارفهم في المستقبل وفقًا لاحتياجاتهم.

إليك مقطع فيديو حول كيفية قيام الروبوت ببناء منزل تم إنشاؤه بواسطة هذه الخوارزمية:


( , ). . ( ) . , . , . - , , .