Алгоритм поиска наименьшего количества сделок между людьми
Я уже давно думаю над этим вопросом.
Допустим, есть список s, содержащий книги, которые продают люди. У меня есть книга в s, и я хочу обменять ее на книгу из s (чего у меня нет).
Каждый человек в этом сценарии продает одну книгу в s, а также хочет, чтобы одна книга была в s.
Есть ли алгоритм, позволяющий определить наименьшее количество сделок, необходимых между людьми, чтобы получить книгу, которую я хочу (и передать мою книгу тем, кто ее хочет)?
Пожалуйста, скажите мне, если это кажется запутанным (потому что, вероятно, так оно и есть).
Спасибо, что ответили на вопрос!
Обновлено: Список s может увеличиваться в любое время.
Да, ваш вопрос сбивает с толку. Вы также, вероятно, пострадаете за то, что не попытаетесь решить эту проблему самостоятельно. Пожалуйста, опубликуйте, что вы пробовали до сих пор.
Гарантировано ли, что никакие два человека не продают одну и ту же книгу и что два человека не хотят одну и ту же книгу? (Другими словами: гарантировано ли, что есть способ поменять местами все книги, и каждый получит ту книгу, которую хочет?)
Можете ли вы предоставить примеры входных и ожидаемых результатов?
@ruakh, что не гарантируется. Иногда сделки были бы невозможны.
@BrentR что сбивает с толку? И причина, по которой я не предпринял попытки, в том, что я не знаю, с чего начать.
Вы единственный человек в группе, который желает временно держать ненужную книгу? Что определяет, готов ли человек обменять книгу, которую он не хочет, в надежде в конечном итоге получить книгу, которую он хочет?
Как они торгуют? Есть ли у книги себестоимость или продажная цена? Потому что в противном случае просто обмен.
@ vivek_23, к книге нет ни цен, ни чего-либо подобного. Предположим, что все возможные обмены между людьми действительно возможны, но я хочу, чтобы обменов происходило как минимум, чтобы я получил ту книгу, которую хочу.
@mypetlion Предположим, что никто, даже я, не захочет держать ненужную книгу в течение длительного периода времени. Единственный раз, когда люди будут держать ненужную книгу, - это если они могут сразу же обменять ее на книгу, которую они хотят.
@GauthamRajesh пример ввода и вывода было бы лучше
Определите, пожалуйста, «обмен» - два человека обмениваются книгами?
@Prune да, это то, что я имею в виду под торговлей.
Могут ли несколько человек предлагать одну и ту же книгу? Например, может ли в s быть три копии «Сильмариллиона»? Благодарим @btilly за этот момент.
@Prune: да, несколько человек могут продавать одну и ту же книгу. Если на то пошло, несколько человек могут захотеть одну и ту же книгу.
@GauthamRajesh: Спасибо; это полностью опровергает мой ответ. Исправление моего ответа делает его эквивалентным первому, поэтому я удаляю его.
@Prune На самом деле, если вы посмотрите выше, ruakh первым заметил то же самое.
Ответы 2
Обновлено: Этот ответ предполагает, что вы хотите, чтобы у всех была желанная книга в конце дня. Другой (-ые) ответ (-и) относится к случаю, когда все, что вас волнует, - это получение желаемой книги ваш.
Я считаю, что это эквивалентно минимальному количеству свопов для сортировки массива. Пронумеруйте книги от 1 до N и пронумеруйте людей от 1 до N так, чтобы человеку я понадобилась книга я. Теперь у нас есть такой массив:
Book: 2 1 4 3
Person: 1 2 3 4
т.е. у человека 1 есть книга 2, у человека 2 - книга 1 и т. д. Теперь сделка - это просто своп в этом массиве, поэтому нам просто нужно минимальное количество свопов для сортировки массива. Это известная проблема.
Если у вас может быть более одного человека, продающего данную книгу, или более одного человека, который хочет данную книгу, вы должны убедиться, что для каждой книги количество людей, которые хотят ее, равно количеству людей, которые ее продают. , иначе решения нет. Затем просто используйте несколько копий книги в массиве «book», снова сортируя людей по числовому значению книги, которую они хотят. Например, предположим, что у нас есть 4 человека и 2 книги, где два человека хотят книгу 1, а два человека хотят книгу 2; у нас было бы:
Book: 2 2 1 1
Person: 1 2 3 4
Опять же, мы хотим отсортировать массив «книжный» за наименьшее количество свопов.
Хорошее решение! :)
Это не эквивалент. Вы не собираетесь сортировать весь массив. Просто найти минимальную цепочку из любого экземпляра книги, которую вы хотите себе, а все остальные могут пойти повесить. (Тот факт, что несколько человек могут иметь определенную книгу, также является важной проблемой.)
@btilly О, в этом случае я неправильно понял вопрос (хотя, в свою защиту, он сформулирован запутанно). Я отмечу это, но сохраню этот ответ, поскольку он все еще может быть полезен, а другой ответ ссылается на него.
@arshajii Прошу прощения за то, что запутал вопрос, хотя это не было моим намерением.
Сообщение, на которое вы ссылаетесь, использует другую концепцию «свопа», которая не переключает два элемента массива. Ответы там не применимы к этой проблеме.
Ваш ответ довольно хорош и имеет смысл (я проголосовал за него), но я сделаю ответ @btilly принятым, потому что его ответ больше относится к моему случаю.
@ user2357112 Спасибо, исправили.
Я бы превратил это в график следующим образом. Книги - это узлы графа. У вас есть направленный переход от книги A к книге B, если кто-то из S предлагает книгу B и хочет книгу A. Вы ищете кратчайший путь от книги, которая у вас есть, к книге, которая вам действительно нужна.
Кратчайший путь можно найти с помощью поиска в ширину. Вы можете реализовать его следующим образом:
todo = [starting_book]
path = {starting_book: None}
while len(todo) and target_book not in path:
book = list.pop(0)
for next_book in neighbors(book):
if next_book not in path:
path[next_book] = book
todo.append(next_book)
if target_book in path:
solution = [target_book]
while solution[-1] != starting_book:
solution.append(path[solution[-1]])
else:
solution = None
Обратите внимание, что решение, которое я предлагаю здесь, дает возможность совершить набор книжных сделок, но не людей. Превратить конкретную книжную торговлю обратно в человека, с которым можно поговорить, можно сделать либо путем поиска по s, либо с помощью таблицы поиска.
Это также не онлайн-решение - отслеживание кратчайших путей при добавлении / удалении вещей из s потребует много работы.
Это хорошее решение. Есть ли способ реализовать это на Java?
@GauthamRajesh См. geeksforgeeks.org/breadth-first-search-or-bfs-for-a-graph для реализации Java поиска в ширину.
Я думаю, это также может зависеть от того, сколько людей там и какие книги они уже имеют или хотят ... можете ли вы это предоставить?