php - Problema de algoritmo: seleccione dos historias por tema para que la misma historia nunca se seleccione para dos temas diferentes

mysql algorithm

Question

En mi lugar de trabajo me he topado con el siguiente problema que me piden que resuelva. Se prefiere una solución aunque no es absolutamente necesaria.

Hay una base de datos con un conjunto de historias, y cada historia tiene un conjunto de temas asociados con ella. Los temas se almacenan en una tabla separada del formulario (storyid, topicid).

La pregunta es cómo seleccionar idealmente 5 temas (o al menos 2, si 5 es imposible) de modo que cada tema tenga 2 historias (o 1, si 2 es imposible) que no se repitan en ninguno de los otros temas seleccionados. El algoritmo también debe devolver cuáles son exactamente las historias "adecuadas" asociadas con cada tema.

¿Es esto realmente un problema de NP-completo que no tiene una solución eficiente que vaya más allá de la simple enumeración de todas las posibilidades o tiene una solución eficiente?

Si no tiene una solución eficiente, intente probarlo (aunque no es absolutamente necesario).

Si tiene una solución eficiente, sea amable y publíquelo.

Answer 1

¿Qué tal esto? (Si entendi tu pregunta)

(En realidad no lo he ejecutado, solo un pensamiento, así que ... podrían ser errores, o podría haber omitido descaradamente algo. Pero, por el momento, mi cabeza cansada piensa que podría funcionar :)

$num_topics = 5;
$stories_per = 5;
$stories = array(); //array to store story ids
//select 5 topics
$query = mysql_query("SELECT * FROM topics ORDER BY RAND() LIMIT ".$num_topics);
//run repeat as many times as you want stories
for($i=0; $i<$stories_per; $i++) {
//repeat through each selected topic
while($row = mysql_fetch_array($query)) {
$q_addon = "";
foreach($stories as $value) {
$q_addon .= "id <> ''".$value."'' AND ";
}
//find a story not yet chosen for each topic
$q = mysql_query("SELECT storyid FROM stories_topics WHERE ".$q_addon." topicid=''".$row[''id'']."'' LIMIT 1");
//add that id to your $stories array
$tmp_id = mysql_result($q,0,''storyid'');
array_push($stories, $tmp_id);
}
}

Answer 2

Intenta adaptar esto para satisfacer tus necesidades:

SELECT topic, story
FROM story_topic
WHERE story IN (SELECT story FROM story_topic GROUP BY story HAVING COUNT(*) = 1);

La clave aquí es saber qué historias solo ocurren en un solo tema. Es posible que desee pre-calcular el número de temas para erradicar la subselección.

Answer 3

Supongamos que tenemos una tabla SQL TopicStory que relaciona TopicID y StoryID, con ese par de columnas que forman una clave primaria compuesta.

El objetivo es encontrar un cierto tipo de conjunto de TopicID. Como máximo, cinco de un conjunto son requeridos por la Pregunta publicada. Una búsqueda en profundidad de estos se describe a continuación.

Con la profundidad de la búsqueda limitada a cinco, el problema declarado no puede ser peor que la complejidad polinómica. Sin embargo, un problema generalizado que solicita la mayor cantidad de temas que se podrían encontrar con restricciones similares (cada tema elegido tiene al menos dos historias no relacionadas con ninguno de los otros temas elegidos) probablemente sea NP-completo.

El uso de la palabra "búsqueda" sugiere un algoritmo de retroceso. A continuación, hemos efectuado el retroceso a través de bucles anidados, donde cada bucle está definido y parametrizado por los bucles que son externos a él.

Antes de dar detalles importantes, puede ser motivador describir un enfoque de "fuerza bruta", junto al cual se puede apreciar más fácilmente el enfoque más complicado.

BRUTE_FORCE:
Generate all possible subsets of five topics.
Test each of these sets for feasibility (each topic has
at least two stories unrelated to any of the other topics).

Nuestro esquema de búsqueda en profundidad supone que los temas tienen un orden total, por ejemplo, ordenados por valores enteros para TopicID. Esto permite que se generen conjuntos de temas sin repetición (debido a la permutación de los temas).

