Encontrar conjuntos de "huellas digitales"

11

Digamos que tenemos 10 personas, cada una con una lista de libros favoritos. Para una persona determinada, X, me gustaría encontrar un subconjunto especial de libros de X que le guste solo a X, es decir, no hay otra persona a la que le gusten todos los libros del subconjunto especial de X. Pienso en este subconjunto especial como una "huella digital" única para X.

Agradecería sugerencias sobre un enfoque para encontrar tales conjuntos. (Si bien esto se lee como un problema de tarea, está relacionado con un problema en mi investigación de biología que estoy tratando de resolver).

edron79
fuente
1
¿El rango / número de libros posibles es finito? ¿Se puede hacer esta identificación de "huella digital" sobre la marcha, ya que cada libro se agrega a la lista de favoritos de alguna persona, o se le da el conjunto de listas de antemano?
Paresh

Respuestas:

6

Supongo que quiere que la huella digital sea lo más pequeña posible. Entonces este es el problema del conjunto de golpes : para cada persona, haga una lista de todos los libros que le gustan a X pero no a esta persona. Entonces, el objetivo es seleccionar al menos un libro de cada lista. El problema es NP-hard, por lo que no puede esperar encontrar un algoritmo que siempre lo resuelva de manera óptima en tiempo polinómico. El algoritmo codicioso tiene un mal límite teórico en el peor de los casos, pero a menudo funciona bastante bien en la práctica. Si desea resolverlo de manera óptima, un solucionador de programación lineal entera debería ser capaz de resolver instancias de hasta 1000 o quizás 10000 libros. Si proporciona más detalles sobre el tamaño y la estructura de sus instancias, podríamos sugerir otros enfoques.

Falk Hüffner
fuente
+1 ¡Por supuesto que tienes razón! :) No es difícil construir ejemplos en los que mi algoritmo codicioso falla. Ups
Patrick87
OP: Muchas gracias por los comentarios: la solución del algoritmo codicioso original me hizo avanzar en la dirección correcta. El espacio total en el que estoy trabajando se refiere a cientos de personas y miles de "libros". Si esto es factible con el enfoque de programación entera, me encantaría saber más al respecto.
Merbs
4

Este no es un algoritmo particularmente inteligente, pero es polinómico y creo que debería funcionar. Toma cualquier set. Para cada elemento de este conjunto, cuente el número de conjuntos restantes que no lo contienen y recuerde qué conjuntos lo contienen. Elija el elemento con la cuenta más alta y vuelva a hacer las cuentas para los elementos restantes, ignorando los conjuntos que carecen del elemento que acaba de elegir. Continúe hasta que todos los conjuntos restantes hayan sido eliminados de la consideración.

Ejemplo: deje , , y . Luego tenemos conteos , y . Elegimos 1, eliminando los conjuntos y que no lo contenían; rehaciendo los conteos, tenemos y . Elegimos 2 como el siguiente elemento y eliminamos de la consideración. Ya hemos terminado, y nuestro conjunto de "huellas digitales" es . EDITAR: para completar el ejemplo, debe hacer que los otros conjuntos de huellas digitales salgan como ,A={1,2,3}B={2,3,4}C={2,4,6}D={1,3,5}c1=2c2=1c3=1BCc2=1c3=0D{ 3 , 4 } { 6 } { 5 }{1,2}{3,4}{6} y .{5}

No he pensado mucho en esto, pero intuitivamente, parece que debería funcionar. La idea es tomar con avidez como el siguiente elemento de la huella digital establecer el elemento que cubre los conjuntos más descubiertos.

Patrick87
fuente
Vea la respuesta de Falk Huffner, donde identifica correctamente su problema como el problema NP-Hard Hitting Set. Parece que mi respuesta da la aproximación codiciosa habitual para el problema, que no es malo, pero tampoco es óptimo.
Patrick87
0

Tal vez no entendí la pregunta correctamente (basado en respuestas algo complicadas), pero aquí va. Simplemente revisas a todas las personas y todos sus libros que les gustan. Usted crea una estructura de datos (preferiblemente un Hash Map ), donde la clave es el libro y el valor es una lista de personas a las que les gusta este libro. Rellena esta estructura de datos de una manera intuitiva (para cada par de persona / libro, agrega a la persona a la lista ). Luego revisa las teclas del mapa y donde la longitud de la lista es igual a uno, entonces este libro es uno de los de esta persona en particular.M [ b o o k ]MM[book]fingerprint books

Déjame demostrar en el código de Python:

%persons with books they like (it could also be a list or a set)
joe='ABCD'
andy='CDG'
frank='AHX'
anna='HAYZ'
matt='ACH'
%just transformation form variables, to names
names={joe:"Joe",andy:"Andy",frank:"Frank",anna:"Anna", matt:"Matt"}
%the map, from books to persons who like this book
books={}

%for each person
for p in names:
    %go through his liked books
    for book in p:
        %if book is already in the map, then append the person
        if book in books:
            books[book].append(names[p])
        else:
            %if not, then create a new book, and append the current person
            books[book]=[names[p]]

%create the fingerprint map (from person to books he likes)
fingerprint={}

%for each person create an empty list
for p in names:
    fingerprint[names[p]]=[]

%for each book in the map
for book in books:
    %if only one person likes this book, then it must be a part of his fingerprint
    if len(books[book])==1:
        fingerprint[books[book][0]].append(book)

print fingerprint

El código imprime:

{'Frank': ['X'], 'Matt': [], 'Andy': ['G'], 'Joe': ['B'], 'Anna': ['Y', 'Z']}
Nejc
fuente
0

Este es el OP (no se registró en el envío inicial, por lo que ahora no puedo comentar correctamente). Muchas gracias por los comentarios: la solución del algoritmo codicioso original me hizo avanzar en la dirección correcta. El espacio total en el que estoy trabajando se refiere a cientos de personas y miles de "libros". Si esto es factible con el enfoque de programación entera, me encantaría saber más al respecto.

edron79
fuente
Puse tu comentario de tal manera que Falk sería notificado.
Merbs