Algorithmes Approximatifs

Introduction

Les algorithmes approximatifs sont des algorithmes qui trouvent des solutions proches de l'optimal pour des problèmes où il est difficile ou impossible de trouver des solutions exactes en temps raisonnable. Ils sont particulièrement utiles pour les problèmes NP-complets, où les solutions exactes nécessitent un temps exponentiel.

Concepts Clés

1. Approximation : Trouver une solution qui est proche de la solution optimale.
2. Ratio d'Approximation : Le rapport entre la valeur de la solution trouvée par l'algorithme approximatif et la valeur de la solution optimale.
3. Performance Garantie : Une mesure de la qualité de l'approximation fournie par l'algorithme.

Exemple : Problème du Voyageur de Commerce (TSP)

Le problème du voyageur de commerce (TSP) est un problème classique d'optimisation combinatoire. Il s'agit de trouver le plus court chemin passant par un ensemble de villes et revenant à la ville de départ.

Algorithme Approximatif pour TSP

Une approche courante pour résoudre approximativement le TSP est d'utiliser un algorithme de parcours minimal.

Heuristique du Plus Proche Voisin

1. Choisir une ville de départ aléatoirement.
2. Visiter la ville la plus proche non visitée.
3. Répéter jusqu'à ce que toutes les villes soient visitées.

Implémentation en JavaScript

function tspNearestNeighbor(graph, start) {
    const n = graph.length;
    const visited = new Array(n).fill(false);
    const path = [];
    let current = start;
    let totalDistance = 0;

    for (let i = 0; i < n - 1; i++) {
        visited[current] = true;
        path.push(current);

        let next = -1;
        let minDistance = Infinity;

        for (let j = 0; j < n; j++) {
            if (!visited[j] && graph[current][j] < minDistance) {
                next = j;
                minDistance = graph[current][j];
            }
        }

        if (next === -1) break;

        totalDistance += minDistance;
        current = next;
    }

    // Retour à la ville de départ
    totalDistance += graph[current][start];
    path.push(start);

    return { path, totalDistance };
}

// Exemple d'utilisation
const graph = [
    [0, 29, 20, 21],
    [29, 0, 15, 17],
    [20, 15, 0, 28],
    [21, 17, 28, 0]
];
const start = 0;
const result = tspNearestNeighbor(graph, start);
console.log(`Chemin : ${result.path}`);
console.log(`Distance totale : ${result.totalDistance}`);

Explication du Code

1. Initialisation : Marque toutes les villes comme non visitées.
2. Choix de la Ville la Plus Proche : À chaque étape, la ville la plus proche non visitée est choisie.
3. Mise à Jour de la Distance Totale : La distance totale est mise à jour à chaque étape.
4. Retour à la Ville de Départ : Après avoir visité toutes les villes, retourne à la ville de départ.

Exemple : Couplage Maximum dans les Graphes

Le couplage maximum dans un graphe est un ensemble d'arêtes sans sommets communs qui est aussi grand que possible.

Algorithme Approximatif pour le Couplage Maximum

Une heuristique simple pour trouver un couplage approximatif est l'algorithme glouton :

1. Trier les arêtes par poids croissant.
2. Ajouter chaque arête au couplage si elle ne partage pas de sommet avec les arêtes déjà ajoutées.

Implémentation en JavaScript

class Graph {
    constructor(vertices) {
        this.V = vertices;
        this.edges = [];
    }

    addEdge(u, v, w) {
        this.edges.push({ u, v, w });
    }

    findMaximumMatching() {
        // Trier les arêtes par poids croissant
        this.edges.sort((a, b) => a.w - b.w);
        const match = new Array(this.V).fill(false);
        const result = [];

        for (let i = 0; i < this.edges.length; i++) {
            const { u, v, w } = this.edges[i];

            // Vérifier si les sommets u et v ne sont pas déjà appariés
            if (!match[u] && !match[v]) {
                match[u] = match[v] = true;
                result.push({ u, v, w });
            }
        }

        return result;
    }
}

// Exemple d'utilisation
const g = new Graph(4);
g.addEdge(0, 1, 1);
g.addEdge(0, 2, 2);
g.addEdge(1, 2, 3);
g.addEdge(1, 3, 4);

const matching = g.findMaximumMatching();
console.log('Couplage Maximum:', matching);

Explication du Code

1. Trier les Arêtes : Les arêtes sont triées par poids croissant.
2. Ajouter les Arêtes au Couplage : Chaque arête est ajoutée au couplage si elle ne partage pas de sommet avec les arêtes déjà ajoutées.

Comparaison et Applications

Problème du Voyageur de Commerce (TSP)

• Problème : Trouver le plus court chemin passant par toutes les villes.
• Application : Optimisation des itinéraires de livraison, planification des circuits touristiques.

Couplage Maximum dans les Graphes

• Problème : Trouver le plus grand ensemble d'arêtes sans sommets communs.
• Application : Assignation des tâches, planification des ressources.

Conclusion

Les algorithmes approximatifs sont des outils puissants pour résoudre des problèmes difficiles en fournissant des solutions proches de l'optimal en temps raisonnable. Ils sont particulièrement utiles pour les problèmes NP-complets où les solutions exactes sont impraticables. Les exemples du problème du voyageur de commerce et du couplage maximum dans les graphes illustrent comment ces algorithmes peuvent être appliqués à des problèmes réels pour obtenir des solutions efficaces.