NESTED_LOOPS:
(Loop_1) Select into List_1 all topics with at least two stories.
Iterate through List_1, choosing the first topic %T1%.
PASS control into Loop_2.
CONTINUE in Loop_1.
If the end of List_1 is reached, EXIT with failure.
(Loop_2) Select into List_2 all topics > %T1% with at least two
stories unrelated to %T1%.
Iterate through List_2, choosing the second topic %T2%.
If topic %T1% still has at least two stories unrelated
to %T2%, PASS control into Loop_3.
CONTINUE in Loop_2.
If the end of List_2 is reached, go BACK to Loop_1.
(Loop 3) Select into List_3 all topics > %T2% with at least two
stories unrelated to %T1% or %T2%.
Iterate through List_3, choosing the third topic %T3%.
If topic %T1% still has at least two stories unrelated
to %T2% or %T3%,
and topic %T2% still has at least two stories unrelated
to %T1% or %T3%, PASS control into Loop_4.
CONTINUE in Loop_3.
If the end of List_3 is reached, go BACK to Loop_2.
(Loop 4) Select into List_4 all topics > %T3% with at least two
stories unrelated to %T1%, %T2%, or %T3%.
Iterate through List_4, choosing the fourth topic %T4%.
If topic %T1% still has at least two stories unrelated
to %T2%, %T3%, or %T4%,
and topic %T2% still has at least two stories unrelated
to %T1%, %T3%, or %T4%,
and topic %T3% still has at least two stories unrelated
to %T1%, %T2%, or %T4%, PASS control into Loop_5.
CONTINUE in Loop_4.
If the end of List_4 is reached, go BACK to Loop_3.
(Loop 5) Select into List_5 all topics > %T4% with at least two
stories unrelated to %T1%, %T2%, %T3%, or %T4%.
Iterate through List_5, choosing the fifh topic %T5%.
If topic %T1% still has at least two stories unrelated
to %T2%, %T3%, %T4%, or %T5%,
and topic %T2% still has at least two stories unrelated
to %T1%, %T3%, %T4%, or %T5%,
and topic %T3% still has at least two stories unrelated
to %T1%, %T2%, %T4%, or %T5%,
and topic %T4% still has at least two stories unrelated
to %T1%, %T2%, %T3%, or %T5%, EXIT with success
returning five topics %T1%, %T2%, %T3%, %T4%, and %T5%.
CONTINUE in Loop_5.
If the end of List_5 is reached, go BACK to Loop_4.

El uso de "seleccionar" en la apertura de cada bucle anidado tiene la intención de evocar la posibilidad de que las consultas de SQL implementen gran parte de la lógica. Por ejemplo, el bucle más externo es básicamente obtener el conjunto de resultados para esta consulta:

SELECT TS1.TopicID, Count(*)
From TopicStory TS1
Group By TS1.TopicID
Having Count(*) > 1

Las listas correspondientes de los bucles internos se pueden construir de forma similar mediante consultas SQL, en función de los valores paramétricos de los temas elegidos en los bucles externos. Para ilustrar sin repeticiones innecesarias, saltemos directamente al bucle más interno y hacemos una consulta apropiada para List_5:

SELECT TS5.TopicID, Count(*)
From TopicStory TS5
Where TS5.TopicID > %T4%
and NOT EXISTS ( SELECT *
From TopicStory TSX
Where TSX.TopicID in (%T1%,%T2%,%T3%,%T4%)
and TSX.StoryID = TS5.StoryID
)
Group By TS5.TopicID
Having Count(*) > 1

A esto le seguiría comprobando que% T5% en List_5 produce un conteo de al menos dos historias restantes para el tema% T1%:

SELECT Count(*)
From TopicStory TZ1
Where TZ1.TopicID = %T1%
and NOT EXISTS ( SELECT *
From TopicStory TX1
Where TX1.StoryID = TZ1.StoryID
and TX1.TopicID in (%T2%,%T3%,%T4%,TS5.TopicID)
)

y mutatis mutandi para las otras opciones de temas anteriores.

Aunque podría ralentizar el rendimiento de manera inaceptable, la lógica adicional para restringir los temas relacionados con% T5% (de modo que las opciones de temas anteriores aún conservan al menos dos opciones de historia) se podrían incluir en una consulta. Se vería así:

