Comment choisir un point adjacent aléatoire (valide) dans un tableau d'entiers dans C?

Question

Supposons que nous ayons un tableau d'entiers (3x3) représentés comme suit:

+-+-+-+ 
| |1| | 
+-+-+-+ 
|0|x|1| 
+-+-+-+ 
| |0| | 
+-+-+-+ 

(0,1) ci-dessus est fixé à 1 et (1,0) est 0 etc.

Supposons maintenant que je me trouve à (1,1) (à x), quelle serait la méthode la plus facile pour moi de trouver toutes les directions que je peux prendre (disons tout ce qui a la valeur 0) et ensuite parmi celles qui en choisissent une? Ce qui me dérange avec est en fait l'étape entre choisir toutes les directions valides, puis en choisissant parmi celles-ci. Je peux faire les deux étapes séparément assez facilement mais je n'ai pas une solution qui se sent élégante qui combine les deux.

E.g. Je peux multiplier la valeur de chaque cellule par une valeur représentant 1,2,4 et 8 et ou tous ensemble. cela me donnerait les directions que je peux prendre, mais comment choisir entre eux? Aussi je peux facilement randomiser un nombre entre 1 et 4 pour choisir une direction mais si cette direction est "prise" alors je dois randomiser à nouveau mais en excluant la direction qui a échoué.

Des idées?

Answer 1

La solution la plus rapide est probablement la dernière que vous avez postée - choisissez les directions de manière aléatoire, en répétant jusqu'à ce que vous en obteniez une valide. Cela prendra au plus quatre essais (le pire est quand il n'y a qu'un seul voisin valide). Quelque chose de plus élégant est de parcourir toutes les directions possibles, la mise à jour d'une variable aléatoire à chaque voisin valide, tel que ce pseudo-code:

c = 1 
r = invalid 
for i in neighbors: 
    if (valid[i]): 
    if (rand() <= 1./c): r = i 
    ++c 

puis r est la réponse (c est le nombre de voisins valides trouvé à ce jour) .

Answer 2

Voici une astuce très soignée dans pseudocode

1. Initialiser votre « résultat courant » à zéro
2. Initialiser un « numéro trouvé » à 0
3. boucle dans toutes les directions possibles. Si elle est valide alors:
   « numéro trouvé »
   • incrément
   • ensemble « résultat courant » à la direction avec une probabilité 1/« Numéro trouvé »

A la fin de cela, vous aura une direction valide (ou nul si non trouvé). S'il y a plusieurs directions valides, elles seront toutes choisies avec une probabilité égale.

Answer 3

Une façon peut-être slighly artificiel ce (pseudo-code):

1. Construire le masque de bits que vous décrivez sur la base desquels les voisins sont ouverts.

2. Utilisez ce masque de bits comme l'index dans un tableau de:

   struct RandomData
{
size_t num_directions;
struct { signed int dx, dy; } deltas[4];
} random_data[16];

   où num_directions est le nombre de voisins ouverts, et deltas[] vous indique comment arriver à chaque voisin.

Cela a beaucoup de données fastidieuses, mais cela supprime le bouclage et le branchement.

MISE À JOUR: Bon, pour une raison ou pour une autre, j'ai eu des problèmes pour laisser partir cette idée. Je blâme un certain nombre d'endoctrinement au sujet de la «programmation pilotée par les données» au travail, puisque ce problème très simple m'a fait «prendre» un peu mieux l'idée de la gestion des données. Ce qui est toujours agréable.

Quoi qu'il en soit, voici une implémentation complète, travail testé et de la fonction aléatoire pas à pas en utilisant les idées ci-dessus:

/* Directions are ordered from north and going clockwise, and assigned to bits: 
* 
* 3  2  1  0 
* WEST | SOUTH | EAST | NORTH 
* 8  4  2  1 
*/ 
static void random_walk(unsigned int *px, unsigned int *py, unsigned max_x, unsigned int max_y) 
{ 
    const unsigned int x = *px, y = *py; 
    const unsigned int dirs = ((x > 0) << 3) | ((y < max_y) << 2) | 
           ((x < max_x) << 1) | (y > 0); 
    static const struct 
    { 
     size_t num_dirs; 
     struct { int dx, dy; } deltas[4]; 
    } step_info[] = { 
#define STEP_NORTH { 0, -1 } 
#define STEP_EAST { 1, 0 } 
#define STEP_SOUTH { 0, 1 } 
#define STEP_WEST { -1, 0 } 
    { 0 }, 
    { 1, { STEP_NORTH } }, 
    { 1, { STEP_EAST } }, 
    { 2, { STEP_NORTH, STEP_EAST } }, 
    { 1, { STEP_SOUTH } }, 
    { 2, { STEP_NORTH, STEP_SOUTH } }, 
    { 2, { STEP_EAST, STEP_SOUTH } }, 
    { 3, { STEP_NORTH, STEP_EAST, STEP_SOUTH } }, 
    { 1, { STEP_WEST } }, 
    { 2, { STEP_NORTH, STEP_WEST } }, 
    { 2, { STEP_EAST, STEP_WEST } }, 
    { 3, { STEP_NORTH, STEP_EAST, STEP_WEST } }, 
    { 2, { STEP_SOUTH, STEP_WEST } }, 
    { 3, { STEP_NORTH, STEP_SOUTH, STEP_WEST } }, 
    { 3, { STEP_EAST, STEP_SOUTH, STEP_WEST } }, 
    { 4, { STEP_NORTH, STEP_EAST, STEP_SOUTH, STEP_WEST } } 
    }; 
    const unsigned int step = rand() % step_info[dirs].num_dirs; 

    *px = x + step_info[dirs].deltas[step].dx; 
    *py = y + step_info[dirs].deltas[step].dy; 
} 

