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

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

  1. ostrov

    ostrov Гуру

    В общем, универсальный алгоритм я грубо написал выше. Немного обдумал во сне и вывел окончательно, с учетом всяких вариантов. Если интересно, распишу даром, но вечером. Как я и думал, ничего сложного, это не шахматы и даже не шашки.
     
    DIYMan нравится это.
  2. Daniil

    Daniil Гуру

    В моем алгоритме как раз и выделяется место под самого худого, который и будет доутрамбовывать пачку.
    У меня не получается придумать случай, когда самому легкому 1 раз НЕ нужно плыть (исключая случаи когда плавают одни толстые или самых худых больше 2).
    Там где может плавать НеСамыйХудой являясь паромщиком, может плавать и СамыйХудой, что не изменит скорость переплывания всех.
    Может Вы подсознательно жалеете самого худого и хотите ввести параметр "усталость"?;)
     
    Последнее редактирование: 26 дек 2019
    DIYMan нравится это.
  3. ostrov

    ostrov Гуру

    Попробую объяснить.

    1. Проверяем, есть ли в команде как минимум двое, которые помещаются в одну лодку. Без этого задача не имеет решения.
    2. Далее алгоритм делится на два: загрузка лодки "туда" (сложнее) и "обратно" (проще).

    Туда:
    1. Сортируем по весу. Берем самого легкого, сажаем в лодку. Смотрим можно ли посадить с ним кого-то еще.
    2. Если можем, то сажаем второго, третьего и так далее, сколько влезет по весу.
    3. Если не можем, то есть со вторым перевес, высаживаем легкого, отправляем одного тяжелого. Это получится минимум на третьем ходе.

    Обратно:
    1. Плывет самый легкий один.

    И так в цикле, пока не уплывут двое последних. Все. Схема работает на любом количестве и прочих условиях, даже вычурных. Например, лодка 100, чуваки 90, 80, 70, 40, 30.
     
    Последнее редактирование: 26 дек 2019
  4. DIYMan

    DIYMan Guest

    Ок, примем, что схема рабочая. Где доказательство, что найденное решение - оптимальное? ;) Лодка грузоподъёмностью в 150 кг, и 100 человек разных масс - гулять, так гулять :D
     
  5. ostrov

    ostrov Гуру

    Потому что нет лишних и повторяющихся движений.
     
    DIYMan нравится это.
  6. DIYMan

    DIYMan Guest

    Прошу понять правильно: отсутствие лишних и повторяющихся движений - не является доказательством того, что найденное решение - оптимальное.

    Вот расклад по вашему алгоритму при вводных: грузоподъёмность лодки - 10, кол-во человек - 8, заранее отсортированы по весу, переправой считается любое переплытие речки:

    На старте: 1,2,3,4,5,6,7,8

    => 1,2,3,4 = загрузка 10
    <= 1

    1,5,6,7,8 - остались

    => 1,5 = загрузка 6, начинаем терять в полезной к переправе массе
    <= 1

    1,6,7,8 - остались

    => 1,6 = 7 - и тут теряем
    <= 1

    1,7,8 - остались

    => 1,7 = 8, ещё пару кг потерли
    <= 1

    1,8 - остались

    => 1,8 - килограмм потери.

    Итого - 9 переправ. Потери массы - 10 кг, одна полная загрузка лодки!

    А ниже - более оптимальное решение, из 7 переправ:

    На старте: 1,2,3,4,5,6,7,8

    => 1,8 - потеря 1 кг
    <= 1

    1,2,3,4,5,6,7

    => 1,2,7 - без потерь
    <= 1

    1,3,4,5,6

    => 1,3,6 - без потерь
    <= 1

    1,4,5 - без потерь

    => 1,4,5

    7 переправ, потеря массы - 1 кг, на 2 переправы меньше, или на 23% эффективнее решения по вашему алгоритму.

    Ваш алгоритм - не даёт доказанного оптимального решения. И да - комбинаторика тут при чём, как видите ;) Я не зря упоминал задачу про ранец. Как видите, решение, где первым ходом является не самый оптимальный, т.к.потеря массы имеет место быть - далее лидирует без потерь массы вообще, в отличие от первого решения, где первый ход - без потерь массы, зато потом - происходит полная деградация эффективности алгоритма.
     
    Последнее редактирование модератором: 26 дек 2019
    Daniil и b707 нравится это.
  7. DIYMan

    DIYMan Guest

    Исходя из вышеизложенного: нам требуется математическое обоснование следующего утверждения: доказать, что предпринятая на i-том шаге итерации компоновка загрузки лодки по-максимуму - не приведёт к деградации эффективности алгоритма на дальнейших шагах, вплоть до последнего шага.
     
  8. Daniil

    Daniil Гуру

    Старт 1 2 3 4 5 6 7 8
    => 2 и 8 = 10
    <= 2
    осталось 1 2 3 4 5 6 7
    => 1 2 7 = 10
    <= 1
    осталось 1 3 4 5 6
    => 1 3 6 = 10
    <= 1
    осталось 1 4 5 = 10
    => всех
    (игрался с цифрами и только сейчас заметил, что я просто повторил предложенный выше вариант, только 1 ход изменил:confused:)
    Старт 1 2 3 4 5 6 7 8
    => 2 и 8 = 10
    <= 2
    осталось 1 2 3 4 5 6 7
    => 3 7 = 10
    <= 3
    осталось 1 2 3 4 5 6
    => 4 6 = 10
    <= 4
    осталось 1 2 3 5 = 10
    => 2, 3 и 5
    <= 2
    осталось 1 и 2
    => всех
    кпд лодки 100%) есть отклонение от моего алгоритма - на первом шаге попробовал пустить не самого легкого паромщиком, но сути это не меняет.
    Но у меня есть аналогичная проблема. При выборе пачки у меня нет разницы между <2 и 8> и <1, 2, 3 и 4> (я предполагал рандомно выбирать из 2-х пачек). Масса обоих равна 10, но переправа 2-й пачки приведет к увеличению количества перегонов.
    Можно обратить внимание, что я сейчас брал самого толстого из оставшихся и доукомплектовывал до полной лодки легкими. Причем тупо брать 8 и 2 или 7 и 3 не выгодно. Наверное, смысла назначать паромщика нет. Зато можно модернизировать алгоритм выбора пачки. Там должен быть самый толстый и набор (сочетания) легких, чтобы масса доходила до М. Перебор легких начинается с самого начала.
    Хотя, может, и сочетания не нужны? Просто откусывать от кучи слева и справа?
     
  9. DIYMan

    DIYMan Guest

    Ну шо - не самая лёгкая задача, да? ;) Вы уже нашли более оптимальное решение (хотя и оно может быть спорным, например, при перевозке на Марс - самый лёгкий кушает меньше, следовательно, более предпочтительна потеря в эффективности в одну единицу загрузки, чем гонять номер 2 на первом ходу туда-сюда ;)) - хоть ходов также 7, но потерь по загрузке лодки "туда" - нету. Об этом, в частности, я и вёл речь, когда говорил, что нюансов - хватает.

    Комбинаторика и анализ развития ситуации ;)

    Может, и сочетания не нужны. Может, просто откусывать от кучи слева и справа. Может - ещё как. Главное - не это, а доказать, что найденное решение, среди кучи других решений - оптимальное. Ведь в этом весь и смысл, т.к. тупо в лоб задачу решить - очень просто, что и продемонстрировал @ostrov.

    З.Ы. А если представить, что человек - 1000 особей, причём их условные веса распределены несколькими способами: случайным, групповым (когда есть группы с одинаковым весом)? Сколько вариантов комбинаций будет? Какое из найденных решений будет оптимальным? Можно ли утверждать, что если на i-том шаге условная ценность выбора очередного пассажира из группы с одинаковым весом (в ситуации, когда предыдущий шаг с выбором одного человека из группы не привёл к потере эффективности - этой группе повышается приоритет выборки на следующем шаге) - то на шаге i+1 не произойдёт провал алгоритма? Ведь набор возможных эффективных комбинаций - постоянно меняется, по мере перевозки; это только кажется, что раз в начале был строго определённый набор данных, то и количество эффективных комбинаций на каждом шаге - будет неизменным. Но это - не так ;)

    На самом деле - подобный класс задач имеет просто огромнейшее практическое значение, просто огромнейшее. Да и теоретическое - тоже, ведь разминать мозги всегда полезно ;) Представьте, что стоимость одного шага перевозки (на Марс, например) составляет 100 миллионов долларов. Решать в лоб, за 9 ходов - потерять пару сотен миллионов ;) Решивши за 7 - сэкономить эти пару сотен миллионов. Нормальный такой профит ;)
     
    Последнее редактирование модератором: 27 дек 2019
    Daniil и ИгорьК нравится это.
  10. DIYMan

    DIYMan Guest

    На вики, кстати, есть статейка по теме: https://ru.wikipedia.org/wiki/Комбинаторная_оптимизация

    Цитаты оттуда:

    Ну и, чтобы было понятно, к чему хочу подвести: за решение проблемы P=NP дают миллион долларов ;) Реальных, без дураков.
     
    Последнее редактирование модератором: 27 дек 2019
    ИгорьК и DetSimen нравится это.
  11. ostrov

    ostrov Гуру

    Ладно, алгоритм утрамбовывания при посадке нужен чуть сложнее. А что вы хотели за бесплатно? Возможно, просто перевернуть его, к самому тощему начинать запихивать начиная с самого толстого. Кароче, тетрис.
     
  12. DIYMan

    DIYMan Guest

    Уговорил таки :)
    Почему бесплатно? Миллион долларов. Задача-то сводится к решению проблемы P=NP ;) Вон, задача коммивояжёра уже при 67 городах становится трансвычислительной. И обсуждаемая нами задача, скорее всего, при каком-то исходном количестве пассажиров - тоже. И это будет не "чуть сложнее", на секундочку.
     
  13. fps

    fps Нерд

    А почему здесь все исходят из предположения, что все трое подошли к реке с одной и той же стороны?
    В условии этого нет.
     
  14. DIYMan

    DIYMan Guest

    Потому что вводные:
    т.е. по определению трое туристов находятся на оном берегу реки. Нефик там надумывать и жонглировать смысловым слоем, принцип бритвы Оккама.
     
    ostrov и parovoZZ нравится это.
  15. fps

    fps Нерд

    Из процитированного это вовсе не следует однозначно.
    Типичный случай невнимательного чтения ТЗ :)
     
  16. DIYMan

    DIYMan Guest

    Из процитированного как раз это следует однозначно. А ваши додумки - это типичный случай нахождения себе проблем на ровном месте. Про бритву Оккама - я не зря написал.

    Не зашоривайтесь, не надо оставаться настолько программистом. Если написано "должны перебраться" - это значит, что ещё не перебрались, и додумывать - не надо. Задача изначально - НЕ ПРОГРАММИСТСКАЯ, понимаете? И сделана для разминки мозгов. И никто там не парился, что однажды программист Вася начнёт кричать - не полностью формализованное ТЗ, ахтунг!

    С наступающим!
     
  17. fps

    fps Нерд

    В данном случае зашорены как раз вы, и додумываете условия которых исходно в постановке нет.

    А если бы в условии было бы написано, "Двое туристов подошли к реке и должны через нее перебраться" вы бы тоже решили, что они подошли вместе?

    Про Оккама я в курсе :), но тут он не при делах.
     
  18. DIYMan

    DIYMan Guest

    Я, конечно, понимаю, к чему вы клоните: сославшись на неполную формализацию ТЗ, можно поступить, как в байке про поимку льва в пустыне - сказать, что все трое уже на нужном берегу, и всё. Но - давайте не будем прикидываться дурачками, и признаем, что задача - не про мозговыверт, не про логические уловки, и её условия однозначно понятны всем, кроме, пожалуй, совсем затюканных стандартами составления ТЗ программистов. Правда ведь?
     
    parovoZZ нравится это.
  19. fps

    fps Нерд

    Почему нет? Классика же
     
  20. DIYMan

    DIYMan Guest

    В той классике совсем другие условия задачи. Я ещё раз вам напишу: не жонглируйте без необходимости смысловым слоем. Можете открыть голосование, если хотите. И я уверен, что подавляющему большинству будут однозначно понятны условия обсуждаемой в теме задачи. Вы же - хотите всё свести к полной формализации ТЗ.

    Вопрос: зачем? Делать нехрен? Скучно стало, и захотелось перекорёжить задачу так, как карта ляжет? Ещё раз подчеркну: я понимаю ваши доводы, и как программисту - они мне во многом близки, но - это не тот случай, когда надо настолько занудствовать.