/*
Given %T1%, %T2%, %T3$, and %T4% from queries above, find all topics %T5% > %T4%
with at least 2 stories not related to %T1%, %T2%, %T3%, or %T4% and such that
%T1% still has at least 2 stories not related to %T2%, %T3%, %T4%, or %T5% and
%T2% still has at least 2 stories not related to %T1%, %T3%, %T4%, or %T5% and
%T3% still has at least 2 stories not related to %T1%, %T2%, %T4%, or %T5% and
%T4% still has at least 2 stories not related to %T1%, %T2%, %T3%, or %T5%
*/
SELECT TS5.TopicID, Count(*)
From TopicStory TS5
Where TS5.TopicID > %T4%
and NOT EXISTS ( SELECT *
From TopicStory TSX
Where TSX.TopicID in (%T1%,%T2%,%T3%,%T4%)
and TSX.StoryID = TS5.StoryID
)
and ( SELECT Count(*)
From TopicStory TZ1
Where TZ1.TopicID = %T1%
and NOT EXISTS ( SELECT *
From TopicStory TX1
Where TX1.StoryID = TZ1.StoryID
and TX1.TopicID in (%T2%,%T3%,%T4%,TS5.TopicID)
)
) > 1
and ( SELECT Count(*)
From TopicStory TZ2
Where TZ2.TopicID = %T2%
and NOT EXISTS ( SELECT *
From TopicStory TX2
Where TX2.StoryID = TZ2.StoryID
and TX2.TopicID in (%T1%,%T3%,%T4%,TS5.TopicID)
)
) > 1
and ( SELECT Count(*)
From TopicStory TZ3
Where TZ3.TopicID = %T3%
and NOT EXISTS ( SELECT *
From TopicStory TX3
Where TX3.StoryID = TZ3.StoryID
and TX3.TopicID in (%T1%,%T2%,%T4%,TS5.TopicID)
)
) > 1
and ( SELECT Count(*)
From TopicStory TZ4
Where TZ4.TopicID = %T4%
and NOT EXISTS ( SELECT *
From TopicStory TX3
Where TX3.StoryID = TZ3.StoryID
and TX3.TopicID in (%T1%,%T2%,%T3%,TS5.TopicID)
)
) > 1
Group By TS5.TopicID
Having Count(*) > 1

El conjunto de características de MySQL es un trabajo en progreso, por lo que posiblemente sea posible una implementación eficiente en procedimientos almacenados, donde los cursores pueden tomar el rol de las listas de temas. Sin embargo, confío en un buen rendimiento si los "cursores" son listas administradas externamente (por ejemplo, en PHP) y las consultas de la base de datos se mantienen lo más simples posible.

Answer 4

Una versión más general del problema es seleccionar para todos los temas (o al menos tantos como sea posible) dos historias para que la misma historia nunca se seleccione para dos temas diferentes.

Marque las historias con S ₁ ... S _m , y los temas con T ₁ ... T _n . Duplique cada tema, es decir, presente las nuevas historias T '' ₁ ... T'' _n , donde T '' _i contiene S _j si y solo si T _{i lo} contiene. El problema ahora se puede reformular de esta manera: seleccione una historia diferente para todos los temas (o tantos como sea posible). Una vez que tenga sus pares de temas e historias, puede unirse de nuevo a los temas duplicados, y cada tema tendrá dos historias.

El problema de encontrar el mayor número posible de pares mientras nunca se selecciona ningún elemento dos veces se denomina el problema de coincidencia bipartita máxima. (Se puede considerar como seleccionar el número máximo de bordes no conectados de un gráfico bipartito ). Hay un algoritmo simple llamado ruta de aumento que lo resuelve en pasos O ((m + n) e) (siendo e el número de bordes) y algunos más sofisticados (como el algoritmo Hopcroft-Karp ) que lo resuelven en alrededor de O ((m + n) ^ 2.5) pasos. El algoritmo de ruta de aumento consiste en buscar rutas "alternas" en el gráfico donde no se selecciona el primer borde de la ruta, el segundo es, el tercero no y así sucesivamente, que invertir las selecciones en la ruta. Probablemente, esto se puede adaptar a su caso sin realmente dividir y unir temas.

Esto es un poco excesivo porque devolverá dos historias para todos los temas, no solo cinco; Probablemente pueda hacerlo mucho mejor cuando solo necesite buscar historias para un número limitado de temas. (Excepto en algunos casos de borde, solo puede seleccionar los cinco temas que tienen el mayor número de historias, descartar las historias que no contienen y luego ejecutar el algoritmo). En cualquier caso, muestra que el problema está lejos de ser NP -difícil.

Answer 5

si eligió 5 temas similares a diferentes historias, tal como lo entendí: puede hacer una combinación para las 2 tablas y usar los 5 primeros en su consulta con la condición de que el título del tema = "tema que desea"

Si eso no ayuda, por favor hazlo claro para mí >>>