Skip to content

theoretical_foundations.md

Latest commit

 

History

History
125 lines (86 loc) · 4.39 KB

theoretical_foundations.md

File metadata and controls

125 lines (86 loc) · 4.39 KB

Fondements Théoriques

📚 Article de Référence

Ce moteur s'inspire de l'article de recherche :

"Breaking the Sorting Barrier for Directed Single-Source Shortest Paths"

🎯 Contribution de l'Article

L'article démontre qu'il est possible de résoudre les plus courts chemins (SSSP) sur des graphes dirigés avec poids réels non-négatifs en O(m log^{2/3}n) dans le modèle comparaison-addition, sans trier toutes les options globalement.

Résultat clé : C'est le premier résultat à casser la barrière O(m+n log n) de l'algorithme de Dijkstra sur les graphes creux, montrant que l'algorithme de Dijkstra n'est pas optimal pour SSSP.

🔄 Adaptation au Raisonnement Structurel

Concepts Clés de l'Article

  1. Frontière (S) : Ensemble d'actions/états candidats
  2. Pivots (P) : Actions structurantes à fort impact (P ≪ S)
  3. Bornes (B, B') : Seuils pour évaluer la confiance
  4. Pas de Tri Global : Évite O(n log n)

Application dans Notre Moteur

1. Frontière Décisionnelle

Dans l'article : Ensemble S de candidats pour le plus court chemin.

Dans notre moteur : Ensemble S de nœuds candidats pour la décision.

# Module : 01_core_engine/agent/frontier.py
# Maintient l'ensemble S sans trier tous les nœuds
frontier = Frontier(graph)
frontier.add_candidate(node_id)  # Ajoute à S sans tri

2. Pivots Structurants

Dans l'article : Pivots qui réduisent efficacement la frontière.

Dans notre moteur : Nœuds PROVEN avec forte couverture qui structurent la décision.

# Module : 01_core_engine/agent/pivots.py
# Identifie P ≪ S pour réduire la frontière
pivots = pivot_selector.select_pivots(frontier)  # P petit, impact fort

3. Raisonnement par Bornes

Dans l'article : Bornes B et B' pour évaluer la distance.

Dans notre moteur : Bornes B (seuil) et B' (atteinte) pour évaluer la confiance.

# Module : 01_core_engine/agent/bounded_reasoning.py
# Évalue B' vs B sans explorer toutes les options
if B' >= B:
    decision = "accepted"  # Borne satisfaite
else:
    decision = "partial" or "refused"  # Borne insuffisante

4. Pas de Tri Global

Dans l'article : Évite de trier O(n log n) éléments.

Dans notre moteur : L'agent ne trie pas tous les nœuds, il décide dès qu'une borne est satisfaite.

# Module : 01_core_engine/agent/autonomous_agent.py
# Principe : "Do not sort everything. Decide when enough structure is revealed."
agent = AutonomousAgent(graph)
result = agent.decide(goal="G")  # Décide sans trier tous les nœuds

🔬 Différences et Adaptations

Différences Clés

Aspect Article (SSSP) Notre Moteur (Raisonnement)
Problème Plus court chemin Décision structurelle
Objectif Distance minimale Décision optimale
Frontière Candidats de chemin Candidats de décision
Pivots Nœuds de réduction Signaux structurants
Bornes Distances Confiance/Convergence

Adaptations Nécessaires

  1. Métrique : Distance → Confiance/Convergence
  2. Objectif : Chemin minimal → Décision optimale
  3. Évaluation : Distance réelle → Convergence de signaux
  4. Décision : Chemin unique → Décision (accepted/partial/refused)

📖 Citation

Si vous utilisez ce code dans une publication, veuillez citer :

@article{duan2025breaking,
  title={Breaking the Sorting Barrier for Directed Single-Source Shortest Paths},
  author={Duan, Ran and Mao, Jiayi and Mao, Xiao and Shu, Xinkai and Yin, Longhui},
  journal={arXiv preprint arXiv:2504.17033},
  year={2025},
  url={https://arxiv.org/abs/2504.17033}
}

🔗 Références

🎓 Pour Aller Plus Loin

L'article démontre théoriquement qu'on peut éviter le tri global. Notre implémentation montre comment appliquer ce principe au raisonnement structurel pour créer des agents autonomes efficaces et explicables.