Problème de voyage en vol aller simple

Question

Vous partez pour un voyage aller simple en vol indirect qui comprend milliards d'euros un très grand nombre inconnu de transferts.

• Vous ne vous arrêtez pas deux fois dans le même aéroport.
• Vous disposez d'un billet pour chaque partie de votre voyage.
• Chaque billet contient src y dst l'aéroport.
• Tous les billets que vous possédez sont triés au hasard.
• Vous avez oublié l'aéroport de départ initial (tout premier src) et votre destination (dernier dst).

Concevoir un algorithme pour reconstruire votre voyage avec un minimum de big- O complexité.

---

Pour tenter de résoudre ce problème, j'ai commencé à utiliser un système de contrôle de la qualité de l'eau. différence symétrique de deux ensembles, Srcs et Dsts :

1)Trier toutes les clés src dans le tableau Srcs
2) Trier toutes les clés dst dans le tableau Dsts
3) Créez un ensemble d'union des deux tableaux pour trouver les non-duplicatas - ce sont votre premier src et votre dernier dst.
4)Maintenant, en ayant le point de départ, parcourez les deux tableaux en utilisant la recherche binaire.

Mais je suppose qu'il doit y avoir une autre méthode plus efficace.

Answer 1

Construire une table de hachage et ajouter chaque aéroport dans la table de hachage.

<key,value> = <airport, count>

Le décompte pour l'aéroport augmente si l'aéroport est soit la source, soit la destination. Ainsi, pour chaque aéroport, le compte sera de 2 ( 1 pour le src et 1 pour le dst) sauf pour la source et la destination de votre voyage qui auront le compte de 1.

Vous devez examiner chaque billet au moins une fois. La complexité est donc O(n).

Answer 2

Résumé : ci-dessous un algorithme à passage unique est donné . (c'est-à-dire, pas seulement linéaire, mais regarde chaque ticket exactement une fois, ce qui correspond bien sûr au nombre optimal de visites par ticket). Je mets le résumé parce qu'il y a beaucoup de solutions apparemment équivalentes et il serait difficile de repérer pourquoi j'en ai ajouté une autre :)

Cette question m'a été posée lors d'un entretien. Le concept est extrêmement simple : chaque ticket est une liste singleton, avec conceptuellement deux éléments, src et dst.

Nous indexons chacune de ces listes dans une table de hachage en utilisant ses premier et dernier éléments comme clés, de sorte que nous pouvons trouver en O(1) si une liste commence ou se termine à un élément particulier (aéroport). Pour chaque billet, lorsque nous voyons qu'il commence là où une autre liste se termine, il suffit de relier les listes (O(1)). De même, s'il se termine là où une autre liste commence, on joint une autre liste. Bien sûr, lorsque nous lions deux listes, nous détruisons essentiellement les deux et en obtenons une seule. (La chaîne de N tickets sera construite après N-1 de tels liens).

Il faut veiller à maintenir l'invariant selon lequel les clés de la table de hachage sont exactement les premiers et derniers éléments des listes restantes.

En tout et pour tout, O(N).

Et oui, j'ai répondu à cette question sur le champ :)

Editar J'ai oublié d'ajouter un point important. Tout le monde mentionne deux mais un seul fait l'affaire aussi, car l'invariant des algorithmes inclut qu'au maximum un Une liste de billets commence ou est commencée dans une seule ville (s'il y en a deux, nous joignons immédiatement les listes à cette ville et supprimons cette ville de la table de hachage). Asymptotiquement, il n'y a pas de différence, c'est simplement plus simple de cette façon.

Edición 2 Il est également intéressant de noter que, par rapport aux solutions utilisant 2 tables de hachage avec N entrées chaque cette solution utilise une table de hachage avec au maximum N/2 entrées (ce qui se produit si nous voyons les billets dans un ordre de, disons, 1er, 3e, 5e, et ainsi de suite). Cette méthode utilise donc environ la moitié de la mémoire, en plus d'être plus rapide.

Answer 3

Construire deux tables de hachage (ou essais), une clé sur src et l'autre sur dst. Choisissez un ticket au hasard et cherchez son dst dans la table src-hash. Répétez ce processus pour le résultat jusqu'à ce que vous arriviez à la fin (la destination finale). Recherchez maintenant son src dans la table de hachage dst-keyed. Répétez le processus pour le résultat jusqu'à ce que vous arriviez au début.

