Hint per ois minperm

Aiuto
1

Ciao a tutti,
Questa volta sono alle prese con il problema minperm
Ho capito che l’array data la lista l di possibili lunghezze per lo swap puo’ essere visto come un grafo non diretto, ma mi trovo in difficolta’ a trovare un algoritmo valido per la soluzione e soprattutto dimostrare che dia sempre la soluzione ottimale
Ogni hint sarebbe molto apprezzato
Grazie in anticipo

2

Tu sai che puoi formare un grafo non diretto dove i nodi sono le attrazioni ed esiste un arco tra 2 nodi se possono essere scambiati. Pensa ora di eseguire una visita da un verto nodo x su tale grafo trovando tutti i nodi raggiungibili da x (chiamiamo questi nodi X ed includiamo x in X) che corrispondono, nel problema originale alle attrazioni che possono essere messe al posto dell’attrazione x (eventualmente con più di uno scambio) . Supponiamo che i nodi di X si trovino inizialmente in posizione p_{i1}, p_{i2}, ..., p_{i|X|} in che modo puoi spostare tali attrazioni tramite scambi?

1 Mi Piace
3

Parto dal presupposto (spero non sbagliato), che preso un albero sono in grado con lo swap tra nodi collegati di ottenere ogni possibile disposizione dei nodi (in un numero arbitrario di swap) e che ogni grafo puo’ essere ridotto ad albero.
Se questa premessa e’ valida allora significa che sono in grado di “sortare per valore” tutti i nodi all’interno della stessa componente connessa.

Ammesso che io sia sulla giusta strada, pero’, come posso dimostrare che sortando ogni componente connessa io abbia effettivamente in mano la soluzione con il numero minore di inversioni?

Edit: pur non essendo bravo a fare dimostrazioni, e’ stata abbastanza facile farla per assurdo; la scrivo in caso qualcun altro si trovi davanti a questo problema (o almeno faro’ un tentativo)

Sia v il vettore contenente il risultato e siano i e j indici di nodi appartenenti alla stessa componente connessa tali per cui i < j e v[i] < v[j]
Sia anche inv() la funzione che conta il numero di inversioni
Scambiando i e j si ha un vettore w tale per cui inv(v) <= inv(w) + 1
Questo perche’ i e j costituiscono necessariamente un’inversione dato che v[i] < v[j] e preso un terzo indice i < k < j ci sono 3 possibili casi:

  1. v[k] > v[j] → viene aggiunta l’inversione i con j
  2. v[i] < v[k] < v[j] → viene aggiunta l’inversione i con j, i con k e j con k
  3. v[k] < v[i] → viene aggiunta l’inversione i con j

Secondo update:
Risolto, grazie infinite dell’incipit