Вот что получилось: Светодиоды расставлены согласно картинке. http://forum.amperka.ru/attachments/туристы_-jpg.19205/
Да все верно, по этой логике и перевозить. Думаю, ничего сложного так программу написать, алгоритм простейший же. Туда максимальное колво груза, включая сборный, в пределах грузоподьемности, обратно минимальное колво. В итоге все переедут.
Я так не думаю Обобщи задачу, и увидишь, что не простейший. Не стоит писать под известное решение алгоритм, надо писать обобщённый алгоритм. Ок, давай я изменю вводные: человека уже четыре, а не три. Или - 10 человек, причём известно, что среди них существует такая комбинация весов, что в лодку могут поместиться сразу четыре из этой десятки. Причём таких четвёрок - две, одна из них - оптимальная, другая - проигрывает первой. Простейший, говоришь?
Не, ты мне умозаключения не выдавай - ты простейший алгоритм напиши Задача-то - ещё найти эту более тяжёлую четвёрку. А кто сказал, что они вообще будут, такие четвёрки? И не будет ли пары троек и одной четвёрки, при использовании которых получится сделать меньшее количество шагов, чем в случае с двумя четвёрками? Понимаешь, что задача не так проста, как кажется? Ты должен доказать, что найденный вариант (при всём богатстве возможных комбинаций) - ещё и самый лучший. Не писать код по готовому решению - а предоставить обобщённый алгоритм Возьмёшься? Я - нет. ибо задача - крайне сложна. А конкретный упрощённый пример - только путает своей кажущейся простотой. З.Ы. Знаешь - это как в небесной механике, где задача двух тел вполне себе решаема, а задача всего лишь трёх тел - уже огого.
А ни кто не помнит что просил ТС? Ему нужно было устройство моделирующее игровую ситуацию. Вопрос о создании прототипа искусственного интеллекта самостоятельно находящего оптимальное решение поставленной задачи не стоял. ЗЫ: Хотя вопрос интересный.
А мне кажется, что не та эта задача и ее сложность кажущаяся. Если собраться и обдумать, наверняка алгоритм простой получится. Чай не шахматы. А даже к ним алгоритмы придумали.
Попробуй Не получится алгоритм простым, под него, как минимум, нужна мат. модель. Скажем, если взять тот же А* (алгоритм поиска пути) - то он, при всей его понятности - далеко не так прост, как кажется, плюс - имеет в основе мат. модель. С оценками сложности и пр. Глянь, сколько дядек над ним работало, прежде чем он появился на свет в конечном виде Что касается шахмат: удачный пример, как раз в пользу моих доводов Ни разу не просто, ни разу не быстро, не доказано, что текущие реализации алгоритмов шахматных программ - оптимальны (если не ошибаюсь) до сих пор.
У шахмат вариантов миллиарды и миллиарды, да еще и зависят от ответки, т.е. непредсказуемые, а тут главное соблюдать стратегию и вариантов будет не так много или вообще один, как в случае с примером автора.
Лады, ждём от тебя простейший алгоритм, который принимает на входе: 1. Кол-во людей к перевозке с массами каждого из них; 2. Грузоподъёмность лодки. Алгоритм должен на выходе выдавать минимально возможное количество ходов. Причём - доказанное минимальное, не важно, как - тупым перебором, или мат. моделью. Сделаешь?
Кстати сказать, родственный тип задач - задача раскроя. Более-менее успешно решена, но - тоже далеко не проста. Частный случай применимости к обсуждаемой задаче, задача о ранце - почитай, там есть обоснования и методы решения.
По мне это не ханойские башни. Нет требования к порядку попадания на "новую землю". Мне кажется эта задача простая, т.к. нигде нет требований по порядку, т.е. нужно продумать алгоритм переправы всех людей кратчайшим путём, т.е. свести к максимально кучному перевозу людей. Но, надо понять имеет ли решение ли задача. Условимся, что задача решена если ВСЕ N людей окажутся на другой стороне. K - количество толстых людей, которые могут переплыть только в одиночку. H(K)>M-min(H) L - количество худых, которые могут переправиться как минимум вдвоём. Проще говоря, это количество нетолстых. B - мест в лодке. Если К>=1, то должно быть L>=2 (предельный случай уже описан в данной теме). Нет людей толще М. 1 ход равен одной переправе в одну сторону. Простой случай: Мест в лодке В = 2 и предельная масса М. 2 худых и K толстых. X - худой, Т - толстый Спойлер: На переправу одного толстого уходит 4 хода Я тут попробую нарисовать состояния через дефис Слева это Худые и Толстые на левом берегу, которым нужно перебраться на правый берег. Посерёдке те кто в лодке, стрелкой указывал куда плывут. Справа - те кто переправился. Код (C++): XX - 2 худых и T...T - K толстых XX KT - 0 - 0 \\все пришли к берегу и хотят переправиться KT -> XX - 0 \\2 худых переправляются KT - 0 - XX \\ 2 худых переправились KT <- X - X \\1 худой остаётся, один возвращается X KT - 0 - X \\ переправился X KT-1 -> T - X \\ Толстый перепрывает X KT-1 - 0 - T X \\переплыл X KT-1 <- X - T \\ Худой возвращается XX KT-1 - 0 - T \\Вернулись к началу, но 1 толстый переправлен XXT - 2 Худых, 1 Толстый. XXT - 0 - 0 T -> XX - 0 T - 0 - XX T <- X - X XT - 0 - X X -> T - X X - 0 - XT X <- X - T XX - 0 - T 0 -> XX - T 0 - 0 - XXT 5 ходов XXTT - 2 Худых, 2 Толстых. XXTT - 0 - 0 TT -> XX - 0 TT - 0 - XX TT <- X - X XTT - 0 - X XT -> T - X XT - 0 - XT XT <- X - T XXT - 0 - T Пришли к исходному состоянию предыдущего варианта. см. предыдущую задачу. 9 ходов На переправу всех толстых уйдёт 4К ходов. На переправу всех уйдёт 4K+1 ходов. Спойлер: Лирика Три переправы из 4ёх это вынужденные переправы худых. Напомнило Пусть будет только L худых, тогда: Спойлер: то получается L+2 ходов на переправу всех Код (C++): X - 1 худой X - 0 - 0 0 -> X - 0 0 - 0 - X 1X - 1 XX - 2 худых XX - 0 - 0 0 -> XX - 0 0 - 0 - XX 2X - 1 XXX - 3 худых ХХX - 0 - 0 Х -> XX - 0 X - 0 - XX X <- X - X XX - 0 - X см. предыдущее решение 0 -> XX - X 0 - 0 - XXX 3X - 3 ХХХХ - 4 худых XXXX - 0 - 0 ХХ -> XX - 0 ХХ - 0 - XX XX <- X - X XXX - 0 - X см. предыдущее решение Х -> XX - X X - 0 - XXX X <- X - XX XX - 0 - XX 0 -> XX - XX 0 - 0 - XXXX 4X - 5 XXXXX - 5 худых XXXXX - 0 - 0 XXX -> XX - 0 XXX - 0 - XX XXX <- X - X XXXX - 0 - X см. предыдущее решение XXXX - 0 - X ХХ -> XX - X ХХ - 0 - XXX XX <- X - XX XXX - 0 - XX Х -> XX - XX X - 0 - XXXX X <- X - XXX XX - 0 - XXX 0 -> XX - XXX 0 - 0 - XXXXX 5X - 7 XXXXXX - 6 худых XXXXXX - 0 - 0 XXXX -> XX - 0 XXXX - 0 - XX XXXX <- X - X XXXXX - 0 - X см. предыдущее решение 6X - 9 ... последовательность 1 1 3 5 7 9... L+2 ходов на L худых, при L>=5 K>=1 толстых и L>=5 худых - количество ходов 4K+L+2. (Если худых меньше, то кол-во ходов будет меньше, см. спойлер с худыми). Рассмотрим случай когда мест в лодке В и предельная масса М. Нужно выделить самых толстых (К), которые только в одиночку могут переплыть. Они переправятся за 4K ходов. Останутся те, кто может группой плавать. В таком случае, мне кажется, нужно опять взять самого легкого и заставить паромить. Далее перебором нужно найти стайки такие, что сумма(МассЛюдейСтайки(i))<M-min(H). В таком случае кол-во ходов будет от 1 до L+2, т.е. по парам оставшиеся будут плавать (в худшем случае). Алгоритм такой: 1. Найти кол-во сочетаний (комбинаторика) из L-1 (самый худой паромщик) по B-1 (оставляем место для паромщика). 2. Найти из них стайку с MAX{сумма(МассЛюдейСтайки(i))} < [M-min(H)]. Стайка с максимально допустимой массой - данное требование обеспечит минимальное кол-во ходов. 3. Переправить стайку (чтобы кто-нибудь просто так не катался) (Теперь L уменьшилось на количество переправленных людей). 4. Повторяем процесс с п.1 до тех пор пока не кончатся люди или не перестанет выполняться сумма(МассЛюдейСтайки(i))<M-min(H). 5. Если люди остались в куче, то повторяем п.1 но уменьшаем допустимое кол-во мест в лодке на 1 (Например, на 2-й интерации нужно будет найти кол-во сочетаний из L-1 по В-2) 6. Повторять п.5. до тех пор пока не кончатся люди в общей куче. Количество ходов в таком случае будет 2*Ы, где Ы - кол-во стаек, при этом 2Ы < L+2.. Умножаем на 2, т.к. паромщику нужно возвращаться, т.е. 2Ы+4К с учётом толстых. Если же кол-во мест не ограничено, а есть ограничение только по массе, то мы просто устремим В к бесконечности. Но чтобы тот кто считает (ардуина?) не запарился нужно всё таки ограничить В заведомо большим числом. Допустим, я в своей голове держу лодку такую. Поэтому начну с В = 10 - заведомо большое, но и не бесконечное, т.е. в первую очередь поплывут самые большие (многолюдные) стайки, а к концу будут плавать только самые толстые в одиночку. Точные цифры, конечно, зависят от вектора H - от его длины (кол-ва участников) и его координат (весы), ну и от вместимости лодки М. Без доказательства, пожалуйста. Не осилю.
Неверное допущение, пмсм Предлагаю подумать, почему. Если думать не хочется - скажу, что для поиска оптимальной загрузки на следующем ходу (когда назад переправляется самый худой из перевезённых) может появиться вариант, когда к стайке толстых на текущем ходу надо добавить одного худенького, поскольку его переправа назад даст на следующем ходу более выгодную комбинацию по весу, т.е. более полную загрузку лодки (больше на 1 человека, например) Что в конечном итоге может привести к уменьшению количества ходов. Как видите - не такая и простая получается комбинаторика. Т.е., если я нигде не ошибся в своём мысленном эксперименте - не доказано, что алгоритм "на пути <туда> выбираем самых толстых, чтобы обеспечить наиболее полную загрузку" - является оптимальным. Т.е., навскидку, вычислительная сложность такого алгоритма будет О(n^2), так? Неоптимальненько немножко, хотя с этим можно жить Главное, чтобы не было O(2^n) Да, это самое интересное - доказать, что найденное решение - наиболее оптимальное. Комбинаторика, бессердечная ты сучка Спасибо за ваш пост, надеюсь, он даст понять читающим, что обобщённая задача не так проста, как кажется. Да, безусловно, есть вводные, есть зависимости, есть допущения, которым надо следовать при разработке оптимального алгоритма поиска решения, но сам алгоритм тут - не конечная точка. Конечной точкой должно являться решение - является ли найденный путь оптимальным. И это делается либо в лоб - нахождением всех путей и отсечением проигрывающих, либо - доказательной базой разработанной мат. модели. У вас в посте, кстати, изложены наброски одного из видов мат. модели - мысленного эксперимента, Эйнштейн не даст соврать, тот ещё любитель этой модели З.Ы. Меня удивляет, почему участники, отписавшиеся в теме, считают эту задачу Ребята, подводных камней в случае обобщённого алгоритма для решения этой задачи - вагон и тележка. Как ни хочется казаться простой эта комбинаторика - но она дама с изюминкой Всё, что написано выше - моё имхо, я тот ещё математик. Так что - без претензий, пожалуйста. Наоборот - я буду искренне рад, если найдётся человек с фундаментальной мат. подготовкой и расставит точки над i.
Готов финансировать? Рабочий день от 3000. Я посижу, подумаю. ) Предварительно так: сортируем чуваков по массе, отправляя "туда" набиваем сколько влезет, начиная с минимального по весу, но минимум двух. Обратно плывет наилегчайший. Повторить пока не уплывут все или не останутся двое (или более) не соответствующих этому алгоритму. Если на берегу будут двое, которые не влезают в лодку, плывает один толстейший, обратно плывет легчайший из тех, что уже "там". Если толстых несколько, повторить, пока не кончатся. То есть туда всегда плывет легчайший с кем-то, если невозможно, плывет один толстый. Обратно всегда плывет легчайший. Вот и все. Ограничение: легких должно быть минимум двое. Вот и все. Надо погонять на этом алгоритме несколько условий и сравнить с теми, что придут в голову. Наверняка, что-то по ходу дела вылезет, но не глобально, скорее всего заработает и так. Причем с гарантированно минимальным количеством шагов. К комбинаторике это никак не относится, кстати, тут нет вероятностных вычислений. В общем один день можете уже оплатить, я округляю в большую сторону. ))
Набивать не надо , а то можно набить мелкими типами , а потом средние типы составят общую массу где мог бы поместиться мелкий тип и в итоге если много таких мелких типов недоотправить , то мы получим лишний ход лодки. Т.е Вы сначала отправите песок, затем гравий , а потом булыжники , валуны сами доедут... -не правильно. Нужно к булыжникам и песочку и гравия подсыпать -укомплектовывать нужно до полного максимально допустимого. Поэтому нужно сначала составить группы для отправки , а потом отправлять.