La construction des tables de hachage prend O(n) et la construction de la liste prend O(n), donc l'algorithme entier est O(n).

EDIT : Vous n'avez besoin de construire qu'une seule table de hachage, en fait. Disons que vous construisez la table de hachage à clé src. Choisissez un ticket au hasard et comme précédemment, construisez la liste qui mène à la destination finale. Ensuite, choisissez un autre ticket au hasard parmi les tickets qui n'ont pas encore été ajoutés à la liste. Suivez sa destination jusqu'à ce que vous atteigniez le ticket avec lequel vous avez commencé. Répétez ce processus jusqu'à ce que vous ayez construit la liste entière. C'est toujours O(n) puisque dans le pire des cas, vous choisissez les tickets dans l'ordre inverse.

Edit : j'ai interverti les noms des tables dans mon algorithme.

Answer 4

Il s'agit essentiellement d'un graphe de dépendances où chaque billet représente un nœud et où les src y dst L'aéroport représente des liens dirigés, utilisez donc un tri topologique pour déterminer l'ordre des vols.

EDIT : Bien que, puisqu'il s'agit d'un billet d'avion et que vous savez que vous avez réellement établi un itinéraire, vous pourriez physiquement effectuer un tri par date et heure de départ en UTC.

EDIT2 : En supposant que chaque aéroport pour lequel vous avez un billet utilise un code à trois caractères, vous pouvez utiliser l'algorithme décrit ici ( Trouvez trois nombres apparaissant une seule fois ) pour déterminer les deux aéroports uniques en xant tous les aéroports ensemble.

EDIT3 : Voici un peu de C++ pour résoudre ce problème en utilisant la méthode xor. L'algorithme global est le suivant, en supposant un codage unique de l'aéroport en un entier (soit en supposant un code d'aéroport à trois lettres, soit en codant la localisation de l'aéroport en un entier utilisant la latitude et la longitude) :

D'abord, faites un XOR de tous les codes d'aéroport ensemble. Cela devrait être égal à l'aéroport source initial XOR l'aéroport de destination finale. Comme nous savons que l'aéroport initial et l'aéroport final sont uniques, cette valeur ne doit pas être nulle. Puisqu'elle n'est pas nulle, il y aura au moins un bit activé dans cette valeur. Ce bit correspond à un bit qui est activé dans l'un des aéroports et non dans l'autre ; on l'appelle le bit indicateur.

Ensuite, définissez deux compartiments, chacun avec la valeur XORed de la première étape. Maintenant, pour chaque billet, mettez dans le panier chaque aéroport selon qu'il a le bit de désignation activé ou non, et faites le XOR du code de l'aéroport avec la valeur dans le panier. Gardez également la trace, pour chaque case, du nombre d'aéroports d'origine et d'aéroports de destination qui sont entrés dans cette case.

Après avoir traité tous les billets, choisissez l'un des godets. Le nombre d'aéroports sources envoyés dans ce compartiment doit être supérieur ou inférieur d'une unité au nombre d'aéroports de destination envoyés dans ce compartiment. Si le nombre d'aéroports sources est inférieur au nombre d'aéroports de destination, cela signifie que l'aéroport source initial (le seul aéroport source unique) a été envoyé dans l'autre godet. Cela signifie que la valeur dans le seau actuel est l'identifiant de l'aéroport source initial ! Inversement, si le nombre d'aéroports de destination est inférieur au nombre d'aéroports sources, cela signifie que l'aéroport de destination final a été envoyé dans l'autre godet, donc le godet actuel est l'identifiant de l'aéroport de destination final !

struct ticket
{
    int src;
    int dst;
};

int get_airport_bucket_index(
    int airport_code, 
    int discriminating_bit)
{
    return (airport_code & discriminating_bit)==discriminating_bit ? 1 : 0;
}

