Скажем, у нас есть группа людей, и каждый может захотеть продать или купить один из предметов М, как найти замкнутый путь среди них для обмена?

Скажем, у нас есть N человек и M предметов (когда у человека есть определенный предмет, у нее обычно есть только одна часть). Например,

  • человек 1 имеет элемент A, C, D и хочет элемент F
  • человек 2 имеет элемент B, C и хочет E
  • человек 3 имеет элемент E и хочет G

    ...

Вы получаете идею. Таким образом, это в основном проблема соответствия спроса и предложения, и если мы представляем это как матрицу персонального элемента, она будет очень редкой.

Итак, мой вопрос:

  1. Как найти самую длинную серию (или путь) поставки & сопоставление спроса между некоторыми людьми и, следовательно, может способствовать обмену?
  2. Как найти кратчайшую серию (или путь), в которой участвуют более 2 человек (так что один-к-одному обмену я думаю, что я понял, как с помощью некоторых операций с матрицами)?
  3. Какова была бы сложность поиска наиболее длинных /кратчайших путей?

Любые советы будут оценены.

3 голоса | спросил Shuai 21 +03002016-10-21T18:11:00+03:00312016bEurope/MoscowFri, 21 Oct 2016 18:11:00 +0300 2016, 18:11:00

3 ответа


3

Вместо разреженной матрицы я бы пошел с Directed Graph , где каждый узел является человеком, и каждая ссылка является потенциальной транзакцией.

Каждый цикл на графике является потенциальной сделкой. Для получения дополнительной информации см. Лучший алгоритм обнаружения циклов в ориентированном графе .

ответил Dan Pichelman 21 +03002016-10-21T18:32:04+03:00312016bEurope/MoscowFri, 21 Oct 2016 18:32:04 +0300 2016, 18:32:04
3

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

Чтобы создать график, сделайте следующее:

  • Нарисуйте узел для каждого человека.
  • Также нарисуйте узел для каждого элемента.
  • Всякий раз, когда человек имеет элемент, нарисуйте стрелку из этого человека на этот элемент . (Идея такова: если человек счастлив, тогда мы можем получить предмет.)
  • Всякий раз, когда человек хочет элемент, нарисуйте стрелку из этого элемента на person . (Идея такова: если у нас есть предмет, тогда мы можем сделать человека счастливым.)

Ваша цель - просто найти схему на этом графике.

Это означает, что ваш вопрос можно перефразировать так: «Как найти схемы в двунаправленном графе?» Алгоритмы, описанные в этих вопросах и ответах, могут быть полезны:

(Разница между цепью и заключается в том, что схема может посещать один и тот же узел несколько раз (хотя она не может использовать одну и ту же стрелку несколько раз), в то время как цикл может посещать только один узел один раз. В контексте вашей проблемы цикл будет означать, что каждый человек участвует только в одной сделке, и каждый элемент участвует только в одной сделке.) р>

ответил Tanner Swett 21 +03002016-10-21T22:16:02+03:00312016bEurope/MoscowFri, 21 Oct 2016 22:16:02 +0300 2016, 22:16:02
-1

Изменить: Мой другой ответ лучше, чем этот; посмотрите на это.

Проблема может быть представлена ​​путем создания сетки, заполненной точками. Сетка имеет:

  • N , по одному для каждого человека.
  • M , по одному для каждого элемента.
  • Одна зеленая точка, когда человек желает дать элемент (потому что «дать» начинается с «G» для «зеленого»). Например, если Боб готов торговать до трех яблок, тогда поместите 3 зеленых точки в ячейку сетки, которая находится в строке, представляющей Боб и столбец, представляющий яблоки.
  • Одна красная точка, когда человек хочет получать элемент.

(В математических выражениях это были бы две матрицы N × M , называемые G и R . )

Вот один из алгоритмов решения вашей проблемы. Вероятно, это не лучший алгоритм best , а алгоритм a .

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

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

Во-вторых, найдите на графике направленный цикл . Этот цикл дает ответ.

В качестве примера предположим, что у Боба есть яблоко и он хочет оранжевого цвета, а у Сары апельсин и хочет яблоко. Сетка будет содержать

  • зеленая точка для (Боб, яблоко),
  • зеленая точка для (Сара, оранжевый),
  • красная точка для (Боб, оранжевый) и
  • красная точка для (Сара, яблоко).

Цикл, который мы находим

  • начинается с зеленой точки (Боб, яблоко) и идет к красной точке (Сара, яблоко) (Боб дает яблоко, а Сара получает его);
  • идет от красной точки (Сара, яблоко) до зеленой точки (Сара, апельсин) (поскольку Сара получила яблоко, она готова дать апельсин);
  • идет от зеленой точки (Сара, апельсин) до красной точки (Боб, оранжевый) (Сара дает апельсину Бобу); и
  • возвращается из красной точки (Боб, оранжевый) обратно к зеленой точке (Боб, яблоко) (Боб получил апельсин и поэтому готов отказаться от яблока).
ответил Tanner Swett 21 +03002016-10-21T21:55:28+03:00312016bEurope/MoscowFri, 21 Oct 2016 21:55:28 +0300 2016, 21:55:28

Похожие вопросы

Популярные теги

security × 330linux × 316macos × 2827 × 268performance × 244command-line × 241sql-server × 235joomla-3.x × 222java × 189c++ × 186windows × 180cisco × 168bash × 158c# × 142gmail × 139arduino-uno × 139javascript × 134ssh × 133seo × 132mysql × 132