Recuit Simulé (Simulated Annealing)

Cet algorithme de recherche stochastique est utilisé ici pour résoudre un problème d'optimisation géométrique. L'objectif est de trouver des coordonnées (x, y) maximisant le nombre de points couverts sous certaines contraintes.

#include <iostream>
#include <cmath>
#include <algorithm>
#include <ctime>

using namespace std;

const double REFROIDISSEMENT = 0.996;
const double TEMP_FINALE = 1e-10;

struct Point { double px, py, rayon; };
struct Cible { double cx, cy; };

Point obstacles[15];
Cible cibles[1005];
int nb_obs, nb_cibles, rayon_max;
double meilleur_x, meilleur_y;
int score_max = 0;

double distance_eucl(double x1, double y1, double x2, double y2) {
    return sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
}

int evaluer(double tx, double ty) {
    double r_actuel = (double)rayon_max;
    for (int i = 1; i <= nb_obs; ++i) {
        r_actuel = min(r_actuel, distance_eucl(tx, ty, obstacles[i].px, obstacles[i].py) - obstacles[i].rayon);
    }
    if (r_actuel < 0) return 0;
    int points_couverts = 0;
    for (int i = 1; i <= nb_cibles; ++i) {
        if (distance_eucl(tx, ty, cibles[i].cx, cibles[i].cy) <= r_actuel) points_couverts++;
    }
    return points_couverts;
}

void lancer_recuit() {
    double temp = 6000.0;
    double curr_x = meilleur_x, curr_y = meilleur_y;
    while (temp > TEMP_FINALE) {
        double nx = curr_x + (rand() * 2.0 - RAND_MAX) * temp;
        double ny = curr_y + (rand() * 2.0 - RAND_MAX) * temp;
        int score_actuel = evaluer(nx, ny);
        int delta_e = score_actuel - score_max;
        
        if (delta_e > 0) {
            meilleur_x = nx; meilleur_y = ny;
            curr_x = nx; curr_y = ny;
            score_max = score_actuel;
        } else if (exp(delta_e / temp) > (double)rand() / RAND_MAX) {
            curr_x = nx; curr_y = ny;
        }
        temp *= REFROIDISSEMENT;
    }
}

Recherche Binaire Parallèle (Overall Binary Search)

Technique de diviison et conquête permettant de traiter simultanément plusieurs requêtes de type "k-ième élément" dans un contexte dynamique.

struct Requete {
    int id, type, l, r, k;
};

Requete file_q[300005], q_gauche[300005], q_droite[300005];
int resultats[100005], arbre_bit[100005], limite_n;

void maj_bit(int idx, int v) {
    for (; idx <= limite_n; idx += idx & -idx) arbre_bit[idx] += v;
}

int lire_bit(int idx) {
    int s = 0;
    for (; idx > 0; idx -= idx & -idx) s += arbre_bit[idx];
    return s;
}

void resoudre_parallele(int q_deb, int q_fin, int val_min, int val_max) {
    if (q_deb > q_fin) return;
    if (val_min == val_max) {
        for (int i = q_deb; i <= q_fin; ++i)
            if (file_q[i].type == 2) resultats[file_q[i].id] = val_min;
        return;
    }

    int mil = (val_min + val_max) >> 1;
    int cnt_g = 0, cnt_d = 0;

    for (int i = q_deb; i <= q_fin; ++i) {
        if (file_q[i].type != 2) {
            if (file_q[i].k <= mil) {
                maj_bit(file_q[i].l, file_q[i].type == 0 ? 1 : -1);
                q_gauche[++cnt_g] = file_q[i];
            } else {
                q_droite[++cnt_d] = file_q[i];
            }
        } else {
            int nb_inf = lire_bit(file_q[i].r) - lire_bit(file_q[i].l - 1);
            if (nb_inf >= file_q[i].k) {
                q_gauche[++cnt_g] = file_q[i];
            } else {
                file_q[i].k -= nb_inf;
                q_droite[++cnt_d] = file_q[i];
            }
        }
    }

    for (int i = 1; i <= cnt_g; ++i)
        if (q_gauche[i].type != 2) maj_bit(q_gauche[i].l, q_gauche[i].type == 0 ? -1 : 1);

    for (int i = 1; i <= cnt_g; ++i) file_q[q_deb + i - 1] = q_gauche[i];
    for (int i = 1; i <= cnt_d; ++i) file_q[q_deb + cnt_g + i - 1] = q_droite[i];

    resoudre_parallele(q_deb, q_deb + cnt_g - 1, val_min, mil);
    resoudre_parallele(q_deb + cnt_g, q_fin, mil + 1, val_max);
}

Division et Conquête CDQ (Tri dimensionnel)

L'algorithme de CDQ permet de résoudre des problèmes de dominations de points (partial order) en transformant des dimensions en contraintes temporelles ou spatiales.

struct Element {
    int a, b, c, poids, count;
};

bool compareB(const Element& e1, const Element& e2) {
    return e1.b == e2.b ? e1.c < e2.c : e1.b < e2.b;
}

void traiter_cdq(int L, int R) {
    if (L == R) return;
    int M = (L + R) >> 1;
    traiter_cdq(L, M);
    traiter_cdq(M + 1, R);
    
    sort(elements + L, elements + M + 1, compareB);
    sort(elements + M + 1, elements + R + 1, compareB);
    
    int ptr = L;
    for (int i = M + 1; i <= R; ++i) {
        while (ptr <= M && elements[ptr].b <= elements[i].b) {
            ajouter_bit(elements[ptr].c, elements[ptr].poids);
            ptr++;
        }
        elements[i].count += interroger_bit(elements[i].c);
    }
    for (int k = L; k < ptr; ++k) ajouter_bit(elements[k].c, -elements[k].poids);
}

DP Dynamique (DDP)

Utilisation de la décomposition de chaînes lourdes (HLD) combinée à des matrices de transfert pour maintenir la programmation dynamique sur un arbre lors de mises à jour de nœuds.

struct Matrice {
    long long m[2][2];
    Matrice() { m[0][0] = m[0][1] = m[1][0] = m[1][1] = -1e18; }
    
    friend Matrice operator*(const Matrice& A, const Matrice& B) {
        Matrice res;
        for (int i = 0; i < 2; ++i)
            for (int j = 0; j < 2; ++j)
                for (int k = 0; k < 2; ++k)
                    res.m[i][j] = max(res.m[i][j], A.m[i][k] + B.m[k][j]);
        return res;
    }
};

Matrice g_val[100005]; // Matrice de transfert pour les fils légers
int parent[100005], top[100005], fin_chaine[100005];

void update_noeud(int u, int nv_val) {
    g_val[u].m[1][0] += nv_val - poids_origine[u];
    poids_origine[u] = nv_val;
    
    while (u) {
        Matrice ancienne = interroger_segment(top[u], fin_chaine[top[u]]);
        maj_segment(u, g_val[u]);
        Matrice nouvelle = interroger_segment(top[u], fin_chaine[top[u]]);
        
        u = parent[top[u]];
        if (!u) break;
        
        g_val[u].m[0][0] += max(nouvelle.m[0][0], nouvelle.m[1][0]) - max(ancienne.m[0][0], ancienne.m[1][0]);
        g_val[u].m[0][1] = g_val[u].m[0][0];
        g_val[u].m[1][0] += nouvelle.m[0][0] - ancienne.m[0][0];
    }
}