void find_trip_endpoints(const ticket *tickets, size_t ticket_count, int *out_src, int *out_dst)
{
    int xor_residual= 0;

    for (const ticket *current_ticket= tickets, *end_ticket= tickets + ticket_count; current_ticket!=end_ticket; ++current_ticket)
    {
        xor_residual^= current_ticket->src;
        xor_residual^= current_ticket->dst;
    }

    // now xor_residual will be equal to the starting airport xor ending airport
    // since starting airport!=ending airport, they have at least one bit that is not in common
    // 

    int discriminating_bit= xor_residual & (-xor_residual);

    assert(discriminating_bit!=0);

    int airport_codes[2]= { xor_residual, xor_residual };
    int src_count[2]= { 0, 0 };
    int dst_count[2]= { 0, 0 };

    for (const ticket *current_ticket= tickets, *end_ticket= tickets + ticket_count; current_ticket!=end_ticket; ++current_ticket)
    {
        int src_index= get_airport_bucket_index(current_ticket->src, discriminating_bit);

        airport_codes[src_index]^= current_ticket->src;
        src_count[src_index]+= 1;

        int dst_index= get_airport_bucket_index(current_ticket->dst, discriminating_bit);
        airport_codes[dst_index]^= current_ticket->dst;
        dst_count[dst_index]+= 1;
    }

    assert((airport_codes[0]^airport_codes[1])==xor_residual);
    assert(abs(src_count[0]-dst_count[0])==1); // all airports with the bit set/unset will be accounted for as well as either the source or destination
    assert(abs(src_count[1]-dst_count[1])==1);
    assert((src_count[0]-dst_count[0])==-(src_count[1]-dst_count[1]));

    int src_index= src_count[0]-dst_count[0]<0 ? 0 : 1; 
    // if src < dst, that means we put more dst into the source bucket than dst, which means the initial source went into the other bucket, which means it should be equal to this bucket!

    assert(get_airport_bucket_index(airport_codes[src_index], discriminating_bit)!=src_index);

    *out_src= airport_codes[src_index];
    *out_dst= airport_codes[!src_index];

    return;
}

int main()
{
    ticket test0[]= { { 1, 2 } };
    ticket test1[]= { { 1, 2 }, { 2, 3 } };
    ticket test2[]= { { 1, 2 }, { 2, 3 }, { 3, 4 } };
    ticket test3[]= { { 2, 3 }, { 3, 4 }, { 1, 2 } };
    ticket test4[]= { { 2, 1 }, { 3, 2 }, { 4, 3 } };
    ticket test5[]= { { 1, 3 }, { 3, 5 }, { 5, 2 } };

    int initial_src, final_dst;

    find_trip_endpoints(test0, sizeof(test0)/sizeof(*test0), &initial_src, &final_dst);
    assert(initial_src==1);
    assert(final_dst==2);

    find_trip_endpoints(test1, sizeof(test1)/sizeof(*test1), &initial_src, &final_dst);
    assert(initial_src==1);
    assert(final_dst==3);

    find_trip_endpoints(test2, sizeof(test2)/sizeof(*test2), &initial_src, &final_dst);
    assert(initial_src==1);
    assert(final_dst==4);

    find_trip_endpoints(test3, sizeof(test3)/sizeof(*test3), &initial_src, &final_dst);
    assert(initial_src==1);
    assert(final_dst==4);

    find_trip_endpoints(test4, sizeof(test4)/sizeof(*test4), &initial_src, &final_dst);
    assert(initial_src==4);
    assert(final_dst==1);

    find_trip_endpoints(test5, sizeof(test5)/sizeof(*test5), &initial_src, &final_dst);
    assert(initial_src==1);
    assert(final_dst==2);

    return 0;
}

Answer 5

Créez deux structures de données :

Route
{
  start
  end
  list of flights where flight[n].dest = flight[n+1].src
}

List of Routes

Et puis :

foreach (flight in random set)
{
  added to route = false;
  foreach (route in list of routes)
  {
    if (flight.src = route.end)
    {
      if (!added_to_route)
      {
        add flight to end of route
        added to route = true
      }
      else
      {
        merge routes
        next flight
      }
    }
    if (flight.dest = route.start)
    {
      if (!added_to_route)
      {
        add flight to start of route
        added to route = true
      }
      else
      {
        merge routes
        next flight
      }
    }
  }
  if (!added to route)
  {
    create route
  }
}