317 lines
31 KiB
HTML
317 lines
31 KiB
HTML
<!DOCTYPE html>
|
||
<html lang="fr">
|
||
<head>
|
||
<meta charset="utf-8">
|
||
<meta name="viewport" content="width=device-width, initial-scale=1">
|
||
<title>Tanya : un glouton en chaîne pour l’ensemble indépendant</title>
|
||
<style>
|
||
:root{
|
||
color-scheme:light dark;
|
||
--bg:#F3F5F8; --surface:#FFFFFF; --ink:#18212F; --muted:#586377; --line:#D6DBE3; --line2:#B9C1CD;
|
||
--sel:#0E7C7E; --on-sel:#FFFFFF; --ban:#BF422D; --on-ban:#FFFFFF; --blk:#B3BBC8; --add:#6A4FD6; --on-add:#FFFFFF;
|
||
--amber:#E49A12; --focus:#2457D6;
|
||
--font:"Avenir Next","Segoe UI",system-ui,-apple-system,"Helvetica Neue",Arial,sans-serif;
|
||
--mono:ui-monospace,"SF Mono",Menlo,Consolas,monospace;
|
||
}
|
||
@media (prefers-color-scheme:dark){
|
||
:root{
|
||
--bg:#11151C; --surface:#181E28; --ink:#E7EBF2; --muted:#9BA6B8; --line:#2A3342; --line2:#3C485B;
|
||
--sel:#3CB7B9; --on-sel:#0B1718; --ban:#F07F6A; --on-ban:#200D09; --blk:#566176; --add:#A99BFF; --on-add:#150F33;
|
||
--amber:#F2B84B; --focus:#8FB0FF;
|
||
}
|
||
}
|
||
*{box-sizing:border-box}
|
||
html{-webkit-text-size-adjust:100%}
|
||
body{margin:0;background:var(--bg);color:var(--ink);font:17px/1.65 var(--font)}
|
||
.wrap{max-width:1000px;margin:0 auto;padding:0 20px}
|
||
header{padding:56px 0 24px}
|
||
h1{font-size:clamp(2rem,5.4vw,3.5rem);line-height:1.05;letter-spacing:-.025em;font-weight:760;margin:0 0 16px;max-width:15em}
|
||
.lead{font-size:1.15rem;color:var(--muted);max-width:44em;margin:0}
|
||
h2{font-size:1.6rem;line-height:1.2;letter-spacing:-.015em;font-weight:700;margin:0 0 14px}
|
||
section{padding:40px 0;border-top:1px solid var(--line)}
|
||
section.first{border-top:0;padding-top:12px}
|
||
.prose{max-width:66ch}
|
||
.prose p{margin:0 0 14px}
|
||
.prose ol{padding-left:1.3em;margin:0 0 14px}
|
||
.prose li{margin:0 0 12px;padding-left:.2em}
|
||
.prose li>ol,.prose li>ul{margin-top:8px}
|
||
.prose li>ol>li,.prose li>ul>li{margin-bottom:5px}
|
||
dl{margin:0 0 6px;max-width:66ch}
|
||
dt{font-weight:650;margin-top:14px}
|
||
dd{margin:2px 0 0;color:var(--muted)}
|
||
code,var,.m{font-family:var(--mono);font-size:.92em}
|
||
var{font-style:normal}
|
||
.formula{font-size:1.2rem;margin:10px 0 14px;overflow-x:auto;white-space:nowrap}
|
||
.note{color:var(--muted);font-size:.93rem}
|
||
|
||
.demo{background:var(--surface);border:1px solid var(--line);border-radius:10px;padding:14px 16px 16px;margin-top:8px}
|
||
.demo svg{display:block;width:100%;height:auto}
|
||
.legend{display:flex;flex-wrap:wrap;gap:6px 18px;font-size:.88rem;color:var(--muted);margin:6px 0 0;padding:0;list-style:none}
|
||
.legend li{display:flex;align-items:center;gap:7px}
|
||
.dot{width:14px;height:14px;border-radius:50%;display:inline-block;flex:none}
|
||
.dot.n{background:var(--surface);border:1.5px solid var(--ink)}
|
||
.dot.s{background:var(--sel)}.dot.b{background:var(--ban)}.dot.k{background:var(--blk)}.dot.a{background:var(--add)}
|
||
.dot.r1{border:3px solid var(--amber)}.dot.r2{border:2px dashed var(--amber)}
|
||
.step{min-height:8.2em;margin:12px 0 4px}
|
||
.step h3{font-size:1.1rem;margin:0 0 4px;font-weight:680}
|
||
.step p{margin:0;color:var(--muted);max-width:68ch}
|
||
.ctl{display:flex;align-items:center;gap:12px;flex-wrap:wrap}
|
||
button{font:inherit;font-size:.95rem;padding:7px 16px;border-radius:8px;border:1px solid var(--line2);background:var(--bg);color:var(--ink);cursor:pointer}
|
||
button:hover:not(:disabled){border-color:var(--ink)}
|
||
button:disabled{opacity:.4;cursor:default}
|
||
button.go{background:var(--ink);color:var(--bg);border-color:var(--ink)}
|
||
:focus-visible{outline:3px solid var(--focus);outline-offset:2px}
|
||
input[type=range]{flex:1;min-width:140px;accent-color:var(--sel)}
|
||
.cnt{font-size:.9rem;color:var(--muted);min-width:7.5em}
|
||
|
||
#g .edge{stroke:var(--ink);stroke-width:1.2}
|
||
#g .node circle{stroke:var(--ink);stroke-width:1.5}
|
||
#g .node text{font:600 13px var(--font);text-anchor:middle;dominant-baseline:central;fill:var(--ink)}
|
||
#g .st-n circle{fill:var(--surface)}
|
||
#g .st-s circle{fill:var(--sel);stroke:var(--sel)}#g .st-s text{fill:var(--on-sel)}
|
||
#g .st-b circle{fill:var(--ban);stroke:var(--ban)}#g .st-b text{fill:var(--on-ban)}
|
||
#g .st-k circle{fill:var(--blk);stroke:var(--blk)}
|
||
#g .deg{font:500 10px var(--font);fill:var(--muted);text-anchor:start}
|
||
#g .ring{fill:none;stroke:none}
|
||
|
||
.fig{display:block;width:100%;height:auto;background:var(--surface);border:1px solid var(--line);border-radius:10px}
|
||
.fig .edges{fill:none;stroke:var(--ink);stroke-width:.6;opacity:.28}
|
||
.fig .trail{fill:none;stroke:var(--amber);stroke-width:4;stroke-linecap:round;stroke-linejoin:round;opacity:.9}
|
||
.fig .nd circle{stroke:var(--surface);stroke-width:1}
|
||
.fig .sel circle{fill:var(--sel)}.fig .add circle{fill:var(--add)}.fig .ban circle{fill:var(--ban)}.fig .blk circle{fill:var(--blk)}
|
||
.fig .lab text{font:700 12px var(--font);text-anchor:start;dominant-baseline:central;fill:var(--ink);paint-order:stroke;stroke:var(--surface);stroke-width:3px}
|
||
|
||
.tw{overflow-x:auto;margin:8px 0 14px}
|
||
table{border-collapse:collapse;width:100%;min-width:560px;font-size:.95rem;font-variant-numeric:tabular-nums}
|
||
th,td{padding:8px 12px;border-bottom:1px solid var(--line);text-align:right}
|
||
thead th{color:var(--muted);font-weight:600;border-bottom:1px solid var(--line2)}
|
||
tbody th{text-align:left;font-weight:500}
|
||
th:first-child,td:first-child{text-align:left}
|
||
tr.me th,tr.me td{background:var(--surface);font-weight:650}
|
||
footer{padding:28px 0 60px;border-top:1px solid var(--line);color:var(--muted);font-size:.9rem}
|
||
@media (max-width:560px){body{font-size:16px}header{padding-top:36px}.step{min-height:11em}}
|
||
</style>
|
||
</head>
|
||
<body>
|
||
<div class="wrap">
|
||
<header>
|
||
<h1>Tanya : un glouton en chaîne pour l’ensemble indépendant</h1>
|
||
<p class="lead">Dans un graphe aléatoire, on cherche le plus de sommets possible sans qu’aucun soit relié à un autre. Tanya avance de proche en proche, bannit les sommets très connectés pour libérer leurs voisins, puis améliore son résultat par échanges. Voici un exemple, étape par étape.</p>
|
||
</header>
|
||
|
||
<section class="first" aria-labelledby="h-demo">
|
||
<h2 id="h-demo">Un exemple pas à pas sur 12 sommets</h2>
|
||
<div class="demo" id="demo" tabindex="-1">
|
||
<svg id="g" viewBox="0 0 680 410" role="img" aria-label="Graphe de 12 sommets, mis à jour à chaque étape"><g id="edges"></g><g id="nodes"></g></svg>
|
||
<ul class="legend">
|
||
<li><span class="dot n"></span>en jeu (le petit nombre est son nombre de liaisons)</li>
|
||
<li><span class="dot s"></span>approuvé</li>
|
||
<li><span class="dot b"></span>banni</li>
|
||
<li><span class="dot k"></span>bloqué</li>
|
||
<li><span class="dot r1"></span>sommet regardé</li>
|
||
<li><span class="dot r2"></span>candidat</li>
|
||
</ul>
|
||
<div class="step" aria-live="polite"><h3 id="ttl"></h3><p id="txt"></p></div>
|
||
<div class="ctl">
|
||
<button id="prev" type="button">Précédent</button>
|
||
<button id="next" type="button" class="go">Suivant</button>
|
||
<input id="rng" type="range" min="0" value="0" step="1" aria-label="Étape">
|
||
<span class="cnt" id="cnt"></span>
|
||
</div>
|
||
</div>
|
||
<p class="note" style="margin-top:10px">Cette suite d’étapes vient d’une exécution réelle de l’algorithme (règles sûres et échanges désactivés pour garder l’exemple lisible). Les flèches du clavier font aussi avancer.</p>
|
||
</section>
|
||
|
||
<section aria-labelledby="h-pb">
|
||
<h2 id="h-pb">Le problème en bref</h2>
|
||
<dl>
|
||
<dt>Graphe aléatoire G(n, c/n)</dt>
|
||
<dd>n sommets, chaque liaison étant présente avec probabilité c/n. Le nombre c est le degré moyen.</dd>
|
||
<dt>Ensemble indépendant</dt>
|
||
<dd>Un ensemble de sommets où aucun n’est relié à un autre de l’ensemble.</dd>
|
||
<dt><var>I<sub>n</sub></var> et <var>i</var></dt>
|
||
<dd><var>I<sub>n</sub></var> est la taille maximale d’un ensemble indépendant. La proportion <var>I<sub>n</sub> / n</var> tend vers une limite <var>i</var>, qui ne dépend que de c.</dd>
|
||
<dt><var>A<sub>n</sub></var></dt>
|
||
<dd>La taille de l’ensemble que trouve un algorithme. On a toujours <var>A<sub>n</sub> ≤ I<sub>n</sub></var>, et on mesure la qualité par l’écart <var>i − A<sub>n</sub> / n</var>.</dd>
|
||
<dt>Le seuil c = e ≈ 2,718</dt>
|
||
<dd>Pour c < e, les règles simples (prendre un sommet qui a 0 ou 1 liaison) suffisent à résoudre le graphe. Au-delà, les algorithmes simples restent en dessous de <var>i</var>.</dd>
|
||
</dl>
|
||
</section>
|
||
|
||
<section aria-labelledby="h-algo">
|
||
<h2 id="h-algo">L’algorithme en mots</h2>
|
||
<div class="prose">
|
||
<p>Tanya lance plusieurs essais indépendants (20 par défaut) et garde le meilleur. Chaque essai a quatre temps.</p>
|
||
<ol>
|
||
<li><strong>Règles sûres</strong>, appliquées au début puis après chaque pas de la chaîne. Elles ne font jamais perdre l’optimum :
|
||
<ul>
|
||
<li>un sommet à 0 ou 1 liaison est pris (il entre dans la sélection, ses voisins sortent du jeu) ;</li>
|
||
<li>un sommet à 2 liaisons dont les deux voisins sont reliés (triangle) est pris ;</li>
|
||
<li>domination : si tous les voisins d’un sommet v sont aussi voisins d’un voisin u de v (v et u compris), on bannit u.</li>
|
||
</ul>
|
||
</li>
|
||
<li><strong>La chaîne.</strong>
|
||
<ol type="a">
|
||
<li>On part d’un sommet v de degré maximal (égalités tranchées par numéro au premier essai, au hasard ensuite). Ses voisins sont les candidats, et v est le sommet à bannir.</li>
|
||
<li>Parmi les candidats, on garde w, celui qui a le moins de liaisons.</li>
|
||
<li>On bannit le sommet à bannir : il sort du jeu sans être choisi, et ses voisins perdent une liaison.</li>
|
||
<li>Si w a alors moins de 2 liaisons, il est approuvé : il entre dans la sélection et son éventuel voisin restant est bloqué. La chaîne repart des voisins encore en jeu de ce sommet bloqué, sans nouveau bannissement.</li>
|
||
<li>Sinon, w devient le sommet courant : ses voisins sont les nouveaux candidats et c’est lui qu’on bannira au pas suivant.</li>
|
||
<li>Sans candidat, on repart d’un autre sommet de degré maximal. Un sommet isolé est approuvé directement.</li>
|
||
</ol>
|
||
</li>
|
||
<li><strong>Reprise.</strong> Certains sommets bannis n’ont finalement aucun voisin choisi. On les ajoute, ce qui rend la sélection maximale.</li>
|
||
<li><strong>Échanges</strong> (c’est ici que l’algorithme revient sur des choix) :
|
||
<ul>
|
||
<li>échange 1-2 : on retire un sommet choisi pour en ajouter deux libres, non reliés entre eux ;</li>
|
||
<li>échange 2-3 : un sommet non choisi touche exactement deux sommets choisis a et b. On retire a et b, et on ajoute trois sommets non reliés entre eux, pris parmi ceux qui ne touchaient que a ou b.</li>
|
||
</ul>
|
||
On répète jusqu’à ce qu’aucun échange ne marche.
|
||
</li>
|
||
</ol>
|
||
<p>Le résultat est toujours un ensemble indépendant valide et maximal. Pour c < e, les règles sûres vident à elles seules le graphe et l’algorithme atteint <var>i</var>. Pour c > e, il reste des sommets de degré au moins 2 : c’est le bannissement et les échanges qui travaillent.</p>
|
||
</div>
|
||
</section>
|
||
|
||
<section aria-labelledby="h-100">
|
||
<h2 id="h-100">Sur 100 sommets</h2>
|
||
<p class="prose">Graphe aléatoire de 100 sommets et 267 liaisons (c = 5), premier essai. Tanya choisit 44 sommets, soit l’optimum exact. Min-degré en trouve 41.</p>
|
||
<svg class="fig" viewBox="0 0 680 490" role="img" aria-labelledby="t100 d100"><title id="t100">Graphe de 100 sommets après Tanya</title><desc id="d100">Sommets choisis par la chaîne, ajoutés ensuite, bannis ou bloqués, avec le premier trajet de la chaîne en orange.</desc><path class="edges" d="M364 377L335 460M364 377L228 381M364 377L445 318M364 377L364 331M364 377L398 285M364 377L301 366M364 377L237 344M364 377L517 396M364 377L268 333M364 377L403 387M441 261L431 156M441 261L398 285M441 261L500 261M441 261L337 275M441 261L339 384M441 261L387 194M441 261L545 276M441 261L487 173M525 236L455 184M525 236L337 275M525 236L619 239M525 236L501 195M525 236L640 202M525 236L479 302M401 108L457 218M401 108L243 155M401 108L353 169M401 108L517 109M625 302L581 251M625 302L485 350M625 302L509 248M625 302L545 276M571 136L620 194M571 136L575 209M571 136L448 198M571 136L487 173M571 136L533 63M159 283L329 304M159 283L163 196M159 283L299 272M313 236L455 184M313 236L410 166M313 236L364 331M313 236L199 218M313 236L205 244M313 236L268 333M313 236L402 257M543 401L364 331M543 401L567 310M455 184L410 166M455 184L620 194M455 184L266 139M455 184L551 338M335 460L339 384M320 376L454 426M320 376L191 362M320 376L246 405M320 376L380 349M320 376L378 247M320 376L307 315M320 376L403 387M252 285L398 285M252 285L337 275M252 285L378 247M252 285L307 315M252 285L299 272M447 380L500 261M447 380L380 349M447 380L307 315M447 380L513 349M228 381L299 272M431 156L398 285M431 156L575 209M431 156L309 140M431 156L322 90M440 121L410 166M440 121L457 218M440 121L305 173M440 121L501 195M440 121L322 90M440 121L533 63M440 121L337 53M440 121L517 109M511 294L329 304M511 294L457 218M511 294L619 239M511 294L513 349M511 294L567 310M410 166L347 225M410 166L378 247M410 166L309 140M410 166L498 100M410 166L575 168M410 166L353 169M410 166L487 173M410 166L341 133M581 251L457 218M581 251L485 350M581 251L402 257M445 318L380 349M445 318L485 350M445 318L448 198M445 318L509 248M445 318L403 387M445 318L356 251M364 331L301 366M364 331L377 434M364 331L172 231M364 331L509 248M454 426L589 343M454 426L339 384M454 426L517 396M191 362L337 275M620 194L575 168M620 194L545 276M199 218L219 313M199 218L347 225M199 218L243 87M199 218L192 287M199 218L163 196M589 343L471 200M589 343L567 310M398 285L500 261M398 285L307 315M398 285L387 194M398 285L402 257M398 285L479 302M500 261L323 197M500 261L501 195M500 261L522 314M500 261L620 174M500 261L479 302M471 200L255 181M471 200L387 194M471 200L287 197M471 200L545 276M471 200L353 169M471 200L640 202M471 200L341 133M329 304L457 218M329 304L301 366M329 304L270 231M329 304L222 324M329 304L237 344M329 304L268 333M329 304L402 257M329 304L299 272M329 304L403 387M457 218L567 310M457 218L373 123M219 313L246 405M219 313L270 255M219 313L380 349M219 313L307 315M219 313L339 384M219 313L227 202M246 405L301 366M246 405L403 387M270 255L378 247M270 255L307 315M270 255L172 137M270 255L479 302M270 255L227 202M575 209L501 195M575 209L522 314M575 209L575 168M575 209L545 276M301 366L232 455M301 366L337 275M301 366L394 307M255 181L309 140M255 181L237 344M255 181L322 90M270 231L448 198M270 231L402 257M270 231L299 272M270 231L356 251M270 231L117 243M380 349L377 434M380 349L479 302M380 349L299 272M380 349L551 338M347 225L378 247M347 225L307 315M347 225L522 314M414 73L243 87M414 73L448 198M414 73L517 109M337 275L305 173M337 275L268 333M337 275L353 169M337 275L299 272M222 324L394 307M222 324L299 272M378 247L448 198M378 247L309 140M378 247L305 173M378 247L513 349M307 315L394 307M307 315L412 338M307 315L205 244M307 315L268 333M394 307L287 197M394 307L509 248M394 307L545 276M485 350L192 287M485 350L522 314M243 87L322 90M412 338L567 310M412 338L479 302M412 338L299 272M412 338L356 251M448 198L387 194M448 198L619 239M339 384L237 344M387 194L323 197M387 194L243 155M387 194L402 257M387 194L356 251M387 194L373 123M583 30L517 109M309 140L287 197M309 140L203 113M323 197L243 155M323 197L299 272M323 197L341 133M243 155L205 244M243 155L172 231M40 182L163 196M192 287L268 333M192 287L227 202M192 287L117 243M172 137L322 90M305 173L227 202M305 173L341 133M163 196L205 244M163 196L266 139M163 196L203 113M163 196L299 272M163 196L117 243M205 244L356 251M205 244L117 243M633 271L501 195M633 271L567 310M633 271L479 302M501 195L498 100M501 195L620 174M501 195L299 272M266 139L172 231M266 139L337 53M266 139L227 202M266 139L341 133M266 139L373 123M517 396L545 276M203 113L373 123M522 314L403 387M513 349L567 310M402 257L356 251M509 248L487 173M509 248L517 109M575 168L545 276M545 276L479 302M353 169L227 202M487 173L356 251M487 173L373 123M620 174L640 202M227 202L341 133"/><polyline class="trail" points="410,166 498,100 501,195 633,271 567,310 543,401"/><g class="nd blk"><circle cx="364" cy="377" r="8"/><circle cx="625" cy="302" r="8"/><circle cx="571" cy="136" r="8"/><circle cx="455" cy="184" r="8"/><circle cx="320" cy="376" r="8"/><circle cx="431" cy="156" r="8"/><circle cx="440" cy="121" r="8"/><circle cx="581" cy="251" r="8"/><circle cx="364" cy="331" r="8"/><circle cx="454" cy="426" r="8"/><circle cx="199" cy="218" r="8"/><circle cx="398" cy="285" r="8"/><circle cx="500" cy="261" r="8"/><circle cx="471" cy="200" r="8"/><circle cx="329" cy="304" r="8"/><circle cx="270" cy="255" r="8"/><circle cx="301" cy="366" r="8"/><circle cx="255" cy="181" r="8"/><circle cx="380" cy="349" r="8"/><circle cx="414" cy="73" r="8"/><circle cx="394" cy="307" r="8"/><circle cx="339" cy="384" r="8"/><circle cx="387" cy="194" r="8"/><circle cx="309" cy="140" r="8"/><circle cx="243" cy="155" r="8"/><circle cx="192" cy="287" r="8"/><circle cx="163" cy="196" r="8"/><circle cx="501" cy="195" r="8"/><circle cx="513" cy="349" r="8"/><circle cx="575" cy="168" r="8"/><circle cx="487" cy="173" r="8"/><circle cx="640" cy="202" r="8"/><circle cx="356" cy="251" r="8"/><circle cx="117" cy="243" r="8"/><circle cx="517" cy="109" r="8"/><circle cx="373" cy="123" r="8"/></g><g class="nd ban"><circle cx="313" cy="236" r="8"/><circle cx="410" cy="166" r="8"/><circle cx="445" cy="318" r="8"/><circle cx="457" cy="218" r="8"/><circle cx="246" cy="405" r="8"/><circle cx="270" cy="231" r="8"/><circle cx="337" cy="275" r="8"/><circle cx="378" cy="247" r="8"/><circle cx="307" cy="315" r="8"/><circle cx="619" cy="239" r="8"/><circle cx="266" cy="139" r="8"/><circle cx="522" cy="314" r="8"/><circle cx="567" cy="310" r="8"/><circle cx="545" cy="276" r="8"/><circle cx="353" cy="169" r="8"/><circle cx="479" cy="302" r="8"/><circle cx="322" cy="90" r="8"/><circle cx="299" cy="272" r="8"/><circle cx="227" cy="202" r="8"/><circle cx="341" cy="133" r="8"/></g><g class="nd sel"><circle cx="525" cy="236" r="8"/><circle cx="159" cy="283" r="8"/><circle cx="543" cy="401" r="8"/><circle cx="335" cy="460" r="8"/><circle cx="447" cy="380" r="8"/><circle cx="228" cy="381" r="8"/><circle cx="511" cy="294" r="8"/><circle cx="191" cy="362" r="8"/><circle cx="620" cy="194" r="8"/><circle cx="589" cy="343" r="8"/><circle cx="219" cy="313" r="8"/><circle cx="575" cy="209" r="8"/><circle cx="232" cy="455" r="8"/><circle cx="222" cy="324" r="8"/><circle cx="377" cy="434" r="8"/><circle cx="243" cy="87" r="8"/><circle cx="412" cy="338" r="8"/><circle cx="583" cy="30" r="8"/><circle cx="237" cy="344" r="8"/><circle cx="323" cy="197" r="8"/><circle cx="40" cy="182" r="8"/><circle cx="172" cy="137" r="8"/><circle cx="205" cy="244" r="8"/><circle cx="287" cy="197" r="8"/><circle cx="517" cy="396" r="8"/><circle cx="268" cy="333" r="8"/><circle cx="203" cy="113" r="8"/><circle cx="498" cy="100" r="8"/><circle cx="620" cy="174" r="8"/><circle cx="533" cy="63" r="8"/><circle cx="551" cy="338" r="8"/><circle cx="337" cy="53" r="8"/></g><g class="nd add"><circle cx="441" cy="261" r="8"/><circle cx="401" cy="108" r="8"/><circle cx="252" cy="285" r="8"/><circle cx="347" cy="225" r="8"/><circle cx="485" cy="350" r="8"/><circle cx="448" cy="198" r="8"/><circle cx="305" cy="173" r="8"/><circle cx="633" cy="271" r="8"/><circle cx="172" cy="231" r="8"/><circle cx="402" cy="257" r="8"/><circle cx="509" cy="248" r="8"/><circle cx="403" cy="387" r="8"/></g><g class="lab"><text x="421" y="155">18</text><text x="509" y="89">75</text><text x="512" y="184">68</text><text x="644" y="260">67</text><text x="578" y="299">81</text><text x="554" y="390">8</text></g></svg>
|
||
<ul class="legend" style="margin-top:10px">
|
||
<li><span class="dot s"></span>choisi par la chaîne (32)</li>
|
||
<li><span class="dot a"></span>ajouté après : reprise ou échange (12)</li>
|
||
<li><span class="dot b"></span>banni (20)</li>
|
||
<li><span class="dot k"></span>bloqué (36)</li>
|
||
</ul>
|
||
<div class="prose" style="margin-top:14px">
|
||
<p>Le trait orange est le premier départ. Le sommet 18 a 11 liaisons : c’est le maximum, on le bannit. Son voisin 75 n’a plus qu’une liaison, il est approuvé et bloque 68. La chaîne repart des voisins de 68, bannit 67 puis 81, et approuve 8. Le sommet 67 est ensuite récupéré par la reprise, puisqu’il n’a plus de voisin choisi.</p>
|
||
<p>La chaîne ne se lance que 3 fois sur ce graphe, car les règles sûres font une grande partie du travail. Deux échanges 2-3 portent la sélection de 42 à 44 sommets.</p>
|
||
</div>
|
||
</section>
|
||
|
||
<section aria-labelledby="h-res">
|
||
<h2 id="h-res">Résultats à n = 1000 et c = 4</h2>
|
||
<p class="prose">Trois graphes (graines 1, 2 et 3), chacun avec environ 2 000 liaisons et 97 à 99 % des sommets dans la même composante connexe. Les valeurs sont le nombre de sommets sélectionnés.</p>
|
||
<div class="tw"><table>
|
||
<thead><tr><th>Méthode</th><th>Graphe 1</th><th>Graphe 2</th><th>Graphe 3</th><th>Moyenne</th><th><var>A<sub>n</sub> / n</var></th><th>Temps</th></tr></thead>
|
||
<tbody><tr><th scope="row">min-degré</th><td>461</td><td>474</td><td>468</td><td>467,7</td><td>0,468</td><td>< 0,01 s</td></tr><tr><th scope="row">hybride</th><td>469</td><td>477</td><td>468</td><td>471,3</td><td>0,471</td><td>< 0,01 s</td></tr><tr><th scope="row">hybride + échanges 1-2</th><td>469</td><td>477</td><td>470</td><td>472,0</td><td>0,472</td><td>0,01 s</td></tr><tr class="me"><th scope="row"><strong>Tanya</strong> (20 essais)</th><td>469</td><td>475</td><td>470</td><td>471,3</td><td>0,471</td><td>0,55 s</td></tr><tr><th scope="row">exact (60 s, non terminé)</th><td>471</td><td>479</td><td>470</td><td>473,3</td><td>0,473</td><td>60 s</td></tr><tr><th scope="row">ILS (5 s)</th><td>471</td><td>480</td><td>473</td><td>474,7</td><td>0,475</td><td>5,01 s</td></tr></tbody>
|
||
</table></div>
|
||
<div class="prose">
|
||
<p>L’exact (programmation linéaire en nombres entiers) a atteint sa limite de 60 secondes sur les trois graphes : son résultat est une borne basse de <var>I<sub>n</sub></var>, pas une valeur prouvée optimale. L’ILS, en 5 secondes, égale ou dépasse l’exact sur les trois graphes (il le dépasse sur deux). La meilleure valeur connue est donc celle de l’ILS, environ 0,475, et Tanya en est à environ 0,003.</p>
|
||
<p>Tanya passe devant min-degré et rejoint l’hybride en une demi-seconde, mais reste un peu sous l’ILS, qui défait des choix de façon répétée sur toute sa durée.</p>
|
||
</div>
|
||
<h3 style="font-size:1.15rem;margin:22px 0 4px">Ce que chaque étape apporte</h3>
|
||
<div class="tw"><table>
|
||
<thead><tr><th>Version</th><th>Graphe 1</th><th>Graphe 2</th><th>Graphe 3</th><th>Moyenne</th><th>Temps</th></tr></thead>
|
||
<tbody><tr><th scope="row">chaîne + règles sûres, sans reprise ni échanges</th><td>413</td><td>422</td><td>409</td><td>414,7</td><td>0,19 s</td></tr><tr><th scope="row">+ reprise des sommets libres</th><td>456</td><td>464</td><td>460</td><td>460,0</td><td>0,21 s</td></tr><tr><th scope="row">+ échanges 1-2 et 2-3 (1 essai)</th><td>464</td><td>475</td><td>463</td><td>467,3</td><td>0,02 s</td></tr><tr><th scope="row">20 essais</th><td>469</td><td>475</td><td>472</td><td>472,0</td><td>0,47 s</td></tr><tr><th scope="row">100 essais</th><td>470</td><td>478</td><td>472</td><td>473,3</td><td>2,26 s</td></tr></tbody>
|
||
</table></div>
|
||
<div class="prose">
|
||
<p>La chaîne seule, sans reprise, est faible (environ 415). La reprise et les échanges font presque tout le reste. Passer de 20 à 100 essais ne gagne plus que 1,3 sommet en moyenne : les essais se ressemblent trop, il faut améliorer la construction plutôt que les répéter.</p>
|
||
<p class="note">Tanya varie de 1 à 2 sommets selon la graine du hasard (les deux tableaux ont été tirés avec des graines différentes). Trois graphes seulement : ce sont des ordres de grandeur, pas une étude statistique.</p>
|
||
</div>
|
||
</section>
|
||
|
||
<section aria-labelledby="h-th">
|
||
<h2 id="h-th">Ce que l’on sait de <var>i</var>(c)</h2>
|
||
<div class="prose">
|
||
<p>Pour c < e, on a une formule exacte avec la fonction W de Lambert (<var>W e<sup>W</sup> = c</var>) :</p>
|
||
<div class="formula"><var>i(c) = (2·W(c) + W(c)²) / (2c)</var></div>
|
||
<p>Mesure avec la suppression de feuilles seule (règle « 0 ou 1 liaison »), à n = 100 000, qui est exacte dans ce régime :</p>
|
||
</div>
|
||
<div class="tw"><table style="min-width:380px">
|
||
<thead><tr><th>c</th><th>Mesuré</th><th>Formule</th></tr></thead>
|
||
<tbody>
|
||
<tr><th scope="row">0,5</th><td>0,8277</td><td>0,8272</td></tr>
|
||
<tr><th scope="row">1</th><td>0,7293</td><td>0,7280</td></tr>
|
||
<tr><th scope="row">2</th><td>0,6094</td><td>0,6080</td></tr>
|
||
<tr><th scope="row">2,5</th><td>0,5681</td><td>0,5672</td></tr>
|
||
</tbody>
|
||
</table></div>
|
||
<div class="prose">
|
||
<p>Proche de e (à c = 2,7), il reste à n fini un noyau de sommets que cette règle ne traite pas, et la mesure s’écarte un peu de la formule (0,5499 contre 0,5531).</p>
|
||
<p>Pour c > e, il n’y a pas de formule simple. Les algorithmes gloutons classiques atteignent environ n·ln(c)/c sommets, alors que le maximum est d’environ 2n·ln(c)/c pour c grand. Combler cet écart avec un algorithme rapide est le sujet ouvert.</p>
|
||
</div>
|
||
</section>
|
||
|
||
<section aria-labelledby="h-next">
|
||
<h2 id="h-next">Pistes d’amélioration</h2>
|
||
<div class="prose">
|
||
<p>Ce sont des hypothèses, non testées à ce jour.</p>
|
||
<ol>
|
||
<li><strong>Repliement des sommets de degré 2.</strong> Si v a deux voisins u et w non reliés, on fusionne les trois en un seul sommet, et la solution gagne un sommet au dépliage. C’est la règle exacte la plus forte après « 0 ou 1 liaison ».</li>
|
||
<li><strong>Échanges 1-1 sur plateau.</strong> Permuter un sommet choisi avec un voisin non choisi sans changer la taille, pour ouvrir de nouveaux échanges 1-2.</li>
|
||
<li><strong>Meilleur arbitrage des égalités.</strong> Préférer, à degré égal, le voisin dont les voisins sont les plus connectés.</li>
|
||
<li><strong>Départs plus variés.</strong> Choisir le sommet de départ au hasard parmi les sommets de degré presque maximal.</li>
|
||
</ol>
|
||
</div>
|
||
</section>
|
||
|
||
<footer>Code : fonction <code>m_chaine</code> du dossier <code>er_graphes</code> (<code>heuristiques.py</code>). Page autonome : aucun fichier ni connexion n’est nécessaire pour l’ouvrir.</footer>
|
||
</div>
|
||
|
||
<script>
|
||
const N=[[150,200],[270,50],[270,130],[270,210],[270,290],[270,370],[430,40],[430,110],[430,180],[430,250],[430,320],[600,350]];
|
||
const E=[[0,1],[0,2],[0,3],[0,4],[0,5],[1,6],[1,7],[2,3],[2,8],[2,9],[3,4],[3,9],[4,5],[4,10],[5,10],[5,11],[6,7],[7,8],[8,9],[9,10],[10,11]];
|
||
const S=[
|
||
{s:"nnnnnnnnnnnn",cur:[],cand:[],pick:[],t:"Le graphe",d:"12 sommets. On veut en choisir un maximum, sans liaison entre deux sommets choisis. Le sommet 0 a 5 liaisons : c’est le plus connecté."},
|
||
{s:"nnnnnnnnnnnn",cur:[0],cand:[],pick:[],t:"Départ",d:"On part d’un sommet de degré maximal : 0, avec 5 liaisons."},
|
||
{s:"nnnnnnnnnnnn",cur:[0],cand:[2,3,4,5],pick:[1],t:"Voisin le moins connecté",d:"Voisins de 0 : 1, 2, 3, 4 et 5. Le moins connecté est 1, avec 3 liaisons (0, 6 et 7). Les autres en ont 4."},
|
||
{s:"bnnnnnnnnnnn",cur:[1],cand:[],pick:[],t:"On bannit 0",d:"0 sort du graphe sans être choisi. 1 tombe à 2 liaisons (6 et 7) : ce n’est pas moins de 2, donc 1 n’est pas approuvé. Il devient le sommet courant."},
|
||
{s:"bbnnnnnnnnnn",cur:[],cand:[7],pick:[6],t:"Suite depuis 1",d:"Voisins de 1 : 6 (2 liaisons) et 7 (3 liaisons). On garde 6. On bannit 1, et 6 tombe à 1 liaison."},
|
||
{s:"bbnnnnsknnnn",cur:[6],cand:[8],pick:[],t:"6 approuvé",d:"6 a 1 liaison, moins de 2 : on l’approuve. Son voisin 7 est bloqué. La chaîne repart des voisins de 7 qui restent en jeu : 8."},
|
||
{s:"bbnnnnsknnnn",cur:[8],cand:[],pick:[],t:"8 : pas approuvé",d:"Sans 7, 8 a 2 liaisons (2 et 9) : pas moins de 2, donc pas approuvé. Il devient le sommet courant. Pas de bannissement ici, car 7 est déjà sorti."},
|
||
{s:"bbnnnnskbnnn",cur:[],cand:[9],pick:[2],t:"On bannit 8",d:"Voisins de 8 : 2 (3 liaisons) et 9 (4 liaisons). On garde 2. Une fois 8 banni, 2 tombe à 2 liaisons (3 et 9) : pas approuvé."},
|
||
{s:"bbbnnnskbnnn",cur:[],cand:[9],pick:[3],t:"On bannit 2",d:"Voisins de 2 : 3 et 9, tous deux à 3 liaisons. Égalité : on prend le plus petit numéro, 3. Une fois 2 banni, 3 tombe à 2 liaisons (4 et 9) : pas approuvé."},
|
||
{s:"bbbbnnskbskn",cur:[9],cand:[4,5,11],pick:[],t:"On bannit 3, puis 9 est approuvé",d:"Voisins de 3 : 4 (3 liaisons) et 9 (2 liaisons). On garde 9. Une fois 3 banni, 9 tombe à 1 liaison : approuvé. Son voisin 10 est bloqué, et la chaîne repart de ses voisins restants : 4, 5 et 11."},
|
||
{s:"bbbbskskbskn",cur:[4],cand:[11],pick:[],t:"4 approuvé",d:"4 et 11 ont 1 liaison, 5 en a 2. Égalité entre 4 et 11 : on prend 4. Il est approuvé et bloque 5. La chaîne repart des voisins de 5 qui restent : 11."},
|
||
{s:"bbbbskskbsks",cur:[11],cand:[],pick:[],t:"11 approuvé, fin de chaîne",d:"11 n’a plus aucune liaison : on l’approuve. Il ne reste aucun sommet en jeu, la chaîne est finie."},
|
||
{s:"bbbbskskbsks",cur:[],cand:[],pick:[],t:"Résultat : 4 sommets",d:"Choisis : 4, 6, 9 et 11. La reprise cherche un sommet banni (0, 1, 2, 3 ou 8) sans voisin choisi : il n’y en a pas, rien à ajouter. L’optimum de ce graphe est aussi 4."}
|
||
];
|
||
const NS="http://www.w3.org/2000/svg";
|
||
function mk(tag,at,par){const e=document.createElementNS(NS,tag);for(const k in at)e.setAttribute(k,at[k]);par.appendChild(e);return e;}
|
||
const eg=document.getElementById("edges"),ng=document.getElementById("nodes");
|
||
const lines=E.map(function(p){return mk("line",{class:"edge",x1:N[p[0]][0],y1:N[p[0]][1],x2:N[p[1]][0],y2:N[p[1]][1]},eg);});
|
||
const adj=N.map(function(){return [];});
|
||
E.forEach(function(p){adj[p[0]].push(p[1]);adj[p[1]].push(p[0]);});
|
||
const nodes=N.map(function(p,i){
|
||
const ring=mk("circle",{class:"ring",cx:p[0],cy:p[1],r:23},ng);
|
||
const g=mk("g",{class:"node"},ng);
|
||
mk("circle",{cx:p[0],cy:p[1],r:17},g);
|
||
const t=mk("text",{x:p[0],y:p[1]},g);t.textContent=i;
|
||
const dg=mk("text",{class:"deg",x:p[0]+15,y:p[1]-18},ng);
|
||
return {ring:ring,g:g,dg:dg};
|
||
});
|
||
let k=0;
|
||
const el=function(id){return document.getElementById(id);};
|
||
const rng=el("rng");rng.max=S.length-1;
|
||
function render(){
|
||
const st=S[k];
|
||
nodes.forEach(function(n,i){
|
||
const s=st.s[i];
|
||
n.g.setAttribute("class","node st-"+s);
|
||
const isCur=st.cur.indexOf(i)>=0||st.pick.indexOf(i)>=0,isCand=st.cand.indexOf(i)>=0;
|
||
n.ring.style.stroke=(isCur||isCand)?"var(--amber)":"none";
|
||
n.ring.style.strokeWidth=isCur?"3.5":"2.5";
|
||
n.ring.style.strokeDasharray=(isCand&&!isCur)?"5 4":"none";
|
||
if(s==="n"){n.dg.textContent=adj[i].filter(function(j){return st.s[j]==="n";}).length;}else{n.dg.textContent="";}
|
||
});
|
||
E.forEach(function(p,i){lines[i].style.opacity=(st.s[p[0]]==="n"&&st.s[p[1]]==="n")?"0.5":"0.1";});
|
||
el("ttl").textContent=st.t;el("txt").textContent=st.d;
|
||
el("cnt").textContent="Étape "+k+" sur "+(S.length-1);
|
||
el("prev").disabled=k===0;el("next").disabled=k===S.length-1;
|
||
rng.value=k;
|
||
}
|
||
function go(d){k=Math.max(0,Math.min(S.length-1,k+d));render();}
|
||
el("prev").onclick=function(){go(-1);};
|
||
el("next").onclick=function(){go(1);};
|
||
rng.oninput=function(){k=parseInt(rng.value,10);render();};
|
||
el("demo").addEventListener("keydown",function(e){
|
||
if(e.target===rng)return;
|
||
if(e.key==="ArrowRight"){go(1);e.preventDefault();}
|
||
if(e.key==="ArrowLeft"){go(-1);e.preventDefault();}
|
||
});
|
||
render();
|
||
</script>
|
||
</body>
|
||
</html>
|