Алгоритм опроса

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

До сих пор я придумал структуру графа, вот теоретический пример того, как она будет выглядеть:

(У меня есть только базовые знания теории графов, поэтому, пожалуйста, извините за выбор слова, которое может быть не таким точным, как могло бы быть)

введите здесь описание изображения

Круги, такие как A, B, C, представляют собой вопросы, а значение в ссылках представляет собой предварительное условие для доступа к вопросу.

NULL означает, что предварительное условие отсутствует, а значение типа «0» или «1» означает, что предыдущий вопрос должен иметь ответ со значением «0» или «1» для отображения вопроса.

Конкретный пример: я нахожусь в раунде А. У меня есть два возможных ответа. Первый имеет значение «0». Второй - значение «1». Если я выберу ответ со значением «0», я перейду к вопросу B.

Я сейчас в раунде B. Каким бы ни был ответ, я пойду в раунд E, потому что нет никаких предварительных условий.

E - листовой узел, поэтому я возвращаюсь к B. У B есть еще один дочерний узел F без предварительного условия, поэтому я перехожу к вопросу F. Давайте закончим поток на этом.

У меня также может быть один вопрос с несколькими предварительными условиями. Это представлено вопросом N. Доступ к нему возможен только в том случае, если ответ «5» на вопрос F и «DE» на вопрос I. В этом случае, после ответа на вопрос F, поскольку в этом состоянии действует только одно предварительное условие, мы вернется на график, и только после ответа «DE» на вопрос I мы сможем перейти к вопросу N.

Мой вопрос касается алгоритма, который следует использовать для такого опроса. Есть ли существующий алгоритм, охватывающий этот вариант использования? Я думал, что это похоже на обход графа DFS, но условия заставляют меня сомневаться.

Кроме того, не слишком ли я усложняю, и можно ли это выразить гораздо проще? Мне очень нужен совет на этом этапе.

Спасибо за вашу помощь !


algorithm survey
person LaCartouche    schedule 19.01.2017    source источник
comment
Возможно ли иметь несколько дуг или несколько меток в одной дуге? Например, после вопроса «А» перейти к «Б» в ответе было «0» или «1» (но не, если это было «2»).   -  person jdehesa    schedule 19.01.2017
comment
Между двумя узлами будет только одна дуга. Однако в случае узла N в схеме у вас может быть несколько дуг, идущих к одному узлу, если они исходят из разных узлов.   -  person LaCartouche    schedule 19.01.2017

Ответы (2)


arrow_upward
1
arrow_downward

Согласно вашему описанию, я бы немного изменил концепцию предложенного вами графика на следующее:

  • Превратите его в ориентированный граф (то есть граф, в котором каждая дуга имеет источник и цель).
  • Имейте по одному узлу на вопрос и по одному узлу на ответ (каждый ответ на каждый вопрос представляет собой отдельный узел). У каждого узла вопроса должен быть один флаг, чтобы определять, является ли он «типом вопроса» или «типом ответа», и один флаг, чтобы отмечать, был ли он посещен.
  • Каждый узел вопроса будет связан с каждым его ответом (направление [Вопрос] -> [Ответ]).
  • Каждое предварительное условие ответа («чтобы достичь вопроса B, вам нужно ответить на 0 в вопросе A») будет представлено дугой от одного ответа (узел [ответ 0 вопроса A]) до вопроса, который он «разблокирует» (узел [вопрос B ]). Если вопрос требует нескольких ответов, у него будет несколько входящих дуг.
  • Каждое предварительное условие вопроса («чтобы достичь вопроса D, вам нужно ответить на вопрос A, независимо от выбора») будет представлено дугой от одного вопроса (узел [Вопрос A]) к другому вопросу (узел [Вопрос D]).

