Dominos - Compétition

Question

http://ecoo.org/ecoocs/contests/ecoo_2007.pdf Hé les gars, J'étudie vraiment dur pour les éco régionaux à venir pour ma région et je suis perplexe sur cette question. Je n'ai vraiment aucune idée de par où commencer.

C'est dans la section "régionale" "ouest et centrale" "problème 3 - chaînes domino". Je continue à résoudre le problème manuellement et je continue à penser à la première recherche de largeur ou à la première recherche de profondeur, mais les dominos ayant deux côtés me font sérieusement réfléchir. Est-ce que quelqu'un a des conseils ou peut-être des ressources qui pourraient me mettre dans la bonne direction? Merci à l'avance, Dan chevalier programme Ps I en C++ si cela fait une différence

Answer 1

Il semble que ce problème nécessite une approche de retour arrière récursif. Gardez une matrice symétrique 7 par 7 montrant les nombres auxquels sont attachés les nombres. Par exemple, les tuiles données 00 12 63 51 vous auriez la matrice suivante:

0 1 2 3 4 5 6 
    ------------- 
0|1 0 0 0 0 0 0 
1|0 0 1 0 0 1 0 
2|1 0 0 0 0 0 0 
3|0 0 0 0 0 0 1 
4|0 0 0 0 0 0 0 
5|0 1 0 0 0 0 0 
6|0 0 0 1 0 0 0 

Lorsque vous utilisez une tuile en le plaçant dans une chaîne potentielle, supprimer de la matrice, et la remettre en place dans la matrice après que vous unplace la tuile en faisant marche arrière. Par exemple, si la chaîne contient currecntly 51 12, la matrice ressemble à ceci:

0 1 2 3 4 5 6 
    ------------- 
0|1 0 0 0 0 0 0 
1|0 0 0 0 0 0 0 
2|0 0 0 0 0 0 0 
3|0 0 0 0 0 0 1 
4|0 0 0 0 0 0 0 
5|0 0 0 0 0 0 0 
6|0 0 0 1 0 0 0 

Étant donné que la chaîne se termine currecntly à 2, vous regardez le long la ligne 2 pour tous les numéros qui peuvent se connecter. N'en trouvant aucun, vous marqueriez 51 12 comme chaîne la plus longue potentielle, puis revenez à l'état où la chaîne contenait seulement 51. Maintenir un ensemble de toutes les chaînes les plus longues que vous avez trouvées, et vérifier une nouvelle chaîne pour l'existence de lui-même ou son inverse dans l'ensemble avant de l'insérer.

Si vous trouvez une chaîne plus longue, commencez un nouvel ensemble. Une fois que vous avez recherché de manière exhaustive toutes les chaînes possibles, la taille de votre ensemble devrait être le nombre de variations qui sont les plus longues.

Answer 2

Personnellement, lorsque vous travaillez ce genre de problèmes, une excellente façon de les résoudre est de les faire dans un cas (en tenant compte que vous allez augmenter la complexité plus tard), puis augmenter la complexité. De cette façon, vous n'êtes pas submergé par la complexité et les «whatifs» presque sans fin qu'un problème comme celui-ci peut causer. En outre, sur les concours de programmation auxquels j'ai participé, 60 à 70% du crédit ont été accordés pour une solution corrigeant le problème de base, et les pourcentages finaux si vous avez correctement géré certains cas. Le cas qui me vient à l'esprit est que nous avions un problème de mappage avec une variante du vendeur itinérant et que s'ils fournissaient un graphique avec une boucle, ma solution tournait sans cesse ou faisait-elle quelque chose. Donc, avec cette approche, ce que je ferais, c'est essayer de résoudre le problème aussi directement que possible: prenez l'entrée comme indiqué par la documentation et générez juste la plus longue chaîne avec les pièces que vous avez. Ensuite, augmentez la complexité en permettant de faire pivoter les pièces, etc.

Bien qu'il s'agisse d'une approche personnelle du problème, cela m'a bien servi dans le passé. J'espère que cela vous sert aussi bien.

Answer 3

Ceci est un problème dynamic programming, donc vous pouvez le résoudre en utilisant des techniques de programmation dynamique.

Donc, si nous avons ces pièces:

45 36 46 56 

Quelle est la plus longue chaîne qui peut être fait à partir de 4 os?
De toute évidence, la plus longue chaîne qui peut être faite à partir de 3 os et 1 os de plus.

Quelle est la plus longue chaîne qui peut être faite à partir de 3 os?
De toute évidence, la plus longue chaîne qui peut être faite à partir de 2 os et 1 os de plus.

Quelle est la plus longue chaîne qui peut être faite à partir de 2 os?
De toute évidence, la plus longue chaîne qui peut être faite à partir de 1 os et 1 os de plus.

Quelle est la plus longue chaîne qui peut être fabriqué à partir de 1 os?
Évidemment, 1 os est la chaîne la plus longue possible.

Je pense que vous voyez par le modèle ici, nous devons utiliser la récursivité.

Donc, si nous avons:

45 36 46 56 

Supposons que nous avons une fonction longest_chain(set_of_pieces). Ensuite, nous devons vérifier:

longest_chain({36 46 56}) (+ 1 if we can append 45 or 54 else discard this chain) 
longest_chain({45 46 56}) (+ 1 if we can append 36 or 63 else discard this chain) 
longest_chain({45 36 56}) (+ 1 if we can append 46 or 64 else discard this chain) 
longest_chain({45 36 46}) (+ 1 if we can append 56 or 65 else discard this chain) 

Qu'est-ce que longest_chain({36 46 56})?

longest_chain({46 56}) (+ 1 if we can append 36 or 63 else discard this chain) 
longest_chain({36 56}) (+ 1 if we can append 46 or 64 else discard this chain) 
longest_chain({36 46}) (+ 1 if we can append 56 or 65 else discard this chain) 

qu'est-ce que longest_chain({46 56})?

longest_chain({46}) (+ 1 if we can append 56 or 65 else discard this chain) 
longest_chain({56}) (+ 1 if we can append 46 or 64 else discard this chain) 

qu'est-ce que longest_chain({46})? Deux possibilités: {46} {64}
Peut-on ajouter 56 ou 65 à l'un de ces éléments? Oui, nous pouvons faire cette chaîne {46, 65} et nous éliminons {64}. Faites la même chose avec longest_chain({56}) et nous obtenons: {56, 64}.

Par conséquent, nous savons maintenant que longest_chain({46 56}) sont {46, 65}, {56, 64}

Continuez jusqu'à ce que vous obtenez toutes les réponses.

Espérons que cela aide.

Answer 4

Voici comment je commencerais.

Marquez les dominos nD1..Dn.

Soit Cm être l'ensemble des chaînes formées en utilisant le sous-ensemble de domines D1..Dm (et C0 = {}).

Cm+1 est formée par une tentative d'insertion Dm + 1 dans tous les endroits possibles dans les chaînes en Cm, plus Dm+1 utilisant autant que possible pour concaténer paires de chaînes disjointes de Cm, plus la chaîne de singleton constitué par Dm+1 par lui-même.

Vous pouvez probablement faire une certaine optimisation (par exemple, commander les dominos), mais je serais enclin à essayer cela avant de devenir trop intelligent.