algorithm - resueltos - el camino mas corto matematicas discretas

Encuentra las rutas entre dos nodos dados?

Question

Supongamos que tengo nodos conectados de la siguiente manera, ¿cómo llego al número de rutas que existen entre los puntos dados y los detalles de la ruta?

1,2 //node 1 and 2 are connected
2,3
2,5
4,2
5,11
11,12
6,7
5,6
3,6
6,8
8,10
8,9

Encuentra los caminos del 1 al 7:

Respuesta: 2 caminos encontrados y son

1,2,3,6,7
1,2,5,6,7

la implementación que se encuentra here es agradable, voy a usar la misma

Aquí está el fragmento del enlace de arriba en python

# a sample graph
graph = {''A'': [''B'', ''C'',''E''],
             ''B'': [''A'',''C'', ''D''],
             ''C'': [''D''],
             ''D'': [''C''],
             ''E'': [''F'',''D''],
             ''F'': [''C'']}

class MyQUEUE: # just an implementation of a queue

    def __init__(self):
        self.holder = []

    def enqueue(self,val):
        self.holder.append(val)

    def dequeue(self):
        val = None
        try:
            val = self.holder[0]
            if len(self.holder) == 1:
                self.holder = []
            else:
                self.holder = self.holder[1:]   
        except:
            pass

        return val  

    def IsEmpty(self):
        result = False
        if len(self.holder) == 0:
            result = True
        return result


path_queue = MyQUEUE() # now we make a queue


def BFS(graph,start,end,q):

    temp_path = [start]

    q.enqueue(temp_path)

    while q.IsEmpty() == False:
        tmp_path = q.dequeue()
        last_node = tmp_path[len(tmp_path)-1]
        print tmp_path
        if last_node == end:
            print "VALID_PATH : ",tmp_path
        for link_node in graph[last_node]:
            if link_node not in tmp_path:
                #new_path = []
                new_path = tmp_path + [link_node]
                q.enqueue(new_path)

BFS(graph,"A","D",path_queue)

-------------results-------------------
[''A'']
[''A'', ''B'']
[''A'', ''C'']
[''A'', ''E'']
[''A'', ''B'', ''C'']
[''A'', ''B'', ''D'']
VALID_PATH :  [''A'', ''B'', ''D'']
[''A'', ''C'', ''D'']
VALID_PATH :  [''A'', ''C'', ''D'']
[''A'', ''E'', ''F'']
[''A'', ''E'', ''D'']
VALID_PATH :  [''A'', ''E'', ''D'']
[''A'', ''B'', ''C'', ''D'']
VALID_PATH :  [''A'', ''B'', ''C'', ''D'']
[''A'', ''E'', ''F'', ''C'']
[''A'', ''E'', ''F'', ''C'', ''D'']
VALID_PATH :  [''A'', ''E'', ''F'', ''C'', ''D'']

Answer 1

El algoritmo de Dijkstra se aplica más a las rutas ponderadas y parece que el póster quería encontrar todas las rutas, no solo las más cortas.

Para esta aplicación, construiría un gráfico (su aplicación parece que no necesitaría ser dirigida) y usaría su método de búsqueda favorito. Parece que quieres todos los caminos, no solo adivinar el más corto, así que utiliza un algoritmo recursivo simple de tu elección.

El único problema con esto es si el gráfico puede ser cíclico.

Con las conexiones:

• 1, 2
• 1, 3
• 2, 3
• 2, 4

Mientras busca un camino de 1-> 4, podría tener un ciclo de 1 -> 2 -> 3 -> 1.

En ese caso, entonces mantendría una pila atravesando los nodos. Aquí hay una lista con los pasos para ese gráfico y la pila resultante (lo siento por el formato, no hay opción de tabla):

nodo actual (posibles nodos siguientes menos de donde venimos) [pila]

