Минимальное количество переводов для каждого человека, чтобы посетить каждое место
Я изо всех сил пытаюсь решить следующую проблему:
Предположим, что N сборщиков доходов размещены в N различных местах. Какое минимальное количество переводов (свопов) необходимо для того, чтобы каждый из них был размещен в каждом месте (то есть в каждом месте)?
Например, предположим, что A,B,C,D размещены в местах 1,2,3,4. Теперь с последовательностью передачи:
- A с C & B с D
- C с B & A с D
- B с D & A с C
Таким образом, было необходимо минимум 6 переводов.
Для случая 3 мест нам нужно 4 трансфера. Но в отличие от случая 4 мест, здесь трансферы требуют, чтобы коллекционеры снова посетили то же место.
Я не могу обобщить решение.
Обратите внимание, что я не поднял эту проблему из какой-либо книги или веб-сайта, но сам сформулировал ее для некоторого практического варианта использования. Возможно, проблема довольно проста. Любая помощь будет оценена.
Благодарю.