October 20th, 2013

общежитие, Корваллис

traveling salesman problem?

Кстати, а существует ли общее решение задачи о волке, козе и капусте?
Другими словами, пусть программисту задан список из n живых существ, и для каждого из них есть подмножество (из них же), которoе нельзя оставлять вместе с ним без присмотра. Кто кого ест или кто кем съеден - это неважно. Нужно перевезти их в лодке, где есть k свободных мест. Выдать алгоритм (не обязательно самый быстрый) для их перевозок, или прийти к выводу о том, что его не существует.

(Всякие сложности типа "не оставлять мумрика и мямзика вместе с хруброй, потому что вдвоем они её обязательно съедят -- а поодиночке нет" мы пока не будем включать в задачу).