int main(void) 
{ 
    unsigned int w = 16, h = 16, x = w/2, y = h/2, i; 
    struct timeval t1, t2; 
    double  seconds; 

    srand(time(NULL)); 
    gettimeofday(&t1, NULL); 
    for(i = 0; i < 100000000; i++) 
    { 
     random_walk(&x, &y, w - 1, h - 1); 
    } 
    gettimeofday(&t2, NULL); 
    seconds = (t2.tv_sec - t1.tv_sec) + 1e-6 * (t2.tv_usec - t1.tv_usec); 
    printf("Took %u steps, final position is (%u,%u) after %.2g seconds => %.1f Msteps/second\n", i, x, y, seconds, (i/1e6)/seconds); 

    return EXIT_SUCCESS; 
} 

Quelques explications pourraient être dans l'ordre, ce qui précède est assez opaque jusqu'à ce que vous « get » il , Je suppose:

• L'interface à la fonction elle-même devrait être clair. Notez que la largeur et la hauteur de la grille sont représentées par "max_x" et "max_y", pour économiser sur certaines soustractions constantes lorsque vous vérifiez si la position actuelle est sur la bordure ou non.
• La variable dirs est définie sur un masque de bits des directions «ouvertes» à parcourir. Pour une grille vide, il s'agit toujours de 0x0f sauf si vous êtes sur une bordure. Cela pourrait être fait pour gérer les murs en testant la carte, bien sûr. Le tableau step_info recueille des informations sur les étapes disponibles pour chacune des 16 combinaisons possibles de directions ouvertes. Lorsque vous lisez les initialisations (une par ligne) de chaque struct, pensez à l'index de cette structure en binaire et convertissez-le en bits dans dirs.
• La macro STEP_NORTH (et les amis) réduit la saisie et permet de mieux comprendre ce qui se passe.
• J'aime comment la «viande» de random_walk() est juste quatre expressions presque claires, il est rafraîchissant de ne pas voir un seul if là-bas.

Lors de la compilation avec gcc (Ubuntu/Linaro 4.4.4-14ubuntu5) 4.4.5 sur mon 2,4 GHz système x86_64, en utilisant le niveau d'optimisation -O3, la performance semble être un peu moins de 36 millions de mesures par seconde. En lisant l'assemblage, la logique de base est sans branches. Bien sûr, il y a un appel à rand(), je n'avais pas envie d'aller jusqu'au bout et de mettre en place un générateur de nombres aléatoires local pour le mettre en ligne.

NOTE: Cela ne résout pas la question exacte posée, mais je pensais que la technique valait la peine d'être développée.

Answer 4

utilisées:

Chaque emplacement dispose d'un certain nombre d'emplacements cibles valides (un certain endroit peut avoir des cibles moins valides, un chevalier d'échecs a moins de cibles valides lorsqu'ils sont placés dans un coin que quand au milieu du conseil d'administration

Vous souhaitez sélectionner une cible aléatoire parmi tous les mouvements valides disponibles.

---

Algorithme:

Créer un tableau de bits avec un bit représentant une chaque cible valide. (Dans l'exemple original, vous créez un tableau à quatre bits.

Pour chaque cible valide, déterminez si l'emplacement est vide; mettre le bit correspondant dans le tableau de bits à 1 s'il est vide.

Si bit-array> 0, alors number_of_targets = SUM (tableau de bits), sinon return (No Valid Moves).

Sélectionnez un nombre aléatoire compris entre 1 et number_of_targets.

retour (l'emplacement associé à la n-ième bit de réglage dans le tableau de bits)

---

Exemple d'utilisation de l'origine de la question:

X comporte quatre mouvements valides. Nous créons un tableau de 4 bits et le remplissons avec '1' pour chaque emplacement vide; en commençant par la cellule directement au-dessus et en se déplaçant dans le sens des aiguilles d'une montre, on se retrouve avec: 0: 0: 1: 1:

La somme des bits nous indique que nous avons deux endroits où nous pouvons nous déplacer. Notre sélection aléatoire choisira «1» ou «2». Nous nous déplaçons dans le tableau de bits jusqu'à ce que nous trouvions le nième bit défini et que nous passions à cet emplacement.

Cet algorithme fonctionnera pour n'importe quel système avec n'importe quel nombre de cibles valides (non limité à 2-D). Vous pouvez remplacer le sélecteur de nombre aléatoire par une fonction qui retourne récursivement le meilleur mouvement (algorithme MIN-MAX.)