закажу проект

Тема в разделе "Закажу проект", создана пользователем qazw, 22 дек 2019.

  1. vvr

    vvr Инженерище

    вот тему развезли аж на две страницы...
     
    DetSimen нравится это.
  2. DetSimen

    DetSimen Guest

    Аптамуш, вопрошающий - жертва ЕГЭ. Иначе б такого даже вопроса здесь не появилось.
     
  3. sser

    sser Гик

    Последнее редактирование: 25 дек 2019
  4. ИгорьК

    ИгорьК Оракул Модератор

  5. ostrov

    ostrov Гуру

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

    DIYMan Guest

    Я так не думаю ;) Обобщи задачу, и увидишь, что не простейший. Не стоит писать под известное решение алгоритм, надо писать обобщённый алгоритм. Ок, давай я изменю вводные: человека уже четыре, а не три. Или - 10 человек, причём известно, что среди них существует такая комбинация весов, что в лодку могут поместиться сразу четыре из этой десятки. Причём таких четвёрок - две, одна из них - оптимальная, другая - проигрывает первой.

    Простейший, говоришь?
     
    vvr нравится это.
  7. ostrov

    ostrov Гуру

    Более тяжелая четверка поедет первой.
     
  8. DIYMan

    DIYMan Guest

    Не, ты мне умозаключения не выдавай - ты простейший алгоритм напиши ;) Задача-то - ещё найти эту более тяжёлую четвёрку. А кто сказал, что они вообще будут, такие четвёрки? И не будет ли пары троек и одной четвёрки, при использовании которых получится сделать меньшее количество шагов, чем в случае с двумя четвёрками?

    Понимаешь, что задача не так проста, как кажется? Ты должен доказать, что найденный вариант (при всём богатстве возможных комбинаций) - ещё и самый лучший. Не писать код по готовому решению - а предоставить обобщённый алгоритм ;)

    Возьмёшься? Я - нет. ибо задача - крайне сложна. А конкретный упрощённый пример - только путает своей кажущейся простотой.

    З.Ы. Знаешь - это как в небесной механике, где задача двух тел вполне себе решаема, а задача всего лишь трёх тел - уже огого.
     
  9. a1000

    a1000 Гик

    А ни кто не помнит что просил ТС? Ему нужно было устройство моделирующее игровую ситуацию. Вопрос о создании прототипа искусственного интеллекта самостоятельно находящего оптимальное решение поставленной задачи не стоял.
    ЗЫ: Хотя вопрос интересный.:)
     
    DIYMan нравится это.
  10. ostrov

    ostrov Гуру

    А мне кажется, что не та эта задача и ее сложность кажущаяся. Если собраться и обдумать, наверняка алгоритм простой получится. Чай не шахматы. А даже к ним алгоритмы придумали.
     
  11. DIYMan

    DIYMan Guest

    Мы тут просто развлекаемся, мозги разминаем ;)
     
  12. DIYMan

    DIYMan Guest

    Попробуй ;) Не получится алгоритм простым, под него, как минимум, нужна мат. модель. Скажем, если взять тот же А* (алгоритм поиска пути) - то он, при всей его понятности - далеко не так прост, как кажется, плюс - имеет в основе мат. модель. С оценками сложности и пр. Глянь, сколько дядек над ним работало, прежде чем он появился на свет в конечном виде ;)

    Что касается шахмат: удачный пример, как раз в пользу моих доводов ;) Ни разу не просто, ни разу не быстро, не доказано, что текущие реализации алгоритмов шахматных программ - оптимальны (если не ошибаюсь) до сих пор.
     
  13. ostrov

    ostrov Гуру

    У шахмат вариантов миллиарды и миллиарды, да еще и зависят от ответки, т.е. непредсказуемые, а тут главное соблюдать стратегию и вариантов будет не так много или вообще один, как в случае с примером автора.
     
  14. DIYMan

    DIYMan Guest

    Лады, ждём от тебя простейший алгоритм, который принимает на входе:

    1. Кол-во людей к перевозке с массами каждого из них;
    2. Грузоподъёмность лодки.

    Алгоритм должен на выходе выдавать минимально возможное количество ходов. Причём - доказанное минимальное, не важно, как - тупым перебором, или мат. моделью.

    Сделаешь?
     
  15. DIYMan

    DIYMan Guest

    Кстати сказать, родственный тип задач - задача раскроя. Более-менее успешно решена, но - тоже далеко не проста. Частный случай применимости к обсуждаемой задаче, задача о ранце - почитай, там есть обоснования и методы решения.
     
    ИгорьК нравится это.
  16. Daniil

    Daniil Гуру

    По мне это не ханойские башни. Нет требования к порядку попадания на "новую землю".
    Мне кажется эта задача простая, т.к. нигде нет требований по порядку, т.е. нужно продумать алгоритм переправы всех людей кратчайшим путём, т.е. свести к максимально кучному перевозу людей.

    Но, надо понять имеет ли решение ли задача.
    Условимся, что задача решена если ВСЕ N людей окажутся на другой стороне.
    K - количество толстых людей, которые могут переплыть только в одиночку. H(K)>M-min(H)
    L - количество худых, которые могут переправиться как минимум вдвоём. Проще говоря, это количество нетолстых.
    B - мест в лодке.
    Если К>=1, то должно быть L>=2 (предельный случай уже описан в данной теме).
    Нет людей толще М.
    1 ход равен одной переправе в одну сторону.

    Простой случай:
    Мест в лодке В = 2 и предельная масса М.
    2 худых и K толстых.
    X - худой, Т - толстый
    Я тут попробую нарисовать состояния через дефис
    Слева это Худые и Толстые на левом берегу, которым нужно перебраться на правый берег.
    Посерёдке те кто в лодке, стрелкой указывал куда плывут.
    Справа - те кто переправился.
    Код (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 худых, тогда:
    Код (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 - от его длины (кол-ва участников) и его координат (весы), ну и от вместимости лодки М.

    Без доказательства, пожалуйста. Не осилю.
     
    Последнее редактирование: 26 дек 2019
    DetSimen, ИгорьК и DIYMan нравится это.
  17. DIYMan

    DIYMan Guest

    Неверное допущение, пмсм ;) Предлагаю подумать, почему. Если думать не хочется - скажу, что для поиска оптимальной загрузки на следующем ходу (когда назад переправляется самый худой из перевезённых) может появиться вариант, когда к стайке толстых на текущем ходу надо добавить одного худенького, поскольку его переправа назад даст на следующем ходу более выгодную комбинацию по весу, т.е. более полную загрузку лодки (больше на 1 человека, например) ;) Что в конечном итоге может привести к уменьшению количества ходов. Как видите - не такая и простая получается комбинаторика. Т.е., если я нигде не ошибся в своём мысленном эксперименте - не доказано, что алгоритм "на пути <туда> выбираем самых толстых, чтобы обеспечить наиболее полную загрузку" - является оптимальным.

    Т.е., навскидку, вычислительная сложность такого алгоритма будет О(n^2), так? Неоптимальненько немножко, хотя с этим можно жить :) Главное, чтобы не было O(2^n) :D:D:D

    Да, это самое интересное - доказать, что найденное решение - наиболее оптимальное. Комбинаторика, бессердечная ты сучка :D:D:D

    Спасибо за ваш пост, надеюсь, он даст понять читающим, что обобщённая задача не так проста, как кажется. Да, безусловно, есть вводные, есть зависимости, есть допущения, которым надо следовать при разработке оптимального алгоритма поиска решения, но сам алгоритм тут - не конечная точка. Конечной точкой должно являться решение - является ли найденный путь оптимальным. И это делается либо в лоб - нахождением всех путей и отсечением проигрывающих, либо - доказательной базой разработанной мат. модели. У вас в посте, кстати, изложены наброски одного из видов мат. модели - мысленного эксперимента, Эйнштейн не даст соврать, тот ещё любитель этой модели ;)

    З.Ы. Меня удивляет, почему участники, отписавшиеся в теме, считают эту задачу
    Ребята, подводных камней в случае обобщённого алгоритма для решения этой задачи - вагон и тележка. Как ни хочется казаться простой эта комбинаторика - но она дама с изюминкой ;)

    Всё, что написано выше - моё имхо, я тот ещё математик. Так что - без претензий, пожалуйста. Наоборот - я буду искренне рад, если найдётся человек с фундаментальной мат. подготовкой и расставит точки над i.
     
    Daniil, ИгорьК и DetSimen нравится это.
  18. ostrov

    ostrov Гуру

    Готов финансировать? Рабочий день от 3000. Я посижу, подумаю. )

    Предварительно так: сортируем чуваков по массе, отправляя "туда" набиваем сколько влезет, начиная с минимального по весу, но минимум двух. Обратно плывет наилегчайший. Повторить пока не уплывут все или не останутся двое (или более) не соответствующих этому алгоритму. Если на берегу будут двое, которые не влезают в лодку, плывает один толстейший, обратно плывет легчайший из тех, что уже "там". Если толстых несколько, повторить, пока не кончатся. То есть туда всегда плывет легчайший с кем-то, если невозможно, плывет один толстый. Обратно всегда плывет легчайший. Вот и все. Ограничение: легких должно быть минимум двое. Вот и все. Надо погонять на этом алгоритме несколько условий и сравнить с теми, что придут в голову. Наверняка, что-то по ходу дела вылезет, но не глобально, скорее всего заработает и так. Причем с гарантированно минимальным количеством шагов.

    К комбинаторике это никак не относится, кстати, тут нет вероятностных вычислений. В общем один день можете уже оплатить, я округляю в большую сторону. ))
     
    Последнее редактирование: 26 дек 2019
    issaom и ИгорьК нравится это.
  19. sser

    sser Гик

    Набивать не надо , а то можно набить мелкими типами , а потом средние типы составят общую массу где мог бы поместиться мелкий тип и в итоге если много таких мелких типов недоотправить , то мы получим лишний ход лодки.

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

    Поэтому нужно сначала составить группы для отправки , а потом отправлять.
     
    Последнее редактирование: 26 дек 2019
  20. DIYMan

    DIYMan Guest

    Ошибаешься ;)
    Конечно, нет :)