Тогда алгоритм будет выглядеть следующим образом:

  1. Имейте стек ожидающих узлов P, который изначально содержит узел, соответствующий первому вопросу опроса.
  2. Вставьте первый элемент P, Q, который всегда должен быть узлом вопроса, и отметьте его как посещенный.
  3. Получите список преемников Q (узлов, которые связаны с текущим узлом через исходящую дугу) и разделите его на «последователей ответа», QtoA и «преемников вопроса» ", QtoQ.
  4. Добавьте все элементы в QtoQ в P (если есть какой-либо способ упорядочить их, например, по некоторому "идентификатору вопроса", убедитесь, что они добавлены в способ, которым первый элемент заканчивается на вершине стека).
  5. Задайте вопрос (вы даже можете сохранить вопросы на графике и извлечь из него всю необходимую информацию).
  6. Получите узел выбранного ответа A из QtoA, отметьте его как посещенный и по очереди соберите список всех его последователей, AtoQ.
  7. Для каждого узла R в AtoQ (опять же, рассмотрите возможность заказа здесь, если он есть), если все предшественники R (т. Е. Узлы подключенные к R через входящую дугу) помечаются как посещенные, затем добавляется R к P.
  8. Если в P есть какие-либо узлы, переходите к шагу 2.

Это должно воспроизводить описанный вами порядок. Если вы хотите иметь возможность иметь несколько возможных ответов на разблокировку (например, «из A вы перейдете к B, если вы ответите 1 или 2»), вам нужно будет сделать еще несколько настроек (а именно, на шаге 6 вам нужно будет заменить «посещенная» проверка на «тип ответа» предшественников R на что-то вроде «R достижима через посещенные узлы от предшественника предшественника R "), но все равно должно быть возможно заставить его работать.

Возможно, вы уже знаете об этом, но если вы заинтересованы в использовании графа в качестве единственного источника данных (что может быть, а может и нет), вы можете найти интересные графо-ориентированные базы данных, такие как Neo4j.

person jdehesa    schedule 19.01.2017
comment
Это кажется действительно интересным. Спасибо за идею, я сейчас занимаюсь этим. - person LaCartouche; 20.01.2017
comment
Я считаю, что алгоритм в этом состоянии не соблюдает порядок вопросов. Он будет правильно обрабатывать один уровень вопроса-ответа-вопроса, но затем переключится на вопрос, который находится в QtoQ, вместо того, чтобы идти дальше вниз по дереву. Однако я думаю, что использование другого стека вместо того, чтобы помещать элементы QtoQ в P, решит проблему. - person LaCartouche; 20.01.2017
comment
@LaCartouche Да, ты прав! Я отредактировал ответ - как вы сказали, вам понадобится стек вместо очереди. - person jdehesa; 20.01.2017

arrow_upward
0
arrow_downward

Вот мое общее представление о том, как решить вашу проблему.

Согласно представленному вами графику, я предполагаю, что для каждого вопроса (узла) вы можете указать для данного ответа, какие вопросы (узлы) могут быть разблокированы. Под «могут быть разблокированы» я имею в виду, что они действительно разблокируются или вы только что выполнили одно из условий, чтобы разблокировать вопрос.

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

Когда значение любого счетчика уменьшается до нуля, вы добавляете разблокированный вопрос в очередь или стек (вы можете выбрать, какой порядок вы предпочитаете - FIFO или LIFO). Конечно, вы начинаете с очереди, содержащей безусловные вопросы (только «А» в вашем случае).

С FIFO (очередью) вы получите BFS-подобный порядок обхода графа. С LIFO (стеком) вы получите порядок, подобный DFS. Все, что вам удобно.

person Ardavel    schedule 19.01.2017
comment
Хорошо, я понимаю, что есть идея, о которой я не говорил. На графике представлены не только предварительные условия для разблокировки вопросов, но и последовательность, в которой они отображаются. Поэтому я не могу использовать для этого стек / очередь. Порядок имеет значение. Но спасибо за ответ. - person LaCartouche; 19.01.2017
comment
Так что в вашем случае подходит подход DFS. Случай LIFO - достойная отправная точка. Самым важным изменением является то, что вы должны переходить к следующему вопросу сразу после уменьшения значения счетчика до нуля. Кроме того, вам необходимо отсортировать исходящие ребра (узлы, для которых вы уменьшаете счетчики после определенного ответа, если их много). Рекомендую использовать рекурсию для удобной реализации этого случая. Просто взгляните на некоторый эталонный псевдокод DFS, и все станет более ясным. - person Ardavel; 19.01.2017