1. 1 (2, 3) [1]
2. 2 (3, 4) [1, 2]
3. 3 (1) [1, 2, 3]
4. 1 (2, 3) [1, 2, 3, 1] // error - número duplicado en la pila - ciclo detectado
5. 3 () [1, 2, 3] // retrocedió al nodo tres y sacó 1 de la pila. No más nodos para explorar desde aquí
6. 2 (4) [1, 2] // retrocedió al nodo 2 y sacó 1 de la pila.
7. 4 () [1, 2, 4] // Nodo de destino encontrado - pila de registros para una ruta. No más nodos para explorar desde aquí
8. 2 () [1, 2] // retrocedió al nodo 2 y sacó 4 de la pila. No más nodos para explorar desde aquí
9. 1 (3) [1] // retrocedió al nodo 1 y sacó 2 de la pila.
10. 3 (2) [1, 3]
11. 2 (1, 4) [1, 3, 2]
12. 1 (2, 3) [1, 3, 2, 1] // error - número duplicado en la pila - ciclo detectado
13. 2 (4) [1, 3, 2] // retrocedió al nodo 2 y sacó 1 de la pila
14. 4 () [1, 3, 2, 4] Nodo de destino encontrado: pila de registros para una ruta. No más nodos para explorar desde aquí
15. 2 () [1, 3, 2] // retrocedió al nodo 2 y sacó 4 de la pila. No más nodos
16. 3 () [1, 3] // retrocedió al nodo 3 y extrajo 2 de la pila. No más nodos
17. 1 () [1] // retrocedió al nodo 1 y sacó 3 de la pila. No más nodos
18. Hecho con 2 rutas registradas de [1, 2, 4] y [1, 3, 2, 4]

Answer 2

El código original es un poco engorroso y es posible que desee utilizar las colecciones.deque en su lugar si desea utilizar BFS para encontrar si existe una ruta entre 2 puntos en el gráfico. Aquí hay una solución rápida que pirateé:

Nota: este método puede continuar infinitamente si no existe una ruta entre los dos nodos. No he probado todos los casos, YMMV.

from collections import deque

# a sample graph
  graph = {''A'': [''B'', ''C'',''E''],
           ''B'': [''A'',''C'', ''D''],
           ''C'': [''D''],
           ''D'': [''C''],
           ''E'': [''F'',''D''],
           ''F'': [''C'']}

   def BFS(start, end):
    """ Method to determine if a pair of vertices are connected using BFS

    Args:
      start, end: vertices for the traversal.

    Returns:
      [start, v1, v2, ... end]
    """
    path = []
    q = deque()
    q.append(start)
    while len(q):
      tmp_vertex = q.popleft()
      if tmp_vertex not in path:
        path.append(tmp_vertex)

      if tmp_vertex == end:
        return path

      for vertex in graph[tmp_vertex]:
        if vertex not in path:
          q.append(vertex)

Answer 3

En Prolog (específicamente, SWI-Prolog)

:- use_module(library(tabling)).

% path(+Graph,?Source,?Target,?Path)
:- table path/4.

path(_,N,N,[N]).
path(G,S,T,[S|Path]) :-
    dif(S,T),
    member(S-I, G), % directed graph
    path(G,I,T,Path).

prueba:

paths :- Graph =
    [ 1- 2  % node 1 and 2 are connected
    , 2- 3 
    , 2- 5 
    , 4- 2 
    , 5-11
    ,11-12
    , 6- 7 
    , 5- 6 
    , 3- 6 
    , 6- 8 
    , 8-10
    , 8- 9
    ],
    findall(Path, path(Graph,1,7,Path), Paths),
    maplist(writeln, Paths).

?- paths.
[1,2,3,6,7]
[1,2,5,6,7]
true.

Answer 4

Lo que estás tratando de hacer es esencialmente encontrar una ruta entre dos vértices en un gráfico (dirigido?), Echa un vistazo al algoritmo de Dijkstra si necesitas una ruta más corta o escribe una función recursiva simple si necesitas las rutas que existen.

Answer 5

Para aquellos que no son expertos PYTHON, el mismo código en C ++

