Задача сложного алгоритма

Ответ 1

Более общая версия проблемы - выбрать для всех тем (или, по крайней мере, как можно больше) две истории, чтобы одна и та же история никогда не выбиралась для двух разных тем.

Отметьте истории с помощью S ₁... S _m, а темы с T ₁... T _{nсуб > . Дублируйте каждую тему, то есть введете новые истории T ' 1... T' n, где T ' i содержит S j тогда и только тогда, когда содержит T i. Теперь проблему можно перефразировать следующим образом: выберите другую историю для всех тем (или как можно больше). После того, как у вас есть свои пары сюжетных сюжетов, вы можете снова присоединиться к дублированным темам, и каждая тема будет иметь две истории.}

Проблема нахождения наибольшего числа пар, хотя и никогда не выбирая ни один элемент дважды, называется максимальной двудольной совпадающей задачей. (Вы можете думать об этом как о выборе максимального количества несвязанных ребер из двухстороннего графика.) Существует простой алгоритм, называемый дополнительным путем, который решает его в O ((m + n) e) этапы (e - количество ребер) и некоторые более сложные (такие как алгоритм Хопкрофта-Карпа), которые решают ее в пределах шагов O ((m + n) ^ 2,5). Алгоритм расширенного пути состоит в поиске "чередующихся" путей в графе, где первый край пути не выбран, второй - третий и т.д., Чем инвертирование выбора на пути. Это может быть, вероятно, адаптировано к вашему делу без фактического разделения и объединения тем.

Это немного перебор, потому что он вернет две истории для всех тем, а не только пять; вы, вероятно, можете сделать намного лучше, когда вам нужно только найти истории для ограниченного количества тем. (За исключением некоторых случаев краев, вы можете просто выбрать пять тем, которые имеют наибольшее количество историй, отбросить истории, не содержащиеся в них, и запустить алгоритм.) Во всяком случае, это показывает, что проблема далека от NP -Жесткий.

Ответ 2

Предположим, что у нас есть SQL-таблица TopicStory, которая связывает темуID и StoryID, с этой парой столбцов, образующих составной первичный ключ.

Цель состоит в том, чтобы найти определенный тип набора тем. Не более пяти в наборе требуются в опубликованном Вопросе. Поиск по глубине для они описаны ниже.

С глубиной поиска, ограниченной в пять, указанная проблема не может быть хуже полиномиальной сложности. Однако обобщенная задача который запрашивает самый большой набор тем, которые можно найти с помощью ограничения (каждая выбранная тема имеет по меньшей мере две истории, не связанные с любая из других выбранных тем), вероятно, NP-complete.

Использование слова "поиск" предполагает алгоритм обратного отслеживания. Ниже мы осуществили обратное отслеживание через вложенные циклы, где каждый цикл определяемый и параметризованный контурами, которые являются внешними для него.

Прежде чем дать подробные данные, может быть мотивирующим описание подход "грубой силы", рядом с которым более сложный подход может более легко оценить.

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).

Наш эскиз поиска по глубине предполагает, что темы имеют общий порядок, например упорядоченных по целочисленным значениям для TopicID. Это позволяет наборы тем для генерации без повторения (из-за перестановки тем).

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.

Использование "select" при открытии каждого вложенного цикла предназначено для вызова возможность SQL-запросов реализовать большую часть логики. Для Например, самый внешний цикл - это просто получение набора результатов для этот запрос:

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

Соответствующие списки внутренних циклов могут быть построены аналогично по SQL-запросам в зависимости от параметрических значений тем, выбранных в внешние петли. Чтобы проиллюстрировать без лишнего повторения, скажите право на самый внутренний цикл и дать соответствующий запрос для 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

После этого будет проверяться, что% T5% в List_5 создает количество не менее двух историй осталось для темы% 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)
                  )

и mutatis mutandi для других предыдущих вариантов выбора темы.

Хотя это может замедлить производительность неприемлемо, дополнительная логика для ограничения тем, связанных с% T5% (так, чтобы выбор предыдущих тем по-прежнему сохраняются как минимум два варианта сюжета), которые могут быть перенесены в один запрос. Это будет выглядеть так:

/*
   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

Набор функций MySQL - это работа, которая, по-видимому, эффективна возможна реализация в хранимых процедурах, где курсоры могут принимать роль списков тем. Однако я был бы уверен в хорошей производительности, если "курсоры" - это управляемые извне списки (например, в PHP) и запросы к базе данных как можно проще.

Ответ 3

Попробуйте адаптировать это в соответствии с вашими потребностями:

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

Ключ здесь - знать, какие истории происходят только в одной теме. Возможно, вам захочется предварительно вычислить количество тем для устранения подзапроса.

Ответ 4

Как насчет этого? (Если я понял ваш вопрос)

(Я на самом деле не запустил его - просто мысль - так... может быть ошибкой, или я мог бы явно пропустить что-то. Но на данный момент моя усталая голова думает, что это сработает:)

$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);

    }
}

Ответ 5

Если вы выиграете аналогичные 5 тем, похожих на разные истории, как я понял: так что вы можете сделать объединение для 2 таблиц и использовать 5 лучших в своем запросе, где заголовок условия = "тема, которую вы хотите"

если это не поможет мне прояснить мне → >