Mostra notizie nelle discussioni
  • Avatar
    ☺
    Scritto da
    ::1
    il 2015-05-05 11:44:49.0 alle 2015-05-05 11:44:49.0
    Trollate totali: 12321
    ordinamento alberi discreto
    Domanda per sarrusofoni in ascolto.
    Ho una set di dati che mi danno le dipendenze di alcune cose, e con queste vi costruisco un albero: sono circa 400 oggetti.
    Ora, di ogni oggetto ho l'elenco delle dipendenze, e vorrei costruire una lista ordinata dove gli oggetti senza dipendenze sono in cima e quelle con più dipendenze in fondo, ordinata in modo da non avere (o comunque minimizzare) il numero di ogggeti che dipendono da oggetti posti sopra di essi nella lista.
    Il problema è che l'albero è pieno di loop, quindi non basta esplorarlo per avere la lista, che mi invento?
    Sono riuscito ad avere un ordinamento di massima guardando l'albero e prendendo la posizione più bassa assegnando quindi un valore "profondità" che riceve un valore minimo di 1 massimo di 5; ma il sottoordinamento dei pari livello è ancora problematico.
    Se vi serve un set di dati e un pezzo di codice ve lo pasto.
    Young professional woman and busy mom.
    • Avatar
      ☺
      Scritto da
      аvvelentani
      Utente privilegiato
      il 2015-05-05 12:01:59.0 alle 2015-05-05 12:01:59.0
      Trollate totali: 58
      Re: ordinamento alberi discreto
      Scritto da: ::1
      > Domanda per sarrusofoni in ascolto.
      > Ho una set di dati che mi danno le dipendenze di alcune cose, e con queste vi costruisco un albero: sono circa 400 oggetti.
      > Ora, di ogni oggetto ho l'elenco delle dipendenze, e vorrei costruire una lista ordinata dove gli oggetti senza dipendenze sono in cima e quelle con più dipendenze in fondo, ordinata in modo da non avere (o comunque minimizzare) il numero di ogggeti che dipendono da oggetti posti sopra di essi nella lista.
      > Il problema è che l'albero è pieno di loop, quindi non basta esplorarlo per avere la lista, che mi invento?
      > Sono riuscito ad avere un ordinamento di massima guardando l'albero e prendendo la posizione più bassa assegnando quindi un valore "profondità" che riceve un valore minimo di 1 massimo di 5; ma il sottoordinamento dei pari livello è ancora problematico.
      > Se vi serve un set di dati e un pezzo di codice ve lo pasto.

      E` una domanda degna di avvelenato.
      I think happiness is love
      - Vladimir Putin
    • Avatar
      ☺
      Scritto da
      avvelentani
      Cubicolario
      il 2015-05-05 12:47:24.0 alle 2015-05-05 12:47:24.0
      Trollate totali: 18184
      Re: ordinamento alberi discreto
      > Il problema è che l'albero è pieno di loop,

      non e` un albero.

      > ordinata in modo da non avere (o comunque minimizzare) il numero di ogggeti che dipendono da oggetti posti sopra di essi nella lista.

      ovviamente e` impossibile non avere dipendenze se ci sono cicli.

      > che mi invento?

      Quello che stai cercando si chiama ordinamento topologico. L'ordinamento topologico esiste soltanto per grafi che sono dag (directed acyclic graph), quello che ti interesserebbe fare e` ridurre un grafo in un dag rimuovendo il minor numero di archi, googlando in giro si scopre che questo problema e` noto NP-hard, alla luce di questo fatto eviterei se possibile di cercare la soluzione ottimale e mi accontenterei di un'euristica.
      Un'idea che potresti provare e` usare un algoritmo per cercare cicli, collassare ogni ciclo in un singolo nodo, e ripetere finche' non hai un dag. Il dag risultante lo ordini topologicamente, quando viene il momento di stampare nodi che rappresentano cicli collassati fai una visita breadth first partendo da ognuno dei nodi del ciclo e scegli l'ordinamento che contiene meno dipendenze invertite.

      **Modificato dall'autore il 05.05.2015 12:52**
      I think happiness is love
      - Vladimir Putin
      • Avatar
        Scritto da
        Non Autenticato
        il 2015-05-05 13:05:33.0 alle 2015-05-05 13:05:33.0
        Re: ordinamento alberi discreto
        Scritto da: avvelentani
        > > Il problema è che l'albero è pieno di loop,
        >
        > non e` un albero.
        >
        > > ordinata in modo da non avere (o comunque minimizzare) il numero di ogggeti che dipendono da oggetti posti sopra di essi nella lista.
        >
        > ovviamente e` impossibile non avere dipendenze se ci sono cicli.
        >
        > > che mi invento?
        >
        > Quello che stai cercando si chiama ordinamento topologico. L'ordinamento topologico esiste soltanto per grafi che sono dag (directed acyclic graph), quello che ti interesserebbe fare e` ridurre un grafo in un dag rimuovendo il minor numero di archi, googlando in giro si scopre che questo problema e` noto NP-hard, alla luce di questo fatto eviterei se possibile di cercare la soluzione ottimale e mi accontenterei di un'euristica.
        > Un'idea che potresti provare e` usare un algoritmo per cercare cicli, collassare ogni ciclo in un singolo nodo, e ripetere finche' non hai un dag. Il dag risultante lo ordini topologicamente, quando viene il momento di stampare nodi che rappresentano cicli collassati fai una visita breadth first partendo da ognuno dei nodi del ciclo e scegli l'ordinamento che contiene meno dipendenze invertite.
        >

        mi è venuto duro Imbarazzato
        • Avatar
          Scritto da
          Non Autenticato
          il 2015-05-05 14:59:00.0 alle 2015-05-05 14:59:00.0
          Re: ordinamento alberi discreto
          Scritto da:
          > Scritto da: avvelentani
          > > > Il problema è che l'albero è pieno di loop,
          > >
          > > non e` un albero.
          > >
          > > > ordinata in modo da non avere (o comunque minimizzare) il numero di ogggeti che dipendono da oggetti posti sopra di essi nella lista.
          > >
          > > ovviamente e` impossibile non avere dipendenze se ci sono cicli.
          > >
          > > > che mi invento?
          > >
          > > Quello che stai cercando si chiama ordinamento topologico. L'ordinamento topologico esiste soltanto per grafi che sono dag (directed acyclic graph), quello che ti interesserebbe fare e` ridurre un grafo in un dag rimuovendo il minor numero di archi, googlando in giro si scopre che questo problema e` noto NP-hard, alla luce di questo fatto eviterei se possibile di cercare la soluzione ottimale e mi accontenterei di un'euristica.
          > > Un'idea che potresti provare e` usare un algoritmo per cercare cicli, collassare ogni ciclo in un singolo nodo, e ripetere finche' non hai un dag. Il dag risultante lo ordini topologicamente, quando viene il momento di stampare nodi che rappresentano cicli collassati fai una visita breadth first partendo da ognuno dei nodi del ciclo e scegli l'ordinamento che contiene meno dipendenze invertite.
          > >
          >
          > mi è venuto duro Imbarazzato

          NP-hard Imbarazzato
          • Avatar
            Scritto da
            Non Autenticato
            il 2015-05-06 04:53:42.0 alle 2015-05-06 04:53:42.0
            Re: ordinamento alberi discreto
            Scritto da:
            > Scritto da:
            > > Scritto da: avvelentani
            > > > > Il problema è che l'albero è pieno di loop,
            > > >
            > > > non e` un albero.
            > > >
            > > > > ordinata in modo da non avere (o comunque minimizzare) il numero di ogggeti che dipendono da oggetti posti sopra di essi nella lista.
            > > >
            > > > ovviamente e` impossibile non avere dipendenze se ci sono cicli.
            > > >
            > > > > che mi invento?
            > > >
            > > > Quello che stai cercando si chiama ordinamento topologico. L'ordinamento topologico esiste soltanto per grafi che sono dag (directed acyclic graph), quello che ti interesserebbe fare e` ridurre un grafo in un dag rimuovendo il minor numero di archi, googlando in giro si scopre che questo problema e` noto NP-hard, alla luce di questo fatto eviterei se possibile di cercare la soluzione ottimale e mi accontenterei di un'euristica.
            > > > Un'idea che potresti provare e` usare un algoritmo per cercare cicli, collassare ogni ciclo in un singolo nodo, e ripetere finche' non hai un dag. Il dag risultante lo ordini topologicamente, quando viene il momento di stampare nodi che rappresentano cicli collassati fai una visita breadth first partendo da ognuno dei nodi del ciclo e scegli l'ordinamento che contiene meno dipendenze invertite.
            > > >
            > >
            > > mi è venuto duro Imbarazzato
            >
            > NP-hard Imbarazzato

            ah ecco perchè le "dipendenze invertite" sono chiaramente roba da froci
<softv>

Pagina generata in 68 millisecondi

Utenti attivi: 15 nell'ultimo minuto, 39 negli ultimi cinque minuti, 76 negli ultimi 15 minuti