//@Author :Ritesh Kumar Gupta
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <vector>
#include <queue>
#include <iostream>
using namespace std;
vector<vector<int> >GRAPH(100);
inline void print_path(vector<int>path)
{
    cout<<"[ ";
    for(int i=0;i<path.size();++i)
    {
        cout<<path[i]<<" ";
    }
    cout<<"]"<<endl;
}
bool isadjacency_node_not_present_in_current_path(int node,vector<int>path)
{
    for(int i=0;i<path.size();++i)
    {
        if(path[i]==node)
        return false;
    }
    return true;
}
int findpaths(int source ,int target ,int totalnode,int totaledge )
{
    vector<int>path;
    path.push_back(source);
    queue<vector<int> >q;
    q.push(path);

    while(!q.empty())
    {
        path=q.front();
        q.pop();

        int last_nodeof_path=path[path.size()-1];
        if(last_nodeof_path==target)
        {
            cout<<"The Required path is:: ";
            print_path(path);
        }
        else
        {
            print_path(path);
        }

        for(int i=0;i<GRAPH[last_nodeof_path].size();++i)
        {
            if(isadjacency_node_not_present_in_current_path(GRAPH[last_nodeof_path][i],path))
            {

                vector<int>new_path(path.begin(),path.end());
                new_path.push_back(GRAPH[last_nodeof_path][i]);
                q.push(new_path);
            }
        }




    }
    return 1;
}
int main()
{
    //freopen("out.txt","w",stdout);
    int T,N,M,u,v,source,target;
    scanf("%d",&T);
    while(T--)
    {
        printf("Enter Total Nodes & Total Edges/n");
        scanf("%d%d",&N,&M);
        for(int i=1;i<=M;++i)
        {
            scanf("%d%d",&u,&v);
            GRAPH[u].push_back(v);
        }
        printf("(Source, target)/n");
        scanf("%d%d",&source,&target);
        findpaths(source,target,N,M);
    }
    //system("pause");
    return 0;
}

/*
Input::
1
6 11
1 2 
1 3
1 5
2 1
2 3
2 4
3 4
4 3
5 6
5 4
6 3
1 4

output:
[ 1 ]
[ 1 2 ]
[ 1 3 ]
[ 1 5 ]
[ 1 2 3 ]
The Required path is:: [ 1 2 4 ]
The Required path is:: [ 1 3 4 ]
[ 1 5 6 ]
The Required path is:: [ 1 5 4 ]
The Required path is:: [ 1 2 3 4 ]
[ 1 2 4 3 ]
[ 1 5 6 3 ]
[ 1 5 4 3 ]
The Required path is:: [ 1 5 6 3 4 ]


*/

Answer 6

Si quieres todas las rutas, usa la recursión.

Usando una lista de adyacencia, preferiblemente, crea una función f () que intente completar una lista actual de vértices visitados. Al igual que:

void allPaths(vector<int> previous, int current, int destination)
{
    previous.push_back(current);

    if (current == destination)
        //output all elements of previous, and return

    for (int i = 0; i < neighbors[current].size(); i++)
        allPaths(previous, neighbors[current][i], destination);
}

int main()
{
    //...input
    allPaths(vector<int>(), start, end);
}

Debido al hecho de que el vector se pasa por valor (y, por lo tanto, cualquier cambio realizado más abajo en el procedimiento recursivo no es permanente), se enumeran todas las combinaciones posibles.

Puede obtener un poco de eficiencia pasando el vector anterior por referencia (y, por lo tanto, no necesita copiar el vector una y otra vez), pero deberá asegurarse de que las cosas se vuelvan popped_back () manualmente.

Una cosa más: si el gráfico tiene ciclos, esto no funcionará. (Supongo que en este caso querrá encontrar todos los senderos simples ). Antes de agregar algo al vector anterior , primero verifique si ya está allí.

Si quiere todos los caminos más cortos, use la sugerencia de Konrad con este algoritmo.

Answer 7

dada la matriz de adyacencia:

{0, 1, 3, 4, 0, 0}

{0, 0, 2, 1, 2, 0}

{0, 1, 0, 3, 0, 0}

{0, 1, 1, 0, 0, 1}

{0, 0, 0, 0, 0, 6}

{0, 1, 0, 1, 0, 0}

