Quelle est la différence entre le flux maximal et le flux maximum?

Question

Quelle est la différence entre le flux maximal et le débit maximal.Je lis ces termes tout en travaillant sur des algorithmes Ford Fulkerson et ils sont assez déroutants.J'ai essayé sur Internet, mais je n'ai pas pu obtenir une réponse raisonnable.Je crois que le débit maximal est assez clair car cela signifie une quantité maximale d'écoulement pouvant être transférée de la source à l'évier dans un réseau, mais quel est exactement le flux maximal.

Veuillez répondre en termes de laïcs si possible.

merci.

Answer 1

Réponse courte:

Pensez au sommet des montagnes, Chacun d'entre eux est une solution maximale, il n'y a pas de place à proximité qui est plus élevé qu'eux-mêmes, Mais seul le sommet de la montagne Everest a la hauteur maximale et est donc la solution maximale.

Réponse plus longue:

Permettez-moi d'l'expliquer en termes géométriques: Pensez à un avion (par exemple une grande paix de papier). Chaque point de l'avion est une solution possible pour le problème. La hauteur de chaque point est la qualité de la solution correspondant à ce point. En optimisation, nous voulons trouver la solution optimale, c'est-à-dire le point le plus élevé de l'avion. Une idée de trouver la solution optimale est de commencer par une solution possible dans l'avion et Améliorez-le petit à petit: Chaque fois que nous passons d'un point à un point près de celui qui est plus élevé. Ceci s'appelle un algorithme de recherche local. Ce processus s'arrête lorsque nous atteignons un point supérieur à tous les points à proximité. Un tel point s'appelle un optimum local. La solution correspondante s'appelle Maximal car nous ne pouvons pas augmenter la qualité de la solution en passant à une solution à proximité. Cependant, une solution maximale n'a pas besoin d'être la solution optimale, Il est optimal par rapport à ses voisins.

Il y a des conditions communes qui sont satisfaites Nous n'aurons pas d'optimaux locaux sur l'avion qui ne sont pas optimaux globalement. Dans de telles situations, nous pouvons utiliser des algorithmes de recherche locaux pour trouver la solution optimale. Un de ces conditions est si le plan des solutions est convexe, intuitivement pour tous les deux points, nous avons tous des points sur la ligne de connexion aussi dans l'espace de la solution et La qualité de chacun d'entre eux peut être déterminée à partir de la distance relative du point aux deux points d'extrémité et la qualité des deux points finaux. L'optimisation des espaces convexes est étudiée dans optimisation convexe .

Maintenant, revenons au problème du flux maximal. Corrigez un graphique comme entrée. Pensez à chaque flux qui satisfait la capacité et la préservation du flux exigences en tant que point. Nous appelons ces flux valides. Nous voulons trouver un débit maximum. Deux points sont proches les uns des autres si nous pouvons en obtenir un en augmentant ou en diminuant l'écoulement à travers un chemin de la source à l'évier.

Nous pouvons commencer par le flux où le flux sur tous les bords est zéro (Ceci est un flux valide). À chaque étape, nous trouvons un chemin de la source à l'évier dans le graphe de capacité restante mise à jour (le poids de chaque bord est la quantité de sa capacité qui n'est pas utilisée) D'une manière ou d'une autre (par exemple, de BFS) et d'augmenter le flux en ajoutant ceci. Cela nous donne un algorithme de recherche local. Le problème est que l'espace des solutions n'est pas convexe et Nous pouvons nous retrouver avec un flux que nous ne pouvons plus augmenter, mais ce n'est pas un débit maximal.

Que pouvons-nous faire? Une idée est de changer l'espace des solutions à un convexe. Pour l'intuition, pensez à une étoile dans un avion. Les points à l'intérieur de l'étoile ne font pas un espace convexe Mais nous pouvons le transformer en un espace convexe en incluant plus de points dans notre espace de solution et la transformer en pentagone.

C'est essentiellement ce que nous faisons en considérant le flux existant sur les bords d'origine du graphique En tant que nouveaux bords (appelés bords résiduels ) où l'écoulement sur eux correspond à la réduction du flux existant sur les bords d'origine. Cela rend l'espace convexe et notre algorithme de recherche local ne reste pas bloqué sur des solutions qui sont optimaux localement mais non optimaux globalement.