Давайте вернёмся к моему первому вопросу. Меня интересует только сама задача, больше ничего. Если это известная задача, то дайте, пожалуйста, ссылку. Если это бизнес-тайна или слишком долго - тогда попробую сама поискать. Заинтриговали. И склады, и многокритериальность - все как мы любим))
Давайте по пунктам. 1. Вы сказали, что ваша задача сводится к одномерной упаковке. По факту одномерная упаковка к ней сводится как подзадача. Эта разные вещи. 2. Разумеется, бизнес-задачи обычно содержат комплекс NP- трудных задач. Я про это уже знаю, т.к. делала (в качестве математика-постановщика), например, задачу по размещению и отгрузке готовой листопрокатной продукции. Все опубликовано, могу в личку дать соответствующие ссылки, если интересно. 3.NP -hard в производственной размерности не решаются точными алгоритмами, только приближенными и эвристическими (нет верхней оценки погрешности), о каких сотых долях процентах вы пишете? 4. Про генетические алгоритмы я уже читала. Где-то они, видимо, хорошо работают, но для оперативного планирования производства (а размещение на складе относится к оперативному планированию) они не подходят, по моему опыту.
Для FFD-алгоритма доказана верхняя оценка погрешности. Решение, полученное FFD-алгоритмом (для задачи одномерной упаковки), отличается от оптимального не более, чем на 22%. Нужно понимать, что эти 22% достигаются на специально сконструированных "плохих" примерах (откройте Гэри, Джонсона и посмотрите, какой они сконструировали плохой пример). А на наборах реальных данных FFD часто даёт оптимальное решение. Вот такой редкий уникальный случай: задача NP-hard в сильном смысле, и решается простым FFD-алгоритмом. Что же касается, например, генетических алгоритмов, то для них нет оценки погрешности, вы не знаете, насколько ваше решение может отклониться от оптимального.
Здравствуйте. Не могли бы вы сформулировать постановку одномерной упаковки?
P.S. Если под одномерной упаковкой подразумевать т.н. задачу упаковки одномерных предметов в минимальное число одинаковых контейнеров (раскрой при изготовлении пластиковых окон, упаковка в вагоны металлопроката), то она прекрасно решается FFD-алгоритмом, см. Гэри, Джонсон Вычисл. техника и трудно решаемые задачи.
Здравствуйте. История 1. Через 4 месяца вы задали ученику первый вопрос. А он уже на первом занятии должен был что-то при вас сделать руками. Чистая кибернетика - обратная связь))
История 2. Ничего не поняла. Взялись учить "с нуля"? Тогда каких знаний вы ожидали?
История 3. Вот тут вы молодец! Не смалодушничали. Я занималась с сыном подруги дочери, трудным подростком, 3,5 года. Бесплатно - т.е. мой труд ничего не стоит. И вообще я должна. В принципе да, это чисто православная традиция - нужно пострадать)) сколько раз он опаздывал, переносил занятия на неудобное время, сколько моей крови выпил. 2,5 года занимались математикой, последний год всё-таки наняли по математике репетитора, а я готовила к ОГЭ по информатике. Вот что ему хорошо давалось - руками делать что-то в экселе, фильтры, диаграммы и т.д. Программировать даже не начинали, из-за отсутствия малейшего интереса. Сдал математику и информатику на 4, но из школы его выперли, поступил в колледж... на программиста. Заблокировала его везде.
Это да. Периодически езжу в Петропавловск-Казахский, моих университетских друзей по распределению направили в Северо-Казахстанский университет, сразу трёхкомнатную дали! (в советское время, разумеется). Там всегда было лучше с продуктами. И при коммунистах, и при капиталистах. Вообще замечательный город.
Город - 420 тысяч, на границе с Башкирией. Единственные пельмени, которые можно употреблять в пищу, привозят из Казахстана, продают в небольшом магазине, зажатом в одном здании между магнитом и пятерочкой.
Да, теперь поняла. То есть как для U-машины Тьюринга (интерпретатора) алфавит и состояния любой другой машины Т кодируются в виде последовательностей из ее (U-машины) символов (сам принцип кодировки описан у Кузнецова, Адельсона-Вельского "Дискретная математика для инженера").
У пролог- системы встроенный обратный логический вывод. Если вы сами уже запрограммировали машину логического вывода, то вам и пролог не нужен, имхо. И одно небольшое замечание про бесконечный алфавит. Символы счётного алфавита занумеруем натуральными двоичными числами - получили конечный алфавит))
Пролог вообще ориентирован на передачу естественного языка. И на работу с базами знаний. В каком-то смысле пролог - мощный и гибкий язык запросов к базе данных. Например, описываем ситуацию на ест. языке:
Мэри любит яблоки. Бэт любит то же, что и Мэри. Запрос: Что любит Бэт?
А на прологе это выглядит практически так же, только константы со строчной, свободные переменные с заглавной. Пишем утверждение, ставим точку, вместо if пишем :-
Здравствуйте. Если я правильно поняла ваше сообщение, то вам поможет модель "система продукций". Ищите книги по ИИ, там они описаны. Задаётся гбд (глобальная база данных, у вас - формулы какого-то языка), задаются правила продукции (у вас - правила переписывания) и система управления. Если к какой-то формуле применимы несколько правил продукции, то система управления определяет, какое именно правило нужно применить. Больше ничем вам помочь не могу, т.к. программировала такие вещи только на языке Пролог.
Это вы придумали, что один алгоритм - частный случай другого. И теперь пишете это в каждом сообщении. Или процитируйте, где я это сказала, или уже завершите свой бесконечный цикл))
Ещё раз. Я утверждала, что орграф из математической постановки для Дейкстры - частный случай орграфа из постановки для Ф.-Б. И ещё утверждала, что автору статьи нужно ознакомиться с постановками задач поиска кр. путей. Достаточно взять книгу Витольда Липского "Комбинаторика для программиста"
Автор пишет дословно следующее: "Алгоритм Дейкстры для графов, а это означает, что он может быть применим к проблеме, только если она представлена в графоподобном виде."
Где хоть одно слово в статье, для каких графов можно пользоваться этим алгоритмом? Сколько человек прочитают эту статью и будут думать, что алгоритмом Дейкстры можно пользоваться для любого "графа". Граф просто граф.
P.S. для графа с неотр. весами Ф.-Б. сработает корректно. В отличии от. Уж лучше бы автор Ф.-Б. рассказал, меньше бы вреда было.
Если учиться алгоритмам не в телеграм-каналах, то начинать нужно с постановки: что дано, что требуется найти. В обоих алгоритмах дан орграф и вершина-источник. Орграф с неотр. весами, на котором корректно работает алг. Дейкстры, является частным случаем нагруженного орграфа без контуров отр. веса для алг. Ф.-Б.
Другими словами. Ф.-Б. будет корректно работать на любом орграфа без контуров отр. веса, Дейкстра - только с неотр. весами.
Добрый день. Извините, но так учить алгоритмам на графах нельзя. Чего стоит ваше утверждение: алгоритм Дейкстры подходит для любого графа. Нет, не для любого. Начинают с математической постановки задачи, а не с гифок. И не с алгоритма Дейкстры, который частный случай с неотрицательными весами, а с алгоритма Форда - Беллмана для самого общего типа графов. И акцентировать внимание на том, что это опять-таки не для любого графа, а для графов без контуров отрицательного веса. И далее на картинке показать, что для контура отрицательного веса теряет смысл понятие кратчайшего пути.
Лучше уж совсем не знать алгоритмов, чем знать алгоритм и не знать его область применимости.
Это вы ещё не знаете, как оплачивается работа университетских преподавателей. У нас любой выпускник (2204, программное обеспечение) сразу же получал зп больше, чем доктор наук.
Давайте вернёмся к моему первому вопросу. Меня интересует только сама задача, больше ничего. Если это известная задача, то дайте, пожалуйста, ссылку. Если это бизнес-тайна или слишком долго - тогда попробую сама поискать. Заинтриговали. И склады, и многокритериальность - все как мы любим))
Давайте по пунктам. 1. Вы сказали, что ваша задача сводится к одномерной упаковке. По факту одномерная упаковка к ней сводится как подзадача. Эта разные вещи. 2. Разумеется, бизнес-задачи обычно содержат комплекс NP- трудных задач. Я про это уже знаю, т.к. делала (в качестве математика-постановщика), например, задачу по размещению и отгрузке готовой листопрокатной продукции. Все опубликовано, могу в личку дать соответствующие ссылки, если интересно. 3.NP -hard в производственной размерности не решаются точными алгоритмами, только приближенными и эвристическими (нет верхней оценки погрешности), о каких сотых долях процентах вы пишете? 4. Про генетические алгоритмы я уже читала. Где-то они, видимо, хорошо работают, но для оперативного планирования производства (а размещение на складе относится к оперативному планированию) они не подходят, по моему опыту.
Для FFD-алгоритма доказана верхняя оценка погрешности. Решение, полученное FFD-алгоритмом (для задачи одномерной упаковки), отличается от оптимального не более, чем на 22%. Нужно понимать, что эти 22% достигаются на специально сконструированных "плохих" примерах (откройте Гэри, Джонсона и посмотрите, какой они сконструировали плохой пример). А на наборах реальных данных FFD часто даёт оптимальное решение. Вот такой редкий уникальный случай: задача NP-hard в сильном смысле, и решается простым FFD-алгоритмом. Что же касается, например, генетических алгоритмов, то для них нет оценки погрешности, вы не знаете, насколько ваше решение может отклониться от оптимального.
Здравствуйте. Не могли бы вы сформулировать постановку одномерной упаковки?
P.S. Если под одномерной упаковкой подразумевать т.н. задачу упаковки одномерных предметов в минимальное число одинаковых контейнеров (раскрой при изготовлении пластиковых окон, упаковка в вагоны металлопроката), то она прекрасно решается FFD-алгоритмом, см. Гэри, Джонсон Вычисл. техника и трудно решаемые задачи.
Здравствуйте. История 1. Через 4 месяца вы задали ученику первый вопрос. А он уже на первом занятии должен был что-то при вас сделать руками. Чистая кибернетика - обратная связь))
История 2. Ничего не поняла. Взялись учить "с нуля"? Тогда каких знаний вы ожидали?
История 3. Вот тут вы молодец! Не смалодушничали. Я занималась с сыном подруги дочери, трудным подростком, 3,5 года. Бесплатно - т.е. мой труд ничего не стоит. И вообще я должна. В принципе да, это чисто православная традиция - нужно пострадать)) сколько раз он опаздывал, переносил занятия на неудобное время, сколько моей крови выпил. 2,5 года занимались математикой, последний год всё-таки наняли по математике репетитора, а я готовила к ОГЭ по информатике. Вот что ему хорошо давалось - руками делать что-то в экселе, фильтры, диаграммы и т.д. Программировать даже не начинали, из-за отсутствия малейшего интереса. Сдал математику и информатику на 4, но из школы его выперли, поступил в колледж... на программиста. Заблокировала его везде.
Это да. Периодически езжу в Петропавловск-Казахский, моих университетских друзей по распределению направили в Северо-Казахстанский университет, сразу трёхкомнатную дали! (в советское время, разумеется). Там всегда было лучше с продуктами. И при коммунистах, и при капиталистах. Вообще замечательный город.
Город - 420 тысяч, на границе с Башкирией. Единственные пельмени, которые можно употреблять в пищу, привозят из Казахстана, продают в небольшом магазине, зажатом в одном здании между магнитом и пятерочкой.
Да, теперь поняла. То есть как для U-машины Тьюринга (интерпретатора) алфавит и состояния любой другой машины Т кодируются в виде последовательностей из ее (U-машины) символов (сам принцип кодировки описан у Кузнецова, Адельсона-Вельского "Дискретная математика для инженера").
У пролог- системы встроенный обратный логический вывод. Если вы сами уже запрограммировали машину логического вывода, то вам и пролог не нужен, имхо. И одно небольшое замечание про бесконечный алфавит. Символы счётного алфавита занумеруем натуральными двоичными числами - получили конечный алфавит))
Пролог вообще ориентирован на передачу естественного языка. И на работу с базами знаний. В каком-то смысле пролог - мощный и гибкий язык запросов к базе данных. Например, описываем ситуацию на ест. языке:
Мэри любит яблоки. Бэт любит то же, что и Мэри. Запрос: Что любит Бэт?
А на прологе это выглядит практически так же, только константы со строчной, свободные переменные с заглавной. Пишем утверждение, ставим точку, вместо if пишем :-
likes(mary, apples). likes(beth, X):- likes(mary, X).
goal likes(beth, Y), write(Y).
Здравствуйте. Если я правильно поняла ваше сообщение, то вам поможет модель "система продукций". Ищите книги по ИИ, там они описаны. Задаётся гбд (глобальная база данных, у вас - формулы какого-то языка), задаются правила продукции (у вас - правила переписывания) и система управления. Если к какой-то формуле применимы несколько правил продукции, то система управления определяет, какое именно правило нужно применить. Больше ничем вам помочь не могу, т.к. программировала такие вещи только на языке Пролог.
Спасибо, теперь буду знать. Очень надеюсь, что на этом наш продуктивный диалог закончен.
И вправду, коряво. Каюсь. Неудобно было с телефона писать, поторопилась. Но теперь буду знать, что на хабре нужно писать очень аккуратно.
"который частный случай с неотрицательными весами"
который частный случай ОРГРАФА с неотрицательными весами
Спасибо тебе, добрый человек))
Это вы придумали, что один алгоритм - частный случай другого. И теперь пишете это в каждом сообщении. Или процитируйте, где я это сказала, или уже завершите свой бесконечный цикл))
Ещё раз. Я утверждала, что орграф из математической постановки для Дейкстры - частный случай орграфа из постановки для Ф.-Б. И ещё утверждала, что автору статьи нужно ознакомиться с постановками задач поиска кр. путей. Достаточно взять книгу Витольда Липского "Комбинаторика для программиста"
Автор пишет дословно следующее: "Алгоритм Дейкстры для графов, а это означает, что он может быть применим к проблеме, только если она представлена в графоподобном виде."
Где хоть одно слово в статье, для каких графов можно пользоваться этим алгоритмом? Сколько человек прочитают эту статью и будут думать, что алгоритмом Дейкстры можно пользоваться для любого "графа". Граф просто граф.
P.S. для графа с неотр. весами Ф.-Б. сработает корректно. В отличии от. Уж лучше бы автор Ф.-Б. рассказал, меньше бы вреда было.
Если учиться алгоритмам не в телеграм-каналах, то начинать нужно с постановки: что дано, что требуется найти. В обоих алгоритмах дан орграф и вершина-источник. Орграф с неотр. весами, на котором корректно работает алг. Дейкстры, является частным случаем нагруженного орграфа без контуров отр. веса для алг. Ф.-Б.
Другими словами. Ф.-Б. будет корректно работать на любом орграфа без контуров отр. веса, Дейкстра - только с неотр. весами.
Добрый день. Извините, но так учить алгоритмам на графах нельзя. Чего стоит ваше утверждение: алгоритм Дейкстры подходит для любого графа. Нет, не для любого. Начинают с математической постановки задачи, а не с гифок. И не с алгоритма Дейкстры, который частный случай с неотрицательными весами, а с алгоритма Форда - Беллмана для самого общего типа графов. И акцентировать внимание на том, что это опять-таки не для любого графа, а для графов без контуров отрицательного веса. И далее на картинке показать, что для контура отрицательного веса теряет смысл понятие кратчайшего пути.
Лучше уж совсем не знать алгоритмов, чем знать алгоритм и не знать его область применимости.
Это вы ещё не знаете, как оплачивается работа университетских преподавателей. У нас любой выпускник (2204, программное обеспечение) сразу же получал зп больше, чем доктор наук.