Блог

Главная - Вопросы по программированию - Учитывая список рецептов и список собственных ингредиентов, какой алгоритм лучше всего подходит для определения «Какой ингредиент я мог бы добавить, чтобы получить доступ к большинству рецептов?»

Учитывая список рецептов и список собственных ингредиентов, какой алгоритм лучше всего подходит для определения «Какой ингредиент я мог бы добавить, чтобы получить доступ к большинству рецептов?»

#algorithm #performance #graph-theory #coding-efficiency

Вопрос:

Я надеюсь, что длинное название хорошо объясняет вопрос. Это похоже на номинальный вопрос, поэтому я подозреваю, что для этого существует известный алгоритм, или, может быть, он соответствует NP.

Дана поваренная книга в виде

 cookbook = {
    recipe1: [ingredient1, ingredient2, ingredient35],
    recipe2: [ingredient1, ingredient8, ingredient12], 
    recipe3: [ingredient10, ingredient22, ingredient35],
    ...
}

И список ингредиентов в форме

 ingredients = {
    ingredient1: true, //owned
    ingredient2: false, //unowned
    ingredient3: true,
    ...
}

Какой алгоритм эффективно ответил бы на вопрос «Какой ингредиент вы можете добавить для выполнения большинства рецептов?»

Предполагать

  • Существует большое количество рецептов и ингредиентов
  • В данном рецепте будет не более 10 ингредиентов
  • Вы можете преобразовывать/манипулировать данными так, как считаете нужным
  • Критерии оценки-насколько эффективно вы можете создать алгоритм, который может ответить на вопрос «Какой ингредиент я должен добавить, чтобы приготовить наибольшее количество рецептов, учитывая, что ингредиент у меня уже есть».
  • Человек может добавлять/удалять ингредиенты случайным образом и должен быть в состоянии ответить на вопрос «Какой ингредиент?». вопрос эффективно
  • Сложность пространства пока можно игнорировать
  • Затем цель состоит в том, чтобы разработать структуру данных алгоритм, каким бы сложным он ни был с точки зрения вычислений, который позволяет выполнять быстрые запросы. «Оценка» — это то, насколько быстры эти будущие запросы

Комментарии:

1. Я подозреваю, что преобразование списков ингредиентов в растровые изображения будет хорошо работать. Применение к ним битовой математики происходит быстро и дает ответы, которые легко фильтровать в зависимости от типов ваших запросов.

2. Незначительная ошибка: похоже, вы просите динамическую структуру данных для ответа на различные запросы, а не один алгоритм. Это точная перефразировка? Кроме того, знаете ли вы относительное количество запросов «добавить/удалить ингредиенты» к запросам «лучший ингредиент»? Любая структура данных будет иметь компромисс между оптимизацией этих двух параметров.

3. Да, это лучшая перефразировка, я изменю вопрос. Цель состоит в том, чтобы отформатировать данные (даже если этот шаг является дорогостоящим) таким образом, чтобы будущие вызовы были как можно более быстрыми.

Ответ №1:

Псевдокод

 bestIngredient = 0
bestCount = 0
Loop I  over owned ingredients
   count = 0
   Loop R over recipes
       If I completes R
          increment count
   if count > bestCount
      bestCount = count
      bestIngredient = I

Когда добавляется ингредиент I:

 Loop R over recipies
    If R needs I 
    Add I to R

Комментарии:

1. Я думаю, вы имели в виду цикл над не принадлежащими ингредиентами

2. Это прекрасное решение, за исключением того, что оно довольно медленное. O(Неизвестные * рецепты) ~ O(n^2) Может быть, это лучшее, что существует, но я надеялся на что-то более быстрое

Ответ №2:

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

Ответ №3:

 score = empty hashmap
for each R in recipes
  missing = empty list
  for each I in R
    if ingredients[i] = false
      missing  = I
  if size(missing) = 1
    I = missing[0]
    score[I]  
result = choose key I in score with maximum value
Метки: , ,