Backtracking

backtracking هو أسلوب يستكشف جميع الحلول الممكنة لمشكلة معينة. يقوم الـbacktracking ببناء الحلول خطوة بخطوة يتراجع عن الخطوات كلما انتهت من استكشاف اتجاه معين.

كيف تعمل

تبدأ خوارزمية backtracking بحل فارغ. في كل خطوة، تحاول الخوارزمية كل الطرق الممكنة. بعد استكشاف جميع الطرق، تتراجع الخوارزمية إلى الخطوة السابقة عن طريق التراجع عن اخر خطوة. يمكن تلخيص الخوارزمية كما يلي:

1. ابدأ بحل فارغ.
2. قم بتمديد الحل خطوة بخطوة.
3. استكشف بشكل متكرر جميع الطرق المختلفة التي يمكن أن يُبنى بها الحل.
4. تراجع عن آخر خطوة تم تنفيذها.

توليد المجموعات الجزئية

لتوليد جميع المجموعات الجزئية لمصفوفة باستخدام backtracking، ابدأ بحل فارغ. في كل خطوة، لديك الموقع i حاول كلا الاحتمالين: إضافة a[i] في المجموعة الجزئية أو استبعاده. بعد استكشاف كل طريقة، تراجع عن آخر تغيير. عندما يصبح i خارج المصفوفة، اطبع المجموعة الجزئية الحالية. مثال على كود يطبع جميع المجموعات الجزئية الممكنة كما يلي:

#include <iostream>
#include <vector>

using namespace std;

int n = 3;
int a[3] = {5, 3, 1};
vector<int> v;

void backtracking(int i) {

    // تم المرور على جميع العناصر، اطبع المجموعة الجزئية الحالية i == n إذا 
    if (i == n) {
        cout << "subset: ";
        for (int j = 0; j < v.size(); j++) {
            cout << v[j] << ' ';
        }
        cout << "\n";
        return;
    }

    // إلى المجموعة الجزئية a[i] حاول إضافة
    v.push_back(a[i]);   // v أضفها إلى 
    backtracking(i + 1); // v موجودة في  a[i] حاول جميع الحلول حيث 

    // من المجموعة الجزئية a[i] حاول إستبعاد
    v.pop_back();        // a[i] تراجع عن إضافة
    backtracking(i + 1); // v غير موجودة في  a[i] حاول جميع الحلول حيث 

    // لا نحتاج لأي تراجع لأننا لم نغيز شيء في آخر خطوة
}

int main() {

    backtracking(0);
}

مثال على مشكلة

Apple Division

Apple Division

CSES

لديك مصفوفة a من \(n\) عنصر. نريد تقسيم العناصر إلى مجموعتين بحيث يكون الفرق بين مجموع كل المجموعتين صغيرًا أصغر ما يمكن. المطلوب عو طباعة أصغر فرق ممكن.

Solution

سنستخدم backtracking لتجربة كل التقسيمات الممكنة وطباعة الحل الذي يعطي أصغر فرق.

#include <iostream>

using namespace std;

int n;
int a[20];
long long sum1 = 0;         // مجموع المجموعة الإولى
long long sum2 = 0;         // مجموع المجموعة الإولى
long long ans = 2000000000; // الحل رقم كبير جدا مبدئيا

void backtracking(int i) {
    // حدث الحل الحالي i == n إذا
    if (i == n) {
        ans = min(ans, abs(sum1 - sum2));
        return;
    }
    //حاول جميع الاختيارات الممكنة

    // للمجموعة الأولى a[i] حاول إضافة
    sum1 += a[i];
    backtracking(i + 1);
    sum1 -= a[i];

    // للمجموعة الثانية a[i] حاول إضافة
    sum2 += a[i];
    backtracking(i + 1);
    sum2 -= a[i];

}

int main() {

    cin >> n;

    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    backtracking(0);

    cout << ans << "\n";
}