el siguiente código de Wolfram Mathematica resuelve el problema para encontrar todas las rutas simples entre dos nodos de un gráfico. Usé recursión simple y dos variables globales para realizar un seguimiento de los ciclos y almacenar el resultado deseado. el código no ha sido optimizado solo por el bien de la claridad del código. la "impresión" debería ser útil para aclarar cómo funciona.

cycleQ[l_]:=If[Length[DeleteDuplicates[l]] == Length[l], False, True];
getNode[matrix_, node_]:=Complement[Range[Length[matrix]],Flatten[Position[matrix[[node]], 0]]];

builtTree[node_, matrix_]:=Block[{nodes, posAndNodes, root, pos},
    If[{node} != {} && node != endNode ,
        root = node;
        nodes = getNode[matrix, node];
        (*Print["root:",root,"---nodes:",nodes];*)

        AppendTo[lcycle, Flatten[{root, nodes}]];
        If[cycleQ[lcycle] == True,
            lcycle = Most[lcycle]; appendToTree[root, nodes];,
            Print["paths: ", tree, "/n", "root:", root, "---nodes:",nodes];
            appendToTree[root, nodes];

        ];
    ];

appendToTree[root_, nodes_] := Block[{pos, toAdd},
    pos = Flatten[Position[tree[[All, -1]], root]];
    For[i = 1, i <= Length[pos], i++,
        toAdd = Flatten[Thread[{tree[[pos[[i]]]], {#}}]] & /@ nodes;
        (* check cycles!*)            
        If[cycleQ[#] != True, AppendTo[tree, #]] & /@ toAdd;
    ];
    tree = Delete[tree, {#} & /@ pos];
    builtTree[#, matrix] & /@ Union[tree[[All, -1]]];
    ];
];

llamar al código: initNode = 1; endNode = 6; lcycle = {}; tree = {{initNode}}; builtTree [initNode, matriz];

paths: {{1}} root: 1 --- nodos: {2,3,4}

paths: {{1,2}, {1,3}, {1,4}} root: 2 --- nodes: {3,4,5}

paths: {{1,3}, {1,4}, {1,2,3}, {1,2,4}, {1,2,5}} root: 3 --- nodes: {2, 4}

caminos: {{1,4}, {1,2,4}, {1,2,5}, {1,3,4}, {1,2,3,4}, {1,3,2, 4}, {1,3,2,5}} raíz: 4 --- nodos: {2,3,6}

rutas: {{1,2,5}, {1,3,2,5}, {1,4,6}, {1,2,4,6}, {1,3,4,6}, { 1,2,3,4,6}, {1,3,2,4,6}, {1,4,2,5}, {1,3,4,2,5}, {1,4, 3,2,5}} raíz: 5 --- nodos: {6}

RESULTADOS: {{1, 4, 6}, {1, 2, 4, 6}, {1, 2, 5, 6}, {1, 3, 4, 6}, {1, 2, 3, 4, 6}, {1, 3, 2, 4, 6}, {1, 3, 2, 5, 6}, {1, 4, 2, 5, 6}, {1, 3, 4, 2, 5, 6}, {1, 4, 3, 2, 5, 6}}

... Desafortunadamente no puedo subir imágenes para mostrar los resultados de una mejor manera :(

http://textanddatamining.blogspot.com

Answer 8

La búsqueda de primer orden atraviesa un gráfico y, de hecho, encuentra todas las rutas desde un nodo inicial. Por lo general, BFS no mantiene todas las rutas, sin embargo. En cambio, actualiza una función predecesora π para guardar la ruta más corta. Puede modificar fácilmente el algoritmo para que π(n) no solo almacene un predecesor sino una lista de posibles predecesores.

Entonces, todas las rutas posibles se codifican en esta función y, al recorrer π recursivamente, se obtienen todas las posibles combinaciones de ruta.

Un buen pseudocódigo que utiliza esta notación se puede encontrar en Introducción a los algoritmos por Cormen et al. y posteriormente se ha utilizado en muchos guiones de la Universidad sobre el tema. Una búsqueda en Google de "predecesor de pseudocódigo BFS π" desencadena este hit en Stack Exchange .